Options
Category:

12 results found:

### Jump Point Search - Preprocessing   PUZZLE_SOLO by aCat

view contribution on CodinGame
This exercise requires implementing the preprocessing phase of the improved Jump Point Search algorithm, based on Steve Rabin, Fernando Silva. "An Extreme A* Speed Optimization for Static Uniform Cost Grids", Game AI Pro 2: Collected Wisdom of Game AI Professionals, pp. 131-143, 2015.

The second part of this exercise, focusing on the runtime phase, is available here.

# The Goal

For a given map, the goal is to compute the table with the correct wall / jump point distances, according to the algorithm from the article.

# Rules

Jump Point Search (JPS) is an A* optimization dedicated to uniform-cost grid maps. Its two main improvements are using cardinal path ordering - responsible for pruning redundant optimal paths of the same cost; and jump points - special direction-changing nodes placed in the open list to reduce its size. JPS+ is an enhanced version of JPS, introducing static map analysis to further improve search speed.

The goal of this series of puzzles is to implement JPS+ according to the description from Steve Rabin, Fernando Silva. "An Extreme A* Speed Optimization for Static Uniform Cost Grids", Game AI Pro 2: Collected Wisdom of Game AI Professionals, pp. 131-143, 2015.

Here, your task is to implement the preprocessing phase. For a given rectangle map containing open tiles and walls, you have to compute distances to the closest wall / jump point for every open tile in each of the octile directions.

Detailed rules
• Given a grid of the size width×height, with 0 0 being the upper left corner in column row notation.
• The grid contains only open (passable) tiles, encoded as ., and wall tiles (impassable), encoded as #.
• There are eight possible directions of movement: N NE E SE S SW W NW, where N means "up", and E "right".
• Moving diagonally is possible only when tiles of both related cardinal directions are passable.
For example, going NE requires both N and E neighboring tiles to be open.
• The JPS+ preprocessing procedure should work as described in the section 14.6 of the cited publication.
• For each of the open tiles, your goal is to send one line, containing computed distances to the closest wall / jump point in each of the eight directions.
• Each line should be formatted as column row N NE E SE S SW W NW, where column row contains the tile coordinates, and the remaining numbers are distances in the corresponding directions.
For example, 2 0 3 -2 1 4 2 -1 -1 4 means that for the tile of column 2 and row 0 going north there is a jump point 3 tiles away, going northeast there is a wall 2 tiles away, etc.
• Ordering of the lines is irrelevant as long as all open nodes are assigned all their corresponding distance values.
Victory Conditions
• All given distance values are correct.
Loss Conditions
• At least one of the given distance values is incorrect.
• Given answer is not properly formatted.
• Response time exceeds the time limit.

# Game Input

Initial input

First line: two space-separated integers, width height, for the size of the map, 0 0 being the upper left corner.

Following height lines: a string of length width, containing a row of the map (top to bottom). Impassable wall tiles are encoded as #, and passable terrain is encoded as ..

Output
One line for each empty tile of the map containing space-separated integer values column row N NE E SE S SW W NW, where column row indicates the position of the tile, and the remaining eight values are distances in corresponding directions to the closest jump point (positive number) or wall (otherwise). The ordering of the tiles is arbitrary.
Constraints
3 ≤ width ≤ 20
3 ≤ height ≤ 20
Response time ≤ 1s

### Jump Point Search - Runtime   PUZZLE_SOLO by aCat

view contribution on CodinGame
This exercise requires implementing the runtime phase of the improved Jump Point Search algorithm, based on Steve Rabin, Fernando Silva. "An Extreme A* Speed Optimization for Static Uniform Cost Grids", Game AI Pro 2: Collected Wisdom of Game AI Professionals, pp. 131-143, 2015.

The first part of this exercise, focusing on the preprocessing phase, is available here.

# The Goal

For a given map, the goal is to compute the optimal path given the table with the precomputed jump point distances, according to the algorithm from the article.

# Rules

Jump Point Search (JPS) is an A* optimization dedicated to uniform-cost grid maps. Its two main improvements are using cardinal path ordering - responsible for pruning redundant optimal paths of the same cost; and jump points - special direction-changing nodes placed in the open list to reduce its size. JPS+ is an enhanced version of JPS, introducing static map analysis to further improve search speed.

The goal of this series of puzzles is to implement JPS+ according to the description from Steve Rabin, Fernando Silva. "An Extreme A* Speed Optimization for Static Uniform Cost Grids", Game AI Pro 2: Collected Wisdom of Game AI Professionals, pp. 131-143, 2015.

Here, your task is to implement the runtime phase. For a given rectangle map containing open tiles and walls, start and goal tiles, and precomputed distances to the closest wall / jump point for every open tile in each of the octile directions, you have to simulate the pathfinding procedure.

Detailed rules
• Given a grid of the size width×height, with 0 0 being the upper left corner in column row notation.
• The grid contains only open (passable) tiles and wall tiles (impassable).
• There are eight possible directions of movement: N NE E SE S SW W NW, where N means "up", and E "right".
• Moving diagonally is possible only when tiles of both related cardinal directions are passable.
For example, going NE requires both N and E neighboring tiles to be open.
• The result of the preprocessing phase is encoded as a set of passable tiles, each formatted as column row N NE E SE S SW W NW, where column row contain the tile coordinates, and the remaining numbers are distances in the corresponding directions.
For example, 2 0 3 -2 1 4 2 -1 -1 4 means that for the tile of column 2 and row 0 going north there is a jump point 3 tiles away, going northeast there is a wall 2 tiles away, etc.
• The JPS+ runtime procedure should work as described in the section 14.7 of the cited publication.
• You need to implement the open list with a priority queue.
• The heuristic function in use for the A* part shall be the octile distance:
For two points (x1,y1) and (x2,y2), the octile distance is given by dx + dy + (√2 - 2) . min(dx,dy) where dx = |x2-x1| and dy = |y2-y1|.
• Each line should be formatted as nodeColumn nodeRow parentColumn parentRow givenCost, where nodeColumn nodeRow contains the coordinates of the current node, parentColumn parentRow contain the coordinates of the node's parent, and givenCost is the cost of traversing from the start to the node.
• When the algorithm finds that path does not exist (open list is empty), you should send NO PATH.
Victory Conditions
• All given nodes are correct.
• If path does not exist, it is detected in the right time.
Loss Conditions
• Incorrect node information is sent.
• No information about nonexisting path is sent.
• Given answer is not properly formatted.
• Response time exceeds the time limit.

# Game Input

Initial input

First line: two space-separated integers, width height, for the size of the map, 0 0 being the upper left corner.

Second line: four space-separated integers, startColumn startRow goalColumn goalRow, with the coordinates of the start tile and goal tile accordingly.

Third line: an integer open, the number of open tiles on the map.

Following open lines: one line for each empty tile of the map containing space-separated integer values column row N NE E SE S SW W NW, where column row indicates the position of the tile, and the remaining eight values are distances in corresponding directions to the closest jump point (positive number) or wall (otherwise). The ordering of the tiles is arbitrary.

Output for the first turn
Initial node representing the start tile: a single line containing startColumn startRow -1 -1 0.00.
Output for the following turns
Information about the node popped from the open list containing nodeColumn nodeRow parentColumn parentRow givenCost, where nodeColumn nodeRow contain the coordinates of the current node, parentColumn parentRow contain the coordinates of the node's parent, and givenCost is the cost of traversing from the start to the node.
Information that the path does not exist, the string NO PATH. It has to be sent on the turn that has an empty open list.
Constraints
3 ≤ width ≤ 20
3 ≤ height ≤ 20
Response time for first turn ≤ 1s
Response time for one turn ≤ 50ms

### SameGame   PUZZLE_OPTI by aCat

view contribution on CodinGame
This is a port of the tile-matching puzzle SameGame. The rules are the same as used for benchmarks in AI publications. Human-playable version is available here.

# The Goal

The goal of the game is to maximize your score, which can be achieved by removing as large as possible regions of connected cells of the same color.

# Rules

SameGame is a puzzle composed of a rectangular grid containing cells of different colors. A move removes connected cells of the same color. The cells of other colors fall to fill the void created by a move down, and when a column is empty the columns on the right are moved to the left. At least two cells have to be removed for a move to be legal. The score of a move is the square of the number of removed cells minus two. A bonus of one thousand is credited for completely clearing the board.

Detailed rules
• Game board has 15 rows and 15 columns, with 0 0 (column row) being the bottom left corner and 14 14 the upper right corner.
• An action consist of choosing a tile on the bord, giving its coordinates (also using column row notation).
• An action is legal if the pointed cell has at least one neighbour (in cardinal direction) of the same color.
• There are five colors, encoded as integers: 0, 1, 2, 3, 4, and the empty cells are encoded as -1.
• A legal action removes the entire region of the same color connected with the chosen tile.
• In every column, all blocks that were above removed cells fall down, so that there is no free space between them and the row 0.
• Then, for every empty column, all columns that are on the right are moved maximally to the left, so that the row 0 has no gaps.
• Choosing illegal action i.e. pointing out an empty cell or a region of size 1 ends the game with an error.
• The game ends naturally when there are no legal actions, i.e. the tile 0 0 is empty or all remaining regions have size 1.
• The score of the game is a cumulative score of each action.
• The score of an action removing a region of size n is (n-2)2.
• When the board is cleared (tile 0 0 is empty), the score is additionally increased by 1000.

Source code
You can find the source code of the contribution at:

# Game Input

Input for one game turn

First 15 lines: rows of the board, top (row 14) to bottom (row 0).

Each line: a single row consisting of 15 space-separated integers representing colors of each cell. Possible color values are: 0, 1, 2, 3, 4 and empty cell is -1.

Output for one game turn
A single line containing an action: two space-separated integers column row optionally followed by any text printed on-screen as a debug message.

Example: 0 1 this is optional\\nmessage
Constraints
Response time for first turn ≤ 20s
Response time for one turn ≤ 50ms

### Monte Carlo Tree Search exercise   PUZZLE_INOUT by aCat

view contribution on CodinGame

## Goal

Difficulty: Medium
Topic: Monte Carlo Tree Search (MCTS), Upper Confidence Bound 1 applied to trees (UCT), Simulations

Assume we are dealing with (nondeterministic) one-player game. To find an optimal sequence of movements we could use Monte Carlo Tree Search algorithm (https://en.wikipedia.org/wiki/Monte_Carlo_tree_search).

Thus, we perform a number of so-called playouts, and gradually build an MCTS tree that will help us choosing statistically best choices for each turn of the game. A playout is a sequence of moves reaching the game tree leaf, so it has assigned a true score. It consists of two parts: the beginning, which is selected by the algorithm using the UCT formula; and the remaining part which is usually a random sequence of movements.

In this puzzle, we are given a list of playouts (encoded as words, where each letter is a single move) with assigned scores, that should be used to build an MCTS tree. After building a tree, the task is to return the sequence of moves, reaching the MCTS tree leaf, that will be chosen using UCT policy given exploration/exploitation constant C.

For given node N visited N.v times, according to the UCB1 formula we should choose a child M that maximizes the value given by: M.s/M.v + C*sqrt(ln(N.v)/M.v), where M.v is number of visits in node M and M.s is sum of scores obtained for this node (so the first component of the sum is average score for node M).

Final remarks:
- Note that this puzzle differs form the real-life-scenario where the playouts are not given, but they are also computed using UCT+random policies.
- In standard implementations you are forced to choose an unexplored move if such exists. Here we assume that after reading the playout data we do not have such moves in the non-leaf nodes of the MCTS tree.
- A tie-breaking rules when comparing UCT values is the ordering on letters (i.e. smaller letter should be chosen).

Example explanation:
- Reading baa 30 will create child node labeled b with avg. score 30 and one visit. The MCTS tree root will have the same statistics. Note that we are adding only one new node at a time.
- Reading ab 20 will create another child node for the root, updating its statistics.
- Finally, reading bbb 4 will create a new node on a path bb from the root, updating all statistics on a way to the root, so the root will have 3 visits, and b node 2 visits.
- Choosing move from the root based on the UCB1 formula will favor move a (average score 20), instead of move b (average score 17). This is because the small value of constant C, makes the exploration part of the equation not significant.
- As there are no further nodes in MCTS tree along that paths, the 1-move sequence a is the answer.
Input
Line 1: 2 space-separated values:
an integer N - the number of performed playouts
a real number C - the constant C (the exploration parameter)

Next N lines: Sequence of movements performed in this playout, followed by a space, followed by the playout's result
Output
Sequence of movements that will be chosen in the MCTS tree using UCB1 selection.
Constraints
0 < N < 500
0 < playout length < 50
1 < branching factor < 10
-100.1 < score (playout's result) < 100.1
Example
Input
```3 0.1
baa 30
ab 20
bbb 4```
Output
`a`

### Minimax exercise   PUZZLE_INOUT by aCat

view contribution on CodinGame

## Goal

Difficulty: Medium
Topic: Minimax algorithm, Alpha–beta pruning, Zero-sum games, Negamax

We are given a 2-player, zero-sum game, where players alternate turns. The game always lasts D turns, and during its move, every player has to choose from B choices. Thus, D is the game tree depth, B its branching factor, and depending on players' choices, the game has B^D possible outcomes.

Assuming the game tree is small enough, we can check all outcomes and solve the game (i.e. compute the best strategy for every player) using the Minimax algorithm ( https://en.wikipedia.org/wiki/Minimax ).

To make our algorithm more efficient, we can skip some computations using the alpha-beta prunning technique ( https://en.wikipedia.org/wiki/Alpha-beta_pruning ).

Your task is to compute the minimum gain for the first player using Minimax with alpha-beta cutoffs. Moves should be examined in left-to-right order, as provided in the input.
Input
Line 1: 2 space-separated integers:
D - depth of the game tree (assuming root is depth 0)
B - the branching factor

Line 2: B^D space-separated integers - the leafs of the game tree containing scores of the first (max) player.
Output
Two space-separated numbers:
- the best score that the root player is guaranteed to obtain
- the number of visited tree nodes
Constraints
0 < D < 15
0 < B < 15
-1000 < game score < 1000
number of leafs < 3500
Example
Input
```1 4
2 -1 3 0```
Output
`3 5`

### A-star exercise   PUZZLE_INOUT by aCat

view contribution on CodinGame

## Goal

You are given an undirected graph with weighted edges, a start and a goal node, and for each node the heuristic value, which is the estimated distance to the end. Your task is to trace a canonical A* execution (see https://en.wikipedia.org/wiki/A*_search_algorithm ) by computing a shortest path from the start to the goal.

We recall that the A* algorithm will rely on three values for each node v:
- the g-value, which is the minimum distance from the start to v;
- the h-value, which is an estimation of the minimum distance from v to the goal and is given by the heuristic provided in input;
- the f-value, which is the sum of the g-value and h-value.

There is always a path between the start and the goal. The given heuristic is admissible and consistent, meaning that the A* algorithm will always find a shortest path from the start to the goal.

When some nodes have the same f-value, the one with the smaller identifier is considered first.
Input
Line 1: 4 space-separated integers:
N - the number of nodes in the graph (nodes are identified by integers from 0 to N-1),
E - the number of edges in the graph,
S - the identifier of the start node,
G - the identifier of the goal node

Line 2: N space-separated integers - estimated distances to the goal (heuristics) for each node from 0 to N-1

Next E lines: three space-separated integers X Y C that indicate the edge between nodes X and Y with the cost C. Notice that, since the graph is undirected, there is also an edge from Y to X with the same cost.
Output
A sequence of lines containing information about the node expanded in each step of the algorithm: the node's identifier, followed by a space, followed by its f-value.
Constraints
0 < N < 100
0 < E < 10000
0 < C < 1000
Example
Input
```3 3 0 2
33 11 0
0 1 10
0 2 40
1 2 20```
Output
```0 33
1 21
2 30```

### Parsing context-free grammar   PUZZLE_INOUT by aCat

view contribution on CodinGame

## Goal

Difficulty: Hard
Topic: Context-free grammars, CYK algorithm, dynamic programming

Given the context-free grammar and a set of words, your task is to decide which words belong to the language defined by that grammar.

The grammar is presented in Chomsky normal form, without epsilon-rules. Non-terminal symbols are always uppercase letters, terminal symbols are always lowercase letters.
Input
Line 1: the number N of rules in the grammar
Line 2: the character START indicating the start symbol
Next N lines: rules of the grammar
Next line: the number T of testcases
Next T lines: words to parse
Output
T lines containing true if word can be successfully parsed by the grammar, false otherwise.
Constraints
0 < number of terminal symbols < 25
0 < number of nonterminal symbols < 25
0 < N < 100
0 < T < 100
0 < length of word < 100
Example
Input
```6
S
S -> SS
S -> OT
T -> SC
S -> OC
O -> a
C -> b
10
ab
ba
abba
ababab
aaabbb
abaabb
a
aaabababbb
aababababbb
aaabababbabb```
Output
```true
false
false
true
true
true
false
true
false
true```

### Distinct letters   CLASHOFCODE by aCat

view contribution on CodinGame

# Goal

Given a word W containing only uppercase and lowercase letters, return the number of distinct letters (regardless of a case) in W.
Input
A word W containing only uppercase and lowercase letters.
Output
A single line containing the integer N which is the number of distinct letters appearing in W.
Constraints
1 ≤ length of W ≤ 100
Example
Input
`abc`
Output
`3`

### The longest sequence of repeated digits   CLASHOFCODE by aCat

view contribution on CodinGame

# Goal

Given an integer N, return the length of the longest sequence containing the same digit.
Input
An integer N.
Output
A single line containing the integer K which is the length of the longest sequence of repeated digits.
Constraints
2 ≤ N ≤ 100000000
Example
Input
`111`
Output
`3`

### The king of the hill   CLASHOFCODE by aCat

view contribution on CodinGame

# Goal

For a given matrix of integers find the highest value such that all its adjacent (NSWE) values are strictly lower. Values on the edges of matrix are never a valid answer (they do not have all four neighbors required).
Input
Line 1: Integers R C being the numbers of, accordingly, rows and columns of the matrix.
Next R lines: C space separated integers.
Output
One integer K, which is the highest matrix value such that its four adjacent neighbors are strictly lower, or -666 if such value does not exist.
Constraints
3 ≤ R, C ≤ 100
-100 ≤ K ≤ 100
Example
Input
```3 3
1 2 2
1 3 1
2 2 1```
Output
`3`

### Cooperative Mate with Rook   PUZZLE_SOLO by aCat

view contribution on CodinGame
Cooperative mate is a family of Chess game puzzles where both sides cooperate towards a common goal. Here, we consider endgames with only black king, white king, and white rook, aiming to checkmating the black king. Your task is to provide a shortest sequence of moves leading to such mate.

# The Goal

For a given state of the game, the goal is to compute a sequence of chess piece moves leading to the fastest checkmate.

# Rules

The game state is described by the player-to-move and position of each piece: white king, white rook, and black king, formatted as white d5 g7 a6.

The goal of this puzzle is to provide a sequence of moves leading to a cooperative checkmate, according to the Chess rules. The sequence should be formatted as d5c5 a6a5 g7a7.

Victory Conditions
• Given sequence of moves leads to the fastest checkmate possible in the current board position.
Loss Conditions
• Given sequence of moves does not lead to a checkmate within a turn limit.
• Given sequence of moves contains illegal move.
• Given answer is not properly formatted.
• Response time exceeds the time limit.

# Detailed rules

• Given board state is always a valid Chess game position.
• You can hide showing legal moves in the settings panel ( )..

# Related puzzles

• Adversarial variant of single rook endgames, requiring you to play as white against the black player, is available here.
• To play full version of Chess as a bot programming game you can go here.

# Game Input

Initial input

A single line containing space-separated strings, movingPlayer being either black or white, and whiteKing whiteRook blackKing positions in column-row format, e.g. a1.

Output
A single line containing a sequence of space-separated moves (each move in a1h8 format).
Constraints
1 ≤ solution length ≤ 12
Response time ≤ 20s

### Adversarial Mate with Rook   PUZZLE_SOLO by aCat

view contribution on CodinGame
Here, we consider Chess endgames with only black king, white king, and white rook. Your goal, as the white player, is to checkmate the black king as quickly as possible.

# The Goal

For a given initial state of the game, your goal is to compute moves of the white player leading to the fastest checkmate. You need to consider an opponent, who may try to prolong play and achieve a draw when possible.

# Rules

The initial game state is described by the position of each piece: white king, white rook, and black king, formatted as e3 h5 e1. The white player is always the one who moves first.

The goal of this puzzle is to, in each turn, provide a move leading to quickest checkmate, according to the Chess rules. Each move should be formatted as h5h1.

After each white move, black's reply will be given in the same format.

Victory Conditions
• Given moves leads to the fastest checkmate possible in the current board position.
Loss Conditions
• Given sequence of moves does not lead to a fastest checkmate.
• Given move is illegal.
• Given answer is not properly formatted.
• Response time exceeds the time limit.

# Detailed rules

• If the black player makes a suboptimal move and a quicker checkmate becomes possible, you should find the faster checkmate.
• Given board state is always a valid Chess game position.
• You can hide showing legal moves in the settings panel ( )..

# Related puzzles

• Cooperative variant of single rook endgames, requiring you to reach the fastest checkmate by controlling both players, is available here.
• To play full version of Chess as a bot programming game you can go here.

# Game Input

Initial input

A single line containing space-separated strings, whiteKing whiteRook blackKing positions in column-row format, e.g. a1.

Input for the following turns

A single line containing a string opponentMove wih the opponent move encoded as from-to in column-row format, e.g. a1h8.

Output each turn
A single line containing a moves in a1h8 format.
Constraints
1 ≤ depth of the quickest checkmate solution ≤ 13
Response time for first turn ≤ 25s
Response time for the following turns ≤ 200ms