Coding Challenge

[Nonsanity]

Oh!

I forgot to add "J < W" to the list when I re-did it in the email. It comes
from the "in that order" phrase below. Without it, there are TWO names
missing from the youngest side of the list, so W and J would be grouped
together (into X) like so:

T < R
X < T
X < T
X < R
X < R
R < S
X < R
X < M
R < S
S < M
T < M

And the output of the first iteration would be:

(youngest) [J,W] ... M

The rest of the solution would proceed as normal. You would end up knowing
that Jack and Will are younger than everyone else, but not know which of the
two was the youngest.

Oh, and any equality statements in the original data (Karen is the same age
as Helen) should be substituted for a single variable, grouping them the
same way you would a pair of unknowns, like J and W when I left out the one
conditional statement.


 ~ Chris Innanen
 ~ Nonsanity



On Tue, Mar 8, 2011 at 10:41 AM, Nonsanity <form at nonsanity.com> wrote:

> On Tue, Mar 8, 2011 at 10:07 AM, Nonsanity <form at nonsanity.com> wrote:
>
>> Malte, are you looking for a general solution to problems such as this:
>>
>> "Tom is younger than Rose, but older than Will and Jack, in that order.
>> Rose is younger than Susie, but older than Jack. Jack is younger than Jim.
>> Susie is older than Rose, but younger than Jim. Jim is older than Tom. Who
>> is the oldest?"
>>
>>  ~ Chris Innanen
>>  ~ Nonsanity
>
>
> Using that as an example, the steps to get not just the oldest but a
> complete ordered list is to:
>
> 1) Codify all the less-than greater-than pairs and group them in a list all
> going the same way. I'll pick less-than here. (Names have been reduced to
> the first letter, except for Jim who is "M".)
>
> T < R
> W < T
> J < T
> J < R
> W < R
> R < S
> J < R
> J < M
> R < S
> S < M
> T < M
>
> 2) IF you have enough relationships to determine a complete ordering, then
> the names missing from each side of the list represent the youngest and
> oldest. In this case, "M" is not on the left (younger) side, and "J" is not
> on the right (older) side, so Jim is the youngest and Jack is the oldest.
>
> 3) Eliminate all pairings that involve the known individuals and see if you
> have enough information to proceed.
>
> (youngest) J ... M (oldest)
>
> T < R
> W < T
>                [J < T]
>                [J < R]
> W < R
> R < S
>                [J < R]
>                [J < M]
> R < S
>                [S < M]
>                [T < M]
>
> 4) Repeat. "S" is not on the left (younger) side and "W" is not on the
> right (older) side, so add them to the ordered list.
>
> (youngest) J W ... S M (oldest)
>
> T < R
>
> 5) With only two names remaining, and one conditional, we have enough
> information to complete the list.
>
> (youngest) J W T R S M (oldest)
>
>
> If the data given is not enough to get a complete list, it may be possible
> to pluck out some slightly more complex relationships (A is older than B IF
> C is older than D) but it sounds like you need more solid answers.
>
> Anyway, that's A general solution to this sort of problem. I don't know if
> there's a better one or not... I didn't already know this proceedure, I just
> worked it out when you asked. I only now went back to the web site where I
> got the sample problem and clicked the answer button. It's Jim. Yeay.
>
> Hmmm... Looking back, I think that if you have incomplete data, you can
> still get a mostly ordered list out of this. If more than one name is
> missing from the left (younger) side, then you know that those names are the
> youngest, you just don't know which is younger or older among them. I'd
> repackage them as a single unit (new letter) and substitute it though the
> whole list for all the affected names, then try again. In the end, you
> should have a list with groups of unknown order scattered throughout, but
> still have an overall list. If further data is presented for the names in
> those groups, they can be put through this same routine in isolation from
> the rest of the list.
>
> Hope this is what you were looking for! (But it was fun to work out
> anyway...)
>
>
>  ~ Chris Innanen
>  ~ Nonsanity
>
>