Advent of Code 2016 Day1: No Time for a Taxicab

Article

Danny Wijnschenk · Nov 1, 2017 8m read

#Caché #Code Snippet #Contest #ObjectScript

Advent of Code is a series of 25 small programming challenges, it's an ideal way for beginners to start learning a computer language, and for advanced people to sharpen their programming skills.

There are small and bigger puzzles, which you can solve typically in half an hour to a few hours. (Looking at the leaderboard, the top aces can do them in less than 10 minutes.)

Advent of Code is created by Eric Wastl, you can find all info on https://adventofcode.com/.

To help you get trained for this year's challenges which start at December 1st, we* will try to solve and comment the puzzles from 2016. (we = Bert Sarens and myself)

Each day, you get two puzzles, where the second one is usually a slight variation on the first one, which shows you how your code will cope with requirement changes or other input (in some cases by having to completely rewriting your code !).

You can find the complete puzzle description and input files on the https://adventofcode.com site, we will briefly explain them here.

Our solutions can be downloaded on https://github.com/DannyWijnschenk/AdventOfCode2016 (Studio xml export) and https://bitbucket.org/bertsarens/advent2016 (Atelier .mac).

Feel free to comment and show your solution : the Good, the Bad and the Ugly !

In the 2016 challenge, you need to help Santa to retrieve 50 stars that were stolen by the Easter Bunny. (I kid you not, full story on http://adventofcode.com/2016/day/1)

In today's challenge, you need to find the shortest path from your current location to the Easter Bunny Headquarters through a street grid, by using a list of instructions in the form L (left) or R (right), followed by a number of blocks to walk. (e.g. R2 : turn right and walk 2 blocks further)

For example R2, R2, R2 leaves you 2 blocks due South of your starting position (you start heading North), thus the distance is 2.

R5 L5 R5 R3 results in a distance of 12.

Given the input of directions found here http://adventofcode.com/2016/day/1/input, can you calculate the distance between your starting point and the destination.

!!!!!!!!

Spoiler alert : first write your own code, submit your solution (distance) on the adventofcode website, than read further and compare !

!!!!!!!!

So, first we need to read the input, and for each instruction change our direction, and walk the amount of blocks.

I noticed spaces in the input, so while reading the file, $Translate is fine to get rid of them. (i copied the input in a txt file)

When we face North, and the instruction says R, we have to change direction to East, if direction says L(eft), we need to turn West, and so on.

In my code, I used a series of If's; using $Select/$Case will be shorter, but not so readable.

Here is a snippet of my code :

(I use Caché Studio with 'option explicit' on, this option will mark all variables that are not explicitly declared by #Dim, this helps to detect typos in variabele names. You can set this option in Tools->Options->Environment:Class:Option Explicit)

ClassMethod Part1(file As %String = "j:\winfo\aoc\day1.txt")
{
#Dim locX as %Integer = 0
#Dim locY as %Integer = 0 ;initial starting point
#Dim heading as %Char = "N"  ;start facing North
#Dim direction as %Char      ;to hold the current instruction's direction
#Dim length as %Integer      ;to hold the current instruction's blocks to walk
#Dim line, route as %String
#Dim iRoute as %Integer

Open file:"R":1 Else  Use 0 Write "Could not open file ",file,! Quit
  Try {
    For {
      Use file Read line If line="" Quit
      Set line=$Translate(line," ") ;get rid of spaces in input directions
      For iRoute=1:1:$Length(line,",") {
        Set route = $Piece(line,",",iRoute)
        Set direction=$E(route,1)
        Set length=$E(route,2,*)
        If (heading="N") {
          If (direction="R") {
            Set heading="E"
            set locX=locX+length
          } else {
            Set heading="W"
            set locX=locX-length
          }
        } elseIf (heading="S") {
          If (direction="R") {
            Set heading="W"
            set locX=locX-length
          } else {
            Set heading="E"
            set locX=locX+length
          }
        } elseIf (heading = "E") {
          If (direction="R") {
            Set heading="S"
            set locY=locY-length
          } else {
            Set heading="N"
            set locY=locY+length
          }
        } elseIf (heading = "W") {
          If (direction="R") {
            Set heading="N"
            set locY=locY+length
          } else {
            Set heading="S"
            set locY=locY-length
          }
        }
      }
    }
  } Catch {
    If $ZE'["ENDOFFILE" Use 0 Write "Error : ",$ZE,!
  }
  Close file
  Use 0 Write "[X,Y] = ",locX,",",locY,!,"Answer = ",$ZAbs(locX)+$ZAbs(locY)
Quit
}

Hmm, I could change reading the input by using a file by reading the actual http link to the input by using %Net.HttpRequest : If you will do the actual 2017 challenge, every second counts to get a higher ranking).

When you submit your answer, you unlock the second part of the puzzle (or you have to wait for 1 minute if your answer was wrong).

The second part of the puzzle changes the challenge a bit : when you are at a location that you visited already, you can stop.

My first thought was to store the current location after processing each instruction, and to test if we used this one before, but this was too easy : not only the endpoint per instruction should be tested, but also all coordinates in between while walking from one point to another !

Oh well, back to the drawing board : instead of the instruction Set locX = locX + length, we need to set this 1 by 1 and test for each step if the location was not used already.

So I ended up with using a separate method to do the 'walking'.

Instead of showing these changes here (you can look it up at my github), let's look at Bert's code, which is a lot shorter (in routine format) :

Start() PUBLIC {
	s input="R3, L5, R1, R2, L5, R2, R3, L2, L5, R5, L4, L3, R5, L1, R3, R4, R1, L3, R3, L2, L5, L2, R4, R5, R5, L4, L3, L3, R4, R4, R5, L5, L3, R2, R2, L3, L4, L5, R1, R3, L3, R2, L3, R5, L194, L2, L5, R2, R1, R1, L1, L5, L4, R4, R2, R2, L4, L1, R2, R53, R3, L5, R72, R2, L5, R3, L4, R187, L4, L5, L2, R1, R3, R5, L4, L4, R2, R5, L5, L4, L3, R5, L2, R1, R1, R4, L1, R2, L3, R5, L4, R2, L3, R1, L4, R4, L1, L2, R3, L1, L1, R4, R3, L4, R2, R5, L2, L3, L3, L1, R3, R5, R2, R3, R1, R2, L1, L4, L5, L2, R4, R5, L2, R4, R4, L3, R2, R1, L4, R3, L3, L4, L3, L1, R3, L2, R2, L4, L4, L5, R3, R5, R3, L2, R5, L2, L1, L5, L1, R2, R4, L5, R2, L4, L5, L4, L5, L2, L5, L4, R5, R3, R2, R2, L3, R3, L2, L5"
	d part1(input)
}

part1(Input) {
	#Dim Input As %LibraryDir.String
	
	s xLocation=0
	s yLocation=0
	s xDir=0
	s yDir=1
	
	s visited(xLocation,yLocation)=""
	for command=1:1:$LENGTH(Input,",") {
		s part=$ZSTRIP($PIECE(Input,",",command),"*W")
		s direction=$EXTRACT(part)
		s steps=$EXTRACT(part,2,*)
		//w !,part,*9,a,*9,b
		
		s (a,b)=1
		if direction="R" s b=-1
		if direction="L" s a=-1
		if 'xDir {
			s xDir=a*yDir
			s yDir=0
		} else {
			s yDir=b*xDir
			s xDir=0
		}
		for step=1:1:steps {
			s xLocation = xLocation + xDir
			s yLocation = yLocation + yDir
			if $Data(visited(xLocation,yLocation)) {
				w !,xLocation,*9,yLocation
				w !,"twice visited distance: ",$ZABS(xLocation)+$ZABS(yLocation)
			}
			s visited(xLocation,yLocation)=$ZABS(xLocation)+$ZABS(yLocation)			
		}

	}
	w !,"distance: ",$ZABS(xLocation)+$ZABS(yLocation)
}

End of day one, if you execute both parts of the code, you should end up with two stars, and one part of the advent finished!

We will start at the next challenge tomorrow.

List of other Advent of Code 2016 challenges so far :

https://community.intersystems.com/post/advent-code-2016-day2-bathroom-s...

https://community.intersystems.com/post/advent-code-2016-day3-squares-th...

https://community.intersystems.com/post/advent-code-2016-day4-security-t...

https://community.intersystems.com/post/advent-code-2016-day5-how-about-...

https://community.intersystems.com/post/advent-code-2016-day6-signals-an...

https://community.intersystems.com/post/advent-code-2016-day7-internet-p...

https://community.intersystems.com/post/advent-code-2016-day8-two-factor...

https://community.intersystems.com/post/advent-code-2016-day9-explosives...

https://community.intersystems.com/post/advent-code-2016-day10-balance-bots