1

Predictable Board Game - A possible New Problem

 2 years ago
source link: https://www.codeabbey.com/index/forum_topic/5e60cf20d09b7109561b38fd3737f01e
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.

Predictable Board Game - A possible New Problem

Back to General discussions forum

CSFPython     2022-05-24 08:37:15

The following is a draft problem description:

Two friends invented a new board game. They used a board which was a large grid of squares. The bottom left square on the board is the origin of the grid, having coordinates (0,0). Other squares on the board can be described by the usual (x,y) coordinates. The values of x and y can be 0 or any positive integer up to a maximum of 100,000.

A disc is placed on one square of the board and the friends take it in turns to move the disc. The first player to move the disc to the origin wins the game. The friends decided to allow three different kinds of move.

A move to the left decreases the x value of the position of the disc. Any size move is allowed provided that the disc remains on the board.

A move downwards decreases the y value of the position of the disc. Any size move is allowed provided that the disc remains on the board.

A diagonal move decreases both the x and y values of the position of the disc BY THE SAME AMOUNT. Any size move is allowed provided that the disc remains on the board.

Note that it is not possible for either the x or the y value of the disc position to increase.

For example, from the square (3,4) it is possible to move directly to any of the squares (2,4), (1,4), (0,4), (3,3), (3,2), (3,1), (3,0), (2,3), (1,2) and (0,1).

To make the game fair one player would place the disc on the board and the other player would get the first move. The two friends were pleased with their invention and enjoyed playing many games until they began to suspect that the game outcome is determined by the starting position of the disc; assuming optimal play.

We can describe some squares as winning squares (W) because the player making the first move is guaranteed to win the game, no matter what sequence of moves is played by their opponent; provided that the first player plays optimally.

Similarly we can describe squares as losing squares (L) because the first player is guaranteed to lose the game, no matter what sequence of moves they play, provided that their opponent plays optimally.

When squares are close to the origin it is easy to classify them. (8,8) is clearly a winning square because we can reach the origin in a single move. (1,2) is a losing square. The only valid moves from this square go to (0,2), (1,1), (1,0) or (0,1). From any of these positions the second player can make a move to the origin and win the game.

As positions get further from the origin it becomes harder to decide whether they are winning or losing positions. That is the object of this puzzle. The first line of the input data will contain a single integer N. N lines will follow. On each line there will be a pair of integers (separated by a space). These are the (x,y) coordinates of the disc position. For each position answer W or L to indicate winning or losing. Give all answers on a single line, separated by single spaces.

Example:

input:
14
1 2
8 8
45 73
57 32
162 100
353 216
645 1039
1262 2043
3062 4955
4303 6961
11181 6914
12537 7748
42312 26150
90853 56153

answer:
L W L W L W W W L W W L L W

report

Recommend

About Joyk


Aggregate valuable and interesting links.
Joyk means Joy of geeK