Advent of Code 2016 – Day 19

Advent of Code 2016 Day 18 (Bash)
Advent of Code 2016 Day 17 (Ruby)

Advent of Code 2016 Day 16 (Scala)

Advent of Code 2016 Day 15 (Typescript)

Advent of Code 2016 Day 14 (Go)

Advent of Code 2016 Day 13 (Lua)
Advent of Code 2016 Day 12 (C#)
Advent of Code 2016 Day 11 (Groovy)

Advent of Code 2016 Day 10 (OcaML)

Advent of Code 2016 Day 9 (Factor)

Advent of Code 2016 Day 8 (c++)
Advent of Code 2016 Day 7 (Javascript)
Advent of Code 2016 – Day 6 (Julia)
Advent of Code 2016 – Day 5( Java 8)

Advent of Code 2016 – Day 4 (Perl 6)

Advent of Code 2016 – Day 3 (Clojure)
Advent of Code – Day 2 (Python 3)
Advent Of Code 2016 – Day 1(Haskell)

Day 19

Start: 12/25/2016

Finish 12/26/2016

Language: Swift

SPOILER ALERT: If you have any inkling, any whatsoever, to work on the Advent of Code…. DO NOT READ THIS BLOG POST.  DO NOT LOOK AT MY GITHUB PROJECT.  It is no fun if you’re not solving it yourself, and you’ll feel so much better about yourself if you can figure it out without looking up an answer.  This blog post is not to give away the answer, but instead, is there for people to learn from.

As always, the following code is in my GitHub: https://github.com/pviafore/AdventOfCode2016

The Challenge

So I ran into toolchain issues off the bat (just what I feared).  I knew I had a messed up Clang install on my machine, and it caused Swift to not be able to find some .so objects that it wanted.  Thankfully, I found a Docker image to build Swift in.  This was my first time working in Swift, and I enjoyed it.  I had been avoiding it since it was so Apple-oriented (and I haven’t done any Apple development before), but I was quite surprised.  It reminded me of Scala or Rust as far as syntax goes, and it was easy to write code.

This challenge was a rehash of Circle of Josephus.  A quick wiki refresher was what I needed to figure everything out.

Part 1

The code was quite simple :


func josephus(circleSize: Int, num: Int)-> Int {
    var last = 0
    for index in 2...circleSize {
        last=(last + num) % index 
    }
    return last + 1 
}

print(josephus(circleSize: 3014603, num:2))

I don’t even need to spend a whole lot of time on this.  I grabbed the recurrence relation from Wikipedia, and used dynamic programming to transform this into a simple linear loop.

g(n,k)=(g(n-1,k)+k){\bmod  n},{\text{ with }}g(1,k)=0

Part 2

Part two threw me for a loop (no pun intended).  I was fully expecting to see the number go up, but instead, the trick was that instead of every Kth person being eliminated, it was the person directly across who got eliminated.

I tried to do a bunch of mathematical induction and proofs to figure this one out, but kept getting stuck.  I had to go sleep on it, and came up with a better way.  The first person to get eliminated will be n/2 positions away from your index.

First I created a circular linked list to represent the elves in this example.


public class Node {
    var value: Int
    init(value: Int) {
        self.value = value
    }

    var next: Node? = nil
    weak var previous: Node?
}

func createList(size: Int) -> Node {
    let head:Node = Node(value: 1)
    var tail:Node = head
    for index in 2...size {
        let node = Node(value:index)
        node.previous = tail
        tail.next = node
        tail = node
    }
    head.previous = tail
    tail.next = head
    return head
}

Then, I advanced n/2 positions.  Then it was a simple pattern of who got eliminated.  If the circle size was odd, it was n/2 and then you skipped n/2 +1.  If the circle size was even, it was just n/2 (no skipping after).  Thus you get in the pattern, eliminate eliminate skip eliminate eliminate skip eliminate eliminate skip….. and so on.


func removeSelf(node: Node) -> Node {
    let nextNode = node.next!
    let previousNode = node.previous!
    previousNode.next = nextNode
    nextNode.previous = previousNode
    return nextNode
}

func josephus(circleSize: Int)-> Int {
    var list: Node = createList(size: circleSize)
    for _ in 1...circleSize/2 {
        list=list.next!
    }
    for size in stride(from: circleSize, to: 1, by: -1) {
        list = removeSelf(node:list)
        if (size % 2 == 1){
            list=list.next!
        }
    }
    return list.value
}

This got the right answer.

Wrap-up

I give myself a B+ on this.  I got to play around with Swift, and I liked it.  The compiler was helpful, and I found a lot of good examples.  I had to go look at the wiki to remember the Josephus equation, and if I didn’t recognize this as a Josephus problem, I would have been waiting a lot longer.

Next up is Day 20, using F#

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s