Challenge24 2014 writeups

H. Tile design

Task background

Back in 2011 the Pre-EC had a task called Loopz (which was based on an old video game) where you had to solve a jigsaw puzzle that gave a complete pipe loop in the end. When writing an input generator for the problem (that created a pipe loop on an NxM grid and then broke it up into larger pieces), we noted that generating a random enough loop that fills a rectangle can itself be an interesting problem.

So we just had to come up with a definition for "random enough" this year. The longest repeating pipe line metric was chosen because it seemed non-trivial to directly construct a loop without long repetitions, but it can be checked efficiently.

Longest repetition

A tile design can be turned into a string with three letters (L,R,F) by following the pipes and recording left, right and forward moves. The longest (possibly overlapping) repeated substring corresponds to a longest repeating pipe line if wrap around repetitions are allowed in the string.

Longest repeated substring can be found in linear time using longest common prefix arrays, but a rolling hash is simpler to implement, it can nicely take care of the wrap around and in this problem there was a good lower bound given for the repetition which can be used as the size of the hashing window.

Loop generator

We had two generators, one from 2011 and a new one which used the following idea: Generating a random spanning tree on a W/2 * H/2 grid (red dots), then moving around the edges of the tree gives a W * H loop (blue line). This does not give all possible loops (only ones where the "inner wall tree" has its vertices on odd coordinates, but it's easy to generate a random tree (I used random walks and a disjoint-set data structure, Wilson's algorithm actually gives a uniform spanning tree).

loop example

Inputs and solutions

Our policy was not to have two competitive tasks on the EC, as those may take up a lot of time, and we already had the image compression task, so based on a few hours worth of iterations of our new generator we set the required L value. (L was set to be a bit below our best solution, but the scoring was such that an average loop could get reasonable amount of points).

As usual the contestants could generate much better solutions than us. (Eventhough they could get the 100 points by submitting a solution with at most L length repetitions, they did better).
WHLbest Lsubmission