Intro

While digging around on a bug bounty I came across a company’s subdomain that hosts a maze challenge. Probably for vetting interviewees.

Overview

The instructions were pretty simple, and we get three endpoints to work with.

• Start - Returns an ~ID~ for the Maze, as well as ~Height~ and ~Width~
• Check - Returns a 200 status code if the Maze location(x,y) you sent it is valid
• Solve - Returns a 200 if you solve the maze

The end of the maze is Height-1, Width-1

For this I decided to code the answer in Golang.

A couple of reasons to use Golang

• Compiles to a static binary not needing dependencies
• Cross platform compilation is a breeze
• Great concurrency model

On top of that I find it leads to very readable code. The challengers also recommend something that makes working with HTTP easy which Golang’s net/http library does without need to download any particular library or dependencies.

Methodology

Theres an algorithm for just about everything and I’m not one to reinvent the wheel, especially one I’ve never rolled before. So lets give ~maze solving algorithm~ a whirl and see what we get.

Relevant Wikipedia Page
Relevent .edu site

Pretty cool, Wikipedia has a recursive algorithm that looks very relevant and the edu page does well to further elaborate on it.

Essentially the recursive function iterates over the possible moves calling itself with various increments and decrements of the points to form a path of valid moves, based on what it has seen already and what has been declared a valid move from our CheckRoute function.

When it comes to recursion always have your base case in mind before starting your function calls, in our case its the end of the maze.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39

//Recursive algorithm to solve the maze modified from
//https://en.wikipedia.org/wiki/Maze_solving_algorithm
func (m *maze) RecursiveSolveMaze(x int, y int) bool {
  if x == m.Width-1 && y == m.Height-1 {
    return true
  }
  if m.CheckRoute(x, y) == false || m.Seen[x][y] {
    return false
  }

  m.Seen[x][y] = true
  if x != 0 { // Checks if not on left edge
    if m.RecursiveSolveMaze(x-1, y) { // Recalls method one to the left
      m.Path[x][y] = true // Sets that path value to true;
      return true
    }
  }

  if x != m.Width-1 { // Checks if not on edge
    if m.RecursiveSolveMaze(x+1, y) { // Recalls method one to the right
      m.Path[x][y] = true
      return true
    }
  }
  if y != 0 {
    if m.RecursiveSolveMaze(x, y-1) { // Recalls method one up
      m.Path[x][y] = true
      return true
    }
  }
  if y != m.Height-1 { // Checks if not on edge
    if m.RecursiveSolveMaze(x, y+1) { // Recalls method one down
      m.Path[x][y] = true
      return true
    }
  }
  return false
}

That’s the algorithm driving our search for a valid maze path. I mentioned before that Go makes HTTP a breeze so lets look at CheckRoute and the function we use to submit the solution.

Overall they’re simple, for the route they use URL parameters so we just craft a URL and make our request then check the status code.

The solution route wants an array of objects in the format [{“x”:“1”,“y”:“1”}…{}]

So when its time we’ll just Marshal an array of structs with that format and POST it as the body.

They said be mindful of HTTP status codes, 503 came up sometimes and means ‘Service Unavailable’, maybe we’re hitting the server too quickly? We’ll just catch that, add a brief sleep and try again with our request.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44

func (m *maze) CheckRoute(x int, y int) bool {
  check := root + "/" + m.Id + "/check?x=" + strconv.Itoa(x) + "&y=" + strconv.Itoa(y)
  resp, err := http.Get(check)
  if err != nil {
    panic(err)
  }
  defer resp.Body.Close()
  sc := resp.StatusCode
  if sc == 503 {
    time.Sleep(time.Second)
    resp, err = http.Get(check)
    sc = resp.StatusCode
  }
  if sc == 403 {
    return false
  }
  return true
}

func (m *maze) CheckSolution(body interface{}) bool {
  check := root + "/" + m.Id + "/solve"
  b, err := json.Marshal(body)
  if err != nil {
    log.Fatalln(err)
  }
  resp, err := http.Post(check, "application/json", bytes.NewBuffer(b))
  defer resp.Body.Close()
  if err != nil {
    log.Fatalln(err)
  }
  sc := resp.StatusCode
  if sc == 503 { //Service unavailable try again
    time.Sleep(time.Second)
    resp, err = http.Get(check)
    sc = resp.StatusCode
  }
  if sc == 422 { //Not a valid solution
    return false
  } else {
    log.Println("We solved the maze!")
    os.Exit(0)
    return true
  }
}

Conclusion

The recursive algorithm made quick work of this problem and I didn’t want to play around with alternate maze algorithms since I just wanted this to be some quick coding practice.

That leaves us with this -