Alexa-Controlled Remote Part II

So I got my new LEDs in, and lo and behold, it works!

To make sure that they were blinking, I wrote a quick Python script that toggled multiple pins (right now its hardcoded to just 1 pin, but I could have changed variables to toggle others).  This was very nice, as I could have it turn on every 15 seconds or so and watch it on my phone camera.


import RPi.GPIO as GPIO
import time

gpio_start = 18
gpio_end = 19

GPIO.setmode(GPIO.BCM)

for x in range (gpio_start, gpio_end):
   GPIO.setup(x, GPIO.OUT)

while True:
   
   for y in range (gpio_start, gpio_end):
      GPIO.output(y, True)
      print 'on ', y
   time.sleep(15)
   
   for z in range (gpio_start, gpio_end):
      GPIO.output(z, False)
      print 'off ',z
   time.sleep(15)

Toggling pins through Python was nice and easy.

Continue reading

Advertisements

DIY Alexa-Controlled Remote Control

So, I think I’m going to embark on my first official hardware project.  I want to make something I can voice-control that allows me to do common operations on my projector and sound system (Like power on, switch to Blu-Ray, etc.)  I don’t have much of a HW background (I’ve made it maybe halfway through Make Electronics – excellent book by the way), so I figured this would be interesting.  I got a new RaspberryPi 3 for Christmas, and have been looking for a good project for it.

So, I knew I needed an IR transmitter to simulate a remote.  I figured I’d get a IR receiver as well to record signals and learn more.  So I browsed the web and found two that I liked (IR Transmitter and IR Receiver) from the same company.  It looked no-fuss as well, where I just had to connect ground, voltage, and two GPIO pins.  Didn’t sound too bad.

So let’s get started!

Continue reading

PyTennessee 2017 Day 2

Some of our party were feeling ill for the second day of PyTN, so we made it as far as my talk, and then had to boogey out of there.

Let’s see what I went to though:

 

Keynote: A deeper look at the Operating System by Sophie Rapaport (@sfrapoport)

Sophie was a good speaker, keeping us engaged for most of the talk.  While I knew most of the stuff from before, due to operating systems and working on embedded systems,it was still nice to see Sophie explain that even just with Python, you can start learning about under the hood parts of the language without diving into C.  I think it was a nice talk for all the people who had no OS experience before.  She also was able to relate to why we should care, and I’ve always liked when a speaker finds a way to connect the why with the how.

 

Scraping a great data set to predict Oscars by Deborah Hanus (@deborahhanus)

This was a nice quick talk about the methodology Deborah used to complete one of our course projects.  Her goal was to predict box office hits and Oscars using data science.  She walked through how to scrape data from multiple sources, how to analyze and clean data, and then how to present it.   I didn’t find too much of this revolutionary, but it did offer a glimpse into how easy it may be to grab a data set and go to town on it.

Lunch Lightning Talks

This was another set of good lightning talks.  We heard about writing great tutorials, Legacy Python vs Python 2, and a few others that I can’t remember

What Time is it Anyway by Greg Back (@gtback)

This was another quick talk discussing the options that you have in Python of how to get timing right.  We explored what the standard library gave us (which is great if you need to be timezone naive), and what some other libraries offered (including up to date timezone information.

BDD To The Bone by Pat Viafore (@PatViaforever)

So this was my talk!  It went quite well in my opinion, but I’m biased.  I didn’t get the audience I was hoping for (~25 people) but I saw a lot of vigorous nodding so I got some things right.  I had some immediate feedback and questions, which means people were interested.  I talked to some QA engineers from Emma, and some local Huntsville people and had some good discussions on how BDD can help people.

I had some nerves in the beginning, but I think the talk went smoothly.  See for yourself at https://youtu.be/H2FuJYlbzDg

 

We were so tired after all this though, we skipped the last two talks and headed home.  It was another great conference.  I wish I took some more time to meet more people, but I’ll have another chance when we go next year.

PyTennessee 2017 Day 1

Well, I’ve made it to another conference (they are even letting me present at this one).  I was in Nashville for PyTenessee.  I love Python, and this is a great conference and community to be a part of .

 

Keynote: The Importance of Community and Networking, by Sarah Guido (@sarah_guido)

I watched Sarah the first time I went to PyTennessee two years ago, and she had one of my favorite talks about data science.  This time, she was talking a bit about her personal journey, from classically trained trumpet player in college, to a senior data scientist at Mashable.   She gave some great tips of how to give back to the community (starting meetups, going to meetups, slack channels, open source contributions) and gave some great tips to avoiding burnout.

 

What’s in your pip toolbox? by Jon Banafato (@jonafato)

So I was trying to figure out a lightning talk, so I didn’t pay too close attention to this one, but what I did get out of it was something I’m going to go use at work.  I knew most of the pip requirements.txt information, but I learned about pip-compile and pipdeptree.  Pip-compile was nice as it helped you with a requirements.txt file based on the libraries you import, not giving you anything extraneous.   pipdeptree was a great tool to show  where your dependencies in pip are coming from.

 

Lunch Lightning Talks

There were a series of 5 minute lightning talks.  I decided thirty minutes before them that I’d write a unit test talk.  However, I fought with Linux windowing twice and never got it going :(.

Other talks were things like pipenv, xpath, and Rust community.

 

A brief introduction to concurrence and coroutines by Eric Appelt (@appeltel)

This was probably my favorite talk.  Eric did a good job with easy to understand examples, and walked through iteration, generators, and then to the new async/await syntax in Python 3.5.  I learned a lot through this, but I don’t know if I’ll get to asyncio stuff at ADTRAN.  It is in 3.5 only (we’re using legacy Python only), and it has a bit of a viral effect.

 

Let’s Build A Hash Table, In C by Jacques Woodcock (@jacqueswoodcock)

This one was alright.  I knew C pretty well, and I’ve written hash tables before, so I didn’t learn a whole lot new.  The slides were pretty good, though.

 

Big data Analysis In Python with Apache Spark, Pandas, and Matplotlib by Jared M. Smith (@jaredthecoder)

This was another great talk.  I heard Jared on Software Engineering Daily a few weeks ago, and liked that episode.  I saw his picture in the PyTN bios and recognized it and decided to go to his talk.  It was a bonus that it was about data science.  I’ve been to a few meetups where Spark was talked about, but Jared gave a good example of how to actually use it.  The Pandas and Matplotlib part felt a little tacked on, but it was good to mention it (I probably feel this way because I knew what he talked about.)  I wish we could have saw some more examples.

 

Keynote: Humaning is Hard by Courey Eliot (@dev_branch)

This was a short, but very honest talk about privilege, disabilities, mentoring, community and helping people in need.  She held everyone’s attention, and it was refreshing to see such a candid talk on such a tough subject.

 

Advent Of Code 2016 Day 21 (PHP)

Advent of Code 2016 Day 20 (F#)
Advent of Code 2016 – Day 19 (Swift)

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 20

Start: 1/6/2016

Finish 1/7/2017

Language: PHP

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

This challenge was to take a string, and apply a series of transformations on it (Swapping letters, rotating, reversing, etc.)

My idea was to keep an array where the head pointer moves around based on rotations, and operating based on that (similar to the idea of a circular array)

 

Part 1

Code Code Code ……


<?php

$head = 0;
$arr = array("a", "b", "c", "d", "e", "f", "g", "h");

function convertIndex($index){
    global $arr, $head;
    $newIndex = $index+$head;
    while($newIndex < 0){
        $newIndex += sizeof($arr);
    }
    return  $newIndex%sizeof($arr);
}
function getCharAt($index)
{
    global $arr, $head;
    $newIndex =convertIndex($index);
    return $arr[$newIndex];
}

function setCharAt($index, $value)
{
    global $arr, $head;
    $arr[convertIndex($index)] = $value;
}

function swapPos($pos1, $pos2) {
    $tmp1 = getCharAt($pos1);
    $tmp2 = getCharAt($pos2);
    setCharAt($pos1, $tmp2);
    setCharAt($pos2, $tmp1);
}

function swapLetters($letter1, $letter2) {
    global $arr;
    $index1 = array_search($letter1, $arr);
    $index2 = array_search($letter2, $arr);
    $arr[$index2] = $letter1;
    $arr[$index1] = $letter2;
}

function reverse($pos1, $pos2) {
    for ($i = $pos1, $j=$pos2; $i < $j; $i++, $j--){
        swapPos($i, $j);
    }
}

function printArray() {
    global $arr;
    for ($i = 0; $i < sizeof($arr); $i++){
        echo getCharAt($i);
    }
    echo "\n";
}

function rotateLeft($steps)
{
    global $head;
    $head += $steps;
}

function rotateRight($steps)
{
    global $head;
    $head -= $steps;
}

function move($from, $to) {
    global $arr;
    
    if ($to =$to; $i--){ 
            $newChar = getCharAt($i);
            setCharAt($i, $char);
            setCharAt($i+1, $newChar);
        }
    }
    else {
        $char = getCharAt($from);
        for ($i = $from+1; $i<=$to; $i++){ 
            $newChar = getCharAt($i);
            setCharAt($i, $char);
            setCharAt($i-1, $newChar);
        }
    }
}

function rotatePos($letter) {
    global $arr, $head;
    $index = 0;
    for ($i = 0; $i = 4) {
        $index += 1;
    }
    rotateRight($index+1);
}

function getLines() {
    $f = fopen("../day21.txt", "r");
    $lines = array();
    while (($buffer = fgets($f)) !== false) {
        $lines[] = trim($buffer);
    }
    fclose($f);
    return $lines;
}

function processLine($line) {
    $words = explode(" ", $line);
    if($words[0] == "swap" && $words[1] =="position"){
        swapPos($words[2], $words[5]);
    }
    if($words[0] == "swap" && $words[1] =="letter"){
        swapLetters($words[2], $words[5]);
    }
    if($words[0] == "rotate" && $words[1] =="left"){
        rotateLeft($words[2]);
    }
    if($words[0] == "rotate" && $words[1] =="right"){
        rotateRight($words[2]);
    }
    if($words[0] == "rotate" && $words[1] =="based"){
        rotatePos($words[6]);
    }
    if($words[0] == "reverse"){
        reverse($words[2], $words[4]);
    }
    if($words[0] == "move"){
        move($words[2], $words[5]);
    }
}


$lines = getLines();
foreach($lines as $line){   
    processLine($line);
}
printArray();
?>

This was my first foray in PHP in quite some time.  It was a bit more verbose than I remembered, but I still got this one relatively easy.

The main loop was easy, as it mostly took things line by line by line, and then chose a transformation based on the text.

Most transformations are straight forward.  I keep a global array and head pointer, along with a way to convert indices, get characters and set characters in the array.


$head = 0;
$arr = array("a", "b", "c", "d", "e", "f", "g", "h");

function convertIndex($index){
    global $arr, $head;
    $newIndex = $index+$head;
    while($newIndex < 0){
        $newIndex += sizeof($arr);
    }
    return  $newIndex%sizeof($arr);
}
function getCharAt($index)
{
    global $arr, $head;
    $newIndex =convertIndex($index);
    return $arr[$newIndex];
}

function setCharAt($index, $value)
{
    global $arr, $head;
    $arr[convertIndex($index)] = $value;
}

Swapping based on positions and swapping based on letters are pretty straight forward



function swapPos($pos1, $pos2) {
    $tmp1 = getCharAt($pos1);
    $tmp2 = getCharAt($pos2);
    setCharAt($pos1, $tmp2);
    setCharAt($pos2, $tmp1);
}

function swapLetters($letter1, $letter2) {
    global $arr;
    $index1 = array_search($letter1, $arr);
    $index2 = array_search($letter2, $arr);
    $arr[$index2] = $letter1;
    $arr[$index1] = $letter2;
}

Reversing and Rotating were also pretty easy.


function reverse($pos1, $pos2) {
    for ($i = $pos1, $j=$pos2; $i < $j; $i++, $j--){
        swapPos($i, $j);
    }
}

function rotateLeft($steps)
{
    global $head;
    $head += $steps;
}

function rotateRight($steps)
{
    global $head;
    $head -= $steps;
}

Once we get into moving (removing from one index and inserting in the other index), it took me a little while longer to get this.  I treat moving differently based on which direction I’m going to, and then I effectively “bubble” the values to the appropriate position.  I originally tried to do array slicing and recombining, but my wonky index recalculations made it tricky.


function move($from, $to) {
    global $arr;
    
    if ($to =$to; $i--){ 
            $newChar = getCharAt($i);
            setCharAt($i, $char);
            setCharAt($i+1, $newChar);
        }
    }
    else {
        $char = getCharAt($from);
        for ($i = $from+1; $i<=$to; $i++){ 
            $newChar = getCharAt($i);
            setCharAt($i, $char);
            setCharAt($i-1, $newChar);
        }
    }
}

Lastly, I worked on the rotate based on the position of a letter.  I pretty much searched for the letter in my array, then figured out how many rotations needed to happen.


function rotatePos($letter) {
    global $arr, $head;
    $index = 0;
    for ($i = 0; $i = 4) {
        $index += 1;
    }
    rotateRight($index+1);
}

 

Part 2

This part was to unscramble a password rather than scramble a password.  I reversed the lines of code, and reversed the relevant sections (such as rotating left when the command is rotate right)


function processLine($line) {
    $words = explode(" ", $line);
    if($words[0] == "swap" && $words[1] =="position"){
        swapPos($words[2], $words[5]);
    }
    if($words[0] == "swap" && $words[1] =="letter"){
        swapLetters($words[2], $words[5]);
    }
    if($words[0] == "rotate" && $words[1] =="left"){
        rotateRight($words[2]);
    }
    if($words[0] == "rotate" && $words[1] =="right"){
        rotateLeft($words[2]);
    }
    if($words[0] == "rotate" && $words[1] =="based"){
        rotatePos($words[6]);
    }
    if($words[0] == "reverse"){
        reverse($words[2], $words[4]);
    }
    if($words[0] == "move"){
        move($words[5], $words[2]);
    }
}

The tricky part of this one was figuring out how the rotate based on the position of a letter was handled.  Based on some pen and paper calculations, I found a way to derive how many rotations were needed to get to the next password


function rotatePos($letter) {
    global $arr, $head;
    $index = 0;
    for ($i = 0; $i < sizeof($arr); $i++){
        if (getCharAt($i) == $letter) {
            $index = $i;
            break;
        }
    }
    $numRotations=0;
    for ($j = 0; $j < sizeof($arr); $j++) {
        if ($j = 4 && ($j + $j + 2) % sizeof($arr) == $index) {
            $numRotations = $j+2;
            break;
        }
    }
    rotateLeft($numRotations);
}

 

Wrap-up

I had a lot of stupid mistakes in my part 2.  I kept not thinking through the problem.  Also PHP’s verbosity was weighing me down.  I felt like the array functions were clunky, and my code endd up all over the place.

I give myself a B- on this one.  I could have done better, and thought through the problems better.  My PHP code isn’t great either, so I wasn’t satisfied with this, but it’s better than some other ones.

Next up, is Day 22 with Elm.

 

Advent of Code 2016 Day 20 (F#)

Advent of Code 2016 – Day 19 (Swift)
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 20

Start: 12/26/2016

Finish 1/6/2017

Language: F#

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

This challenge wasn’t too bad at first glance.  Given a list of blacklisted ranges of IP addresses, find the first IP address not in a blacklist.  I decided to give F# a go with this.  After OcaML didn’t go so well, I was determined to use my lessons learned and write some better code.

There was a long delay on this one due to Christmas, and a vacation in between, so I definitely missed my goal of 25 languages in 25 days.  But let’s see how far I can go.

Part 1

As usual, code first.


open System

let readlines  = System.IO.File.ReadAllLines("../day20.txt")
let toInts arr =  Seq.map uint32 arr
let getFilterFunction range =  (fun x -> x  (Seq.last range))
let uintRange = seq { System.UInt32.MinValue..System.UInt32.MaxValue} 
let allFiltersPass (filters:seqbool)>) (num:UInt32) = Seq.forall (fun f -> (f num)) filters
let skipIfOutOfRange filterFuncs = uintRange |> Seq.skipWhile (fun x -> (not (allFiltersPass filterFuncs x)) )

[]
let main argv = 
        Seq.toArray readlines 
        |> Seq.map (fun x -> x.Split[|'-'|])
        |> Seq.map toInts
        |> Seq.map getFilterFunction
        |> skipIfOutOfRange
        |> Seq.head
        |> printfn "%d"
        0


This wasn’t too bad, as I read and sanitize the input to be integers.  Then I just start iterating through numbers from 0 to MAX_INT until I find one that doesn’t fit within all the functions

Part 2

Part 2 is much tougher.  Instead of finding the first non-blacklisted IPs, we needed a count of all non-blacklisted IPs.

The basic idea was to start at zero, and then find the first number that is not in a blacklisted range.  Then find the next number that is a range and subtract the difference.  Add that difference to the sum, and start again with the ranges that are left.

First, I had to implement a solve method to do the basic checking


let rec solve num accum  ranges = 
        let matching = (getFiltersMatching num ranges)
        let remainingRanges = (getRemainingRanges ranges num)
        match Seq.isEmpty matching with
        | true ->
            match (Seq.isEmpty remainingRanges) with
            | true -> accum + (System.UInt32.MaxValue - num) + 1u
            | false -> 
                let invalidNumber = (getFirstInvalidNumber remainingRanges)
                let diff = invalidNumber - num
                solve (getNextStartingNumber (invalidNumber+1u) remainingRanges) (accum + diff) remainingRanges
        | false ->     
            let lastValid = (getLastValidNumber matching)
            match lastValid with
            | System.UInt32.MaxValue -> accum
            | otherwise -> solve (lastValid+1u) accum remainingRanges
       

[]
let main argv = 
        Seq.toArray readlines 
        |> Seq.map (fun x -> x.Split[|'-'|])
        |> Seq.map toInts
        |> solve 0u 0u
        |> printfn "%d"
        0

This was ugly code, to be sure.  First I check if I’m already in a range, and if I am, either I’m at the end of my int range, or I need to recursively check the number out of my current range.  If I’m currently in a number not in a range, I need to check what the next invalid number is.  I subtract my current number from the invalid number and then add it to an accumulator.

I had to write a few utility functions to find information about the ranges


let getFirstInvalidNumber ranges =
         ranges
         |> Seq.map (fun r -> (Seq.head r))
         |> Seq.min

let getNextStartingNumber num ranges = 
        getFiltersMatching num ranges
        |> Seq.map (fun r -> (Seq.last r))
        |> Seq.filter (fun x -> x >= num)
        |> Seq.min

let isNumBeforeRange num range =
        num  Seq.filter (fun r -> (isNumBeforeRange num r) )

let getLastValidNumber ranges =
         match (Seq.isEmpty ranges) with
         | false ->
                ranges
                |> Seq.map (fun r -> (Seq.last r))
                |> Seq.max
         | true -> System.UInt32.MaxValue

These were just straight forward sequence operations.

 

Wrap-up

F# did not go as smoothly as I wanted.  I got part two wrong at first, and it took me a while to write ugly code.  The documentation was great though, and Visual Studio Code was a blast to write F# in (inline type annotations? Yes, please.)  I would definitely consider F# for a .NET project over OcaML.

I give myself a C+ on this one.  I had a vacation in the middle, but I still had some time on either end that I was working on this one.

Next up, PHP.

 

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#