A post in the scala-user group (via Mauro Ciancio) asked the following problem:

there are 3 people. let’s name them peter, simon and daniel. the three

are supposed to figure out a pair of numbes. the possible pairs are all

combinations of numbers from 0 to 1000, meaning:

(0,0), (1,0), (2,0)….(1000,0),(1,1),(1,2) up to (1000,1000)

peter knows the product of the pair, simon knows the sum, and daniel

knows the difference.the following conversation takes places:

peter: i don’t know the solution

simon: i already knew that

peter: know i know the solution

simon: know i know it, too

daniel: wtf? i can only suspect one of the numbers but can’t be sure

peter: the number you are suspecting is wrong

daniel: k, now i now the numbers, too

As this riddle is a variation on the product & sum riddle, giving us an additional protagonist and a difference sequence of questions and answers, we can try to adapt our previous solution to this new problem.

the possible pairs are all

combinations of numbers from 0 to 1000, meaning:

(0,0), (1,0), (2,0)….(1000,0),(1,1),(1,2) up to (1000,1000)

This section of the riddle isn’t very clear, but we can tentatively translate it to Python as:

all_pairs = [(i, j) for i in range(1000+1) for j in range(i, 1000+1)]

peter knows the product of the pair, simon knows the sum, and daniel

knows the difference.peter: i don’t know the solution

simon: i already knew that

peter: know i know the solution

simon: know i know it, too

The following four sections of the riddle are identical to those of the “product & sum” riddle, so they can be solved using essentially the same code (read the previous solution for the detailed explanation!):

def make_freq_table(it, initial_freqs=None): freq_table = {} if initial_freqs is None else dict(initial_freqs) for e in it: if e not in freq_table: freq_table[e] = 0 freq_table[e] += 1 return freq_table # peter: i don't know the solution num_pairs_by_prod = make_freq_table(x * y for x, y in all_pairs) pairs_1 = [(x, y) for x, y in all_pairs if num_pairs_by_prod[x * y] > 1] # simon: i already knew that identif_by_prod_pairs_sums = set(x + y for x, y in all_pairs if num_pairs_by_prod[x * y] == 1) pairs_2 = [(x, y) for x, y in pairs_1 if x + y not in identif_by_prod_pairs_sums] # peter: know i know the solution num_pairs_by_prod_2 = make_freq_table(x * y for x, y in pairs_2) pairs_3 = [(x, y) for x, y in pairs_2 if num_pairs_by_prod_2[x * y] == 1] # simon: know i know it, too num_pairs_by_sum_3 = make_freq_table(x + y for x, y in pairs_3) pairs_4 = [(x, y) for x, y in pairs_3 if num_pairs_by_sum_3[x + y] == 1]

daniel: wtf? i can only suspect one of the numbers but can’t be sure

This indicates us that, based on the information he has available, Daniel is unable to choose one solution. Furthermore, there is one number that appears more frequently than the others in the pairs he is considering. As Daniel is aware of the information provided by Peter and Simon, we can start by classifying the pairs that are still candidates according to that information by their difference:

def get_pairs_by_diff(pairs): pairs_by_diff = {} for x, y in pairs: if x - y not in pairs_by_diff: pairs_by_diff[x - y] = [] pairs_by_diff[x - y].append((x, y)) return pairs_by_diff pairs_by_diff_4 = get_pairs_by_diff(pairs_4)

The fact that Daniel is still unsure indicates that, whatever the value of the difference might be, there must be more than one pair associated with it. And the fact he has one “suspect number” indicates that one number appears more often than the others (in other words, there is *only one* modal value). Translating this reasoning to code:

def get_modal_elems(pairs): ft = make_freq_table((p[1] for p in pairs), make_freq_table(p[0] for p in pairs)) max_freq = max(ft.values()) return [e for e in ft if ft[e] == max_freq] pairs_5 = [(x, y) for x, y in pairs_4 if len(pairs_by_diff_4[x - y]) > 1 and\ len(get_modal_elems(pairs_by_diff_4[x - y])) == 1]

peter: the number you are suspecting is wrong

This means that, of the previously selected pairs, only those that don’t have the “suspect number” need to be considered. Getting the “suspect number” for each difference (we know that there is one, as we have done a selection by this criteria):

pairs_by_diff_5 = get_pairs_by_diff(pairs_5) susp_num_by_diff_5 = dict((d, get_modal_elems(p)[0]) for d, p in pairs_by_diff_5.items())

Now, based on Peter’s information, we know we can remove the pairs containing the “suspect number” associated to their difference. Doing that:

pairs_6 = [(x, y) for x, y in pairs_5 if susp_num_by_diff_5[x - y] not in (x, y)]

daniel: k, now i now the numbers, too

As Daniel now knows the answer, we know that there is only one pair associated to the difference value known to him. Selecting these pairs:

num_pairs_by_diff_6 = make_freq_table(x - y for x, y in pairs_6) pairs_7 = [(x, y) for x, y in pairs_6 if num_pairs_by_diff_6[x - y] == 1]

Finally, if the riddle is uniquely answerable, we can get the pair items now:

assert len(pairs_7) == 1 print(pairs_7[0])

Putting all the code together and running it, we effectively obtain a single value for the pair: **(64, 73)**.

Top notch solution all the way!

Also, the use of lists comprehensions throughout the code is pretty amazing =D

Just a side note: the setdefault method of the dict class might be used to simplify a little bit get_pairs_by_diff (and similar expressions):

There is also the collections.defaultdict class which does quite that by default, and could be nicer if one needs to increment some dict value as in make_freq_table:

But I don’t know if using a non-build-in type like that in an example code snippet si the best idea for understandability (if that word even exists).

Also, I don’t know why the itertools.groupby function doesn’t do just that, like it’s Groovy homonym does 😛

Thanks for the praise!

The omission of

defaultdictis attributable mainly to laziness, as I made this code by cutting & pasting old code.It’s a shame.

Counterobjects can be used to replacemake_freq_table(), but I am unable to find an elegant replacement for a non-broken groupby…[…] this blog we have solved similar problems before, but this is one that can be easily solved by hand. We only need to be careful not to confuse our […]