## Car Talk Puzzler #5: The Perfect Square Dance

PUZZLER: The Perfect Square Dance!Sally invited 17 guests to a dance party. She assigned each guest a number from 2 to 18, keeping 1 for herself. The sum of each couple’s numbers was a perfect square. What was the number of Sally’s partner?

The fifth in my ongoing series of solving Car Talk Puzzlers with my programming language of choice. I’m using Python again, just like last time.

There are a few pieces to this. The first is, how do we generate a list of all possible pairs that match the perfect square constraint? With list comprehensions and a helper function this is easy.

def perfect_square(n): return math.sqrt(n) == int(math.sqrt(n)) # range creates a list that's exclusive of last number. Thus to go from 1 to n, # use range(1, n+1) guests = range(1, num_guests + 1) # By enforcing the x# a whole bunch of equivalent pairs (e.g. (3,6) and (6,3)). pairs = [(x,y) for x in guests for y in guests if x<y and perfect_square(x+y)] >>> guests [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18] >>> pairs [(1, 3), (1, 8), (1, 15), (2, 7), (2, 14), (3, 6), (3, 13), (4, 5), (4, 12), (5, 11), (6, 10), (7, 9), (7, 18), (8, 17), (9, 16), (10, 15), (11, 14), (12, 13)]

>>> itertools.combinations([1,2,3,4,5], 2) # This is a sort of generator object which lazily returns the values as needed. # To force them to all be evaluated at once, to see how this works, # wrap the call in a list function. >>>list(itertools.combinations([1,2,3,4,5],2)) [(1, 2), (1, 3), (1, 4), (1, 5), (2, 3), (2, 4), (2, 5), (3, 4), (3, 5), (4, 5)]

This performs exactly as how we would expect. Note that I want combinations rather than permutations because the order does not matter.

Yeah, I think we can handle checking 48620 combinations.

def flatten(nested): """ Flatten one level of nesting. Returns a generator object For instance: list(flatten([(1,3),(5,6)])) --> [1,3,5,6] """ return itertools.chain.from_iterable(nested) def all_guests_present_once(combination): """ Returns whether each guest is present once Combination is a list of tuples, e.g. [(1,5),(7,8)] """ flattened = list(flatten(combination)) return len(set(flattened)) == len(flattened) >>> all_guests_present_once([(1,3),(4,5)]) True >>> all_guests_present_once([(1,3),(3,6)]) False

OK we’re ready to throw it all together.

def dance_arrangement(num_guests): """ Returns a valid pairing for all guests if possible, else an empty set """ # Clearly you need an even number of guests to have everyone paired if num_guests % 2 == 1: return [] else: # range creates a list that's exclusive of last number. Thus to go from 1 to n, # use range(1, n+1) guests = range(1, num_guests + 1) # By enforcing the x # a whole bunch of equivalent pairs (e.g. (3,6) and (6,3)). pairs = [(x,y) for x in guests for y in guests if x # brute force search all_arrangements = itertools.combinations(pairs, num_guests / 2) return filter(all_guests_present_once, all_arrangements)

Running the program with num_guests = 18, we get

[((1, 15), (2, 14), (3, 13), (4, 12), (5, 11), (6, 10), (7, 18), (8, 17), (9, 16))]

8 [((1, 8), (2, 7), (3, 6), (4, 5))] 14 [((1, 8), (2, 14), (3, 13), (4, 12), (5, 11), (6, 10), (7, 9))] 16 [((1, 8), (2, 7), (3, 6), (4, 5), (9, 16), (10, 15), (11, 14), (12, 13))] 18 [((1, 15), (2, 14), (3, 13), (4, 12), (5, 11), (6, 10), (7, 18), (8, 17), (9, 16))]

As you can see, 8, 14, and 16 guests can also be paired up in this way. Something to keep in mind the next time you are going to have a party.

Full sourcecode can be found on Github.

Pretty nifty. I think logic is the quicker way for this specific question (I finished it pretty quickly working backwards), but definitely useful for larger sets of numbers.

Also, it is surprisingly dead here. I guess, looking at your archives, one can tell roughly when you got the new job. I bet your stats still beat out the Lure though.

Thanks for the comment. I think the questions in general on car talk are designed to be solved without a computer, but I like to use them as a way to illustrate some techniques in various programming languages.

Yeah I’m sorry to say I’ve barely blogged at all recently. I have some ideas in the works. Some of my blogging activity has also moved towards quick updates on G+/Twitter.