Solution to Adam Babcock's brain-teaser

cycles.py

'''
Solution to Adam Babcock's brain-teaser

Here's the basic gist of the problem: A principal places one hundred students'
names into one hundred identical boxes, which are sitting in a row in the principal's
office. Each box contains exactly one name, but the names are not guaranteed to
be arranged in any particular order within those boxes.
Students are called in one at a time and are permitted to open up to fifty of
those boxes. If one of the boxes they open contains their name, they get a reward.

Students are not permitted to share information with each other regarding the
contents of the boxes (students are sent to a different room when they're done),
and the boxes are all closed again after each student is done opening them. No
boxes are removed from the principal's office at any time.

As the teacher, your goal is to help as many students succeed as possible, so
you can help the students plan a strategy. You are also allowed to step into
the principal's office beforehand, examine the contents of all the boxes, and
swap the positions of two of them. However, you cannot share any information
with the students after doing so.

Assume that the principal is privvy to your strategy and will lay out the boxes
in the most difficult manner possible to thwart your plans. Therefore, score
you solution according to the "worst" case rather than the "average" case.

It's a "pure algorithms" question, involving no lateral thinking. If you want to
work this out for yourself instead of seeing the solution, immediately stop
reading this.

- - - - -

I've come to realize that this problem comes down the finding and breaking long
cycles in linked lists. Assume that students have a natural ordering which they
are capable of remembering -- i.e. assign each student a number between 0 and 99
(inclusive). Also assume that the boxes have a natural ordering as well.

Imagine that a student first opens the box corresponding to their ID. This box
will either contain their name (in which case they have "won"), or it will
contain someone else's name. In the latter case, the student finds the box
corresponding to that student and opens it. (The box is guaranteed to be unopened
because no names are repeated.) If permitted to open up to all 100 boxes in this
manner, the student must find the one containing their name.

Thus, the placement of names into their boxes forms one or more circular chains
of mutually-exclusive sets of students. The longest possible chain can include
up to all 100 students, but no two chains can include more than 50 because one
group of 51 students only leaves a maximum remaining chain of size 49.

Any student in a group of 50 or fewer students is guaranteed to succeed by
starting at "their" box and recursively following their chain. However, if there
is a group of 51 or more students, it's necessary to break the cycle due to the
arbitrary limit imposed in the problem. Fortunately, it's easy to divide a
reference cycle into two by swapping two elements:

```
    a[0] -> a[1] -> ... -> a[n] -> a[n+1] -> ... -> a[m-1] -> a[m]
     ^                                                         |
     |                                                         |
     +---------------------------------------------------------+
```

Switch a[n] and a[m] so that a[n] points to a[0] and a[m] points to a[n+1]:

```
    a[0] -> a[1] -> ... -> a[n]    a[n+1] -> ... -> a[m-1] -> a[m]
     ^                       |       ^                         |
     |                       |       |                         |
     +-----------------------+       +-------------------------+
```

If the swapped elements are on opposite "sides" of the cycle from each other,
the resulting two cycles are roughly half the size of the original one, and both
are guaranteed to be 50 or smaller.

As the teacher, your job is simply to find the cycle of 50 or more elements
(if one exists), and swap two elements.

The rest of this file is a program demonstrating how it works.

'''


from random import random
from textwrap import dedent


RESET = '\033[0m'
TERM_COLORS = [f'\033[{bold};{color}m' for bold in range(1, -1, -1) for color in range(31, 38)]


def check_for_cycles(l):
    cycle_id = 0
    cycles = []
    found_in_cycle = {}

    for x in range(100):
        if x not in found_in_cycle:
            cycle = []
            cycles.append(cycle)
            while x not in cycle:
                cycle.append(x)
                found_in_cycle[x] = cycle_id
                x = l[x]
            cycle_id += 1

    return cycles, found_in_cycle


def print_cycles(l, cycles, found_in_cycle):
    print('Distribution:')
    for x in range(0, 10):
        print('   '.join(
            f'{index:2}: {color}{value:2}{RESET}'
            for y in range(0, 100, 10)
            for index in (x+y,)
            for value in (l[index],)
            for cycle_id in (found_in_cycle[index],)
            for color in (TERM_COLORS[cycle_id],)
        ))
    print()

    print(f'Found {len(cycles)} cycles:')
    for cycle_id, cycle in enumerate(cycles):
        color = TERM_COLORS[cycle_id]
        print(f'  Cycle {color}{cycle_id}{RESET} ({len(cycle)}): {cycle!r}')
    print()


if __name__ == '__main__':
    l = sorted(range(100), key=lambda *args: random())
    cycles, found_in_cycle = check_for_cycles(l)
    print_cycles(l, cycles, found_in_cycle)

    longest_cycle = max(cycles, key=len)
    if len(longest_cycle) <= 50:
        print(dedent('''\
            The longest cycle is 50 or fewer.

            Every student will find their name if they open the container at their
            position first, and use the name inside that container as the key to
            open the next container.
        '''))
    else:
        midpoint = longest_cycle[len(longest_cycle)//2]
        endpoint = longest_cycle[0]

        print(dedent(f'''\
            The longest cycle is longer than 50.

            We can switch two containers to break this cycle into two independent cycles.

            For example, let's swap the container at position {midpoint} (={l[midpoint]})
            with the container at position {endpoint} (={l[endpoint]}).
            
            We know we only need to do this once because no two cycles can have more
            than 50 elements.
        '''))

        l2 = list(l)
        l2[midpoint], l2[endpoint] = l2[endpoint], l2[midpoint]
        new_cycles, new_found_in_cycle = check_for_cycles(l2)
        print_cycles(l2, new_cycles, new_found_in_cycle)

        assert all(len(cycle) <= 50 for cycle in new_cycles)
        print(dedent('''\
            The longest cycle is NOW 50 or fewer.

            Every student will find their name if they open the container at their
            position first, and use the name inside that container as the key to
            open the next container.
        '''))

example_run.txt

Distribution:
 0: 25   10: 92   20: 70   30: 54   40: 81   50: 30   60: 88   70: 75   80: 63   90: 22
 1:  0   11:  7   21: 48   31: 57   41: 97   51: 95   61: 24   71: 65   81: 32   91:  9
 2: 90   12: 73   22: 79   32:  1   42:  6   52: 17   62: 45   72: 91   82: 11   92: 26
 3: 43   13: 13   23:  4   33: 56   43: 62   53: 38   63: 72   73:  8   83: 47   93: 39
 4: 12   14: 74   24: 55   34: 59   44: 16   54: 86   64: 21   74: 51   84: 60   94: 94
 5: 96   15: 40   25: 50   35: 36   45: 14   55: 66   65: 15   75: 67   85: 20   95: 35
 6: 27   16: 28   26: 87   36: 89   46: 98   56: 99   66: 44   76: 83   86: 34   96: 93
 7:  5   17:  3   27:  2   37: 82   47: 33   57: 53   67: 84   77: 37   87: 58   97: 76
 8: 23   18: 80   28: 77   38: 71   48: 68   58: 10   68: 18   78: 31   88: 64   98: 49
 9: 69   19: 41   29: 42   39: 85   49: 29   59: 19   69: 46   79: 52   89: 61   99: 78

Found 6 cycles:
  Cycle 0 (29): [0, 25, 50, 30, 54, 86, 34, 59, 19, 41, 97, 76, 83, 47, 33, 56, 99, 78, 31, 57, 53, 38, 71, 65, 15, 40, 81, 32, 1]
  Cycle 1 (59): [2, 90, 22, 79, 52, 17, 3, 43, 62, 45, 14, 74, 51, 95, 35, 36, 89, 61, 24, 55, 66, 44, 16, 28, 77, 37, 82, 11, 7, 5, 96, 93, 39, 85, 20, 70, 75, 67, 84, 60, 88, 64, 21, 48, 68, 18, 80, 63, 72, 91, 9, 69, 46, 98, 49, 29, 42, 6, 27]
  Cycle 2 (5): [4, 12, 73, 8, 23]
  Cycle 3 (5): [10, 92, 26, 87, 58]
  Cycle 4 (1): [13]
  Cycle 5 (1): [94]

The longest cycle is longer than 50.

We can switch two containers to break this cycle into two independent cycles.

For example, let's swap the container at position 35 (=36)
with the container at position 27 (=2).

We know we only need to do this once because no two cycles can have more
than 50 elements.

Distribution:
 0: 25   10: 92   20: 70   30: 54   40: 81   50: 30   60: 88   70: 75   80: 63   90: 22
 1:  0   11:  7   21: 48   31: 57   41: 97   51: 95   61: 24   71: 65   81: 32   91:  9
 2: 90   12: 73   22: 79   32:  1   42:  6   52: 17   62: 45   72: 91   82: 11   92: 26
 3: 43   13: 13   23:  4   33: 56   43: 62   53: 38   63: 72   73:  8   83: 47   93: 39
 4: 12   14: 74   24: 55   34: 59   44: 16   54: 86   64: 21   74: 51   84: 60   94: 94
 5: 96   15: 40   25: 50   35:  2   45: 14   55: 66   65: 15   75: 67   85: 20   95: 35
 6: 27   16: 28   26: 87   36: 89   46: 98   56: 99   66: 44   76: 83   86: 34   96: 93
 7:  5   17:  3   27: 36   37: 82   47: 33   57: 53   67: 84   77: 37   87: 58   97: 76
 8: 23   18: 80   28: 77   38: 71   48: 68   58: 10   68: 18   78: 31   88: 64   98: 49
 9: 69   19: 41   29: 42   39: 85   49: 29   59: 19   69: 46   79: 52   89: 61   99: 78

Found 7 cycles:
  Cycle 0 (29): [0, 25, 50, 30, 54, 86, 34, 59, 19, 41, 97, 76, 83, 47, 33, 56, 99, 78, 31, 57, 53, 38, 71, 65, 15, 40, 81, 32, 1]
  Cycle 1 (15): [2, 90, 22, 79, 52, 17, 3, 43, 62, 45, 14, 74, 51, 95, 35]
  Cycle 2 (5): [4, 12, 73, 8, 23]
  Cycle 3 (44): [5, 96, 93, 39, 85, 20, 70, 75, 67, 84, 60, 88, 64, 21, 48, 68, 18, 80, 63, 72, 91, 9, 69, 46, 98, 49, 29, 42, 6, 27, 36, 89, 61, 24, 55, 66, 44, 16, 28, 77, 37, 82, 11, 7]
  Cycle 4 (5): [10, 92, 26, 87, 58]
  Cycle 5 (1): [13]
  Cycle 6 (1): [94]

The longest cycle is NOW 50 or fewer.

Every student will find their name if they open the container at their
position first, and use the name inside that container as the key to
open the next container.