Five cells to freedom logic puzzle

I found the following logic puzzle and decided to solve it using Python rather than logical deduction in my head:

I got it from here. 

You have been incarcerated in a high-security prison for several nefarious
crimes which we need not go into here. The warden, being a kindly logician,
offers you a single chance to escape. You are blindfolded and given a choice of
five doors, one of which leads to freedom and the other four to prison cells.
You know that the doors are red, blue, green, yellow, and white; they are
evenly spaced, each 2 paces from the next; and you are standing in front of the
middle one. There is a guard standing by each door, and all five guards tell
the truth (weren't expecting that, were you?). They make the following
statements:

1. The red door is somewhere to the left of the door leading to freedom.
2. The blue door is not at either end.
3. The green door is 3 doors away from the door leading to freedom (2 doors between them).
4. The yellow door is adjacent to the door leading to freedom.
5. The white door is the middle one.

To find out how many paces you need to take to which side in order to be
standing in front of the door to freedom, you need to answer the following two
questions:

• What is the order of the coloured doors, left to right?
• Which colour of door leads to freedom?

You may assume that all statements made about "left" and "right" refer to your

left and right.

Strategy

Well it's only five doors which means a limited number of permutations to test. I will need the doors and individual colours (this should probably have been an enumeration for the individual colours). I use a namedtuple as my main data-structure as it is succinct and I think I am going to need access to the assumed position and colour of the freedom cell out of any particular permutation of door positions and cell-to-freedom under test at any time.

from itertools import permutations
from collections import namedtuple
 
FreeDoor = namedtuple('FreeDoor', 'doors, free_colour, free_position')
 
doors = 'red, blue, green, yellow, white'.split(', ')
R, B, G, Y, W = doors

I would construct a list of constraint functions then apply them to a permutation and select those permutations that fit all constraints.

Constraints #1

Extracting the constraints, I knew, was going to be the hardest part of this.  I initially thought that I could solve for cell order then solve again for which one led to freedom so started with the following list of lambda functions.

Note how I have extracted the five statements as comments to guide me in extracting the constraints.

position_constraints = [
    #The red door is somewhere to the left of the door leading to freedom.
    lambda fd: fd.doors.index(R) < 4, # can't be at far right
    #The blue door is not at either end.
    lambda fd: 0 < fd.doors.index(B) < 4,
    #The green door is 3 doors away from the door leading to freedom (2 doors between them).
    lambda fdd: fd.doors.index(G) != 2,
    #The yellow door is adjacent to the door leading to freedom.
    #lambda d: d.index(Y)
    #The white door is the middle one.
    lambda fd: fd.doors.index(W) == 2,
    ]

I knew that I was having problems when there was nothing about the position of the yellow door that could be stated from statement 4.

Constraints #2

I then resolved to write constraints for both freedom cell position and cell order at the same time and came up with the following constraints. You have to be able to extract this from the text and like most "wordy" maths problems extracting the maths from the text is usually harder than solving the resultant maths.

all_constraints = [
    #The red door is somewhere to the left of the door leading to freedom.
    lambda fd: (fd.free_position > 0 and fd.free_colour != R 
                and fd.doors.index(R) < fd.free_position),
    #The blue door is not at either end.
    lambda fd: 0 < fd.doors.index(B) < 4,
    #The green door is 3 doors away from the door leading to freedom (2 doors between them).
    lambda fd: (fd.free_colour != G and fd.doors.index(G) != 2 
                and (fd.doors.index(G) + 3 == fd.free_position 
                     or fd.doors.index(G) - 3 == fd.free_position)),
    #The yellow door is adjacent to the door leading to freedom.
    lambda fd: (fd.free_colour != Y and (fd.doors.index(Y) + 1 == fd.free_position 
                                      or fd.doors.index(Y) - 1 == fd.free_position)),
    #The white door is the middle one.
    lambda fd: fd.doors.index(W) == 2,
    ]

The Solver

I decided to gather all solutions as I was not sure if there would be more than one.  To get the permutations I need the permutations of the door colours permuted with possible door to freedom positions within that accomplished with the nested for loops then I stuff a new FreeDoor instance with the correct values and check it against all the constraints with the all() function.

def solve():
    solutions = []
    for order in permutations(doors):
        for freedom in doors:
            freedomdoor = FreeDoor(order, freedom, order.index(freedom))
            if all(constraint(freedomdoor) for constraint in all_constraints):
                solutions.append(freedomdoor)
    return solutions
 
ans = solve()
print(ans)

The answer

[FreeDoor(doors=('green', 'red', 'white', 'blue', 'yellow'), free_colour='blue', free_position=3)]

(The position given above is zero-indexed from the LHS).

END.

Solving the Monkey and coconuts problem

Numberphile had another great video which introduced me to the Monkey and coconut problem

The problem statement paraphrased from the video is:

Five sailors are shipwrecked on an island and collect a large pile of coconuts during the day. That night the first sailor wakes up and decides to take his first share early so tries to divide the pile of coconuts equally into five piles but finds that there is one coconut left over so tosses it to a monkey, he then hides "his" one of the five equally sized piles of coconuts and pushes the other four piles together to form a single visible pile of coconuts again and goes to bed.

To cut a long story short, each of the sailors gets up singly, once during the night and performs the same actions of dividing the coconut pile into five, finding that one coconut is left over and giving that single remainder coconut to the monkey.

In the morning (after the surreptitious and separate action of each of the five sailors during the night), The pile of coconuts are divided into five equal piles for each of the sailors and whereupon it is found that the pile of coconuts divides equally amongst the sailors with no remainder. (Nothing for the monkey in the morning).

The task is to calculate the minimum size of the initial pile of coconuts collected during the first day.

I choose to find a solution using a Python program.

Initial thoughts.

Thinking about how I could solve it I thought that I would write something that had a lot of cut-n-pasted code for the night time activities of each sailor followed by a slightly different copy where there is no remainder which models the next days final distribution.

That would lead to me creating another version using a loop for the night time activities and possibly folding in the last days division

Finally I could look at creating a recursive version.

The progression looked like a good idea and I set out to do just that.

First cut-n-paste code

I have removed the print statements that allowed me to debug this initial version but a quick google showed that this was giving the right answer and looked correct.

def monkey_coconuts_5sailors():
    "Hard coded and copy-pasted for only five sailors"
    nuts = sailors = 5
    while True:
        n0, wakes = nuts, []
        portion, remainder = divmod(n0, sailors)
        wakes.append((n0, portion, remainder))
        if portion <= 0 or remainder !=1:
            nuts += 1
            continue
        n0 = n0 - portion - remainder
        portion, remainder = divmod(n0, sailors)
        wakes.append((n0, portion, remainder))
        if portion <= 0 or remainder !=1:
            nuts += 1
            continue
        n0 = n0 - portion - remainder
        portion, remainder = divmod(n0, sailors)
        wakes.append((n0, portion, remainder))
        if portion <= 0 or remainder !=1:
            nuts += 1
            continue
        n0 = n0 - portion - remainder
        portion, remainder = divmod(n0, sailors)
        wakes.append((n0, portion, remainder))
        if portion <= 0 or remainder !=1:
            nuts += 1
            continue
        n0 = n0 - portion - remainder
        portion, remainder = divmod(n0, sailors)
        wakes.append((n0, portion, remainder))
        if portion <= 0 or remainder !=1:
            nuts += 1
            continue
        #
        n0 = n0 - portion - remainder
        portion, remainder = divmod(n0, sailors)
        wakes.append((n0, portion, remainder))
        if portion <= 0 or remainder !=0:
            nuts += 1
            continue
        else:
            break
    return nuts, wakes
 
nuts, wake_stats = monkey_coconuts_5sailors()
print('##', monkey_coconuts_5sailors.__doc__)
print("Initial nut count =", nuts)
print("On each waking, the nuts, portion taken, and monkeys share are:\n ", 
      wake_stats)

The output:

## Hard coded and copy-pasted for only five sailors
Initial nut count = 3121
On each waking, the nuts, portion taken, and monkeys share are:
  [(3121, 624, 1), (2496, 499, 1), (1996, 399, 1), (1596, 319, 1), (1276, 255, 1), (1020, 204, 0)]

Turn the copy-pasted code into a loop

Note that their is slightly different logic in the last section of code above and that is reflected in this second version

def monkey_coconuts1(sailors=5):
    "Parameterised the number of sailors using an inner loop"
    nuts = sailors
    while True:
        n0, wakes = nuts, []
        for sailor in range(sailors):
            portion, remainder = divmod(n0, sailors)
            wakes.append((n0, portion, remainder))
            if portion <= 0 or remainder !=1:
                nuts += 1
                break
            n0 = n0 - portion - remainder
        else:
            portion, remainder = divmod(n0, sailors)
            wakes.append((n0, portion, remainder))
            if portion <= 0 or remainder !=0:
                nuts += 1
                continue
            break
    return nuts, wakes
 
nuts, wake_stats = monkey_coconuts1(sailors=5)
print('\n##', monkey_coconuts1.__doc__)
print("Initial nut count =", nuts)
print("On each waking, the nuts, portion taken, and monkeys share are:\n ", 
      wake_stats)

Output:

## Parameterised the number of sailors using an inner loop
Initial nut count = 3121
On each waking, the nuts, portion taken, and monkeys share are:
  [(3121, 624, 1), (2496, 499, 1), (1996, 399, 1), (1596, 319, 1), (1276, 255, 1), (1020, 204, 0)]

Fold in the logic for the morning division

The code for the morning is similar to the code for each sailors nightly excursion except that there is no remainder for the monkey. This last procedural code version folds this last case into the loop with extra logic around the remainder checking.

I also take the opportunity to solve the case of there being six sailors not five.

def monkey_coconuts2(sailors=5):
    "Parameterised the number of sailors using an inner loop including the last mornings case"    
    nuts = sailors
    while True:
        n0, wakes = nuts, []
        for sailor in range(sailors + 1):
            portion, remainder = divmod(n0, sailors)
            wakes.append((n0, portion, remainder))
            if portion <= 0 or remainder != (1 if sailor != sailors else 0):
                nuts += 1
                break
            n0 = n0 - portion - remainder
        else:
            break
    return nuts, wakes
 
if __name__ == "__main__":
    for sailors in [5, 6]:
        nuts, wake_stats = monkey_coconuts2(sailors)
        print('\n##', monkey_coconuts2.__doc__)
        print("For %i sailors the initial nut count is %i" % (sailors, nuts))
        print("On each waking, the nut count, portion taken, and monkeys share are:\n ", 
              ',\n  '.join(repr(ws) for ws in wake_stats))

Output:

## Parameterised the number of sailors using an inner loop including the last mornings case
For 5 sailors the initial nut count is 3121
On each waking, the nut count, portion taken, and monkeys share are:
  (3121, 624, 1),
  (2496, 499, 1),
  (1996, 399, 1),
  (1596, 319, 1),
  (1276, 255, 1),
  (1020, 204, 0)

## Parameterised the number of sailors using an inner loop including the last mornings case
For 6 sailors the initial nut count is 233275
On each waking, the nut count, portion taken, and monkeys share are:
  (233275, 38879, 1),
  (194395, 32399, 1),
  (161995, 26999, 1),
  (134995, 22499, 1),
  (112495, 18749, 1),
  (93745, 15624, 1),
  (78120, 13020, 0)

Using Recursion

Function monkey_coconuts3 sets up for the recursive calling of wake_and_split which has a depth parameter to control the maximum depth of recursion and returns either None or the last integer division of nuts to sailors (in the morning) on success.

def wake_and_split(n0, sailors, depth=None):
    if depth is None:
        depth = sailors
    portion, remainder = divmod(n0, sailors)
    #print((n0, portion, remainder, depth))
    if portion <= 0 or remainder != (1 if depth else 0):
        return None
    else:
        return n0 if not depth else wake_and_split(n0 - portion - remainder, sailors, depth - 1)
 
 
def monkey_coconuts3(sailors=5):
    "Parameterised the number of sailors using recursion including the last mornings case"    
    nuts = sailors
    while True:
        if wake_and_split(n0=nuts, sailors=sailors) is None:
            nuts += 1
        else:
            break
    return nuts
 
if __name__ == "__main__":
    for sailors in [5, 6]:
        nuts = monkey_coconuts3(sailors)
        print('\n##', monkey_coconuts3.__doc__)
        print("For %i sailors the initial nut count is %i" % (sailors, nuts))

Output:

# Parameterised the number of sailors using recursion including the last mornings case
For 5 sailors the initial nut count is 3121

## Parameterised the number of sailors using recursion including the last mornings case
For 6 sailors the initial nut count is 233275

Rosetta Code Task

Oh yes, I also created a new task:   Sailors, coconuts and a monkey problem  from the last two versions of Python code.

END.