Moving code around with branches
DataGenetics proposed a neat number puzzle:
You are at a party and overhear a conversation between Lucy and her friend. In the conversation, Lucy mentions she has a secret number that is less than 100. She also confesses the following information:
"The number is uniquely describable by the answers to the following four questions:"
- Is the number divisible by two?
- Is the number divisible by three?
- Is the number divisible by five?
- Is the number divisible by seven?
She then proceeds to whisper the answers to these questions to her friend. Unfortunately, because of the ambient noise at the party, you only hear the answer to one of the questions. However, knowing just this one answer allows you to determine Lucy’s secret number.
- Which question and answer did you overhear?
- If the answer to this question is “Yes”, what is Lucy’s secret number?
Rather than solve the puzzle by hand, I reached for a computational approach (implemented in Python).
My approach is to take all the numbers from 1–100 and calculate the signature for each: the signature is the answer to Lucy's four questions.
def signature(n): return ( n % 2 == 0 , n % 3 == 0 , n % 5 == 0 , n % 7 == 0 )
The question is about going from the signature to a unique number, so I want to find, for each signature, which numbers have that signature.
I do that by going through all the numbers and generating the signature for each one. I store the results in a
signatures which has a key of the signature and a value which is a
list of all the numbers with that signature.
import collections signatures = collections.defaultdict(list) for i in range(1, 100): signatures[signature(i)] += [i]
(I use the
collections.defaultdict just so I don't have to bother checking for non-existent keys in the loop.)
I can then see which signatures have just one number:
[(s, ns) for s, ns in signatures.items() if len(ns) == 1] # -> [((False, False, True, True), ), ((True, False, True, True), )]
Only two signatures have unique numbers:
False, False, True, True for 35 and
True, False, True, True for 70. Those signatures are the same, except for the first question ("is the number divisible by 2?").
So that's the answer:
- You overheard the first question.
- If you heard, "Yes," Lucy's number is 35.