Robert A. Uhl

Yesterday’s solution was awesome: I read the problem, walked my dog, then sat down at the computer and wrote both solutions perfectly, one after the other. First time I managed to do that!

Today took a bit longer. The difficult thing was coming up with a heuristic for knowing when the stars aligned to give a message, without manually reviewing each possible image. My first idea was to somehow calculate entropy across the grid of stars (and find the lowest-entropy frame), but a quick Googling didn’t really yield anything which was likely to help. My second idea was to find the frame which minimised the sum of the distances between stars (based on the idea that the stars come together to form a message, then fly apart again); sadly, running this on the test data revealed that a non-message frame actually had the stars closest together.

My final idea — and the one which ended up yielding an answer — was a variation on the same heuristic: rather than minimising the sum of distances, I minimised the minimal bounding box around the stars. It was pretty awesome to run the simulation and see the message appear.

Both yesterday & today I ended up using cons cells a lot. This isn’t really good Lisp style, but it’s really easy, and it’s performant enough for simple little test problems like this.