KeiruaProd

I help my clients acquire new users and make more money with their web businesses. I have ten years of experience with SaaS projects. If that’s something you need help with, we should get in touch!
< Back to article list

Puzzle : Je ne sais pas quels sont les chiffres

Je suis tombé sur un puzzle récemment : I don’t know the numbers

L’intitulé est très cool et à la lecture, la première chose qu’on se dit, c’est what the fuck:

Two numbers are chosen randomly, both are positive integers smaller than 100.
Sandy is told the sum of the numbers,
while Peter is told the product of the numbers.

Then, this dialog occurs between Sandy and Peter:

Peter: I don't know the numbers.
Sandy: I don't know the numbers.
Peter: I don't know the numbers.
Sandy: I don't know the numbers.
Peter: I don't know the numbers.
Sandy: I don't know the numbers.
Peter: I don't know the numbers.
Sandy: I don't know the numbers.
Peter: I don't know the numbers.
Sandy: I don't know the numbers.
Peter: I don't know the numbers.
Sandy: I don't know the numbers.
Peter: I don't know the numbers.
Sandy: I don't know the numbers.
Peter: I do know the numbers.

What are the numbers?

Dans la suite (mega spoiler), on va résoudre ce problème avec un peu de code.

Résoudre ce problème

Alors, que se passe-t-il ?

Hé bien le plus simple pour démarrer, c’est de commencer par visualiser ce genre de problèmes:

import pprint as pp
from collections import defaultdict
max_value = 100
products = defaultdict(set)
sums = defaultdict(set)
for i in range(1, max_value):
    for j in range(1, max_value):
        pair = (min(i,j), max(i,j))
        products[i*j].add(pair)
        sums[i+j].add(pair)

Qu’est ce qu’on vient de faire ? Hé bien, avec ce bout de code, on vient de générer deux dictionnaires:

On utilise un set plutôt qu’une liste pour éliminer les doublons. On trie la paire de valeurs pour gérer facilement le cas (j, i) qui est le même que (j, i), car i+j == j+i et ij == ji.

Voici le début du dictionnaire des produits:

>>> pp.pprint(products)
defaultdict(<class 'set'>,
            {1: {(1, 1)},
             2: {(1, 2)},
             3: {(1, 3)},
             4: {(1, 4), (2, 2)},
             5: {(1, 5)},
             6: {(2, 3), (1, 6)},
             # …

On peut voir qu’il y a deux manières d’obtenir 4 : 14, et 22. Pareil pour 6: 23, et 16

Comprendre les contraintes

Comment on utilise ça pour résoudre le problème ? On peut remarquer qu’à chaque tour, les personnages nous donnent un indice: il n’ont pas assez d’élément pour décider. Il semble y avoir une progression, car au bout d’un moment, Peter trouve la réponse.

Peter connait le produit qu’il doit atteindre, mais il y forcément plus d’une manière de l’obtenir car sinon, il pourrait décider.

Par exemple, si la valeur que Peter cherche est 5, il pourrait dès le début conclure: il y a une seule manière d’obtenir 5, c’est 1*5.

Maintenant, comment avancer ? Nous allons propager les contraintes.

Propagation des contraintes

On sait que tout un tas de paires ne sont pas des solutions: par exemple, on vient de voir que (1, 5) n’est pas la solution, car si c’était le cas, on peut répondre.

On peut donc:

def find_single(d):
	"""
	Retourne la liste des valeurs qui sont seules dans le dictionnaire
	"""
	return [next(iter(v)) for v in d.values() if len(v) == 1]


single_pairs = find_single(products)
# Réduction de l’espace de recherche
products = {x:y-set(single_pairs) for x,y in products.items() if len(y-set(single_pairs)) >= 1}
sums = {x:y-set(single_pairs) for x,y in sums.items() if len(y-set(single_pairs)) >= 1}

Solution complète en Python

from collections import defaultdict
import pprint as pp

class ProductSumPuzzle:
	def __init__(self, max_value):
		self.sums = defaultdict(set)
		self.products = defaultdict(set)

		# Generate the candidate lists for the products and sums
		for i in range(1, max_value):
			for j in range(1, max_value):
				pair = (min(i,j), max(i,j))

				self.products[i*j].add(pair)
				self.sums[i+j].add(pair)

	def reduce_search_space(self, single_pairs):
		self.products = {x:y-set(single_pairs) for x,y in self.products.items() if len(y-set(single_pairs)) >= 1}
		self.sums = {x:y-set(single_pairs) for x,y in self.sums.items() if len(y-set(single_pairs)) >= 1}


def find_single(d):
	return [next(iter(v)) for v in d.values() if len(v) == 1]

if __name__== "__main__":
	MAX_VALUE = 100
	puzzle = ProductSumPuzzle(MAX_VALUE)

	# Les 14 "je ne sais pas" réduisent l’espace de recherche, tour à tour avec les produits et les sommes:
	for i in range(7):
		# remove product pairs that have single elements
		puzzle.reduce_search_space(find_single(puzzle.products))
		# remove sum pairs that have single elements
		puzzle.reduce_search_space(find_single(puzzle.sums))

	# Finalement, un des produits a une unique paire de valeurs
	# qui mène à ce produit:
	pair = find_single(puzzle.products)[0]
	prod = pair[0]*pair[1]
	print(pair, prod)