I like these post mortums as well, so thanks to all for sharing.

I made a number of optimisations to the grid to improve performance of large grids:

* Implemented as a bit fields to save memory, cache and bandwidth.

* Implemented a process routine that used the bit field to process more in one go. A bit like the idea behind using SSE.

* Implemented a hardwired byte based 5x5 grid, like Lazydodo did, that just processes the inner 3x3. I would rip this 5x5 from the large grid. Calculated the next move and iteration and if any of them resulted in a live cell then iterate the whole grid, reinsert the 3x3 grid and save for later proessing.

For the threading each thread had its own collection of work. Work being a live cell position and a grid. If a thread ran out of work it would steal a job from another thread. This kept the cross talk between threads low. I started off with each work collection just being a queue of work but changed it to be an array of queues. New work was always taken from the lowest queue with work. New work was push onto the array based on a scoring system. The score was based on the live cell distance from the target and the path length of the present solution. So work that was closer to the solution got done sooner unless it was getting a long path. This gave me a quick route to find **A** solution and also pushed the infinte loops out of the way of more valid routes. But was not so good at finding the shortest path as it is basically a depth first search with prunning.

I made the same mistake and placed effort more on being able to handle large problems and scaling than on finding the shortest route. Bih ouch. Would have been nice to see some larger problems.

Code attached. (Linux, GCC, pthreads)

## Post-mortem

Since the post mortem thread in A3 was kinda interesting lets have a go at the other two problems as well

This problem was an interesting one for me, I figured its a threading contest, i bet we get to use threads! However the best solution seemed to be single threaded. (Weird!)

The best optimalisation I could come up with was a lookup table for every 5x5 block on the field you could determine the inner 9 cells by just looking in a big ass table, turning this problem from a heavy test problem into a simple lookup problem. and by running a single 5x5 block it was easy to determine possible spots to move to in the next cycle. One last optimalisation was to check the current cell's location compared to the target cell and try the possible directions that would get us closer (or atleast in the right direction) to the target cell first.

I kinda misread or mis understood the problem description and figured there would be more points for performance then for the 'shortest' route (boy was that a mistake) and opted to have a go at trying to be fastest, looking back yeah big mistake, but hey on timing points alone still got 12 points out of it.

(warning due to the lookup table download is about 16 megs)