FastPrepCan You Finish the Teleporter Board?

Can You Finish the Teleporter Board?

Atlassian logoAtlassian● MediumFULLTIMEPHONE SCREEN
Learn

Problem statement

A board has squares numbered from 0 through end. Starting at start, decide whether some sequence of die rolls can reach the last square in any number of turns.

teleporters contains strings of the form source,destination. The die has die sides.

  • A roll chooses any integer from 1 through die and moves forward by that amount. If the move would pass end, it lands on end.
  • After landing on a teleporter source, move to its destination exactly once during that turn. Do not chain another teleporter at the destination.
  • The initial square does not automatically trigger a teleporter. If start == end, the board is already finished.
  • For this exercise, assume every teleporter is valid, source squares are unique, and the last square is not a teleporter source.

Return true if the last square is reachable and false otherwise.

Function

finishable(teleporters: String[], die: int, start: int, end: int) → boolean

Examples

Example 1

teleporters = ["10,8","11,5","12,7","13,9"]die = 4start = 0end = 20return = false

Every reachable square remains unable to reach the last square.

Example 2

teleporters = ["10,8","11,5","12,7","13,9","2,15"]die = 4start = 0end = 20return = true

A sequence of legal rolls reaches the last square.

Example 3

teleporters = ["10,8","11,5","12,7","13,9","2,15"]die = 4start = 9end = 20return = false

Every reachable square remains unable to reach the last square.

Example 4

teleporters = ["10,8","11,5","12,1","13,9","2,15"]die = 4start = 9end = 20return = true

A sequence of legal rolls reaches the last square.

Example 5

teleporters = ["2,4","9,8","11,7","12,6","18,14","19,16","20,9","21,14","22,6","23,26","25,10","28,19","29,27","31,29","38,33","39,17","41,30","42,28","45,44","46,36"]die = 4start = 0end = 50return = false

Every reachable square remains unable to reach the last square.

Example 6

teleporters = ["2,4","9,8","11,7","12,6","18,14","19,16","20,9","21,14","22,6","23,26","25,10","28,19","29,27","31,29","38,33","39,17","41,30","42,28","45,44","46,36"]die = 6start = 0end = 50return = true

A sequence of legal rolls reaches the last square.

Example 7

teleporters = ["4,21","11,18","13,17","16,17","18,21","22,11","26,25","27,9","31,38","32,43","34,19","35,19","36,39","38,25","41,31"]die = 4start = 0end = 50return = true

A sequence of legal rolls reaches the last square.

Example 8

teleporters = ["4,21","11,18","13,17","16,17","18,21","22,11","26,25","27,9","31,38","32,43","34,19","35,19","36,39","38,25","41,31"]die = 2start = 0end = 50return = false

Every reachable square remains unable to reach the last square.

Constraints

  • For this exercise, assume 1 <= end <= 1000 and 0 <= start <= end.
  • 1 <= die <= end + 1.
  • 0 <= teleporters.length <= end.
  • Each teleporter source is in [0,end-1] and destination is in [0,end].
  • Teleporter strings contain two decimal integers separated by one comma, with no spaces.

More Atlassian problems

See Atlassian hiring insights
public boolean finishable(String[] teleporters, int die, int start, int end) {
    // Write your code here.
    return false;
}
teleporters["10,8","11,5","12,7","13,9"]
die4
start0
end20
expectedfalse
Checking account…