# 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.

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