Mainly Tech projects on Python and Electronic Design Automation.

Monday, May 04, 2015

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.


1 comment:

  1. I tried to implement this using pandas. Here is my result:


    >>> import numpy as np
    >>> import pandas as pd
    >>>
    >>> doors = ['red', 'blue', 'green', 'yellow', 'white']
    >>> frees = range(len(doors))
    >>> doorcombs = permutations(range(len(doors)))
    >>> combs = list(x+(y,) for x, y in product(doorcombs, frees))
    >>> df = pd.DataFrame(combs, columns=doors+['free'])
    >>>
    >>> rule0 = df['red'] < df['free']
    >>> rule1 = ~df['blue'].isin([0, 4])
    >>> rule2 = np.abs(df['green'] - df['free']) == 3
    >>> rule3 = np.abs(df['yellow'] - df['free']) == 1
    >>> rule4 = df['white'] == 2
    >>>
    >>> res = df[rule0 & rule1 & rule2 & rule3 & rule4]
    >>>
    >>> free = np.asscalar(res.pop('free').values)
    >>> order = res.T.sort(res.index[0]).index.tolist()
    >>> freecolor = order[free]
    >>> steps = (free-2)*2
    >>> direction = '' if steps == 0 else 'left' if steps < 0 else 'right'
    >>>
    >>> print('Exit: %s, %s;' % (free, freecolor), '%s steps %s;' % (np.abs(steps), direction), 'Order:', order)
    Exit: 3, blue; 2 steps right; Order: ['green', 'red', 'white', 'blue', 'yellow']

    ReplyDelete

Followers

Subscribe Now: google

Add to Google Reader or Homepage

Go deh too!

whos.amung.us

Blog Archive