1. About.com
  2. Computing & Technology
  3. C / C++ / C#
About.com
C / C++ / C#

Discuss in my forum

Programming Challenge 34 - Complete Lines

Completed

By , About.com Guide

See More About:

There's a simple boardgame set on a 10 x 10 grid numbered 0..9 on each axis. Each cell can have 1 of 4 numbers (0-3) and these are scattered randomly at the start with 25 of each number. You are given a starting position. To win the game you must move pieces so that numbers are lined up to form a row, horizontally, vertically or diagonally of 10 cells all the same number. It doesn't matter which number wins btw. If your move completes a line then the game is over and you win.

Pieces are moved by swapping any two adjacent pieces, where adjacent means any of the 8 surrounding cells. However the moves you can make are determined by a very odd dice. It's seven sided and throwing it can give one of these: 1,2 or 3 lateral (i.e. horizontal or vertical) moves, 1,2 or 3 diagonal moves and 4 moves either diagonal or lateral. 1L, 2L, 3L, 1D, 2D, 3D,4DL.

You must of course obey the dice so if it's 1L, then you can only swap one piece laterally so a piece at 4,6 can only swap with one at 3,6, 5,6, 4,7 or 4,5. Swapping it with the piece at 5,7 is not allowed. You need a 1D, 2D, 3D, or 4DL for that. The 4DL means you can make 4 moves each of which is diagonal or lateral.

Your application must read a file containing a starting position and a set of dice throws and make moves that will win the game in as few moves (and code execution time) as quickly as possible. To make it a little trickier, after each dice roll there will be 1-4 moves by an opponent. Each move is a 4 digit number xyxy. Each x and y is a digit 0-9 like 4647 which swaps the piece at 4,6 with 4,7 (swap the piece at x=4,y=6 with x=4,y=7). If you rolled a 2 (ie 2D or 2L) then you get two moves and so on.

The Input File

Located in the same location as your exe, input.txt contains 2 parts. the first ten lines are ten chars long each char being one of 0-3 for the starting position. This is followed by a large number of lines each starting with a dice roll (one of 1L,2L,3L,1D,2D,3D,4DL followed by a space) and 1-4 moves where each move is a 4 digit number followed by a space. Eg
  • 2L 4656 4636 3635

There are several hundred lines, hopefully enough for you to finish the game. For each line your program must make the number of moves of the specified type, checking after each move to see if the game is over. If not then you must apply the opponents moves to the board.

The Output File

Please output these results into output.txt in the same location as your exe. Each line read from the input text file should be output directly with an I (and a space) prefix so the above line would appear in the output file as

  • I 2L 4656 4636 3635/li>

followed by your moves, each on one line so two moves would look like this:

3738
3849
These two moves effectively swap 37 with 49. If your application wins the game then output one of these rows immediately after your last move
Win! 10H in row 6
Win! 10V in col 0
Win! 10D from 0,0 to 9,9
Win! 10D from 9,0 to 0,9

(H means Horizontal, V means vertical and D = diagonal)

Then output the count of the number of moves your application made and the time it took to run.

56 Moves in 0.425 ms
87 moves in 4.5 seconds

The number of moves is the important one, with the quickest time taken as tie breaker. I'll be verifying the output files.

Questions

Am I allowed to pre-process the file rather than working out moves one line at a time. Yes.

Timing Code

Results

Congrats to our sole entrant Shashi Sadasivan whose C# entry solved the straight line in 8 ms.

  1. Shashi Sadasivan (Australia, 27) - C# Time(secs) = 8 ms

More Programming Challenges

©2012 About.com. All rights reserved. 

A part of The New York Times Company.