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

Advertisement

Searching for bits in C

Some years ago, a friend asked me how to (efficiently) get the position of some bit with value 1 inside an (unsigned) integer. For example, taking 32 bit integers and taking the least significant bit (LSB) as the bit 0, these are valid answers:

0xa9e7da24 --> 5
0x1d56b8b0 --> 28
0x9459ffbb --> 0
0x9f0c2a38 --> 24

If we reduce the problem to a more specific one, finding the lowest bit with value 1 inside an integer, it’s easy to get a solution just by doing a bitwise AND against a moving mask:

size_t bitscan(uint32_t a)
{
  size_t i;
  uint32_t mask = 1;
  for (i = 0; i < 32 && !(a & mask); i++)
    mask <<= 1;
  return i;
}

but it’s relatively slow. Can we do it faster?

The answer is clearly yes if we are using x86 assembly, as this instruction set has a specific instruction for this purpose: Bit Scan Forward (BSF). But, even in C, we can do better by a three step process:

• First we isolate the least significant bit that is set by using: a & (-a).
• Then we take the residue of dividing this power of two by 37.
• Finally, we look up the associated bit position, using the residue obtained in the previous step as an index.

Why the first step works? We can start with the zero: doing a bitwise AND against -0 gives us just zero. As the zero doesn’t have any 1 bits to start with, we can say we’ve “isolated” the least significant one, though in a somewhat vacuous sense.

To check the nonzero integers, let’s define the bit expansion of an unsigned integer a:

Then the result of doing –a (remember we are dealing with unsigned integers) will be:

If the number is nonzero, there must a least significant nonzero bit. Let’s call its position M. Writing a & (-a) now:

(definition of M)

(geometric series sum)

(AND bit by bit)

we get the isolated M^th bit, as desired.

We can look for the smallest divisor giving different residues for 2⁰, 2¹, …, 2³¹ via a small piece of code:

def get_modulo(n):
    m = 1
    while True:
        if len(set(2**i % m for i in range(n))) == n:
            return m
        m += 1

if __name__ == '__main__':
    print(get_modulo(32))

Now we just have to put the bit numbers in their associated positions inside the lookup table. We can calculate the table using the following Python code:

def get_lut(max_exp, modulo):
    lut = [-1] * modulo
    for i in range(max_exp + 1):
        assert lut[2 ** i % modulo] == -1
        lut[2 ** i % modulo] = i
    return lut

def print_table(table):
    print('{%s}' % ', '.join('%d' % t for t in table))

if __name__ == '__main__':
    print_table(get_lut(32, 37))

Then, putting these two pieces together, we get the following C function:

int lut_bit_pos(uint32_t a)
{
  const int bit_pos_lut[37] =
  {
    -1, 0, 1, 26, 2, 23, 27, 32, 3, 16,
    24, 30, 28, 11, -1, 13, 4, 7, 17,
    -1, 25, 22, 31, 15, 29, 10, 12, 6, 
    -1, 21, 14, 9, 5, 20, 8, 19, 18
  };
  return bit_pos_lut[(a & (-a)) % 37];
}

As we are working with 32 bit integers, we can do a full test… though not using Ideone (it exceeds the runtime limits).

Edited 5/30/11 – Bit sets

The original problem was to handle a set of task slots, each slot having two possible states: occupied or empty. This set required an efficient support of the following operations:

• Checking if a slot is occupied.
• Occupying/freeing a slot.
• Getting a free slot if one is available.

As this problem doesn’t ask us for the slot number, we can use an opaque type and internally codify the slot as its associated power of two:

typedef uint32_t set_t;
typedef int32_t set_aux_t;
typedef uint32_t slot_t;

#define NUM_SLOTS 32

#define EMPTY_SET ((set_t)-1)
#define FULL_SET ((set_t)0)

#define IS_VALID_SLOT(slot) ((slot)&&!((slot)&((slot)-1)))
#define SLOT_FROM_INDEX(slot_idx) (1<<(slot_idx))

#define GET_EMPTY_SLOT(set) ((set)&(-(set_aux_t)(set)))

#define SET_SLOT(set, slot) ((void)((set)&=~(slot)))
#define CLEAR_SLOT(set, slot) ((void)((set)|=(slot)))

#define IS_SLOT_SET(set, slot) (!((set)&(slot)))

We can check the implementation using Ideone.