81–90 of 119 posts
An alternate solution guaranteed to work in every case and bounded to a maximum of 14 steps (for each side): both players can just encode the number they know in binary and say “I don’t know” for a zero and “I know” for a 1.
Peter: "My number is [X]." Sandy: I know the answer!
-- Create Table #x(v) from 1..99
WITH x AS (SELECT n FROM (VALUES (0),(1),(2),(3),(4),(5),(6),(7),(8),(9)) v(n))
SELECT ROW_NUMBER() OVER (ORDER BY (SELECT NULL)) AS v INTO #x
FROM x ones, x tens ORDER BY 1
;
DELETE FROM #x WHERE v > 99
;
-- Create Candidate #c(x, y, s, p) with pair (x,y) (x Their code was horrific. My algorithm: import itertools import collections candidates = [s for s in itertools.product(range(100), range(100)) if s[0] (Usually, next step is variable names, comments, etc.)
data class Candidate(val x: Int, val y: Int)
fun List.filterCandidates(knows: Boolean, aggBy: (Candidate) -> Int) =
groupBy(aggBy)
.values
.filter {value -> if (knows) {value.count() == 1} else {value.count() > 1} }
.flatten()
fun main() {
var cs = (1..99).flatMap { x -> (x..99).map { y -> Candidate(x, y) } }
repeat(7) {
cs = cs.filterCandidates(knows = false) { (x, y) -> x * y }
cs = cs.filterCandidates(knows = false) { (x, y) -> x + y }
}
cs = cs.filterCandidates(knows = true) { (x, y) -> x * y }
println(cs)
}Did I miss it, or does the article not actually explain why we know that at least one pair can be eliminated every round? It seems plausible that the process could get "stuck" in a place where Peter and Sandy both don't learn anything new from discovering the other doesn't know the answer yet. (The puzzle being solvable means that they can't actually get stuck, but that feels like outside information...)
Their code was horrific. My algorithm: import itertools import collections candidates = [s for s in itertools.product(range(100), range(100)) if s[0] (Usually, next step is variable names, comments, etc.)
Horrific is a new one! Thanks for posting your solution :)
- Use of higher-order operations, like filters and aggregations, to avoid loops.
- Passing around functions (the * and + side are the same, except for one operation) to avoid repeated code
This results in:
- Less code. Defects per KLOC tends to be pretty constant, so shorter / higher-level programs are typically less buggy.
- In particular, less repeated code. Cut-and-paste introduces a whole slew of potential defects.
- Less dependence on order-of-operations, which eliminates whole classes of errors, from off-by-ones to data structures in intermediate inconsistent states.
The relevant book here is still SICP.
Did I miss it, or does the article not actually explain why we know that at least one pair can be eliminated every round? It seems plausible that the process could get "stuck" in a place where Peter and Sandy both don't learn anything new from discovering the other doesn't know the answer yet. (The puzzle being solvable means that they can't actually get stuck, but that feels like outside information...)
Yup, without a critical assumption - each "I don't know eliminates a potential solution" - it's not solvable because there is no new information when someone says "I don't know the answer"
Did I miss it, or does the article not actually explain why we know that at least one pair can be eliminated every round? It seems plausible that the process could get "stuck" in a place where Peter and Sandy both don't learn anything new from discovering the other doesn't know the answer yet. (The puzzle being solvable means that they can't actually get stuck, but that feels like outside information...)
I understand it’s a puzzle and it requires some suspension of disbelief, but I think Peter is wrong. He doesn’t know the numbers after 14 tries. He is assuming that Sandy has figured out the trick and is able to correctly keep track of 9801 + 198 = 9999 lists of number pairs in her head. As far as I can tell by how the puzzle is phrased, that’s a totally unreasonable assumption. It’s more likely that she says “I don’…