There seems to be an error in the backtracking algorithm. E.g.: https://imgur.com/a/1miv1AK
Show HN: I made a puzzle game that gently introduces my favorite math mysteries
51–60 of 177 posts
Re: Show HN: I made a puzzle game that gently introduces my favorite math mysteries
#521. Nice site, bookmarked to give it to people.
2. You are a very bad and annoying person ;)
Re: Show HN: I made a puzzle game that gently introduces my favorite math mysteries
#53Earlier quoted context omitted.
Diving into Wikipedia, apparently variations of the name "Britain" have been in use since 30BC, and referred to the big island, with the smaller islands grouped with it, e.g. British Isles. The Irish may not like it, but they're fighting against two millenia of history.
And it's use in English only comes from the mid 16th and 17th centuries, right around the time that much of Ireland was being colonized by the British. Frankly, I find the term offensive, and think it should be discouraged in much the same way people have shifted away from "the Ukraine" to simply Ukraine.
Why is "the Ukraine" bad?
Re: Show HN: I made a puzzle game that gently introduces my favorite math mysteries
#54There seems to be an error in the backtracking algorithm. E.g.: https://imgur.com/a/1miv1AK
Good catch -- I'll look into this!
Re: Show HN: I made a puzzle game that gently introduces my favorite math mysteries
#55Thanks for sharing. This was instructive and fun in equal parts
Re: Show HN: I made a puzzle game that gently introduces my favorite math mysteries
#56Earlier quoted context omitted.
Thanks for pointing this out! Switched to "British Isles" -- update should be percolating now
The British Isles is also a somewhat controversial term with colonial implications, and it's not used by the government of Ireland[1]. "Britain and Ireland" would be a safer bet, as the map doesn't include any other islands. https://en.wikipedia.org/wiki/Names_of_the_British_Isles
Switched to "Britain + Ireland"!
Re: Show HN: I made a puzzle game that gently introduces my favorite math mysteries
#57Uh, when you draw the map that requires three colors, I couldn't figure out how to submit it to at least be told it's not good enough. Or if it automatically accepts for a 3-min [1], then it was too hard to make sure that the boundary reached the edge of the screen. (I thought I successfully drew five regions around a point.) [1] sorry, 3-chromatic or whatever
Hmm, my guess is you're trying to use the box's borders as lines (they don't count, only the lines you draw count). Let me know if that's not the issue. Also, I'll think about ways to make this more clear!
Re: Show HN: I made a puzzle game that gently introduces my favorite math mysteries
#58Loved the interactions and flow overall but I'm a bit lost on the zero knowledge proof example. I'm familiar with the concept but I don't follow how the example is one. E.g. "By repeating the process enough times, the probability that you never catch me becomes smaller than, say, getting struck by lightning" doesn't seem to show it's a proof? If I pick a hundred numbers it'll look like I just proved some black box fu…
Very glad you enjoyed it! For the ZK example, the math behind it is this: if there are m bordering regions and I am lying, you have a 1/m chance of catching me each time. Thus after k repetitions the chance you haven't caught me is (1-1/m)^k \approx e^{-k/m} which is extremely small for k sufficiently larger than m. Now, you may rightfully say: hey that's still not a "proof," you could still be lying! There are two r…
Yeah, I got tripped up by that formulation as well and it's actually something that annoys me with a lot of algorithms that have some properties proven in a limit: It's "easy" (or at least possible) to mathematically prove that in the limit of some variable, the property will hold: If you repeat the challenge increasingly often, the probability of being lied to will get arbitrarily close to zero; for sufficiently large input sizes, some algorithm runs in linear time; with sufficiently large amounts of training data and iterations, some prediction error will become arbitrarily small, etc etc.
But none of that is telling you how much is "sufficient", or even which order of magnitude we're talking about. If the quantity has a real life cost, this would result in enormous practical differences.
(With the formula you have given for the ZK proof, we're at least one step further: You can start with the desired probability, e.g. the gamma ray burst und calculate the required minimum k from that - also, it's easy to see that the color problem lends itself well to such proofs because the probability of failure drops exponentially quickly with growing k, so the actual k you choose can be relatively small. But if all you have is a proof in the limit, that's not possible)
Re: Show HN: I made a puzzle game that gently introduces my favorite math mysteries
#59In Android using Firefox the button to go to the next challenge doesn't seem to work.
Will look into this. Did it happen on the first page (map of Britain + Ireland)?
Re: Show HN: I made a puzzle game that gently introduces my favorite math mysteries
#60Loved the interactions and flow overall but I'm a bit lost on the zero knowledge proof example. I'm familiar with the concept but I don't follow how the example is one. E.g. "By repeating the process enough times, the probability that you never catch me becomes smaller than, say, getting struck by lightning" doesn't seem to show it's a proof? If I pick a hundred numbers it'll look like I just proved some black box fu…
I've got another problem about this zero knowledge proof. The digital version doesn't make a lot of sense to me. It depends on the fact we don't have a fast integer factorization algorithm. But integer factorization is not proven to be NP-complete, and 3-coloring is NP-complete.
So isn't it possible that there is a polynomial time algorithm for integer factorization, but no polynominal time algorithm for 3-coloring, and therefore the "zero knowledge proof" actually reveals the answer?