What is this?
This is a quick hack implementation of a simulator for xkcd 2529's weirdly concrete problem. This is barely tested and I suck at computational geometry, so this implementation is likely not correct.
How does it work?
I generate self-avoiding walks using the dimer method described in this notebook. There is apparently some more fancy stuff, but I haven't gotten to that.
To find the largest distance line I find the convex hull using a Grahan scan and from that find antipodal points using the rotating caliper technique and take the maximal pair.
To find all the colinear points I just got lazy and brute forced it.
How do I run it?
The program depends on matplotlib and numpy.
There are two entry points:
plot_main
which will generate and plot a random walk, its marbles, its largest distance line, and the marbles colinear to that line.stat_main
will generate many random walks, and find the mean and standard deviations of the number of marbles on the line.