2 ms·
My cursory analysis suggests that there are hidden constructions invisible in the game but used for the verification (you can see a base64-encoded task file fly
by lifthrasiir 8y ago
My cursory analysis suggests that there are hidden constructions invisible in the game but used for the verification (you can see a base64-encoded task file flying through the network). The actual verification happens in an Emscripten-powered C++ engine and it is pretty opaque to me---the only thing I can identify is a parser for the task file.
My best guess without the actual source code is as follows: The perfect algorithm would involve the equality between two functions returning constructible numbers [1], where each function would map from unspecified points (that you can move around with the hand tool) to the result points. As far as I concerned comparing two constructible numbers is possible but inefficient [2], and comparing two functions is probably much harder. However for the purpose of game, we can approximate the equality by randomly evaluating a difference between two functions to the reasonable accuracy and checking if it is close to zero. Theoretically exact real arithmetic would be preferable, but adaptive fixed-precision real arithmetic may be also possible as long as rounding errors are tracked.
[1] https://en.wikipedia.org/wiki/Constructible_number https://en.wikipedia.org/wiki/Constructible_number
[2] https://mathoverflow.net/a/211556 https://mathoverflow.net/a/211556
- obastani 8y agoThanks for the response! I think you're right that it's something along these lines. I didn't find any further information about Euclidea, but for anyone interested, I did find some information about open source engines that achieve similar purposes [1,2]. Need to do some more digging... [1] https://en.wikipedia.org/wiki/List_of_interactive_geometry_software https://en.wikipedia.org/wiki/List_of_interactive_geometry_s... [2] https://dev.geogebra.org/trac/wiki/TheoremProving https://dev.geogebra.org/trac/wiki/TheoremProving
- lifthrasiir 8y agoThank you for the pointer to Geogebra, yeah, there ought to be someone already dealing this :-) It seems that there are some shortcuts for many functions (e.g. [1] only evaluates the function finite number of times). [1] http://ggb1.idm.jku.at/~kovzol/papers/Kovacs-Recio-Weitzhofer-20120323.pdf http://ggb1.idm.jku.at/~kovzol/papers/Kovacs-Recio-Weitzhofe...