Your browser (Unknown 0) is no longer supported. Some parts of the website may not work correctly. Please update your browser.

AVAILABLE EXERCISES:

Exercise 9

Bitwise operations (bit-ops)

Exercise 8

Frontend

Exercise 7

Data Structures

Exercise 6

SQL

Exercise 5

Coding skills

Exercise 4

Algorithmic skills

Exercise 3

2017 Contest

Exercise 2

2016 Contest

Exercise 1

2015 Contest

Find the shortest path between two fields in a Hilbert maze.

Spoken language:

A halfling is searching for treasure hidden in a maze in the dwarfs' mine. He has a map of the maze and would like to find the shortest path to the treasure.

The maze has a specific shape. It is placed on a square grid with M^{2} cells, where M = 2^{N+1}+1 for some given size N. Each cell has coordinates (x, y), where 0 ≤ x, y < M, and can either be empty or contain a rock.

The mazes of sizes N = 1 and N = 2 are presented in the pictures below:

A maze of size N is constructed recursively from the layout of the maze of size N−1 (like the Hilbert curve). It contains four mazes of size N−1, each maze in one quarter. The maze in the bottom-left quarter is rotated by 90 degrees clockwise and the maze in the bottom-right quarter is rotated by 90 degrees counter-clockwise. The mazes in the top quarters are not rotated. There are three additional rocks (squares marked in green in the picture below) in the areas where the mazes intersect. The construction of the maze of size N = 3 is shown below:

The halfling would like to reach the treasure in the smallest number of steps possible. At each step, he can move to any one of the four adjacent cells (north, south, west, east) that does not contain a rock and is not outside of the grid.

For example, given N = 1, the halfling needs 8 steps to move from cell (2, 1) to cell (3, 4):

Write a function:

int solution(int N, int A, int B, int C, int D);

that, given the size of the maze N, coordinates of the halfling (A, B) and coordinates of the treasure (C, D), returns the minimum number of steps required for the halfling to reach the treasure.

Given N = 1, A = 2, B = 1, C = 3 and D = 4 the function should return 8, as shown above.

Given N = 2, A = 2, B = 5, C = 6 and D = 6 the function should return 7:

Given N = 3, A = 6, B = 6, C = 10 and D = 13 the function should return 39:

Write an ** efficient** algorithm for the following assumptions:

- N is an integer within the range [1..25];
- A, B, C, D are integers within the range [0..2
^{N+1}];- cells (A, B) and (C, D) do not contain rocks;
- the result will be an integer smaller than 2,147,483,647.

Copyright 2009–2021 by Codility Limited. All Rights Reserved. Unauthorized copying, publication or disclosure prohibited.

A halfling is searching for treasure hidden in a maze in the dwarfs' mine. He has a map of the maze and would like to find the shortest path to the treasure.

The maze has a specific shape. It is placed on a square grid with M^{2} cells, where M = 2^{N+1}+1 for some given size N. Each cell has coordinates (x, y), where 0 ≤ x, y < M, and can either be empty or contain a rock.

The mazes of sizes N = 1 and N = 2 are presented in the pictures below:

A maze of size N is constructed recursively from the layout of the maze of size N−1 (like the Hilbert curve). It contains four mazes of size N−1, each maze in one quarter. The maze in the bottom-left quarter is rotated by 90 degrees clockwise and the maze in the bottom-right quarter is rotated by 90 degrees counter-clockwise. The mazes in the top quarters are not rotated. There are three additional rocks (squares marked in green in the picture below) in the areas where the mazes intersect. The construction of the maze of size N = 3 is shown below:

The halfling would like to reach the treasure in the smallest number of steps possible. At each step, he can move to any one of the four adjacent cells (north, south, west, east) that does not contain a rock and is not outside of the grid.

For example, given N = 1, the halfling needs 8 steps to move from cell (2, 1) to cell (3, 4):

Write a function:

int solution(int N, int A, int B, int C, int D);

that, given the size of the maze N, coordinates of the halfling (A, B) and coordinates of the treasure (C, D), returns the minimum number of steps required for the halfling to reach the treasure.

Given N = 1, A = 2, B = 1, C = 3 and D = 4 the function should return 8, as shown above.

Given N = 2, A = 2, B = 5, C = 6 and D = 6 the function should return 7:

Given N = 3, A = 6, B = 6, C = 10 and D = 13 the function should return 39:

Write an ** efficient** algorithm for the following assumptions:

- N is an integer within the range [1..25];
- A, B, C, D are integers within the range [0..2
^{N+1}];- cells (A, B) and (C, D) do not contain rocks;
- the result will be an integer smaller than 2,147,483,647.

Copyright 2009–2021 by Codility Limited. All Rights Reserved. Unauthorized copying, publication or disclosure prohibited.

A halfling is searching for treasure hidden in a maze in the dwarfs' mine. He has a map of the maze and would like to find the shortest path to the treasure.

The maze has a specific shape. It is placed on a square grid with M^{2} cells, where M = 2^{N+1}+1 for some given size N. Each cell has coordinates (x, y), where 0 ≤ x, y < M, and can either be empty or contain a rock.

The mazes of sizes N = 1 and N = 2 are presented in the pictures below:

A maze of size N is constructed recursively from the layout of the maze of size N−1 (like the Hilbert curve). It contains four mazes of size N−1, each maze in one quarter. The maze in the bottom-left quarter is rotated by 90 degrees clockwise and the maze in the bottom-right quarter is rotated by 90 degrees counter-clockwise. The mazes in the top quarters are not rotated. There are three additional rocks (squares marked in green in the picture below) in the areas where the mazes intersect. The construction of the maze of size N = 3 is shown below:

The halfling would like to reach the treasure in the smallest number of steps possible. At each step, he can move to any one of the four adjacent cells (north, south, west, east) that does not contain a rock and is not outside of the grid.

For example, given N = 1, the halfling needs 8 steps to move from cell (2, 1) to cell (3, 4):

Write a function:

class Solution { public int solution(int N, int A, int B, int C, int D); }

that, given the size of the maze N, coordinates of the halfling (A, B) and coordinates of the treasure (C, D), returns the minimum number of steps required for the halfling to reach the treasure.

Given N = 1, A = 2, B = 1, C = 3 and D = 4 the function should return 8, as shown above.

Given N = 2, A = 2, B = 5, C = 6 and D = 6 the function should return 7:

Given N = 3, A = 6, B = 6, C = 10 and D = 13 the function should return 39:

Write an ** efficient** algorithm for the following assumptions:

- N is an integer within the range [1..25];
- A, B, C, D are integers within the range [0..2
^{N+1}];- cells (A, B) and (C, D) do not contain rocks;
- the result will be an integer smaller than 2,147,483,647.

Copyright 2009–2021 by Codility Limited. All Rights Reserved. Unauthorized copying, publication or disclosure prohibited.

^{2} cells, where M = 2^{N+1}+1 for some given size N. Each cell has coordinates (x, y), where 0 ≤ x, y < M, and can either be empty or contain a rock.

The mazes of sizes N = 1 and N = 2 are presented in the pictures below:

For example, given N = 1, the halfling needs 8 steps to move from cell (2, 1) to cell (3, 4):

Write a function:

func Solution(N int, A int, B int, C int, D int) int

Given N = 1, A = 2, B = 1, C = 3 and D = 4 the function should return 8, as shown above.

Given N = 2, A = 2, B = 5, C = 6 and D = 6 the function should return 7:

Given N = 3, A = 6, B = 6, C = 10 and D = 13 the function should return 39:

Write an ** efficient** algorithm for the following assumptions:

- N is an integer within the range [1..25];
- A, B, C, D are integers within the range [0..2
^{N+1}];- cells (A, B) and (C, D) do not contain rocks;
- the result will be an integer smaller than 2,147,483,647.

^{2} cells, where M = 2^{N+1}+1 for some given size N. Each cell has coordinates (x, y), where 0 ≤ x, y < M, and can either be empty or contain a rock.

The mazes of sizes N = 1 and N = 2 are presented in the pictures below:

For example, given N = 1, the halfling needs 8 steps to move from cell (2, 1) to cell (3, 4):

Write a function:

class Solution { public int solution(int N, int A, int B, int C, int D); }

Given N = 1, A = 2, B = 1, C = 3 and D = 4 the function should return 8, as shown above.

Given N = 2, A = 2, B = 5, C = 6 and D = 6 the function should return 7:

Given N = 3, A = 6, B = 6, C = 10 and D = 13 the function should return 39:

Write an ** efficient** algorithm for the following assumptions:

- N is an integer within the range [1..25];
- A, B, C, D are integers within the range [0..2
^{N+1}];- cells (A, B) and (C, D) do not contain rocks;
- the result will be an integer smaller than 2,147,483,647.

^{2} cells, where M = 2^{N+1}+1 for some given size N. Each cell has coordinates (x, y), where 0 ≤ x, y < M, and can either be empty or contain a rock.

The mazes of sizes N = 1 and N = 2 are presented in the pictures below:

For example, given N = 1, the halfling needs 8 steps to move from cell (2, 1) to cell (3, 4):

Write a function:

class Solution { public int solution(int N, int A, int B, int C, int D); }

Given N = 1, A = 2, B = 1, C = 3 and D = 4 the function should return 8, as shown above.

Given N = 2, A = 2, B = 5, C = 6 and D = 6 the function should return 7:

Given N = 3, A = 6, B = 6, C = 10 and D = 13 the function should return 39:

Write an ** efficient** algorithm for the following assumptions:

- N is an integer within the range [1..25];
- A, B, C, D are integers within the range [0..2
^{N+1}];- cells (A, B) and (C, D) do not contain rocks;
- the result will be an integer smaller than 2,147,483,647.

^{2} cells, where M = 2^{N+1}+1 for some given size N. Each cell has coordinates (x, y), where 0 ≤ x, y < M, and can either be empty or contain a rock.

The mazes of sizes N = 1 and N = 2 are presented in the pictures below:

For example, given N = 1, the halfling needs 8 steps to move from cell (2, 1) to cell (3, 4):

Write a function:

function solution(N, A, B, C, D);

Given N = 1, A = 2, B = 1, C = 3 and D = 4 the function should return 8, as shown above.

Given N = 2, A = 2, B = 5, C = 6 and D = 6 the function should return 7:

Given N = 3, A = 6, B = 6, C = 10 and D = 13 the function should return 39:

Write an ** efficient** algorithm for the following assumptions:

- N is an integer within the range [1..25];
- A, B, C, D are integers within the range [0..2
^{N+1}];- cells (A, B) and (C, D) do not contain rocks;
- the result will be an integer smaller than 2,147,483,647.

^{2} cells, where M = 2^{N+1}+1 for some given size N. Each cell has coordinates (x, y), where 0 ≤ x, y < M, and can either be empty or contain a rock.

The mazes of sizes N = 1 and N = 2 are presented in the pictures below:

For example, given N = 1, the halfling needs 8 steps to move from cell (2, 1) to cell (3, 4):

Write a function:

fun solution(N: Int, A: Int, B: Int, C: Int, D: Int): Int

Given N = 1, A = 2, B = 1, C = 3 and D = 4 the function should return 8, as shown above.

Given N = 2, A = 2, B = 5, C = 6 and D = 6 the function should return 7:

Given N = 3, A = 6, B = 6, C = 10 and D = 13 the function should return 39:

Write an ** efficient** algorithm for the following assumptions:

- N is an integer within the range [1..25];
- A, B, C, D are integers within the range [0..2
^{N+1}];- cells (A, B) and (C, D) do not contain rocks;
- the result will be an integer smaller than 2,147,483,647.

^{2} cells, where M = 2^{N+1}+1 for some given size N. Each cell has coordinates (x, y), where 0 ≤ x, y < M, and can either be empty or contain a rock.

The mazes of sizes N = 1 and N = 2 are presented in the pictures below:

For example, given N = 1, the halfling needs 8 steps to move from cell (2, 1) to cell (3, 4):

Write a function:

function solution(N, A, B, C, D)

Given N = 1, A = 2, B = 1, C = 3 and D = 4 the function should return 8, as shown above.

Given N = 2, A = 2, B = 5, C = 6 and D = 6 the function should return 7:

Given N = 3, A = 6, B = 6, C = 10 and D = 13 the function should return 39:

Write an ** efficient** algorithm for the following assumptions:

- N is an integer within the range [1..25];
- A, B, C, D are integers within the range [0..2
^{N+1}];- cells (A, B) and (C, D) do not contain rocks;
- the result will be an integer smaller than 2,147,483,647.

^{2} cells, where M = 2^{N+1}+1 for some given size N. Each cell has coordinates (x, y), where 0 ≤ x, y < M, and can either be empty or contain a rock.

The mazes of sizes N = 1 and N = 2 are presented in the pictures below:

For example, given N = 1, the halfling needs 8 steps to move from cell (2, 1) to cell (3, 4):

Write a function:

int solution(int N, int A, int B, int C, int D);

Given N = 1, A = 2, B = 1, C = 3 and D = 4 the function should return 8, as shown above.

Given N = 2, A = 2, B = 5, C = 6 and D = 6 the function should return 7:

Given N = 3, A = 6, B = 6, C = 10 and D = 13 the function should return 39:

Write an ** efficient** algorithm for the following assumptions:

- N is an integer within the range [1..25];
- A, B, C, D are integers within the range [0..2
^{N+1}];- cells (A, B) and (C, D) do not contain rocks;
- the result will be an integer smaller than 2,147,483,647.

^{2} cells, where M = 2^{N+1}+1 for some given size N. Each cell has coordinates (x, y), where 0 ≤ x, y < M, and can either be empty or contain a rock.

The mazes of sizes N = 1 and N = 2 are presented in the pictures below:

For example, given N = 1, the halfling needs 8 steps to move from cell (2, 1) to cell (3, 4):

Write a function:

function solution(N: longint; A: longint; B: longint; C: longint; D: longint): longint;

Given N = 1, A = 2, B = 1, C = 3 and D = 4 the function should return 8, as shown above.

Given N = 2, A = 2, B = 5, C = 6 and D = 6 the function should return 7:

Given N = 3, A = 6, B = 6, C = 10 and D = 13 the function should return 39:

Write an ** efficient** algorithm for the following assumptions:

- N is an integer within the range [1..25];
- A, B, C, D are integers within the range [0..2
^{N+1}];- cells (A, B) and (C, D) do not contain rocks;
- the result will be an integer smaller than 2,147,483,647.

^{2} cells, where M = 2^{N+1}+1 for some given size N. Each cell has coordinates (x, y), where 0 ≤ x, y < M, and can either be empty or contain a rock.

The mazes of sizes N = 1 and N = 2 are presented in the pictures below:

For example, given N = 1, the halfling needs 8 steps to move from cell (2, 1) to cell (3, 4):

Write a function:

function solution($N, $A, $B, $C, $D);

Given N = 1, A = 2, B = 1, C = 3 and D = 4 the function should return 8, as shown above.

Given N = 2, A = 2, B = 5, C = 6 and D = 6 the function should return 7:

Given N = 3, A = 6, B = 6, C = 10 and D = 13 the function should return 39:

Write an ** efficient** algorithm for the following assumptions:

- N is an integer within the range [1..25];
- A, B, C, D are integers within the range [0..2
^{N+1}];- cells (A, B) and (C, D) do not contain rocks;
- the result will be an integer smaller than 2,147,483,647.

^{2} cells, where M = 2^{N+1}+1 for some given size N. Each cell has coordinates (x, y), where 0 ≤ x, y < M, and can either be empty or contain a rock.

The mazes of sizes N = 1 and N = 2 are presented in the pictures below:

For example, given N = 1, the halfling needs 8 steps to move from cell (2, 1) to cell (3, 4):

Write a function:

sub solution { my ($N, $A, $B, $C, $D)=@_; ... }

Given N = 1, A = 2, B = 1, C = 3 and D = 4 the function should return 8, as shown above.

Given N = 2, A = 2, B = 5, C = 6 and D = 6 the function should return 7:

Given N = 3, A = 6, B = 6, C = 10 and D = 13 the function should return 39:

Write an ** efficient** algorithm for the following assumptions:

- N is an integer within the range [1..25];
- A, B, C, D are integers within the range [0..2
^{N+1}];- cells (A, B) and (C, D) do not contain rocks;
- the result will be an integer smaller than 2,147,483,647.

^{2} cells, where M = 2^{N+1}+1 for some given size N. Each cell has coordinates (x, y), where 0 ≤ x, y < M, and can either be empty or contain a rock.

The mazes of sizes N = 1 and N = 2 are presented in the pictures below:

For example, given N = 1, the halfling needs 8 steps to move from cell (2, 1) to cell (3, 4):

Write a function:

def solution(N, A, B, C, D)

Given N = 1, A = 2, B = 1, C = 3 and D = 4 the function should return 8, as shown above.

Given N = 2, A = 2, B = 5, C = 6 and D = 6 the function should return 7:

Given N = 3, A = 6, B = 6, C = 10 and D = 13 the function should return 39:

Write an ** efficient** algorithm for the following assumptions:

- N is an integer within the range [1..25];
- A, B, C, D are integers within the range [0..2
^{N+1}];- cells (A, B) and (C, D) do not contain rocks;
- the result will be an integer smaller than 2,147,483,647.

^{2} cells, where M = 2^{N+1}+1 for some given size N. Each cell has coordinates (x, y), where 0 ≤ x, y < M, and can either be empty or contain a rock.

The mazes of sizes N = 1 and N = 2 are presented in the pictures below:

For example, given N = 1, the halfling needs 8 steps to move from cell (2, 1) to cell (3, 4):

Write a function:

def solution(n, a, b, c, d)

Given N = 1, A = 2, B = 1, C = 3 and D = 4 the function should return 8, as shown above.

Given N = 2, A = 2, B = 5, C = 6 and D = 6 the function should return 7:

Given N = 3, A = 6, B = 6, C = 10 and D = 13 the function should return 39:

Write an ** efficient** algorithm for the following assumptions:

- N is an integer within the range [1..25];
- A, B, C, D are integers within the range [0..2
^{N+1}];- cells (A, B) and (C, D) do not contain rocks;
- the result will be an integer smaller than 2,147,483,647.

^{2} cells, where M = 2^{N+1}+1 for some given size N. Each cell has coordinates (x, y), where 0 ≤ x, y < M, and can either be empty or contain a rock.

The mazes of sizes N = 1 and N = 2 are presented in the pictures below:

For example, given N = 1, the halfling needs 8 steps to move from cell (2, 1) to cell (3, 4):

Write a function:

object Solution { def solution(n: Int, a: Int, b: Int, c: Int, d: Int): Int }

Given N = 1, A = 2, B = 1, C = 3 and D = 4 the function should return 8, as shown above.

Given N = 2, A = 2, B = 5, C = 6 and D = 6 the function should return 7:

Given N = 3, A = 6, B = 6, C = 10 and D = 13 the function should return 39:

Write an ** efficient** algorithm for the following assumptions:

- N is an integer within the range [1..25];
- A, B, C, D are integers within the range [0..2
^{N+1}];- cells (A, B) and (C, D) do not contain rocks;
- the result will be an integer smaller than 2,147,483,647.

^{2} cells, where M = 2^{N+1}+1 for some given size N. Each cell has coordinates (x, y), where 0 ≤ x, y < M, and can either be empty or contain a rock.

The mazes of sizes N = 1 and N = 2 are presented in the pictures below:

For example, given N = 1, the halfling needs 8 steps to move from cell (2, 1) to cell (3, 4):

Write a function:

public func solution(_ N : Int, _ A : Int, _ B : Int, _ C : Int, _ D : Int) -> Int

Given N = 1, A = 2, B = 1, C = 3 and D = 4 the function should return 8, as shown above.

Given N = 2, A = 2, B = 5, C = 6 and D = 6 the function should return 7:

Given N = 3, A = 6, B = 6, C = 10 and D = 13 the function should return 39:

Write an ** efficient** algorithm for the following assumptions:

- N is an integer within the range [1..25];
- A, B, C, D are integers within the range [0..2
^{N+1}];- cells (A, B) and (C, D) do not contain rocks;
- the result will be an integer smaller than 2,147,483,647.

^{2} cells, where M = 2^{N+1}+1 for some given size N. Each cell has coordinates (x, y), where 0 ≤ x, y < M, and can either be empty or contain a rock.

The mazes of sizes N = 1 and N = 2 are presented in the pictures below:

For example, given N = 1, the halfling needs 8 steps to move from cell (2, 1) to cell (3, 4):

Write a function:

Private Function solution(N As Integer, A As Integer, B As Integer, C As Integer, D As Integer) As Integer

Given N = 1, A = 2, B = 1, C = 3 and D = 4 the function should return 8, as shown above.

Given N = 2, A = 2, B = 5, C = 6 and D = 6 the function should return 7:

Given N = 3, A = 6, B = 6, C = 10 and D = 13 the function should return 39:

Write an ** efficient** algorithm for the following assumptions:

- N is an integer within the range [1..25];
- A, B, C, D are integers within the range [0..2
^{N+1}];- cells (A, B) and (C, D) do not contain rocks;
- the result will be an integer smaller than 2,147,483,647.