impossible_puzzle.py

# "impossible puzzle" as described at http://en.wikipedia.org/wiki/Impossible_Puzzle

# X inside 2..99
# Y inside 2..99
# P knows X * Y
# S knows X + Y

def every_pair():
    for x in range(2,100):
        for y in range(x,100):
            yield (x,y)

def prod(pair):
    return pair[0] * pair[1]

def sum(pair):
    return pair[0] + pair[1]

def possible_outputs_to_inputs(inputs, func):
    output_to_inputs = {}

    for input in inputs:
        out = func(input)
        if out not in output_to_inputs:
            output_to_inputs[out] = []

        output_to_inputs[out].append(input)

    return output_to_inputs.items()

possible_pairs = set(every_pair())

def map_possible_outputs_to_possible_pairs(func):
    return possible_outputs_to_inputs(possible_pairs, func)

print "no information, "+str(len(possible_pairs))+" possibilities"

# step 1, P couldn't figure out X,Y. Eliminate any pair where X,Y is knowable from P(X,Y)

for p, possible_xy in map_possible_outputs_to_possible_pairs(prod):
    if len(possible_xy) == 1:
        # print "pair "+str(possible_xy[0])+" is knowable when p = ",p
        possible_pairs.remove(possible_xy[0])

possible_p = set()
for p, possible_xy in map_possible_outputs_to_possible_pairs(prod):
    possible_p.add(p)

print "step 1, "+str(len(possible_pairs))+" possibilities"

# step 2, S already knew that P could not guess X,Y.
# Eliminate every X,Y that has an S where there exists a possible P that causes X,Y to be knowable.

values_of_p_that_make_x_y_knowable = set()
for p, possible_xy in possible_outputs_to_inputs(every_pair(), prod):
    if len(possible_xy) == 1:
        values_of_p_that_make_x_y_knowable.add(p)

values_of_s_where_there_is_a_p_that_makes_x_y_knowable = set()

for s,possible_xy in possible_outputs_to_inputs(every_pair(), sum):
    for xy in possible_xy:
        p = prod(xy)
        if p in values_of_p_that_make_x_y_knowable:
            # print "when s = "+str(s)+" there is a p ("+str(p)+") that makes x,y knowable "+str(xy)
            values_of_s_where_there_is_a_p_that_makes_x_y_knowable.add(s)

for xy in list(possible_pairs):
    if sum(xy) in values_of_s_where_there_is_a_p_that_makes_x_y_knowable:
        possible_pairs.remove(xy)

print "step 2, "+str(len(possible_pairs))+" possibilities"

# step 3, P now knows X,Y. Eliminate any pair where X,Y is NOT knowable from P(X,Y)
p_where_xy_is_not_knowable = set()
for p,possible_xy in map_possible_outputs_to_possible_pairs(prod):
    if len(possible_xy) != 1:
        p_where_xy_is_not_knowable.add(p)

for p,possible_xy in map_possible_outputs_to_possible_pairs(prod):
    if p in p_where_xy_is_not_knowable:
        for xy in possible_xy:
            possible_pairs.remove(xy)

print "step 3, "+str(len(possible_pairs))+" possibilities"

# step 4, S now knows X,Y too. Eliminate any pair where X,Y is NOT knowable from S(X,Y)
s_where_xy_is_not_knowable = set()
for s,possible_xy in map_possible_outputs_to_possible_pairs(sum):
    if len(possible_xy) != 1:
        s_where_xy_is_not_knowable.add(s)

for s,possible_xy in map_possible_outputs_to_possible_pairs(sum):
    if s in s_where_xy_is_not_knowable:
        for xy in possible_xy:
            possible_pairs.remove(xy)

print "step 4, "+str(len(possible_pairs))+" possibilities"

print list(possible_pairs)