You are hereProgramming Problems / 2010 Programming Problems

2010 Programming Problems


By gconway - Posted on 17 April 2012

Free Rooks

Write a computer program to determine *how many ways* to place N rooks on an NxN chess board, in such a way that no rook is attacking another rook.

In Chess, the rook (or castle) is a piece that can attack any piece that is in the same column or row as itself. Normally, a chess board is a square grid with 8 rows and 8 columns, but here we have N rows and N columns.

You may assume N < 13.

 

Free Rooks II

Write a program, as described in task 1 (Free Rooks), except that this time you have R rooks on an NxN board

where 1 <= R < N < 13

 

Digit Dilemma

You are playing a game where your opponent has chosen a 4 digit number, and your task is to determine that number in as few moves as possible.

A move consists of you making a guess, and your opponent will tell you:
(i) how many digits are correct AND in the correct place
(ii) how many digits are correct but in the wrong place

For Example:
Your opponent chooses 8754

You guess: 1234
Response: 1 0    (meaning one number in the right place [i.e. the 4], and no others correct)

You guess: 1567
Response: 0 2    (no digits in the right place, but 2 of them are correct and in the wrong place [5 and 7])

You guess: 8276
Response: 1 1

etc.

Your task is to write a program that will print out (in ascending order) all 4-digit numbers that could be correct answers, given a series of clues. The input to your program is a list of previous guesses and your opponent's responses. Note that 'zero' counts as a digit (e.g. choosing the number 54 is the same as 0054). Also, the same digit can be chosen by your opponent multiple times. If they choose 5551, then a guess of 5005 will get: 1 1

Sample input:
1234 1 0
1567 0 2
8276 1 1
7036 0 1

Correct output:
5874
6225
6252
6255
6259
6295
8654
8754

(Note that every one of these numbers could be the right answer, since they would all produce that set of responses for those guesses)

 

Alan the Apple Robot

When apples fall off the tree, they very quickly go bad. Therefore it is important to gather these apples as quickly as possible.

The local orchard has a very busy apple-collecting robot named Alan. Your goal is to write a computer program that helps Alan collect the apples as quickly as possible.

Your program is given a map, with '1's representing the positions of apples that have fallen in the orchard. In one second, Alan can move one square up, down, left or right. Alan starts in the top-left corner of the grid.

Your program must help Alan by telling him the length of the optimal (shortest) route that will pass through every square that contains an apple. Alan may retrace his steps if necessary.

The first line of input will describe the size of the map: W H (width and height).
The next H lines will contain W characters: 0=empty ground, 1=apple

1 < H <= 20

1 < W <= 20