Computer Science

# Trees: Level 4 Challenges

Consider an $N \times N$ grid of lights, each one either on or off. The grid can be manipulated by pressing any one light on the grid, toggling the light - however, when a given light is pressed, all lights that are edge-wise adjacent to the pressed light also get toggled.

Given an initial configuration, one might be interested in a sequence of moves that turns all of the lights on the board off, or more simply, whether such a sequence exists or not. For example, the following $5 \times 5$ grid can be solved by pressing the five numbered squares in their labeled order:

As surprising as it may seem, this second board is provably unsolvable. There is no sequence of moves in existence that turns all of the lights off:

Grid configurations will be represented as a series of lines in a text file. The first line will be a single integer, $N$, specifying the size of the grid. The following $N$ lines will specify the contents of the grid, where '$\text{\#}$' characters indicate lights that are on, and '$\text{.}$' characters indicate lights that are off. The two grid configurations above would be encoded as:

  1 2 3 4 5 6 7 8 9 10 11 12  5 .#..# #..#. #.#.. .#### ...#. 5 .#... .##.. #.... ..... ..... 

Clicking lights.txt will trigger a download of a ~300KB zip file, which contains a text file named "lights.txt". The text file contains, in the specified format, $10000$ light grids, with sizes $5 \leq N \leq 16$. Precisely $X$ of these grids are solvable.

Find $X$.

Note: An efficient program can find $X$ in well under one minute. If your program is taking hours to complete, you may need to rethink your approach.

###### Image Credit: http://www.edcourtenay.co.uk/musings-of-an-idiot/2002/04/10/LightsOut

What is the number of leaf nodes in a rooted tree of 100 nodes with each node having 0 or 3 children?

Edsger Dogstra is playing soccer with his friends but someone kicked the ball far away. He has to get the ball, but the soccer field is full of puddles. He hates to step in the puddles, and wants to take the shortest distance where possible.

Help him find the number of different paths of minimum length to reach the ball, where he doesn't step in the puddles!

The soccer field is a $25 \times 25$ square grid, $\boxed{\#}$ characters are puddles and $\boxed{.}$ characters are free grass; Edsger starts in the upper left cell and the ball is in the lower right cell and he can only move on adjacent cells (not diagonally).

It is always possible reach the ball moving only right and down.

The soccer field.

×