4 ms·

This isn't quite right. This does find the solution when the problem is well-formed, but it doesn't prove that the solution is valid: if round == 15:

This isn't quite right. This does find the solution when the problem is well-formed, but it doesn't prove that the solution is valid: if round == 15: for product in products: if len(products[product]) == 1: print('Peter: I do know the numbers') print(products[product][0]) return This should not return - it should continue iterating. If the problem (and the code) is correct, then it should only find one answer - but unless you exhaustively search and find exactly one answer you don't know that it's correct. Incidentally, I was also a bit surprised by candidate_pairs = set() for i in range(1, N): for j in range(1, N): if (i, j) not in candidate_pairs and (j, i) not in candidate_pairs: candidate_pairs.add((i, j)) That first (i, j) check can never return false and should be omitted, right?

Jtsummers 5y ago
Regarding the second snippet, yeah, that (i,j) test will always be true. And if the inner loop is changed from `range(1, N)` to `range(i, N`) then it will be totally unnecessary anyways to have the conditional. With that change every pair would be generated exactly once.
otras 5y ago
That's a good point! The `15` check relies on 1) knowing it will stop after 15 rounds as written in the problem (though I explore that later) and 2) assuming that there must be a single answer after 15 rounds (which I also explore later). And that's true, the `(i, j)` check is spurious - I blame it on it being throwaway blog post code :)
Someone 5y ago
The ‘normal’ way to write something like that (I hope I got the range ends right) is for i in range(1, N): for j in range(1, j + 1): candidate_pairs.add((i, j)) Also, conceptually, you don’t have tuples, but multisets. If you were to use those, you wouldn’t need that if at all. Multiset isn’t built-in to python, so you’d need to use an external package. Alternatively, write a class for storing pairs of ints i, j that enforces i ≤ j.
- drexlspivey 5y ago
  Python actually has built in support for multisets, you use a set of frozensets >>> a = set( (frozenset((1,2)), frozenset((3,4)) ) ) >>> frozenset((2,1)) in a True
  - Someone 5y ago
    That’s not a multiset, it’s a set containing tuples. A multiset (https://en.wikipedia.org/wiki/Multiset https://en.wikipedia.org/wiki/Multiset) allows you to add identical items multiple times. You would use that to, for example, store the knowledge that 6 can be written as 3+3, by using a multiset {3,3} instead of a tuple (3,3)

Jtsummers 5y ago

Regarding the second snippet, yeah, that (i,j) test will always be true. And if the inner loop is changed from `range(1, N)` to `range(i, N`) then it will be totally unnecessary anyways to have the conditional. With that change every pair would be generated exactly once.

otras 5y ago

That's a good point! The `15` check relies on 1) knowing it will stop after 15 rounds as written in the problem (though I explore that later) and 2) assuming that there must be a single answer after 15 rounds (which I also explore later). And that's true, the `(i, j)` check is spurious - I blame it on it being throwaway blog post code :)

Someone 5y ago

The ‘normal’ way to write something like that (I hope I got the range ends right) is for i in range(1, N): for j in range(1, j + 1): candidate_pairs.add((i, j)) Also, conceptually, you don’t have tuples, but multisets. If you were to use those, you wouldn’t need that if at all. Multiset isn’t built-in to python, so you’d need to use an external package. Alternatively, write a class for storing pairs of ints i, j that enforces i ≤ j.

drexlspivey 5y ago
Python actually has built in support for multisets, you use a set of frozensets >>> a = set( (frozenset((1,2)), frozenset((3,4)) ) ) >>> frozenset((2,1)) in a True
- Someone 5y ago
  That’s not a multiset, it’s a set containing tuples. A multiset (https://en.wikipedia.org/wiki/Multiset https://en.wikipedia.org/wiki/Multiset) allows you to add identical items multiple times. You would use that to, for example, store the knowledge that 6 can be written as 3+3, by using a multiset {3,3} instead of a tuple (3,3)