|go ahead... be a heretic|
Google Code Jam 2019 Round 1A Problem 1: Pylonsby choroba (Bishop)
|on Apr 14, 2019 at 20:56 UTC||Need Help??|
The round 1A happened at unreasonable hours (around 3AM) for my timezone, so I skipped it. The next day, I checked the problems to see what I could expect in the 1B or 1C rounds. The first problem was called Pylons and it took me a whole day to solve.
It starts simply. We have a grid of a given size and we want to visit each cell in it exactly once. In each turn, we can move in any direction, we just can't stay in the same row, column, or diagonal.
I started with a brute force solution just to see what's possible. After several hours, I was able to guess whether any solution was possible for the given size of the grid, but I wasn't able to find a solution within the time limit for the larger grids.
In the end, I gave up and started to read the Analysis. When they mentioned "random solution should work", I stopped reading and returned to my code. In the brute force solution, I changed the loops
but my program was still timing out. I created a special input file to test all the possible inputs (the maximal size was 20×20) just to notice the program got stuck at a different size every time. I thought: "Maybe there's a random seed that would go through all the inputs smoothly." And I started testing srand $RAND for 0, 1, 2, 3, ... When $RAND was 48, my program solved the first 93 input lines before getting stuck!
And then I had another idea: maybe there's no universal random seed for all the inputs, but each input can have one good random seed. So I wrote a testing program that tried to find the solution for every given size with various random seeds. It set up an alarm timeout of 1 second before trying a solution and only continued in trying the following seed if it timed out.
To my surprise, most of the inputs performed well with the random seed 1. So I used it as the default and specified the exceptions in a hash:
I then just adjusted the srand before I started populating the grid.
And this solution passed the tests.