Coding Challenge

[Nonsanity]

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