## Advent of Code 2017 - Day 13 December 13, 2017

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!!

## Advent of Code 2016 January 4, 2017

I've been doing the Advent of Code 2016 this year, I've been a little late to the game due to a week off of doing anything with computers and generally just not being very attentive to it.

There have been a few favorites. Day 11, 13 and 17 with their tree searching have been a good refresher. Day 15 literally took me longer to understand the problem than to code it up.

Day 19 took me through a few different paths. Day 19 is the White Elephant with 3 million elves. The elf takes the presents from the elf to their left and the next elf that has presents goes next. And it repeats until one elf has all the presents. Part 2, which you find out later, is that it changes it to take the presents from the elf across from them.

The first attempt at this solution was an array of elves. 3 million odd elves. Looping through would be fast but finding the next elf who has presents would be looping a ton. Solving the 5 elf example worked but moving it to 3 million+ pointed out how terribly inefficient this would be.

So. Linked list to the rescue  (I have always said "to the rescue" when picking a tool to solve the job, but ever since seeing "The Martian", now my internal voice is replaced by Matt Damon's, when he determines that hexadecimal is the answer to his problems).

For part one, just create 3 million elves and have a pointer to the next elf. The last elf's next elf is the first elf. Done.

for elf.Next != elf

elf.Presents += elf.Next.Presents

elf.Next = elf.Next.Next

elf = elf.Next // move to the next elf

This solves it very quickly. But then the bombshell of part 2 comes in. Find the elf across from the current elf in a Linked List?! What?

First attempt was for each elf, use a counter to determine the one across. So every time an elf is removed from the circle, decrement the counter. To determine the across elf, loop to across.Next (count / 2) times. This works. But then it proved very slow as well. Each time you're looping it loops 1.5 million-ish times (half). This proved to be correct though, with my test with the five elves.

Then I remembered the ability to just have as many pointers as you want! This is computers, you can do whatever you want. There are no rules :)   So, instead I created an "across" pointer and initialized it with my count/2 loop. This would be the only time it would need to loop. Just determine it's starting location.

I would still have to keep a count though. The count was useful for the case where, for instance in the 5 elf circle...  1 takes presents from 3, but there are 2 across from 1, so you choose the left side. However, removing 3 then, and moving to 2, 2 is across from 5, but if we were to just increment the across elf to across.Next, it would point to 4. So if there are an even number of elves left, add another move to across.Next after setting it to across.Next (move it two forward in the list).  This proved to work and was very fast :)

Check the solution here - https://github.com/jasontconnell/advent/blob/develop/2016/19.go

## Advent Of Code - Day 22 December 30, 2015

I finished Day 22 at 7pm on December 29th. This wasn't due to 7 days of rigorous coding, failing, rethinking, mind you. I didn't do any work on it Christmas Eve, Christmas Day, the 26th, 27th or 28th. Long stories there. On the 23rd and 24th I took a break from 22 because it was clear I was not going about it the right way, and did days 23 and 24. I don't know how much coding I actually put into it. The leaderboard filled up at about 4am on the 22nd, I wouldn't have been on it if I did all of the coding at one time starting at midnight, I know that much. It might have been 8 hours for me.

There were a few little things that made this puzzle very fun but also a pain! Little subtle word clues that I initially just glossed over, turned out to lead to flaws in the logic that prevented me from solving this puzzle.

## The Puzzle

The puzzle returns to day 21, where Little Henry Case is playing the same role playing game, but instead with swords and armor, you're now a magician. You have 5 spells at your disposal, each with varying effects. You are tasked with defeating the boss, who's hit points and damage are the puzzle's input. Mine happened to be 58 HP and 9 DMG. You must find the "path" to defeat the boss using as little mana as possible.

## The Spells

These are the spells at your disposal:

1. Magic Missile - Costs 53. Instant damage of 4.
2. Drain - Costs 73. Instant damage of 2. Instant heal of 2.
3. Shield - Costs 113. Initializes an effect that lasts 6 turns and adds 7 defense to you over those 6 turns.
4. Poison - Costs 173. Lasts 6 turns. At the start of each turn, deals 3 damage
5. Recharge - Costs 229. Lasts 5 turns. At the start of each turn, adds 101 mana to player.

## Rules

The subtle wording comes in the rules and how the spells are interpreted.

• On each of your turns, you must select one of your spells to cast. If you cannot afford to cast any spell, you lose.
• Effects apply at the start of both the player's turns and the boss' turns.
• Effects are created with a timer
• At the start of each turn, after they apply any effect they have, their timer is decreased by one
• You cannot cast a spell that would start an effect which is already active
• However, effects can be started on the same turn they end.
• Do not include mana recharge effects as "spending" negative mana

## Breakdown

• Instant is a property on Effect because Instant effects are processed at the same time as reoccurring effects, and the rule states that you can't start an effect which is already active. However, if you have poison active, which causes Damage, you should be able to cast the Magic Missile effect, which also causes Damage, because it's an instant effect.
• OneTime is a property on Effect to make Shield work correctly. Shield occurs immediately, and remains, but its effects aren't processed every turn. Just once it's cast, and removed when the timer counts down.
• I use random generation to get the next spell. It will pick one based on how much mana is left on the player, and if that effect is not already active, and also checking the Instant flag on Effect, because we want to be able to cast Magic Missile even though Poison may be active.
• I was a little inconsistent in how the functions work. For instance, ApplyEffects applies the Boss and Player hit points and mana directly (use pointers), while Attack just returns the damage to apply. I'm ok with this.
• The Story struct is fun to read through, when it works, and you're verifying everything, and you say to yourself, "This might actually work!" :)

I had a lot of fun on these puzzles. I think I want to post one for Day 25 too, so check back soon for that one!

## Advent of Code - Day 15 December 17, 2015

I've been going through the Advent of Code, and it's been pretty straight forward day to day. I got to day 15, and it took me a little bit to think of how to get an array of 4 digits that also adds up to 100. After some thought, I then gave into the easy, brute force solution. There was a previous puzzle for "incrementing" a password and I thought I could solve this one the same way.

In other words, I'd start with [0,0,0,0] and always increment the right-most digit (array with index = len(array)-1) and when it hit 100, it would increment the digit at position len(array)-2 and reset the current one back to 0. This would take F@#%inG FOREVER. But it would loop through all possible combinations.  Before calculating the "cookie recipe" based on the array, I would first check if they added up to 100, if not I would just increment until it did add up to 100. One quick brilliant optimization I made was to start with the initial array of [0,0,0,99] :)  (I kid on the brilliance of it... it saved 99 iterations in what could be a hundred million).

So then I thought again about it. There were two other previous puzzles where you could brute force the solution by first getting all possible permutations of the elements, and looping over all permutations, applying the logic, and sorting them to tell you the highest / lowest combined value.  I thought, this seems similar in a way to that, moreso than it did to the password incrementing.

So you'd start with inserting 100 into a blank array, then recursively call a method that would give you permutations of the remaining value, in this case would be 0. So in the end it would return [100,0,0,0]

If I inserted 50 into the array first, it would then give me permutations of the remaining 50.

So, [50,25,25,0], [50,25,0,25], [50,26,0,24] etc, all the way to [50,0,0,50], [50,50,0,0], [50,0,50,0].  Totally exhaustive but also, 100% correct and I never have to check if the sum of the array adds up to 100, because it's guaranteed to! :)

Here's that method in Go

```func Perms(total, num int) [][]int {     ret := [][]int{}       if num == 2 {         for i := 0; i < total/2 + 1; i++ {             ret = append(ret, []int{ total-i, i })             if i != total - i {                 ret = append(ret, []int{ i, total-i })             }         }     } else {         for i := 0; i <= total; i++ {             perms := Perms(total-i, num-1)             for _, p := range perms {                 q := append([]int{ i }, p...)                 ret = append(ret, q)             }         }     }     return ret }```

```perms := Perms(5, 3)         fmt.Println(perms)```

`And the output`

```[[0 5 0] [0 0 5] [0 4 1] [0 1 4] [0 3 2] [0 2 3] [1 4 0] [1 0 4] [1 3 1] [1 1 3] [1 2 2] [2 3 0] [2 0 3] [2 2 1] [2 1 2] [3 2 0] [3 0 2] [3 1 1] [4 1 0] [4 0 1] [5 0 0]]```

YES!!! I thought about that one for a while. I knew there had to be a way to do it :)

More importantly, for the Perms(100,4) input in the puzzle, it returns only 176,851 possible permutations, and my original brute force method could have looped 100,000,000 (one hundred million) times!!  Quite the improvement.