Solving the “product, sum & difference riddle”

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).

Advertisements

3 thoughts on “Solving the “product, sum & difference riddle”

  1. Demian says:

    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):

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

    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:

    def make_freq_table(it, initial_freqs=None):
        freq_table = defaultdict(int, {} if initial_freqs is None else initial_freqs)
        for e in it:
            freq_table[e] += 1
        return 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 😛

    • mchouza says:

      Top notch solution all the way!

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

      Thanks for the praise!

      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):

      </em>

      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:

      <em>

      The omission of defaultdict is attributable mainly to laziness, as I made this code by cutting & pasting old code.

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

      It’s a shame. Counter objects can be used to replace make_freq_table(), but I am unable to find an elegant replacement for a non-broken groupby…

  2. […] 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 […]

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s