Advent of Code is one of my favorite times of year. Here is my thought process on 2017 Day 13.

Day 13 reveals itself as a sort of lock picking exercise. Part one is a simple tumble (get it) through the series of inputs they give you, to figure out if you would be caught on a certain layer, and if so, do some multiplication to get your answer. Simple.

The puzzle could also be thought of as the scene in The Rock (the movie about Alcatraz with Nicholas Cage and Sean Connery), where, to get into the prison, Sean Connery has memorized the timing for the fires that blaze, and rolls through them unscathed.

Except, the timings way down the line don't match up since they themselves are on their own timers. And there's like 40+ of them.

The sample input looks like this:

0: 3
1: 2
4: 4
6: 4

So, layer 0 has a depth 3. So on "second 0" the scanner is at 0, on second 1 it's at 1, on second 2 it's at 2, on second 3 it goes back to 1, and on second 5 it's back to the start, blocking any would-be attackers.

Layer 1 only has depth 2, so it's fluctuating back and forth between 0 and 1.

Since the puzzle input may include gaps, and it's easier (probably) to complete the puzzle with no gaps, the first step is to fill them in! As usual I'm writing my answers in Go

func fill(scanners []*Scanner) []*Scanner {
	max := scanners[len(scanners)-1].Depth
	for i := 0; i < max; i++ {
		if scanners[i].Depth != i {
			s := &Scanner{Depth: i, Range: 0, Nil: true}
			scanners = append(scanners[:i], append([]*Scanner{s}, scanners[i:]...)...)
		}
	}
	return scanners
}

That line   ------    append(scanners[:i], append([]*Scanner{s}, scanners[i:]...)...)  ---- with all the dots!! What it's doing is pretty simple, though.

If we don't have a scanner at depth i, insert a scanner with depth i at the current position.   "scanners[:i]" is all scanners up to i.  "scanners[i:]" is all scanners after and including i  ( the :   (colon) syntax is very subtle). So we want to insert it between those two. That's all it's doing. The ellipsis confusion is just because "append" takes a variadic list of parameters, and you can convert an array to variadic parameter with the ellipsis. Done!

We'll need a method to move all of the scanners every step. That's pretty straightforward. I called this method "tick". The Scanner is just a struct with Depth, Range, Current, and Dir for telling which direction the thing is moving.

func tick(scanners []*Scanner) {
	for _, s := range scanners {
		if s.Nil {
			continue
		}

		if s.Current == s.Range-1 {
			s.Dir = -1
		} else if s.Current == 0 {
			s.Dir = 1
		}

		s.Current += s.Dir
	}
}

Part 1 was to just send a "packet" (or Sean Connery) through and every time you are at a security scanner (explosion, going back to the movie), multiply the depth times the range at that scanner, and add it to the previous number to get the new number. That part was fine, and you could do it with the physical motion of passing the Sean Connery through :)

So, to figure out part 2, which is "you need to get through without getting caught this time".  Getting caught is simply being at Depth "d" when the scanner at "d"'s current position is 0. You could brute force this.

For brute force, you'd start at delay 0, then try go figure out if you can make it all the way through. If not, move to delay 1 and try again. For each delay, you have to run the tick method. For delaying 100 seconds, tick would have to be run 100 times to get the puzzle into the correct state. So this becomes computationally intense!

This is a fine solution in most instances. In this instance, though, I let it run over lunch and checked in with it 44 minutes later, and it wasn't complete yet! So, back to the drawing board.

But wait!!  Math is a thing. And it's very useful!  I'm actually pretty certain that I don't even need to check the final answer by actually traversing the sequence of layers, it's just the answer. Due to math!

So, to get through safely, the position of a particular depth has to not be 0 when we're passing through it. I wrote a method to figure this out, called "possible". It's pretty much the key to the puzzle, and solving it insanely fast.

func possible(scanners []*Scanner, delay int) bool {
	p := true
	for _, s := range scanners {
		blocking := (s.Range*2 - 2)
		p = p && (s.Nil || ((delay+s.Depth)%blocking != 0))
	}
	return p
}

A "Nil" scanner is a scanner that was filled in due to gaps. This one has 0 range and can't block anything. So if it's one of these, it can pass through this depth at this time.

The (s.Range * 2) - 2.  Call this "blocking" or whatever. I called it blocking since it's at position 0 of its range every "blocking" number of steps. A scanner with range 4 is back to 0 every 6 steps (4 * 2 - 2) To determine if it's possible at this delay, a layer 7 steps in cannot be blocking on delay + 7. Otherwise it gets caught.  (delay + depth) % blocking.   (After delay, scanner at depth "depth" has to not be at the start ( mod blocking == 0) ).  "p" is kept, for each step, if we can pass through up until now and the current layer. You could possibly shave off some iterations here by checking p, and if it's false, break out of the loop. I might actually update it to do that and report back! It takes about 1 second to run currently. (CONFIRMED. it runs in about half a second now).

So, all that's left is to still brute force the numbers to find if it's possible to get through the sequence at the current delay, without getting caught, but you don't have to actually do it, which speeds it up somewhere on the order of a million percent :)

Check out the full solution here - https://github.com/jasontconnell/advent/blob/master/2017/13.go

Happy coding, and happy holidays!!