Advent of Code 2016 Day17: Two Steps Forward

#########
#S| | | #
#-#-#-#-#
# | | | #
#-#-#-#-#
# | | | #
#-#-#-#-#
# | | |  
####### V

<!--break-->

This is a series of programming challenges for beginners and experienced Caché programmers.

For an introduction : go to article https://community.intersystems.com/post/advent-code-2016-day1-no-time-ta...

The challenge today is again a-maze-ing (as a wellknown president would say).

The maze has a bunch of doors ( | and - on the drawing), but they can be locked depending on a hash that you need to calculate every step. When you visit a location a second time, the lock on each door can be different from the previous time !

The way to know that a door is locked :

- take the MD5 hash of a passcode and a sequence of characters that represent the path you have taken so far.
(U for up, D for down, L for left, R for right).
- The first 4 characters of the hash represent the doors up, down, left and right.
b, c, d or f in the hash means a door is open, else it is locked.

Go for a full explanation to http://adventofcode.com/2016/day/17, it contains your passcode which you need to start your hash.

The challenge is to find the shortest path from start (S) to finish (V).

In part two of the challenge you need to calculate the longest path.

As the maze contains open spaces and doors, don't forget two take two steps every time : one step to go through the door, and another to step into the open space !

Here is the code that will calculate both challenges :

Class AOC2016.Day17
{

ClassMethod Part1()
{
  #Dim input="rrrbmfta"  //"ihgpwlah"
  #Dim smallestPath, longestPath, x, y, startX, startY as %Integer
  #Dim grid as Array of %String
  #Dim path, bestPath as %String
  #Dim room as %Char

  Set grid(1)="#########"
  Set grid(2)="#S| | | #"
  Set grid(3)="#-#-#-#-#"
  Set grid(4)="# | | | #"
  Set grid(5)="#-#-#-#-#"
  Set grid(6)="# | | | #"
  Set grid(7)="#-#-#-#-#"
  Set grid(8)="# | | | "
  Set grid(9)="####### V"

  Set smallestPath=50,longestPath=0
  For y=1:1:9 {
    For x=1:1:$l(grid(y)) {
      Set room = $E(grid(y),x)
      If room="S" Set startX=x,startY=y,room=""
      Set grid(x,y) = room
    }
  }
  Set path="",x=startX,y=startY
  Do ..Move(x,y,.path,.grid,input,.smallestPath,.longestPath,.bestPath)
  write !,"path : ",bestPath
}

ClassMethod Move(x, y, path, grid, input, smallestPath, longestPath, bestPath)
{
  #Dim finish as %Boolean = 0
  #Dim hash as %String
  #Dim door, stepX, stepY as %Integer

  Set hash = ..Hash(input_path)
  For door=1:1:4 {
    If $Case($E(hash,door),"b":1,"c":1,"d":1,"e":1,"f":1,:0) {  //only b, c, d & e are valid doors
      //3: left, 4:right
      set stepX=$Case(door,3:-1,4:+1,:0)
      //1: up, 2: don
      set stepY=$Case(door,1:-1,2:+1,:0)
      If ($Get(grid(x+stepX,y+stepY))="|")!($Get(grid(x+stepX,y+stepY))="-") {
        If (x+(stepX*2))=8,(y+(stepY*2))=8 {
          Set finish=1
          //part1:
          If $Length(path)<smallestPath Set smallestPath=$Length(path)+1,bestPath=path_$Extract("UDLR",door)
          //part2:
          If $Length(path)>longestPath Set longestPath=$Length(path)+1 Write !,longestPath
          Quit
        }
        Do ..Move(x+(stepX*2),y+(stepY*2),path_$Extract("UDLR",door),.grid,input,.smallestPath,.longestPath, .bestPath)
      }
    }
  }
  Quit finish
}

ClassMethod Hash(s) As %String
{
  #Dim md5Hash, hex, hex1 as %String
  #Dim iHash as %Integer
  set md5Hash=$system.Encryption.MD5Hash(s)
  Set hex=""
  For iHash=1:1:$l(md5Hash) {
    Set hex1 = $ZHex($Ascii(md5Hash,iHash))
    If $Length(hex1)=1 set hex1="0"_hex1
    Set hex = hex _ hex1
  }
  Quit $zconvert(hex,"l")
}

}

Look here for all our solutions so far : https://bitbucket.org/bertsarens/advent2016 and https://github.com/DannyWijnschenk/AdventOfCode2016
 

Here is the list of all Advent of Code 2016 articles  :

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