Once upon a time there was a computer game called Maxit. It was just beginning of the IBM-PC era, so the game is older than average user of CodeAbbey. Later ports included version called "Hot Numbers" with pictures by Penthouse (amiga version) - we'll not share the link here! :)
The gameplay (for two players) is simple:
In your free time you can try programming AI for this game - it is a good exercise since it is almost direct implementation of Minimax algorithm, allowing all of its features without additional complexity given by specific rules of chess, checkers etc.
We'll use the following modifiation: there is only one player, and he performs "horizontal" and "vertical" moves in turns. On "horizontal" move he adds the taken value to his score while on "vertical" move he subtracts it.
The goal is to maximize score.
Try playing the small demo above to get the idea of the rules. You will see that different sequences of moves lead
to different result, for example imagine the situation of half-empty board of size
-3 :: +5 @@ :: :: -2 :: -1
@@ marks the current position,
:: represents empty squares and the next turn is "vertical".
Player can choose to take
-3 - then remaining moves would be pre-determined. If he choses
-2 he has
the following chain of score change:
sub -2 add -1 sub +5 add -3 ------ -7
If instead he choses
-3 then his fate is completely different:
sub -3 add +5 sub -1 add -2 ------ +7
If the field has one extra value
-1, like this:
-3 :: +5 @@ :: -1 -2 :: -1
Then player can prefer to take it on the
3rd move to end the game before clearing the whole board with
(because there would be no more values in the middle row and no move could be made).
You will be given large square field and your goal is to get maximum score of it following the rules described above.
As an answer you'll need to return the sequence of moves. Each move should be represented by a single value - the
index of the cell in the current row or current column,
Input data will contain the size of the field in the first line.
Then the field itself will follow, rows are numbered from the top and columns from the left.
0 will mark the starting position of the "current" cell.
Answer should contain the sequence of moves.
input data: 4 0 -3 +4 +3 -3 +4 -2 -1 +2 -1 -4 +3 -3 -1 -1 -2 answer: 2 2 0 1 1 0 3 3 2 1 3 2 1 3 0
This sequence of moves will lead to score of
19, though you can do better!
Challenge result is assessed by the following formula:
score = score_gained_by_user() max = 51000 min = 46000 result = (score - min) / (max - min)