Skip to content

Instantly share code, notes, and snippets.

@prianichnikov
Created November 8, 2023 15:03
Show Gist options
  • Save prianichnikov/ab489a01b1096b355ca23a097a14b9af to your computer and use it in GitHub Desktop.
Save prianichnikov/ab489a01b1096b355ca23a097a14b9af to your computer and use it in GitHub Desktop.
Thrilling Teleporters game
/*
We are developing a new board game, Thrilling Teleporters.
The board consists of consecutive squares from 0 to last_square, some of the spaces also contain Teleporters, which are given as comma delimited strings "from,to".
The game is played as follows:
1. Each turn, the player rolls a die numbered from 1 to die_sides.
2. The player moves forward the rolled number of squares.
3. The player stops at last_square if they reach it.
4. If the player finishes on a square with a teleporter, they are moved to where the teleporter points.
Note: Only one teleporter is followed per turn.
A sample board with last_square 20 the following teleporters might look like this conceptually.
teleporters1 = ["3,1", "4,2", "5,10"]
die_sides = 6
+-----+
v |
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
^ | | ^
+-----+ +---------------+
order -> 1, 2, 1, 2,10, 6 -> 1,2,10,6
Write a function that returns a collection of the possible squares a player can move to in a single turn, given the following inputs:
- A collection of teleporter strings
- The number of sides on the die
- The square the player starts on
- The last square on the board
Example:
With a 6-sided die, starting at square 0 with a board ending at square 20 (as pictured above)
Rolling a 1, 2 or 6 have no teleporters so they end at that square.
Rolling a 3 goes to 1, rolling a 4 goes to 2, rolling a 5 goes to 10.
The possible outcomes are, in order of die roll, are [1, 2, 1, 2, 10, 6].
If we remove the duplicates, the answer is [1, 2, 10, 6]
destinations(teleporters1, 6, 0, 20) => [1, 2, 10, 6]
Additional Inputs:
teleporters2 = ["5,10", "6,22", "39,40", "40,49", "47,29"]
teleporters3 = ["6,18", "36,26", "41,21", "49,55", "54,52",
"71,58", "74,77", "78,76", "80,73", "92,85"]
teleporters4 = ["97,93", "99,81", "36,33", "92,59", "17,3",
"82,75", "4,1", "84,79", "54,4", "88,53",
"91,37", "60,57", "61,7", "62,51", "31,19"]
teleporters5 = ["3,8", "8,9", "9,3"]
Complexity Variable:
B = size of the board
Note: The number of teleporters, T, and the size of the die, D, are bounded by B.
All Test Cases:
(output can be in any order)
die start last
sides, pos, square
destinations(teleporters1, 6, 0, 20) => [1, 2, 10, 6]
destinations(teleporters2, 6, 46, 100) => [48, 49, 50, 51, 52, 29]
destinations(teleporters2, 10, 0, 50) => [1, 2, 3, 4, 7, 8, 9, 10, 22]
destinations(teleporters3, 10, 95, 100) => [96, 97, 98, 99, 100]
destinations(teleporters3, 10, 70, 100) => [72, 73, 75, 76, 77, 79, 58]
destinations(teleporters4, 6, 0, 100) => [1, 2, 3, 5, 6]
destinations(teleporters5, 6, 0, 20) => [1, 2, 4, 5, 6, 8]
*/
import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;
public class Solution {
public static void main(String[] argv) {
String[] teleporters1 = {"3,1", "4,2", "5,10"};
String[] teleporters2 = {"5,10", "6,22", "39,40", "40,49", "47,29"};
String[] teleporters3 = {"6,18", "36,26", "41,21", "49,55", "54,52",
"71,58", "74,77", "78,76", "80,73", "92,85"};
String[] teleporters4 = {"97,93", "99,81", "36,33", "92,59", "17,3",
"82,75", "4,1", "84,79", "54,4", "88,53",
"91,37", "60,57", "61,7", "62,51", "31,19"};
String[] teleporters5 = {"3,8", "8,9", "9,3"};
System.out.println(destinations(teleporters1, 6, 0, 20));
System.out.println(destinations(teleporters2, 6, 46, 100));
System.out.println(destinations(teleporters2, 10, 0, 50));
System.out.println(destinations(teleporters3, 10, 95, 100));
System.out.println(destinations(teleporters3, 10, 70, 100));
System.out.println(destinations(teleporters4, 6, 0, 100));
System.out.println(destinations(teleporters5, 6, 0, 20));
}
static Set<Integer> destinations(String[] teleports, int dieSides, int start, int end) {
Map<Integer, Integer> mapping = new HashMap<>();
for (String teleport : teleports) {
String[] pair = teleport.split(",");
mapping.put(Integer.valueOf(pair[0]), Integer.valueOf(pair[1]));
}
Set<Integer> result = new HashSet<>();
for (int idx = 1; idx <= dieSides; idx++) {
int current = start + idx;
if (current > end) break;
result.add(mapping.getOrDefault(current, current));
}
return result;
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment