C.LAZY_CAT

I guess I'll be writing a series of computer science-related posts as and when I have the time; it's a good way to blow off some steam after a high-adrenalin academic activity.

Today I will be discussing problem C from the National Olympiad for Informatics 2009, Singapore. This problem, known as LAZY_CAT, is quite significantly harder than most of the previous NOI questions that I've seen (for example, 1999 has only three problems and they are all much easier). It's roughly about a problem 5 or 6 standard on the previous local NOIs. That said, it was one of the two problems that I could devise a proper algorithm to solve.

In general, the NOI was a great experience; the challenge of quickly absorbing and then applying a new programming language of C++ was definitely very interesting. That said, I'm lucky the competition focuses strongly on algorithms and not on skilled manipulation of the language.

LAZY_CAT essentially involves a cat starting at a position "S" that moves around a square grid with maximum dimensions of 10 times 10. The cat moves only orthogonally (i.e. up, down, left, right.) one step at a time around the grid, and must remain within the grid at all times. The grid itself contains four main types of squares: "0" meaning a blank square, "F" meaning a square that contains Food or Fish (not too sure which one), "B" is the cat's Bed, and "X" is a wall that the cat cannot step on. The aim is to get the cat to eat all the Food/Fish and then get to the Bed to sleep in as few moves as possible - or rather, on the programmer's part, to design an algorithm that returns the minimum number of moves required to get the cat, from start S to eat all Food and then go to Bed.

The parameters of the question setting are as follows - the memory cap is so large that it might be ignored (it is on the order of magnitude of one gigabyte). The cap on computational time is 10 seconds. Also, the grid is between 3 by 3 and 30 by 30, and there is a maximum of 10 pieces of Food/Fish on the grid.

For example, a sample grid might be as follows.

X0X
0FB
SFX

In this case, the minimum number of moves for the cat to eat all Food/Fish and then go to Bed is 3. The cat moves right to eat one piece of food, moves up to eat a second piece of food, and then goes directly on to the Bed. No better solutions are possible; hence the program written given this input should return 3.

Sometimes, however, the cat just can't do anything. For a simple example,

FFF
XX0
SXB

Obviously the cat has no legal moves and hence can't do anything! In this situation the program should return -1, for an input with no solutions.

I spoke to Hui Jun about this question, and he suggested a brute force method, much like, according to him, what chess programs often do (play a move, see the consequences, and do this for all possible moves and submoves). Of course, this is an inefficient approach and is furthermore made unacceptable by the strict limit on computational time. The solution I have implemented does involve some optimization, but is consistently able to give a correct answer within the prescribed time limit. In a way, it works somewhat similar to how some chess programs execute pruning methods, such as alpha-beta pruning to optimize their efficiency.

The algorithm I have designed involves a recursive call to a function I have defined as test. The function's method signature may be seen below:

test(int x, int y, int Foods, int Moves, char[] modGrid)

x and y refer to the current position of the cat, Foods refers to the number of foods the cat has eaten, Moves refer to the number of moves the cat has made up to this point, and modGrid refers to the present state of the array. This is important, because squares which had food will no longer be considered to have food - in other words, they will have changed from 'F' to '0'. Of course, we cannot just use a global variable for this since in some of our candidate solutions, some foods will have been eaten, but not in others.

The function stores the values of the first four variables into a system of four parallel arrays that will be discussed later; it then recursively calls test to create four new solutions for evaluation that represent motion in the four directions. If the square being hit is an 'F', Foods and Moves will be incremented, the modGrid will be changed along with the relevant changes in x or y, and the function will be called with these different values; if an 'X', the solution will be rejected and the function will not be called to generate a new solution. In this way, solutions that go nowhere will die out. If an 'O', or 'S', it'll just be passed on with the new x and y, and the modified value of Moves.

You might be asking: what's to stop the cat from travelling infinitely between two '0' squares? Well, (fortunately) I thought of this problem as well, and wrote an if-else conditional statement to block solutions exhibiting the following properties:

(x,y) match an (x,y) in the array of all solutions
Foods is less than or equal to another solution
Moves is equal to or more than another solution
(block equal moves only if food is less)

This will eliminate inefficient solutions and get rid of such problems - once a solution travels from say O left to O right, it will reject immediately travelling backwards to O left, since the pairs of (x,y) will match, Foods will be equal to the previous solution but Moves will be 2 more than the previous solution.

Also, in the event that 'S' is reached with all Foods found, there is not much point in continuing to roam around - the cat should just go sleep, being lazy after all. Hence once we have a full solution, with coordinates matching that of S, with all foods collected, we immediately eliminate all of the other solutions since they cannot be more efficient than the solution already found.

It might seem like a very computationally intensive approach; I don't doubt it is. I guess that's why the board was limited to 10 by 10. It doesn't seem to take that long to traverse the long stacks of recursion this program creates - the algorithms to "weed" out bad or inefficient solutions do their job quickly.

Because I have to parse the entire array of possible solutions each time a new solution is generated, this requires cubic time relative to the total number of solutions M (quadratic each time, multiplied by the number of times it must be done, which is once per solution). Recursion, which determines the total number of solutions, can be said to be proportional to 4^N where N is the grid size.

Hence M = 4^N and T = kM^3
T = k * (4^N)^3

So... the algorithm seems to run in cubic exponential time. I hope I'll be able to find a better solution, this works but looks terrible! The problem definition allows for such algorithms, but I do hope there is a better way of doing this...