Advent of Code 2016

 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

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

The Code!

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

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.