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

AVAILABLE LESSONS:

Lesson 1

Iterations

Lesson 2

Arrays

Lesson 3

Time Complexity

Lesson 4

Counting Elements

Lesson 5

Prefix Sums

Lesson 6

Sorting

Lesson 7

Stacks and Queues

Lesson 8

Leader

Lesson 9

Maximum slice problem

Lesson 10

Prime and composite numbers

Lesson 11

Sieve of Eratosthenes

Lesson 12

Euclidean algorithm

Lesson 13

Fibonacci numbers

Lesson 14

Binary search algorithm

Lesson 15

Caterpillar method

Lesson 16

Greedy algorithms

Lesson 17

Dynamic programming

Lesson 90

Tasks from Indeed Prime 2015 challenge

Lesson 91

Tasks from Indeed Prime 2016 challenge

Lesson 92

Tasks from Indeed Prime 2016 College Coders challenge

Lesson 99

Future training

ambitious

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

Programming language:
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:

Assume that:

- 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.

Complexity:

- expected worst-case time complexity is O(N);
- expected worst-case space complexity is O(N).

Copyright 2009–2018 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:

Assume that:

- 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.

Complexity:

- expected worst-case time complexity is O(N);
- expected worst-case space complexity is O(N).

Copyright 2009–2018 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:

Assume that:

- 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.

Complexity:

- expected worst-case time complexity is O(N);
- expected worst-case space complexity is O(N).

Copyright 2009–2018 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:

Assume that:

- 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.

Complexity:

- expected worst-case time complexity is O(N);
- expected worst-case space complexity is O(N).

^{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:

Assume that:

- 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.

Complexity:

- expected worst-case time complexity is O(N);
- expected worst-case space complexity is O(N).

^{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:

Assume that:

- 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.

Complexity:

- expected worst-case time complexity is O(N);
- expected worst-case space complexity is O(N).

^{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:

Assume that:

- 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.

Complexity:

- expected worst-case time complexity is O(N);
- expected worst-case space complexity is O(N).

^{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:

Assume that:

- 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.

Complexity:

- expected worst-case time complexity is O(N);
- expected worst-case space complexity is O(N).

^{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:

Assume that:

- 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.

Complexity:

- expected worst-case time complexity is O(N);
- expected worst-case space complexity is O(N).

^{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:

Assume that:

- 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.

Complexity:

- expected worst-case time complexity is O(N);
- expected worst-case space complexity is O(N).

^{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:

Assume that:

- 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.

Complexity:

- expected worst-case time complexity is O(N);
- expected worst-case space complexity is O(N).

^{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:

Assume that:

- 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.

Complexity:

- expected worst-case time complexity is O(N);
- expected worst-case space complexity is O(N).

^{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:

Assume that:

- 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.

Complexity:

- expected worst-case time complexity is O(N);
- expected worst-case space complexity is O(N).

^{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:

Assume that:

- 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.

Complexity:

- expected worst-case time complexity is O(N);
- expected worst-case space complexity is O(N).

^{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:

Assume that:

- 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.

Complexity:

- expected worst-case time complexity is O(N);
- expected worst-case space complexity is O(N).

^{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:

Assume that:

- 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.

Complexity:

- expected worst-case time complexity is O(N);
- expected worst-case space complexity is O(N).

^{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:

Assume that:

- 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.

Complexity:

- expected worst-case time complexity is O(N);
- expected worst-case space complexity is O(N).

Information about upcoming challenges, solutions and lessons directly in your inbox.

© 2009–2018 Codility Ltd., registered in England and Wales (No. 7048726). VAT ID GB981191408. Registered office: 107 Cheapside, London EC2V 6DN