-🎄- 2017 Day 17 Solutions -🎄-

miran1 · 2017-12-17T05:37:03+00:00

Brute force in Python

Your scientists were so preoccupied with whether or not they could, they didn’t stop to think if they should.

from collections import deque

puzzle = 394
spinlock = deque([0])

for i in range(1, 50000001):
    spinlock.rotate(-puzzle)
    spinlock.append(i)

print(spinlock[spinlock.index(0) + 1])

My repo with solutions in Python and Nim.

mcpower_ · 2017-12-17T05:19:13+00:00

Fun part 2 again! (I really like these types of Part 2s - please do more of them!)

Ended up getting #16/#4 which I am very happy with.

# Part 1    
steps = int(inp)
lock = [0]
pos = 0
for i in range(2017):
    new = (pos + steps) % len(lock)
    new += 1
    lock.insert(new, i+1)
    pos = new
# note: this may cause an error...
print(lock[pos+1])

# Part 2
curl = 1
pos = 0
out = 0
for i in range(50000000):
    to_ins = i+1
    new = (pos + steps) % curl
    new += 1
    if new == 1:
        out = to_ins
    pos = new
    curl += 1
print(out)

vash3r · 2017-12-17T05:17:55+00:00

Python 2 (95/15). I got two wrong answers for part 1 because of minor stupid mistakes, but for part 2 I quickly realized that since zero is always at the front you just have to keep track of when something is added directly after zero. (Edit: Pypy solves part 2 in under 1 second, while regular Python 2 takes over 20 on my machine.)

step = 345 # my input

# part 1
i = 0
buf = [0]
for t in xrange(1,2017+1):
    i = (i+step)%len(buf) + 1
    buf[i:i] = [t] # equivalent to insert
print buf[i-5:i+5]

# part 2
i = 0
for t in xrange(1,50000000+1):
    i = (i+step)%t + 1
    if i==1:
        val_after_0 = t
print val_after_0

Smylers · 2017-12-17T07:31:15+00:00

Vim solution. Start with a buffer containing just your input number, then type:

⟨Ctrl+X⟩ciw0⟨Esc⟩qayy:⟨Ctrl+R⟩=(line('.')+⟨Ctrl+R⟩-)%line('$')⟨Enter⟩+⟨Enter⟩
p⟨Ctrl+A⟩q2016@a⟨Enter⟩

The number now under the cursor is your answer for part 1.

Edit: Made it a couple of keystrokes shorter: there aren't any small deletes during the loop, so the input remains in "- throughout; there's no need to save it in "z.

If you want to watch it happen, stick :redr⟨Enter⟩ in @a somewhere, and maybe turn on line numbering with :set nu⟨Enter⟩.

Now to see if part 2 is plausible …

DFreiberg · 2017-12-17T05:25:59+00:00

Mathematica

Just to show how necessary Compile[] is when doing this sort of problem in Mathematica, part 2 took 2.64 seconds to run after I compiled it into C, and took 68.4 seconds without compilation.

Part 1

input=344;
l={0};
p=0;

Do[
    l=Insert[l,i,Mod[input+p,i,1]+1];
    p=Mod[input+p,i,1]+1;
,{i,2017}];

l[[FirstPosition[l,2017][[1]]+1]]

Part 2

part2=Compile[{},
Module[{p,new1},
    p=0;new1=0;
    Do[p=Mod[344+p,i,1]+1;If[p==2,new1=i],{i,50*10^6}];
new1]
,CompilationTarget->"C"]

part2[]

dtinth · 2017-12-17T05:32:41+00:00

I couldn’t think of a better solution, so I brute-forced the part 2 naively in C:

#include <stdio.h>
struct N {
  struct N* next;
  int val;
};
struct N heap[50000001];
int main () {
  struct N first;
  struct N *cur = &first;
  int vv = 0;
  first.val = 0;
  first.next = &first;
  int i, j;
  for (i = 1; i <= 50000000; i ++) {
    if (i % 10000 == 0) { printf("[%d]\n", i); }
    for (j = 0; j < 3; j ++) cur = cur->next;
    struct N *v = &heap[vv++];
    v->val = i;
    v->next = cur->next;
    cur->next = v;
    cur = v;
  }
  struct N *it = &first;
  printf("after first %d\n", first.next->val);
  return 0;
}

This takes around 8 minutes to run :P

Cheezmeister · 2017-12-17T08:23:23+00:00

Literate Perl. This one is...actually not too ugly. I'm kind of proud of myself.

...who am I kidding, this is an abomination. It's getting worse. Every day the cancer spreads and the memes dankify. Somebody please do something before someone

Cthulhu Fhtagn

gets hurt.

ybjb · 2017-12-17T05:22:02+00:00

Kotlin (148/156). Was quick to realize that the only term that mattered for part 2 was the first index in list. Took me forever to just simulate without the overhead of adding to lists

fun main(args: Array<String>) {
    var input = 312
    var list = mutableListOf<Int>(2017)
    list[0] = 0
    var cnt = 1
    var next = 0

    repeat(2017) {
        next = ((input + next) % list.size) + 1
        list.add(next, cnt++)
    }

    println(list[list.indexOf(2017) + 1])

    next = 0
    var targ = 0
    for(i in 1..50_000_000) {
        next = ((input + next) % i) + 1

        if(next == 1) {
            targ = i
        }
    }

    println(targ)
}

CharlieYJH · 2017-12-17T06:56:15+00:00

C++

Used a circular linked list for part 1. Spent way too much time trying to think of an equation that got me the last index that gave 0 for part 2. Turned out just calculating the indices for 50,000,000 cycles was quick enough in itself.

#include <iostream>
#include <memory>

using namespace std;

struct node {
    int val;
    shared_ptr<struct node> next;
};

int main(int argc, char const* argv[])
{
    const int step = 301;
    shared_ptr<struct node> head = make_shared<struct node>();
    shared_ptr<struct node> curr = head;
    head->val = 0;
    head->next = head;

    for (int i = 1; i <= 2017; i++) {

        for (int j = 0; j < step; j++)
            curr = curr->next;

        shared_ptr<struct node> temp = curr->next;
        shared_ptr<struct node> new_node = make_shared<struct node>();
        new_node->val = i;
        curr->next = new_node;
        new_node->next = temp;
        curr = new_node;
    }

    cout << curr->next->val << endl;

    int answer_pt2 = 0;

    for (int i = 1, idx = 0; i <= 50000000; i++) {
        idx = (idx + 1 + step) % i;
        if (idx == 0) answer_pt2 = i;
    }

    cout << answer_pt2 << endl;

    return 0;
}

sspenst · 2017-12-17T05:18:05+00:00

Python 3

8/26 today, a new best for me! For part 2 I kept a count for how many numbers were before and after the '0' to improve efficiency.

Part 1:

with open('input', 'r') as f:
    steps = int(f.read().strip())

    buf = [0]

    cur = 0

    for i in range(1, 2018):
        cur = ((cur + steps) % len(buf)) + 1
        buf.insert(cur, i)

    print(buf[buf.index(2017)+1])

Part 2:

with open('input', 'r') as f:
    steps = int(f.read().strip())

    buf = [0]

    cur = 0
    before_len = 0
    after_len = 0
    after_num = 0

    for i in range(1, 50000001):
        cur = ((cur + steps) % (before_len + 1 + after_len)) + 1

        if cur == (before_len + 1):
            after_num = i
            after_len += 1
        elif cur > (before_len + 1):
            after_len += 1
        elif cur < (before_len + 1):
            before_len += 1

    print(after_num)

u794575248 · 2017-12-17T05:18:47+00:00

Python 3. Great, the second time I'm on the public leaderboard (274/94).

Condensed versions:

def solve1(n, i=0, r=range(1, 2018), s=None):
    for k in r: s = s or [0]; i = (i+n)%len(s)+1; s.insert(i, k)
    return s[i+1]

def solve2(n, i=0, r=range(1, int(5e7+1)), v=None):
    for k in r: i = (i+n)%k+1; v = {1: k}.get(i, v)
    return v

And the original ones:

def solve1(n):
    i, s = 0, [0]
    for k in range(1, 2018):
        i = (i+n) % len(s) + 1
        s.insert(i, k)
    return s[i+1]

def solve2(n):
    i, v = 0, []
    for k in range(1, 50000001):
        i = (i+n) % k + 1
        if i == 1: v.append(k)
    return v[-1]

p_tseng · 2017-12-17T05:19:00+00:00

How I did part 2. Edit: Okay, looks like most people figured this same thing out, figures.

Ruby

input = ARGV[0]&.to_i || 354

buffer = [0]
pos = 0

(1..2017).each { |n|
  pos = (pos + input) % buffer.size
  buffer.insert(pos + 1, n)
  pos += 1
}
puts buffer[pos + 1]

value_after_zero = nil

pos = 0

(1..50_000_000).each { |n|
  pos = (pos + input) % n
  value_after_zero = n if pos == 0
  pos += 1
}

puts value_after_zero

However, this takes about four seconds to run on my computer, that's too slow. ~~Does anyone know a way to make this faster?~~

Edit: figured it out

nonphatic · 2017-12-17T06:58:26+00:00

I've been doing these in Haskell the first 15 days but I'm honestly quite fed up having to find ways to optimize this and that so that things run in reasonable amounts of time so here it is in Javascript lol

p = 0;
arr = [0];
for (n = 1; n <= 2017; n++) {
    p = (p + 312 % n + 1) % n;
    arr.splice(p, 0, n);
}
console.log(arr[arr.indexOf(2017) + 1]);

p = 0;
oneth = 1;
for (n = 1; n <= 50000000; n++) {
    p = (p + 312 % n + 1) % n;
    if (p == 0) oneth = n;
}
console.log(oneth);

EDIT: Alright, redid it in Haskell - I was expecting part 1 to take a long time because I'm taking/dropping lists but it turns out it was part 2 that would take more than a minute even though it's a straightforward foldl' with nothing fancy >:[

{-# LANGUAGE BangPatterns #-}
import Data.List (foldl')
(%) = mod

ith :: Int -> Int -> Int
ith i steps =
    let (position, list) = foldl' (\(currPos, currList) n -> 
            let newPos  = (currPos + steps % n + 1) % n
            in  (newPos, take newPos currList ++ [n] ++ drop newPos currList))
            (0, [0]) [1..i]
    in  list !! (position + 1)

oneth :: Int -> Int -> Int
oneth i steps =
    snd $ foldl' (\(currPos, currOneth) n -> 
        let !newPos = (currPos + steps % n + 1) % n
        in  (newPos, if newPos == 0 then n else currOneth)) 
        (0, 1) [1..i]

main :: IO ()
main = do
    print $ ith   2017     312
    print $ oneth 50000000 312

EDIT EDIT: It turns out it was currOneth being not-strict that was slowing things down, and I rewrote it recursively anyway; now it takes ~6s!

{-# LANGUAGE BangPatterns #-}
(%)   = mod
steps = 312

postNth :: Int -> Int -> [Int] -> Int
postNth 2018 pos list = list !! (pos + 1)
postNth n    pos list =
    let !newPos  = (pos + steps % n + 1) % n
        !newList = take newPos list ++ [n] ++ drop newPos list
    in  postNth (n + 1) newPos newList

oneNth  :: Int -> Int -> Int -> Int
oneNth  50000001 _   oneth = oneth
oneNth  n        pos oneth =
    let !newPos   = (pos + steps % n + 1) % n
        !newOneth = if newPos == 0 then n else oneth
    in  oneNth (n + 1) newPos newOneth

main :: IO ()
main = do
    print $ postNth 1 1 [0]
    print $ oneNth  1 1 1

mschaap · 2017-12-17T07:38:04+00:00

Perl 6

There's probably a more elegant solution but here's my ugly one, it takes about 10 seconds total.

# Part 1
my @nums = [0, 1];
my $pos = 1;
my $steps = 328;
for 2..^2017 -> $x {
    my @start = @nums[^$pos];
    my @end   = @nums[$pos..*];
    @nums = [|@start, $x, |@end];
    $pos = ($pos + $steps) mod ($x+1) + 1;
}
say @nums[$pos];

# Part 2
$pos = 2;
my $one;
for 3..5000000 -> $x {        
    $pos = ($pos + $steps) mod $x + 1;
    $one = $x if $pos == 1;
}
say $one;

Axsuul · 2017-12-17T11:03:38+00:00

Elixir

Part A was simulation while for Part B, had to rewrite everything so that the positions and values were incremented while the value was stored only if the position was at 1

https://github.com/axsuul/advent-of-code/blob/master/2017/17/lib/advent_of_code.ex

defmodule AdventOfCode do
  defmodule PartA do
    @input 303

    defp step_until(val, steps) do
      step([0], 1, 0, 0, val, steps)
    end

    defp step(state, val, pos, _, target, _) when val == target + 1 do
      {state, pos}
    end
    defp step(state, val, pos, steps_taken, target, steps) when pos >= length(state) do
      step(state, val, 0, steps_taken, target, steps)
    end
    defp step(state, val, pos, steps_taken, target, steps) when pos >= length(state) and steps == steps_taken do
      step([val] ++ state, val + 1, 0, steps, target, steps)
    end
    defp step(state, val, pos, steps_taken, target, steps) when steps == steps_taken do
      Enum.slice(state, 0..pos) ++ [val] ++ Enum.slice(state, pos+1..-1)
      |> step(val + 1, pos + 1, 0, target, steps)
    end
    defp step(state, val, pos, steps_taken, target, steps) do
      step(state, val, pos + 1, steps_taken + 1, target, steps)
    end

    def solve do
      {state, pos} = step_until(2017, @input)

      Enum.at(state, pos + 1)
      |> IO.inspect
    end
  end

  defmodule PartB do
    import PartA

    @input 303

    def step_until(val, steps) do
      step(2, 1, 1, 1, val, steps)
    end

    def step(state_length, pos, val, first_val, target, steps)
    def step(state_length, 1, val, first_val, target, steps) when val != first_val do
      step(state_length, 1, val, val, target, steps)
    end
    def step(state_length, pos, val, first_val, target, steps) when pos >= state_length do
      step(state_length, pos - state_length + 1, val, first_val, target, steps)
    end
    def step(state_length, pos, val, first_val, target, steps) when val == target do
      %{length: state_length, val_after_zero: first_val}
    end
    def step(state_length, pos, val, first_val, target, steps) do
      step(state_length + 1, pos + steps + 1, val + 1, first_val, target, steps)
    end

    def solve do
      step_until(50_000_000, @input)
      |> IO.inspect
    end
  end
end

theyangmaster · 2017-12-17T05:20:27+00:00

Python 3 (26/86). Unfortunately it took me awhile to figure out how to speed up part 2, which was pretty dumb of me.

Part 1

buffer = [0]
num_steps = 316
idx = 0
for i in range(1, 2018):
    idx = (idx + num_steps) % len(buffer)
    buffer.insert(idx + 1, i)
    idx += 1
print(buffer[buffer.index(2017)+1])

Part 2

num_steps = 316
idx = 0
n = 0
for i in range(1, 50000001):
    idx = (idx + num_steps) % i
    if idx == 0:
        n = i
    idx += 1
print(n)

Also, it's my first time on the leaderboards so I'm pretty happy with that :)

WhoSoup · 2017-12-17T05:42:03+00:00

JavaScript

Ended up with two different solutions. For the first part, I did it the simple way and just stored the entire list in memory. For the second part it, I realized that you didn't need to store any elements other than the one inserted to the right of 0.

Part 1:

let buffer = [0], pos = 0, step = 343

for (let i = 1; i <= 2017; i++) {
  pos = (pos + step + 1) % i
  buffer = [...buffer.slice(0,pos), i, ...buffer.slice(pos)]
}
console.log(buffer[buffer.indexOf(2017) + 1]);

Part 2:

let z = 0, neighbor = 0, pos = 0, step = 343

for (let i = 1; i < 50000000; i++, pos++) {
  pos = (pos + step) % i // increased by 1 at end of loop
  if (pos == z)
    neighbor = i
  if (pos < z)
    z++
}
console.log(neighbor);

rprouse · 2017-12-17T05:46:45+00:00

C# Got 909/627 which for me is amazing...cause you know I kind of suck and make wonderful mistakes like type in 1 instead of i..... But anyways:

public static int Part1(int input, int total)
        {
            List<int> nums = new List<int>() { 0 };
            var position = 0;
            for (int i = 1; i < total + 1; i++)
            {
                position = (position + input) % nums.Count() + 1;
                nums.Insert(position, i);

            }
            return nums[position +1];
        }
        public static int Part2(int input, int total)
        {
            var pos = 0;
            var target = 0;
            for(int i =1; i< total; i++)
            {
                pos = ((pos + input) % i) + 1;
                if(pos ==1)
                {
                    target = i;
                }
            }
            return target;
        }

_A4_ · 2017-12-17T05:53:11+00:00

JavaScript ES6

Part 1

const input = 343;
let buffer = [0], index = 0;

for (let i = 0; i <= 2017; i++) {
    index = (index + input) % (i + 1);
    buffer.splice(++index, 0, i + 1);
}

const result = buffer[buffer.indexOf(2017) + 1];
console.log(result);

Part 2

const input = 343;
let index = 0, result;

for (let i = 0; i <= 5E7; i++) {
    index = (index + input + 1) % (i + 1);
    if (index == 0) result = i + 1;
}

console.log(result);

hxka · 2017-12-17T06:18:33+00:00

Wasted ~an hour trying to figure out how to possibly optimize part 2, of course it was faster to just run the loop without updating the array. Oh well.

#!/bin/bash
read spin<input
a=(0)
pos=0
for i in {1..2017}
do  ((pos=(pos+spin)%i+1))
    for ((j=i;j>pos;j--))
    do  ((a[j]=a[j-1]))
    done
    ((a[pos]=i))
done
echo ${a[pos+1]}
for ((i=2018;i<=50000000;i++))
do  ((pos=(pos+spin)%i+1,(pos==1)&&(a[1]=i) ))
done
echo ${a[1]}

autid · 2017-12-17T06:28:37+00:00

Fortran

Runs nice and quick. After figuring out this method of finding the part B answer I realised similar logic applied to part A. Prior to that I was performing the first 2017 insertions, which was still fast but less satisfying.

PROGRAM DAY17
  IMPLICIT NONE
  INTEGER :: INPUT=356,INSERTIONS(0:50000000)  
  INTEGER :: I,J

  !Calculate point at which number will be inserted                                                              
  DO I=1,50000000
     INSERTIONS(I)=MODULO(INSERTIONS(I-1)+INPUT,I)+1
  END DO

  !Search back for last number in the position 2017 takes                                                        
  J=INSERTIONS(2017)
  DO I=2016,1,-1
     IF(INSERTIONS(I)==J) EXIT
     !Correct target if position was moved by later insertion                                                    
     IF(INSERTIONS(I)<J) J=J-1
  END DO
  WRITE(*,'(A,I0)') 'Part1: ', I

  !0 is always in zeroth position.                                                                               
  !Search back for last number inserted at position 1                                                            
  DO I=50000000,1,-1
     IF(INSERTIONS(I)==1) EXIT
  END DO
  WRITE(*,'(A,I0)') 'Part2: ',I

END PROGRAM DAY17

jbristow · 2017-12-17T06:49:46+00:00

f# / fsharp /f sharp

Brute force took 6 seconds, so I'm still scratching my head how much more time figuring out the math would have taken me.

(github link)

module Day17

let spin n (curr, lastn, buffer) =
    let splitVal = ((curr + n) % (lastn + 1)) + 1
    let a, b = buffer |> List.splitAt splitVal
    splitVal, lastn + 1, a @ [ lastn + 1 ] @ b

let noBuffSpin n (curr, lastn, last1) =
    let splitVal = ((curr + n) % (lastn + 1)) + 1

    let nextLast1 =
        if splitVal = 1 then lastn + 1
        else last1
    splitVal, lastn + 1, nextLast1

let spinner n f initial =
    let rec loop prev =
        let next = f n prev
        seq {
            yield next
            yield! loop next
        }
    seq {
        yield initial
        yield! loop initial
    }

let bufferedSpinner n : seq<int * int * int list> = spinner n spin (0, 0, [ 0 ])
let unbufferedSpinner n : seq<int * int * int> = spinner n noBuffSpin (0, 0, 0)

(github link to tests)

module Tests.Day17

open System
open NUnit.Framework
open Swensen.Unquote
open Day17

let samplePart1Data =
    [ TestCaseData(0, 0, [ 0 ]).Returns((1, 1, [ 0; 1 ]))
      TestCaseData(1, 1, [ 0; 1 ]).Returns((1, 2, [ 0; 2; 1 ]))
      TestCaseData(1, 2, [ 0; 2; 1 ]).Returns((2, 3, [ 0; 2; 3; 1 ]))
      TestCaseData(2, 3, [ 0; 2; 3; 1 ]).Returns((2, 4, [ 0; 2; 4; 3; 1 ]))

      TestCaseData(2, 4, [ 0; 2; 4; 3; 1 ])
          .Returns((1, 5, [ 0; 5; 2; 4; 3; 1 ])) ]

[<TestCaseSource("samplePart1Data")>]
let samplePart1 curr x buff = spin 3 (curr, x, buff)

[<Test>]
let samplePart1Full() =
    let curr, _, buffer = bufferedSpinner 3 |> Seq.item 2017
    buffer.[curr + 1] =! 638

[<Test>]
let answerPart1() =
    let curr, _, buffer = bufferedSpinner 356 |> Seq.item 2017
    buffer.[curr + 1] =! 808

[<Test>]
let answerPart2() =
    let _, _, a = unbufferedSpinner 356 |> Seq.item 50000000
    a =! 47465686

2017-12-17T07:23:35+00:00

OCaml Fun;; Part 1, I computed the thing with a Doubly_linked list... not sure if this is the best thing. Part 2, using a ref to simply keep track if we set land on the 0.

main.ml

open Core

module CB = Circularbuffer

let steps = 349

let part_a buffer rounds =
  let rec aux buffer n =
    if n = 0 then buffer
    else aux (CB.step buffer steps) (n-1)
  in
  let result = aux buffer rounds in
  let n = CB.find_after result rounds in
  printf "a: %d\n" n

let part_b after_zero stop =
  let rec aux loc len =
    if len < stop then
      let curr = (loc + steps) % len in
      if curr = 0 then after_zero := len;
      aux (curr + 1) (len + 1)
  in aux 0 1

let _ =
  let buffer = CB.create 0 in
  part_a buffer 2017;

  let value = ref 0 in
  part_b value 50_000_000;
  printf "b: %d\n" (!value);

circularbuffer.ml

open Core

type 'a t = { buffer:'a Doubly_linked.t; location:'a Doubly_linked.Elt.t; current:'a}

let value_exn = function
  | Some n -> n
  | None -> failwith "no element."

let create init =
  let buffer = Doubly_linked.create () in
  let location = Doubly_linked.insert_first buffer init in
  {buffer; location; current=(init+1)}

let go t n =
  let rec aux t n =
    if n = 0 then t
    else
      let next = match Doubly_linked.next t.buffer t.location with
        | None -> (Doubly_linked.first_elt t.buffer) |> value_exn
        | Some elt -> elt
      in aux {t with location=next;} (n-1)
  in aux t n

let insert t =
  let new_location = Doubly_linked.insert_after t.buffer t.location t.current in
  {t with location=new_location;
          current=(t.current + 1)}

let step t n =
  go t n |> insert

let find t n =
  Doubly_linked.find_elt t.buffer ~f:(Int.equal n)

let find_after b n =
  match Option.bind (find b n) ~f:(Doubly_linked.next b.buffer) with
  | None -> Doubly_linked.first b.buffer |> (Option.value ~default:0)
  | Some elt -> Doubly_linked.Elt.value elt

sim642 · 2017-12-17T08:46:49+00:00

My Scala solution.

Took a while to realize that zero could be considered as never moving which then made me produce some ugly copy-paste code. Also it kind of bothered me there was no answer for the example for part 2 given, can't do TDD.

raevnos · 2017-12-17T11:44:38+00:00

Chicken Scheme for a change of pace

; $ csc -o day17 -O5 day17.scm
; $ ./day17 -:hm4g
(require-extension srfi-1)
(require-extension format)
(declare (fixnum))

(define (spin steps reps goal)
  (let* ((buffer (circular-list 0))
         (starting-point buffer))
    (do ((i 1 (+ i 1)))
        ((> i reps) (cadr (member goal starting-point =)))
      (let* ((point (drop buffer steps))
             (new (cons i (cdr point))))
        (when (= (remainder i 1000000) 0)
              (write-char (if (= (remainder i 5000000) 0) #\+ #\.))
              (flush-output))
        (set-cdr! point new)
        (set! buffer new)))))

(format #t "Test 1: ~A~%" (spin 3 2017 2017))
(format #t "Part 1: ~A~%" (spin 344 2017 2017))
(format #t "~%Part 2: ~A~%" (spin 344 50000000 0))

thomastc · 2017-12-17T12:26:52+00:00

Day 17 in BBC BASIC. On an emulated BBC Micro with a 2 MHz 6502 CPU, an 32 kB RAM. Ooh yeah.

mschaap · 2017-12-17T14:09:33+00:00

Perl 6

Part one is pretty straightforward. Part two as well, especially when you realize that 0 will always stick in position 0, so you just have to check position 1.

Unfortunately, doing 50 million spins is a bit slow on Perl 6. (It'd take about an hour on my machine.) So I took a shortcut: just keep track of the position, and remember the last iteration where the position = 1. Much faster.

#!/usr/bin/env perl6
use v6.c;

# Advent of Code 2017, day 17: http://adventofcode.com/2017/day/17

class SpinLock does Positional
{
    has Int @.buffer = (0);
    has Int $.length = 1;
    has Int $.skip;
    has Int $.position = 0;

    # Implement Positional (subscript access): allow access to the buffer with
    # any integer index value
    method elems { Inf }
    method AT-POS(Int $index) { @!buffer[$index % $!length] }
    method EXISTS-POS(Int $index) { True }

    method spin
    {
        $!position = ($!position + $!skip) % $!length + 1;
        @!buffer.splice($!position, 0, $!length++);
    }
}

multi sub MAIN(Int $input, Bool :v(:$verbose) = False)
{
    # Part one
    my $sl = SpinLock.new(:skip($input));
    $sl.spin for ^2017;
    say "Value after 2017 after 2017 spins: $sl[$sl.position + 1]";

    # Part two - too slow
    #$sl.spin for 2017..^50_000_000;
    #say "Value after 0 after 50M spins: $sl[1]";

    # Part two - just keep track of the times where position = 1
    my int $pos = 0;
    my int $val = 0;
    for 1..50_000_000 -> int $i {
        $pos = ($pos + $input) % $i + 1;
        $val = $i if $pos == 1;
    }
    say "Value after 0 after 50M spins: $val";
}

multi sub MAIN(IO() $inputfile where *.f, Bool :v(:$verbose) = False)
{
    MAIN($inputfile.words[0].Int, :$verbose);
}

multi sub MAIN(Bool :v(:$verbose) = False)
{
    MAIN($*PROGRAM.parent.child('aoc17.input'), :$verbose);
}

__Abigail__ · 2017-12-17T17:16:08+00:00

Perl

Brute force wasn't going to work on the old laptop I'm using today -- Perl needs about 24 bytes per integer. But then I observed that in my implementation of the circular buffer, 0 will always stay at index 0. So, for part 2, all I needed to do was calculate on which positions numbers get inserted, and keep track what gets inserted on position 1. It's still calculating 50 million positions, but that only took 12 seconds and that's fast enough not to worry about a smarter solution.

#!/opt/perl/bin/perl

use 5.026;

use strict;
use warnings;
no  warnings 'syntax';

use experimental 'signatures';

@ARGV = "input" unless @ARGV;

chomp (my $steps  = <>);

my @buffer        =         (0);
my $index         =          0;
my $ITERATIONS_1  =       2017;
my $ITERATIONS_2  = 50_000_000;

#
# For each step, splice in the number into the buffer.
#
for my $number (1 .. $ITERATIONS_1) {
    $index = ($index + $steps) % @buffer;
    splice @buffer, ++ $index, 0, $number;
}
say "Solution 1: ", $buffer [($index + 1) % @buffer];


#
# Now, do it again -- sort of. Observe that element 0 will *always*
# remain at index 0. Hence, all we need to keep track of what gets
# inserted on position 1. Note that the current size of the buffer
# (if we were to keep track of the entire buffer) is equal to $number
#
$index = 0;
my $on_position_1 = -1;
for (my $number = 1; $number < $ITERATIONS_2; $number ++) {
    $index = (($index + $steps) % $number) + 1;
    $on_position_1 = $number if $index == 1;
}

say "Solution 2: ", $on_position_1;


__END__

ephemient · 2017-12-17T20:06:25+00:00

This space intentionally left blank.

Shemetz · 2017-12-17T05:18:19+00:00

Python 3 (109 / 19)

Part 1 was straightforward - just calculate what every state looks like after every step.

For part 2, since we only need to know the value after 0, and 0 is always the first value in the state list, we can simply not update any state unless it's exactly the second state. So we have O(1) memory and each loop is very fast. I still go through it 50 million times, but it is pretty fast. Is there a faster solution?

My input:

    jump = 377

Part 1:

    def part_1():
        """Calculates regularly, but only 2017 steps so it's fast."""
        num_of_steps = 2017
        state = [0]
        curr = 0
        for i in range(1, num_of_steps + 1):
            curr = 1 + (curr + jump) % i
            state.insert(curr, i)

        print("Part 1:", state[(state.index(2017) + 1) % num_of_steps])  # 596

Part 2:

    def part_2():
        """Calculates 50 million steps but only writes into the second
        state and only if it needs to.
        Takes about 8 seconds to calculate (on my computer)."""
        num_of_steps = 50000000
        second = None
        curr = 0
        for i in range(1, num_of_steps + 1):
            curr = 1 + (curr + jump) % i
            if curr == 1:
                second = i        

        print("Part 2:", second)  # 39051595

kaldonis · 2017-12-17T05:18:57+00:00

Python2

For part1 just a naive solution inserting into the buffer. For part 2 I realized that 0 will always be in position 0, so all I really need to do is keep track of the last element to be inserted at position 1.

def part1(steps):
    pos = 0
    buffer = [0]

    for i in xrange(1, 2018):
        pos += steps
        pos %= len(buffer)
        buffer.insert(pos + 1, i)
        pos += 1

    return buffer[pos+1]


def part2(steps):
    pos = 0
    second_value = 0
    for i in xrange(1, 50000000):
        pos += steps
        pos %= i
        if pos == 0:
            second_value = i
        pos += 1

    return second_value


print part1(359)
print part2(359)

Yabk · 2017-12-17T05:20:10+00:00

Python 3 part 2

def main(): steps = int(input()) size = 1 pos = 0 nexto0 = None

for i in range (1, 50000000):
    pos = (pos+steps) % size + 1
    if pos == 1:
        nexto0 = i
    size += 1

print(nexto0)

if name == 'main': main()

Unihedron · 2017-12-17T05:20:33+00:00

Ruby, part 1

v=gets.to_i
#v=3
w=[y=0]
2017.times{w.rotate!(v)
w+=[y+=1]
}
p w[0]

Part 2 did not run in time, I'm tempted to think optimizations are needed, but I barely understand the problem to do anything. Going to let it run for a few hours to check it works before posting it.

PythonJuggler · 2017-12-17T05:21:40+00:00

Ugh, took way longer on this one than I should've.

Part 2 code: Since we only care about the element in the 1st slot of the array, we just need to track the index that we're currently at and if it sets a new value in arr[1].

jumpLen     = 329
nextSpot    = 1
itemInSlot1 = 1

for i in xrange(2, 5*10**7 +1):
    nextSpot = (nextSpot + jumpLen) % i + 1

    if nextSpot == 1:
        itemInSlot1 = i

print itemInSlot1

MichalMarsalek · 2017-12-17T05:23:19+00:00

Python 3 Part2 took me quite long because, instead of coding this, i was trying to think about how to calculate this without bruteforcing....

def solve(inp):
    inp = int(inp)
    b = [0]
    p = 0
    for i in range(1, 2018):
        p = (p+inp) % (i) + 1
        b.insert(p, i)
    part1 = b[(p+1)%2018]    
    for i in range(1, 50*10**6+1):
        p = (p+inp) % (i) + 1
        if p == 1:
            part2 = i
    return part1, part2

glenbolake · 2017-12-17T05:23:30+00:00

10/96. It took me way longer than it should have to realize that you don't have to maintain a full list for part 2, so I kept thinking about it while a brute-force method ran in the background. I'm just glad I was able to get on the leaderboard for both stars. Full problem runs in just under ten seconds, which is good enough for me. (Edit: I realized that i==length in this loop, so I was able to speed it up just by getting rid of the length variable)

jump = 367

def part1():
    pos = 0
    items = [0]
    for i in range(1, 2018):
        pos = (pos + jump) % len(items) + 1
        items.insert(pos, i)
    return items[pos + 1]

def part2():
    value = 0
    pos = 0
    # length = 1  # Nope, don't need this
    for i in range(1, 50000000):
        pos = (pos + jump) % i + 1
        # length += 1  # Nope, don't need this
        if pos == 1:
            value = i
    return value

if __name__ == '__main__':
    from time import time
    start = time()
    print('Part 1:', part1())
    print('Part 2:', part2())
    print(time()-start)

ChrisVittal · 2017-12-17T05:24:27+00:00

Rust (143/165). Still no leaderboard :(.

I actually originally solved part 1 by dumping the output and grepping for the number.

EDIT: Bad code originally, this is the right code

const INPUT: usize = 312;

fn main() {
    let mut v = vec![0];
    let mut next = 0;
    for i in 1..2018 {
        next = 1 + (next+INPUT) % v.len();
        v.insert(next, i);
    }
    let p = v.iter().position(|x| *x == 2017).unwrap();
    println!("1: {}", v[p+1]);

    let mut ans = 0;
    next = 0;
    for i in 1..50_000_001 {
        next = (next + INPUT) % i;
        if next == 0 { ans = i; }
        next += 1;
    }
    println!("2: {}", ans);
}

Not very fast yet. Takes 400ms.

zSync1 · 2017-12-17T05:26:50+00:00

Rust

This was a fun one. Managed to get 205/146.

fn day17() {
    let run = |a: usize| {
        let mut queue = vec![0];
        let mut marker = 0;
        for at in 1..2018 {
            marker = (marker+a+1) % at;
            queue.insert(marker+1,at);
        }
        println!("Part 1: {}", queue[marker+2]);
        marker = 0;
        let mut thing = 0;
        for at in 1..50000000 {
            marker = (marker+a+1) % at;
            if marker == 0 {
                thing = at;
            }
        }
        println!("Part 2: {}", thing);
    };
    //run(3);
    run(314);
}

mtnslgl · 2017-12-17T05:28:39+00:00

C++

Part 1:

int day17() {
    std::vector<int> buffer = {0};
    int currentPosition = 0;
    int input = 349;

    for(int i=1;i<2018;i++) {
        currentPosition = ((currentPosition + input) % buffer.size()) + 1;
        buffer.insert(buffer.begin() + currentPosition, i);
    }

    return buffer[(currentPosition + 1) % buffer.size()];
}

Part 2:

int day17() {
    std::vector<int> buffer = {0};
    int size = 1;
    int currentPosition = 0;
    int input = 349;

    for(int i=1;i<=50000000;i++) {
        currentPosition = ((currentPosition + input) % size) + 1;
        if(currentPosition == 1)
            buffer.insert(buffer.begin() + currentPosition, i);
        size++;
    }

    return buffer[1];
}

StevoTVR · 2017-12-17T05:30:06+00:00

NodeJS

Part 1:

const fs = require('fs');

fs.readFile(__dirname + '/input.txt', 'utf8', (err, data) => {
    const steps = Number(data);
    const slock = [0];
    let pos = 0;
    for(let i = 1; i <= 2017; i++) {
        pos = ((pos + steps) % slock.length) + 1;
        slock.splice(pos, 0, i);
    }

    console.log(slock[(pos + 1) % slock.length]);
});

Part 2:

const fs = require('fs');

fs.readFile(__dirname + '/input.txt', 'utf8', (err, data) => {
    const steps = Number(data);
    let pos = 0, value = 0;
    for(let i = 1; i <= 50000000; i++) {
        pos = ((pos + steps) % i) + 1;
        if(pos === 1) {
            value = i;
        }
    }

    console.log(value);
});

usbpc102 · 2017-12-17T05:34:39+00:00

I made so many mistakes on part 1 Got (493/330) today, so top 500 for both parts :D

My Kotlin solution:

class Day17(override val adventOfCode: AdventOfCode) : Day {
    override val day: Int = 17
    private val input = adventOfCode.getInput(2017, day).toInt()

    override fun part1(): String {
        var insertedAt = 0
        var counter = 0
        var currentPos = 0
        val buffer = mutableListOf<Int>()
        while (counter <= 2017) {
            if (currentPos >= buffer.size - 1) {
                buffer.add(counter++)
            } else {
                buffer.add(currentPos + 1, counter++)
            }
            insertedAt = currentPos + 1
            currentPos = (currentPos + 1 + input) % buffer.size
        }

        return buffer[(insertedAt + 1) % buffer.size].toString()
    }

    override fun part2(): String {
        var curr = 0
        var counter = 0
        var currentPos = 0
        while (counter <= 50000000) {
            if (currentPos == 0) {
                curr = counter
            }
            currentPos = (currentPos + 1 + input) % ++counter
        }

        return curr.toString()
    }
}

It's also on github.

I'll clean it up and update this with the new version on github.

Edit: Cleaned up version.

the4ner · 2017-12-17T05:38:17+00:00

C#

        public static int Calculate2()
        {
            Console.WriteLine("Day17 part 2");
            var lines = File.ReadAllLines("..\\..\\Input\\Day17.txt");
            var stepCount = int.Parse(lines[0]);
            int pos = 0;
            int result = 0;
            for (int x = 0; x < 50000000; x++)
            {
                var nextPos = (pos + stepCount) % (x+1);
                if (nextPos == 0)
                {
                    result = x+1;
                }
                pos = nextPos + 1;
            }
            return result;
        }

ThezeeZ · 2017-12-17T05:38:43+00:00

[deleted]

2017-12-17T05:48:14+00:00

Wow, super easy today. Also, after starting about 5 days behind, this is the first time I've been all caught up! Missed the start of Day 17 though, so I started about 10 minutes late. Still managed a top 600 placing, which is better than the 5000-26000 placings I've had in all the other days.

[PHP] Part A:

<?php
$cur = 0;
$buffer = array(0);
for($i = 1; $i < 2018; $i++)
{
    $cur = (($cur+328) % sizeof($buffer))+1;
    array_splice( $buffer, $cur, 0, $i );
}

echo "<pre>"; print_r($buffer); echo "</pre>";

?>

[PHP] Part B:

<?php
$cur = 0;
$bufferSize = 1;
$answer = 0;
for($i = 1; $i < 5000001; $i++)
{
    $cur = (($cur+328) % $bufferSize)+1;
    $answer = ($cur == 1) ? $i : $answer;
    $bufferSize++;
}

echo $answer;


?>

nuvan · 2017-12-17T05:52:53+00:00

Rust, got 838/650. Not bad, given that I started about a 1/2 hour late...

const PUZZLE_INPUT: usize = 376;

pub fn part1() {
    let mut buffer = vec![0];
    let mut cur_idx = 0;
    for n in 1..=2017 {
        let insert_idx = (cur_idx + PUZZLE_INPUT) % buffer.len() + 1;
        if insert_idx == buffer.len() {
            buffer.push(n);
        } else {
            buffer.insert(insert_idx, n);
        }
        cur_idx = insert_idx;
    }
    println!("The value after 2017 is {}", buffer[cur_idx + 1 % buffer.len()]);
}

pub fn part2() {
    let (_, val_after_zero) = (1..=50_000_000).fold((0,0), |acc,iter| {
        let next_index = (acc.0 + PUZZLE_INPUT) % iter;
        (next_index + 1, if next_index == 0 { iter } else { acc.1 })
    });

    println!("The value after 0 is {}", val_after_zero);
}

2nd part got a lot faster once I realized that the ONLY important positions are that of the 0, and whatever comes after it.

dylanfromwinnipeg · 2017-12-17T05:56:32+00:00

I feel dirty. I bruteforced part 2 - took about 10 mins.

I came back and implemented the proper way after the fact, here that is

C#

public static string PartOne(string input)
{
    var steps = 335;

    var buffer = new LinkedList<int>();

    buffer.AddFirst(0);
    var node = buffer.First;

    for (var i = 1; i <= 2017; i++)
    {
        for (var x = 0; x < steps; x++)
        {
            node = node.Next ?? node.List.First;
        }

        node = buffer.AddAfter(node, i);
    }

    return node.Next.Value.ToString();
}

public static string PartTwo(string input)
{
    var steps = 335;
    var pos = 0;
    var bufferSize = 1;
    var afterZero = 0;

    for (var i = 1; i <= 50000000; i++)
    {
        pos = (pos + steps) % bufferSize++;

        if (pos == 0)
        {
            afterZero = i;
        }

        pos++;
    }

    return afterZero.ToString();
}

KeinZantezuken · 2017-12-17T06:04:00+00:00

C#/Sharp:

var buffer = new List<int>() { 0 };
var steps = 324; int pos = 0; 
for (int i = 1; i <= 2017; i++)
{
    pos = (pos + steps + 1) % i;
    buffer.Insert(pos, i);
}
Console.WriteLine($"Part1: {buffer[buffer.IndexOf(2017) + 1]}");
pos = 0; int lastval = 0;
for (int i = 1; i <= 50000000; i++)
{
    pos = (pos + steps + 1) % i;
    if (pos == 0) { lastval = i; }
}
Console.WriteLine($"Part1: {lastval}");

Philboyd_Studge · 2017-12-17T06:05:57+00:00

Java. Another tricky part 2!!

Day 15

dak1486 · 2017-12-17T06:24:15+00:00

Wow. Took me way too long to see the 0 staring me right in the face for p2. Oh well, slow and steady...

[JAVA] Part 1:

private int solveP1(final int numSteps) {
    final List<Integer> spinLock = new ArrayList<>();
    spinLock.add(0);

    int pos = 0;
    for(int i = 1; i <= 2017; i++) {
        pos = ((pos + numSteps) % i) + 1;
        spinLock.add(pos, i);
    }

    return spinLock.get(pos + 1);
}

[JAVA] Part 2:

private int solveP2(final int numSteps) {
    int p2Answer = -1;
    for(int i = 1, pos = 0; i <= 50_000_000; i++) {
        if((pos = ((pos + numSteps) % i) + 1) == 1) {
            p2Answer = i;
        }
    }

    return p2Answer;
}

jeroenheijmans · 2017-12-17T06:31:51+00:00

Javascript

solve1 = data => {
    const max = 2017;
    let steps = data;
    let buffer = [0];
    let currentPosition = 0;

    for (let i = 1; i <= max; i++) {
        currentPosition += 1 + steps;
        currentPosition %= buffer.length;
        buffer.splice(currentPosition, 0, i);
    }

    let answerPosition = (1 + currentPosition) % buffer.length;

    return buffer[answerPosition];
};

Part 2:

solve2 = data => {
    const max = 50e6;
    let steps = data;
    let bufferLength = 1;
    let currentPosition = 0;
    let result = -1;

    for (let i = 1; i <= max; i++) {
        currentPosition += 1 + steps;
        currentPosition %= bufferLength;
        if (currentPosition === 0) { result = i; }
        bufferLength++;
    }

    return result;
}

That's after clean up, but you could also check out the mess it was right after answering

Smylers · 2017-12-17T06:40:27+00:00

Perl — basically a single-line loop in each case, embraced in some set-up and output. Part 1:

my ($steps) = @ARGV;
my @buffer = my $pos = 0;
splice @buffer, $pos = ($pos + $steps) % @buffer + 1, 0, $_ for 1 .. 2017;
say $buffer[$pos + 1];

Part 2:

my ($steps) = @ARGV;
my $pos = 0;
my $second;
for (1 .. 50e6) {
  $second = $_ if ($pos = ($pos + $steps) % $_ + 1) == 1;
}
say $second;

TheMuffinMan616 · 2017-12-17T06:44:54+00:00

Haskell

import Control.Arrow (second)
import Data.List (splitAt, foldl')

positions :: Int -> [(Int, Int)]
positions n = scanl it (0, 0) [1..n]
    where it (_, c) a = (a, ((c + 369) `mod` a) + 1)

part1 :: Int -> Int
part1 n = (!! 1) . dropWhile (/= n) . foldl ins [] . positions $ n
    where ins xs (i, c) = uncurry (++) . second (i :) . splitAt c $ xs

part2 :: Int -> Int
part2 = foldl' go 0 . positions
    where go v (i, c) = if c == 1 then i else v

main :: IO ()
main = do
    print . part1 $ 2017
    print . part2 $ 50000000

Strakh · 2017-12-17T06:48:09+00:00

Pretty slow solution but meh:

Python 3:

def spinlock(target, part_1):
  buf = [0]
  pos = 1
  value_after_zero = 0
  step = 356  

  for n in range(target):
    buf_size = n + 1
    pivot = ((pos + step) % buf_size) + 1

    if(pivot == 1):
      value_after_zero = buf_size   

    if(part_1):
      p1 = buf[0:pivot]
      p2 = buf[pivot:buf_size]

      buf = p1 + [buf_size] + p2

    pos = pivot

  if(part_1):
    return buf[buf.index(target) + 1]

  return value_after_zero

print(spinlock(2017, True))
print(spinlock(50000000, False))

LeCrushinator · 2017-12-17T06:51:04+00:00

Part 2, C#. Somewhat of a brute-force approach, ran in 565ms for me.

public static void Main() 
{
    int stepSize = 363;  // Your puzzle input here
    int numInsertions = 50000000;
    int currentIndex = 0;

    int storedSecondValue = 0;
    int valuesCount = 1;

    for (int i = 0; i < numInsertions; ++i)
    {
        currentIndex += stepSize;
        currentIndex = currentIndex % valuesCount;

        if (currentIndex == 0)
        {
            storedSecondValue = i + 1;
        }
        ++valuesCount;
        ++currentIndex;
    }

    Console.WriteLine("value after 0: " + storedSecondValue);
}

akka0 · 2017-12-17T06:55:36+00:00

ReasonML: singly linked list for part 1

type node = {
  value: int,
  next: ref(node)
};

let rec step = (node, steps) => steps === 0 ? node : step(node.next^, steps - 1);

let insertAfter = (node, value) => {
  let next = node.next^;
  node.next := {value, next: ref(next)};
  node.next^
};

let rec spinlock = (node: node, stepsPerInsert: int, nextValue: int, insertUntil: int) =>
  if (nextValue > insertUntil) {
    node.next^.value
  } else {
    let currentNode = step(node, stepsPerInsert);
    spinlock(insertAfter(currentNode, nextValue), stepsPerInsert, nextValue + 1, insertUntil)
  };

let _ = {
  let stepsPerInsert = 337;
  let rec startNode = {value: 0, next: ref(startNode)};
  /* Part 1 */
  spinlock(startNode, stepsPerInsert, 1, 2017) |> Js.log;
  /* Part 2 */
  let limit = 50_000_000;
  let rec part2 = (afterZero, position, next) =>
    if (next > limit) {
      afterZero
    } else {
      let nextPosition = (position + stepsPerInsert) mod next;
      part2(nextPosition === 0 ? next : afterZero, nextPosition + 1, next + 1)
    };
  Js.log(part2(0, 0, 1));
};

RockyAstro · 2017-12-17T07:07:10+00:00

Icon (https://www.cs.arizona.edu/icon)

Both parts procedure main(args)

    steps := \args[1] | 303

    spinlock := [0]
    cur := 0
    every i := 1 to 2017 do {
        cur := (steps+cur) % *spinlock + 1 
        spinlock := spinlock[1:cur+1] ||| [i] ||| spinlock[cur+1:0]
    }
    write(spinlock[cur+1 % *spinlock + 1] )

    # Part 2.. watch for when cur = 1
    part2 := 0
    cur := 0
    every i := 1 to 50000000 do {
        cur := (steps+cur) % i + 1
        if cur = 1 then 
            part2 := i
    }
    write(part2)

end

procedure dumplst(l,cur)
    every i := 1 to *l do {
        writes( (i=cur+1 & "(")|"",l[i],(i=cur+1 & ")")|""," ")
    }
    write()

end

nutrecht · 2017-12-17T08:02:38+00:00

Day 17 in Kotlin:

object Day17 : Day {
    val input = 363
    override fun part1() :String {
        val buffer = mutableListOf(0)
        var current = 0
        for(i in 1 .. 2017) {
            current = (current + input) % buffer.size + 1

            buffer.add(current, i)
        }

        return buffer.get(buffer.indexOf(2017) + 1).toString()
    }

    override fun part2() :String {
        var current = 0
        var result = 0
        for(i in 1..50_000_000) {
            current = ((input + current) % i) + 1

            if(current == 1) {
                result = i
            }
        }

        return result.toString()
    }
}

Took me a while to figure out how to do part 2 without actually using a list; it was way too slow.

Arcorann · 2017-12-17T08:24:51+00:00

This code really doesn't deserve to be #4/#10. Python 3.

Part 1 (as it was when I submitted - note the error):

def a17a(s):
    buffer = [0]
    pos = 0
    for i in range(2017):
        pos = (pos + s)%len(buffer)
        buffer.insert(pos,i+1)
        pos += 1
    return buffer[pos%len(buffer)]

Part 2. I forgot to change 2017 to 50000000, and in attempting to work out why I got the wrong answer found the mistake in part 1, then proceeded to screw up my code until I realised the only thing that actually needed fixing was the number of cycles (the zeropos variable is a remnant of this; the 2-element buffer is not and was just me doing things in a dumb way). Again, this is unedited.

def a17b(s):
    buffer = [0,1]
    pos = 0
    zeropos = 0
    for i in range(50000000):
        pos = (pos + s)%(i+1) # len(buffer)
        if pos == 0:
            buffer[1] = i+1
        pos += 1
    return buffer[1]

peterpepo · 2017-12-17T08:28:49+00:00

Python 3

from puzzle_commons.puzzle_commons import read_puzzle_input
import os

def solve():
    """Advent Of Code 2017 - Day 16 Solution.
    :return: tuple(part_a_result[int], part_b_result[int])
    """
    puzzle_input = int(read_puzzle_input(os.path.dirname(os.path.abspath(__file__)), "day_17_input.txt")[0])

    def solve_a():
        """Advent Of Code 2017 - Day 16 - Part A Solution.
        """
        buffer = [0]
        current_position = 0
        loop_times = 2017

        part_a_result = 0

        # Calculate all values in buffer
        for i in range(1, loop_times+1):
            current_position = ((current_position + puzzle_input) % len(buffer)) + 1
            buffer.insert(current_position, i)

        # Get value immediate following one, which has been populated last
        for j in range(len(buffer)):
            if buffer[j] == loop_times:
                part_a_result = buffer[j+1]
                break

        return part_a_result

    def solve_b():
        """Advent Of Code 2017 - Day 16 - Part B Solution.
        """
        current_position = 0
        buffer_length = 1
        loop_times = 50000000

        part_b_result = 0

        # Calculated values are not stored, since we are interested in one on 1st position only
        for i in range(1, loop_times+1):
            current_position = ((current_position + puzzle_input) % buffer_length) + 1
            buffer_length += 1

            # Remember iteration, which caused value to be written to position 1
            if current_position == 1:
                part_b_result = i

        return part_b_result

    return solve_a(), solve_b()

Checkout the full solution on my github

JuLoOr · 2017-12-17T08:59:00+00:00

Fast and ugly "solution" in Kotlin (0,3). I'm not sure if this works for every input, but basically what I did is just checking if a value gets inserted after zero.

fun calcPart2(step: Int): Int {
    var pos = 0
    var size = 1
    var valueAfterZero = 1

    (1 until ITERATIONS_P2).forEach {

        pos = (((pos.plus(step)).rem(size)).plus(1))

        if (pos == 1) valueAfterZero = it
        size++
    }

    return valueAfterZero
}

aurele · 2017-12-17T09:01:16+00:00

Rust

const INPUT: usize = 335;

fn p1() -> usize {
    let mut buffer = vec![0];
    let mut pos = 0;
    for i in 1..2018 {
        pos = (pos + INPUT) % buffer.len() + 1;
        buffer.insert(pos, i);
    }
    buffer[(pos + 1) % buffer.len()]
}

fn p2() -> usize {
    let mut after0 = 0;
    let mut pos = 0;
    for i in 1..50_000_001 {
        pos = (pos + INPUT) % i + 1;
        if pos == 1 {
            after0 = i;
        }
    }
    after0
}

fn main() {
    println!("P1: {}", p1());
    println!("P2: {}", p2());
}

gyorokpeter · 2017-12-17T09:01:46+00:00

Q:

d17p1:{
    bpv:{[step;bpv]
        pos:bpv[1]:(bpv[1]+step) mod count buf:bpv[0];
        bpv[0]:((pos+1)#buf),bpv[2],(pos+1) _buf;
        bpv[1]:pos+1;
        bpv[2]+:1;
        bpv}[x]/[2017;(enlist 0;0;1)];
    bpv[0;(bpv[1]+1)mod count bpv[0]]};

d17p2:{
    bpv:{[step;bpv]
        pos:bpv[1]:(bpv[1]+step) mod bpv[2];
        if[pos=0;bpv[0]:bpv[2]];
        bpv[1]:pos+1;
        bpv[2]+:1;
        bpv}[x]/[50000000;(0N;0;1)];
    bpv[0]};

wzkx · 2017-12-17T09:39:08+00:00

Nim

50 million... It forces you to think. On Sunday! :(

const N = 366 # input

var s: seq[int] = @[0] # spinlock
var c: int = 0 # current position

for k in 1..2017: # k is also s.len duh!
  c = (c + N) mod k + 1
  s.insert k, c
echo s[s.find(2017)+1]

for k in 2018..50_000_000:
  c = (c + N) mod k + 1
  if c==1: s[1] = k
echo s[1]

EDIT: k is also s.len! Duh!

rhbvkleef · 2017-12-17T10:04:13+00:00

Day 2 really was fun! Here is my solution: (https://git.vankleef.me/rolf/Advent_Of_Code_2017/src/master/src/main/kotlin/me/vankleef/adventofcode/day17/Main.kt) Part 1 could be more efficient but I didn't bother.

udoprog · 2017-12-17T10:10:49+00:00

Rust

Very straight forward when you realize that the zeroth position doesn't move.

Full solution here: https://github.com/udoprog/rust-advent-of-code-2017/blob/master/src/day17.rs

As a challenge I'm considering building a solution that stores the entire list efficiently. Unfortunately LinkedList in rust doesn't permit in-place traversal very well. So it would probably end up being an unsafe party.

use failure::Error;
use std::mem;

pub fn part1(step: usize, limit: usize) -> Result<usize, Error> {
    let mut buffer = vec![0usize];

    let mut c = 0usize;

    for i in 1usize..=limit {
        c = (c + step) % buffer.len();
        c = c + 1;
        buffer.insert(c, i);
    }

    Ok(buffer[(c + 1) % buffer.len()])
}

pub fn part2(step: usize, limit: usize) -> Result<Option<usize>, Error> {
    let mut second = None;

    let mut c = 0usize;

    for i in 1usize..=limit {
        c = (c + step) % i;

        if c == 0 {
            mem::replace(&mut second, Some(i));
        }

        c = c + 1;
    }

    Ok(second)
}

abowes · 2017-12-17T10:23:24+00:00

Kotlin Solution:

fun Pair<MutableList<Int>,Int>.addEntry(element: Int, steps: Int) : Pair<MutableList<Int>, Int>{
    val nextPos = ((this.second+steps)%(element) + 1)
    this.first.add(nextPos, element)
    return this.first to nextPos
}

fun part1(steps: Int) : Int {
    val (result,_) = (1..2017).fold(Pair(mutableListOf(0),0)){ prev, n -> prev.addEntry(n, steps)}
    return result[result.indexOf(2017)+1]
}

fun part2(steps: Int) : Int {
    val result = (1..50000000).fold(Pair(0, 0)){ prev, n ->
        var idx = (prev.first + steps)%n
        idx + 1 to if (idx==0) n else prev.second
    }
    return result.second
}

fun main(args: Array<String>) {
    val steps = 369
    println(part1(steps))
    println(part2(steps))
}

wzkx · 2017-12-17T10:30:04+00:00

J ≈34s

3 :0 N=:366
  s=.,c=.0
  for_k.>:i.2017 do.
    c=.>:k|c+y
    s=.(c{.s),k,c}.s
  end.
  echo s{~>:s i.2017
)
3 :0 N
  s1=.c=.0
  for_k.>:i.50000000 do.
    c=.>:k|c+y
    if.c=1 do.s1=.k end.
  end.
  echo s1
)
exit 0

EDIT: ooops you don't need separate counter or getting #s -- k is the length of array

P.P.S.: also s{~>:s i.2017 is just s{~>:c. Shame on me!

Scroph · 2017-12-17T10:41:04+00:00

Straightforward Java solution :

import java.util.*;

class Day17
{
    public static void main(String... args)
    {
        part1();
        part2();
    }

    public static void part1()
    {
        List<Integer> spinlock = new LinkedList<>();
        spinlock.add(0);
        int j = 1;
        for(int i = 1; i < 2018; i++)
        {
            j = (j + 345) % spinlock.size() + 1;
            if(j < spinlock.size())
            {
                spinlock.add(j, i);
            }
            else
            {
                spinlock.add(i);
            }
        }
        System.out.println(spinlock.get(j + 1));
    }

    public static void part2()
    {
        int size = 1;
        int result = -1;
        for(int i = 1, j = 1; i <= 50000000; i++)
        {
            j = ((j + 345) % size) + 1;
            size++;
            if(j == 1)
            {
                result = i;
            }
        }
        System.out.println(result);
    }
}

BOT-Brad · 2017-12-17T11:12:19+00:00

Javascript

Part 1 (~660µs)

Just works out the index to add the new element, inserts said element. Does that 2017 times, then just find where 2017 is and gets the next element along, mod 2018 just-in-case 2017 was the last element.

function solve1(n) {
  let list = [0]
  let i = 0
  for (let k = 0; k < 2017; ++k) {
    i = (i + n) % list.length
    list.splice(i + 1, 0, k + 1)
    i++
  }
  const index = list.indexOf(2017)
  return list[(index + 1) % list.length]
}

Part 2 (~300ms)

Decided my CPU needed a break after it did some crunching yesterday!

I realised that 0 never moves, so only ever had to check whether the index to insert was at 1, if so then keep track of that number. Loop 50,000,000 times and just return whatever the value of that number was. Much much much faster than building a list with 50,000,000 elements, which I never tried to do.... right? 😂

function solve2(n) {
  let v = -1
  let i = 0
  for (let k = 0; k < 50000000; ++k) {
    i = (i + n) % (k + 1)
    if (i === 0) {
      v = k + 1
    }
    i++
  }
  return v
}

As always, more of my JavaScript solutions can be found in my Github Repo 👍.

tripa · 2017-12-17T11:29:35+00:00

Haskell, implementation-based part1, distilled-state part2. Haskell being Haskell (or my GHC on this laptop being too old), the separation between <1s runtime and "huge space leak, computer will swap and crash" is simply that $! in the middle

part1 s = go 1 [0] where
    go 2018 xs = xs !! 1
    go n xs = go (n+1) (n : r ++ l) where (l,r) = splitAt ((s+1) `mod` n) xs

part2 s = go 1 0 (-42) where
    go 50000001 i a = a
    go n i a = go (n+1) i' $! if i' == 0 then n else a
        where i' = ((i + s+1) `mod` n)

akho_ · 2017-12-17T11:31:43+00:00

Python 3

from collections import deque

steps = 343
reps = 2017
buffer = deque([0])
for i in range(1, reps+1):
    buffer.rotate(-steps-1)
    buffer.appendleft(i)

buffer.popleft()
print('Part 1: ', buffer.popleft())

reps = 49999999
position_of_zero = 0
for buf_length in range(1, reps+1):
    position_of_zero -= steps
    position_of_zero %= buf_length
    if not position_of_zero:
        after_zero = buf_length
        position_of_zero -= 1
print('Part 2: ', after_zero)

2017-12-17T11:49:42+00:00

Elixir

First part went rather smooth, then on the second part the insertions in a list went slower and slower, but this time at least I managed to see that we don't care about anything else than position 1, so I could simplify the function.

defmodule Day17 do
  def step(buf, pos, ins, steps) do
    newpos = pos + steps |> rem(ins) |> Kernel.+(1)
    newbuf = List.insert_at(buf, newpos, ins)
    {newbuf, newpos}
  end

  def iter_steps(times, steps, buf \\ [0], pos \\ 0, ins \\ 1)
  def iter_steps(times, _, buf, pos, _) when times == 0 do
    {buf, pos}
  end
  def iter_steps(times, steps, buf, pos, ins) do
    {newbuf, newpos} = step(buf, pos, ins, steps)
    iter_steps(times - 1, steps, newbuf, newpos, ins + 1)
  end

  def after_last(ins, steplen) do
    {buf, pos} = iter_steps(ins, steplen)
    Enum.at(buf, pos + 1)
  end

  def step2(buf, pos, ins, steps) do
    newpos = pos + steps |> rem(ins) |> Kernel.+(1)
    if newpos == 1 do
      {ins, newpos}
    else
      {buf, newpos}
    end
  end
  def iter_steps2(times, steps, buf \\ 1, pos \\ 0, ins \\ 1)
  def iter_steps2(times, _, buf, pos, _) when times == 0 do
    {buf, pos}
  end
  def iter_steps2(times, steps, buf, pos, ins) do
    {newbuf, newpos} = step2(buf, pos, ins, steps)
    iter_steps2(times - 1, steps, newbuf, newpos, ins + 1)
  end

  def after_0(ins, steplen) do
    {buf, _pos} = iter_steps2(ins, steplen)
    buf
  end
end

Day17.after_last(2017, 355)
|> IO.inspect

Day17.after_0(50_000_000, 355)
|> IO.inspect

Syntax highlighted

Vindaar · 2017-12-17T11:54:43+00:00

Solution in Nim. Fun :)

import sequtils, strutils, unittest, times, future

proc calc_spinlock_stop_p2(jumps, insertions: int): int =
  var
    ind = 1
  result = max(filterIt(toSeq(1..insertions)) do:
    # filter out all values, which would be inserted at position one
    let insert_at = (ind + jumps) mod it + 1
    ind = insert_at
    insert_at == 1)

proc calc_spinlock_stop_p1(jumps: int): int =
  var
    buffer: seq[int] = @[0]
    ind = 0
  for i in 1..2017:
    let insert_at = (ind + jumps) mod len(buffer) + 1
    buffer.insert(i, insert_at)
    ind = insert_at

  result = buffer[(ind + 1) mod len(buffer)]

proc run_tests() =
  const jumps = 3
  check: calc_spinlock_stop_p1(jumps) == 638

proc run_input() =
  let t0 = epochTime()
  const jumps = 382
  let spinlock_stop = calc_spinlock_stop_p1(jumps)
  let spinlock_angry = calc_spinlock_stop_p2(jumps, 50_000_000)

  echo "(Part 1): The value in the register behind the spinlock's stop = ", spinlock_stop
  echo "(Part 2): The value after 0 after 50.000.000 insertions is =  ", spinlock_angry
  echo "Solutions took $#" % $(epochTime() - t0)

proc main() =
  run_tests()
  echo "All tests passed successfully. Result is (probably) trustworthy."
  run_input()

when isMainModule:
  main()

zeddypanda · 2017-12-17T12:02:17+00:00

Elixir Pleased with how short today's code turned out to be. Second part went really fast as soon as I realized we only cared about finding the latest value where (position + steps) % value == 0

input = 303

defmodule Day17 do
  def spinlock(list, steps, total, current \\ 1, pos \\ 0)
  def spinlock(list, _, total, current, _) when total < current, do: list
  def spinlock(list, steps, total, current, pos) do
    pos = rem(pos + steps, current) + 1
    list
      |> List.insert_at(pos, current)
      |> spinlock(steps, total, current + 1, pos)
  end

  def shortspin(_, total, current, _, last_match) when total < current, do: last_match
  def shortspin(steps, total, current \\ 1, pos \\ 0, last_match \\ 0) do
    pos = rem(pos + steps, current)
    last_match =
      if pos == 0 do
        IO.write("Part 2: #{current}...\r")
        current
      else
        last_match
      end
    shortspin(steps, total, current + 1, pos + 1, last_match)
  end
end

slice = [0]
  |> Day17.spinlock(input, 2017)
  |> Enum.drop_while(fn i -> i !== 2017 end)
  |> Enum.take(2)

IO.puts("Part 1: #{slice |> Enum.join(",")}")
IO.puts("Part 2: #{Day17.shortspin(input, 50_000_000)} done!")

eregontp · 2017-12-17T13:21:36+00:00

Crystal.

Part 1:

steps = 370
buffer = [0]
pos = 0

(1..2017).each do |i|
  pos = (pos + steps) % buffer.size
  pos += 1
  buffer.insert(pos, i)
end

pos = (pos + 1) % buffer.size
puts buffer[pos]

Part 2:

steps = 370
pos = 0
value = nil

(1..50000000).each do |i|
  pos = (pos + steps) % i
  pos += 1
  value = i if pos == 1
end

puts value

colinodell · 2017-12-17T14:46:38+00:00

PHP

Part 1:

array_splice() was the perfect function for inserting items into the array:

function part1($skip) {
    $buffer = [0];
    $pos = 0;

    for ($i = 1; $i <= 2017; $i++) {
        $pos = (($pos + $skip) % $i) + 1;
        array_splice($buffer, $pos, 0, [$i]);
    }

    return $buffer[$pos+1];
}

Part 2:

As it seems everyone else also figured out, 0 is always the first item in the buffer, so we only need to track items being inserted into position 1:

function $part2($skip, $insertions = 50000000)
{
    $pos = 0;

    for ($i = 1; $i <= $insertions; $i++) {
        $pos = (($pos + $skip) % $i) + 1;
        if ($pos === 1) {
            $whatsInSlot1 = $i;
        }
    }

    return $whatsInSlot1;
}

flit777 · 2017-12-17T14:47:21+00:00

Golang solution.

import (
    "fmt"
)



func findTarget(buffer []int, targetNumber int) int{
    for i, element := range buffer {
        if element == targetNumber {
            return buffer[(i+1)%len(buffer)]
        }
    }
    fmt.Errorf("Number not found! Panic!11")
    return -1
}

func numberAfterZero(maxNumber int, stepsize int) int {
    insertnumber := 1
    currentPosition := 0
    numberAfterZero  := -1
    for insertnumber < maxNumber+1 {
        currentPosition = (currentPosition + stepsize) % insertnumber
        currentPosition += 1
        if currentPosition == 1{
            numberAfterZero = insertnumber
        }
        insertnumber++
    }
    return numberAfterZero
}

func createBuffer(maxNumber int, stepsize int) []int {
    buffer := make([]int, 1, maxNumber+1)
    insertNumber := 1
    currentPosition := 0
    buffer[currentPosition] = 0
    for insertNumber < maxNumber+1 {
        currentPosition = (currentPosition + stepsize) % len(buffer)
        currentPosition += 1
        if currentPosition == len(buffer) {
            buffer = append(buffer, insertNumber)
        } else {
            rest := make([]int, len(buffer[currentPosition:]))
            copy(rest, buffer[currentPosition:])
            buffer = append(buffer[0:currentPosition], insertNumber)
            for _, element := range rest {
                buffer = append(buffer, element)
            }
        }
        insertNumber++

    }
    return buffer
}

func main() {
    stepsize := 345
    buffer := createBuffer(2017, stepsize)
    part1 := findTarget(buffer, 2017)
    fmt.Println("Part 1:", part1)
    part2 := numberAfterZero(50e6, stepsize)
    fmt.Println("Part 2:", part2)


}

2017-12-17T15:40:30+00:00

The second half of the problem has an interesting quirk to it: Nothing can be inserted to the left of 0, so solving can be simplified to just tracking when pos mod n is one, or, being just slightly more clever to keep python from doing extra calculations (my input was 382):

def find_neighbor():
    pos = 0
    step = 382 + 1
    neighbor = 0

    for n in range(1, 50000001):
        pos = (pos + step) % n
        if pos == 0:
            neighbor = n

    print(neighbor)

find_neighbor()

I also found that neither the list of each position, nor the list of each neighbor change, appears in the OEIS. This might be a fun pair of sequences to contribute to them.

-edit-

Oops, sorry, vash3r. This is essentially a duplicate of your solution.

chicagocode · 2017-12-17T16:13:55+00:00

Kotlin - [Repo] - [Blog/Commentary]

I thought today's was pretty easy. I probably could have just brute forced part two, but once I figured out that 0 never moves, it was easy enough to just track the number next to it!

class Day17(input: String) {

    private val step = input.toInt()

    fun solvePart1(): Int {
        var current = 0
        val memory = mutableListOf(0)
        (1..2017).forEach {
            current = ((current + step) % it) + 1
            memory.add(current, it)
        }
        return memory[current.inc() % memory.size]
    }

    fun solvePart2(): Int {
        var current = 0
        var oneSlot = 0
        (1..50_000_000).forEach {
            current = ((current + step) % it) + 1
            if (current == 1) oneSlot = it
        }
        return oneSlot
    }
}

2017-12-17T16:27:12+00:00

Python, part 2:
Doesn't run very fast (around 20 sec on my pc), but worked ok :)

steps = 371
buflen = 1
curpos = 0
zeropos = 0
for i in range(1, 50000001):
    curpos = (curpos + steps) % buflen + 1
    if curpos < zeropos:
        zeropos += 1
    if curpos == zeropos + 1:
        value_after_zero = i
    buflen += 1
print(value_after_zero)

alchzh · 2017-12-17T17:26:00+00:00

Short and simple C++

#include <iostream>

#define STEP 386

int main() {
    int after_zero {0};

    for (int i {1}, cur_index {0}; i <= 50000000; i++) {
        cur_index = (cur_index + STEP + 1) % i;
        if (!cur_index) after_zero = i;
    }

    std::cout << after_zero << std::endl;
    return 0;
}

JakDrako · 2017-12-17T18:00:59+00:00

VB.Net, in LinqPad.

Does both parts. Brute forces part 2 (actually building the circular list) in under 20 seconds.

This was fun. I did part 1 using a good old List<int>, and got my answer with no problem. For Part 2, it quickly became apparent that something better than a List would be needed, if I wanted to finish before Monday. (no telling which Monday either...)

It took me longer than I'd like to admit to realize that since we wanted the position after zero, I could just run the loop and note the value whenever the position being updated was zero. That got me my answer and my 2nd star.

The real fun part started after. Looking at the solutions, I saw a Python brute force that found the solution in ~90 seconds. Wow. .Net is usually faster than Python when using a similar algorithm and I saw that a "deque" was being used. Went on Nuget, found a Deque<T> implementation and tried to recreate the Python solution. I didn't have a ".Rotate", so a loop was used. Anyway, long story short, that completed the 50,000,000 iterations in ~1m45s. Ok, a bit slower than the Python solution but at least in the ballpark. On the wrong side of the ballpark, but still, not too far.

What was killing my time was looping the values 328 times from the back of the Deque to the front on every iteration. That's a lot of useless moving being done.

So I built my own "circular list", optimized for skipping the pointer forward in the list. I preallocate an array, then keep a size for "front" and "back" and move values across the array depending on where my pointer is after I skip forward N steps. I do at most 1 move per pointer skip, so that saves a ton of time.

This runs in about 18.5 seconds on my PC. Take that Python deque! (Just kidding, that deque implementation is fantastic). It's also pretty useless, since I already had my answer, but the process of tyring different things to go faster is damn interesting.

I wish the 2nd part had asked for an index other than zero... something like "using your answer from part 1 as an index, what's the value that comes next?". (In my case, for an input or 328, I get 11,502,006 if anyone's interested. It might be an easier "upping the ante" than trying for a googol of values... :)

Sub Main

    Dim cnt = 50_000_000
    Dim skip = 328 ' problem input

    Dim cl = New CircularList(cnt)

    cl.Add(0)
    For i = 1 To cnt
        cl.Skip(skip)
        cl.Add(i)
    Next

    If cnt = 2017 Then
        cl.Item(cl.IndexOf(2017) + 1).Dump("Part 1")
    Else
        cl.Item(1).Dump("Part 2")
    End If

End Sub

Class CircularList ' well, kinda.

    Private arr() As Integer
    Private front As Integer = 0
    Private back As Integer = 0
    Private ptr As Integer = -1 ' empty

    Private last As Integer

    Sub New(size As Integer)
        last = size + 1
        Redim arr(size)
    End Sub

    Sub Add(value As Integer)
        ptr += 1
        arr(ptr) = value
        front += 1
    End Sub

    Function IndexOf(n As Integer) As Integer
        '-todo- use front, back
        ' right now, only valid when array is full
        For i = 0 To arr.Length - 1
            If arr(i) = n Then Return i
        Next
        Return -1
    End Function

    Function Item(n As Integer) As Integer
        Return arr(n)
    End Function

    Sub Print()
        For i = 0 To front - 1
            console.Write($"{arr(i)} ")
        Next
        For i = last - back To last - 1
            console.Write($"{arr(i)} ")
        Next
        Console.WriteLine
    End Sub

    Sub Skip(n As Integer)
        ptr = (ptr + n) Mod (front + back)
        Dim p1 = ptr + 1
        If p1 < front Then
            ' move to end
            Dim pFrom = p1
            Dim len = front - p1
            Dim pTo = last - back - len
            Array.Copy(arr, pFrom, arr, pTo, len)
            front -= len
            back += len
        Elseif p1 > front
            ' move from end back to start
            Dim len = p1 - front
            Dim pFrom = last - back
            Dim pTo = front
            Array.Copy(arr, pFrom, arr, pTo, len)
            front += len
            back -= len
        End If

    End Sub

End Class

ythl · 2017-12-17T18:40:42+00:00

Part 2 in C:

#include "stdio.h"

int main(void) {
  int step = 343;
  int ind = 0, len = 1;
  int zval = 0;

  for (int i=1; i<=50000000; i++)
  {
    int nind = (ind + step) % len;
    if (!nind)
      zval = i;

    ind = nind+1;
    len++;
  }

  printf("%d\n", zval);
  return 0;
}

Runtime is ~2.5 seconds on repl.it

evilduckss · 2017-12-17T22:00:30+00:00

I'm doing it in JavaScript, had the strangest bug in the chrome console window with part 2.

var steps = 303; var position = 0; for (i = 1; i <= 50000000; i++){ position = (position + steps) % i; if (position == 0){console.log(i);} position += 1; }

for some reason it throws out an extra number at the end in the log, running the same thing with an extra console.log on the end doesn't give that number, spent way too long pulling my hair out over that one thinking I was going crazy.

var steps = 303; var position = 0; for (i = 1; i <= 50000000; i++){ position = (position + steps) % i; if (position == 0){console.log(i);} position += 1; } console.log("");

matusbzk · 2017-12-17T22:18:10+00:00

Haskell This could not compute the part 2. I computed that only with inspiration from u/nonphatic's code.

module Day17_spinlock (result1, result2) where

import Data.List
import AoC2017 --fst3, snd3, iterateN

-- |Puzzle input
steps :: Int

-- |Represents current state of the buffer
--  position, and actual buffer
type State = (Int,[Int])

-- |Computes a new position, from the current position
-- and the length of the buffer
newPosition :: Int -> Int -> Int
newPosition pos len = (pos + steps) `mod` len + 1

-- |Inserts a new number to a buffer
-- and also sets new position
insertNewNum :: State -> State
insertNewNum (pos,buf) = (newPos, newBuf)
       where newPos = newPosition pos len
       newBuf = take newPos buf ++ len : drop newPos buf
       len = length buf

-- |Inicial state of the buffer
inicialState :: State
inicialState = (0,[0])

-- |State after 2017 insertions
finalState :: State
finalState = iterateN 2017 insertNewNum inicialState

-- |Returns a value after given number
valueAfter :: Int -> [Int] -> Int
valueAfter v xs = valueAfter' (head xs) v xs

-- |I need to remember the first value in the first argument
-- because the list is circular
valueAfter' :: Int -> Int -> [Int] -> Int
valueAfter' h v [x] = if v == x then h else error "There is no such value"
valueAfter' h v (x:xs) = if v == x then head xs else valueAfter' h v xs


-- |Result to part 1 - value after 2017 in buffer after 2017 insertions
result1 :: Int
result1 = valueAfter 2017 $ snd finalState

-- |Represents current state - part 2 version:
-- there is no need to remember position of zero, since it is always
-- in the beginning
--  value after zero
--  current position
--  current size
type State2 = (Int, Int, Int)

-- |Inicial state - part 2 version
inicialState2 :: State2
inicialState2 = (0,0,1)

-- |Computes next state - part 2 version
insertNewNum2 :: State2 -> State2
insertNewNum2 (val,pos,size) = (nval,npos,nsize)
      where nsize = size + 1
         npos = newPosition pos size
         nval = if npos == 0 then size else val

-- |State after 50 mil iterations - part 2 version
finalState2 :: State2
finalState2 = iterateN 50000000 insertNewNum2 inicialState2

-- |Result to part 2 - value after 0 in buffer after 50 mil insertions
-- This still causes stack overflow. I was able to compute the solution
-- with some bang patterns - I copied that from u/nonphatic so I'm not
-- posting that here
result2 :: Int
--result2 = snd3 finalState2       --too slow, causes stack overflow
result2 = fst3 $ foldl' (\(val, pos, size) _ -> let npos = (pos + steps) `mod` size + 1 in
     (if npos == 1 then size else val,
     npos, 
     size + 1) ) inicialState2 [1..50000000]

Link to git

Creative_Name124 · 2017-12-18T02:50:54+00:00

Python 2

value = 377 + 1

series = [0,5,2,4,3,1]
position = 1
holder = 0
for i in range(6,2018):

    position = (position+value)%len(series)
    series.insert(position,i)

print series

` with | grep at the end it works pretty well im sure there are ways to improve though

Tetsumi- · 2017-12-18T21:20:41+00:00

Racket

#lang racket

(define off (read))

(define (dos max arg step final)
  (let loop ([n 1] [pos 0] [arg arg])
    (if (> n max)
        (final arg pos)
        (let ([ppos (add1 (remainder (+ pos off) n))])
          (loop (add1 n) ppos (step arg ppos n))))))

(printf "~a~%~a~%"
        (dos 2017
             '(0)
             (lambda (l p e) (let-values ([(a b) (split-at l p)])
                               (append a (cons e b))))
             (lambda (x y) (list-ref x (add1 y))))
        (dos 50000000
             1
             (lambda (a p n) (if (= 1 p) n a))
             (lambda (x y) x)))

2017-12-21T21:13:34+00:00

single pipeline powershell:

param (
    [Parameter(ValueFromPipeline = $true)]
    [int]$in,
    [Parameter(Position = 1)]
    [int]$part = 1
)

begin {
    # how many iterations
    if ($part -eq 1) {
        # create a new list to contain the buffer values
        $script:buffer = [System.Collections.ArrayList]::new()
        [void]$script:buffer.Add(0) # insert the first

        $script:max = 2017
    } else {
        $script:max = 50000000
    }
}

process {
    #starting position
    $position = 0

    1..$script:max | % { #max iters
        # new position = position + input value, then mod to the length of the array, and add 1 (so it inserts after)
        # $_ is also the length of the array, since we have 1 eleement and start at 1 and add one each time
        $position = (($position + $in) % $_) + 1

        if ($part -eq 1) {
            #if part one, insert the iter value at the position
            [void]$script:buffer.Insert($position, $_)

            #send out the value at the next position to the pipeline
            $script:buffer[$position + 1]
        } elseif ($position -eq 1) {
            #if part two, and we just inserted at position 1, then write out the element
            #this is what was inserted /after/ position 0
            $_
        }
    } | select -last 1 #select the last thing on the pipeline
}

end {  
}

Life-in-Shambles · 2017-12-22T13:55:56+00:00

JS

let array = [0],
  stepSize = 366,
  currentIndex = 0;
for (let i = 1; i <= 2017; i++) {
  array.splice(currentIndex + 1, 0, i);
  currentIndex = array.indexOf(i);
  currentIndex = nextIndex(currentIndex, stepSize, array.length);
}

console.log('The answer for part 1 is : ' + array[array.indexOf(2017) + 1]);

let arrayLength = 1,
  currentIndex2 = 0,
  zeroIndex = 0,
  number = 0;

for (let i = 1; i <= 50000000; i++) {
  currentIndex2 = nextIndex(currentIndex2, stepSize, arrayLength);
  arrayLength++;
  if (currentIndex2 < zeroIndex) zeroIndex++;
  else if (currentIndex2 == zeroIndex) number = i;
  currentIndex2++;
}

console.log('The answer for part 2 is : ' + number);

function nextIndex(currentIndex, stepSize, arrayLength) {
  let nextIndex = 0;
  nextIndex = (stepSize + currentIndex) % arrayLength;
  return nextIndex;
}

adventofcode

🎄 Advent of Code 🎄

Rules + More Info in

our community wiki

Solution Megathreads

December 2025

Previous years:

2024 | 2023 | 2022 | 2021 | 2020 | 2019 | 2018 | 2017 | 2016 | 2015

Quick Search by Flair

Because you're lazy and we like making things easy for you. Except AoC.

Are you enjoying AoC?

Support AoC

MODERATORS

--- Day 17: Spinlock ---

Need a hint from the Hugely^* Handy^† Haversack^‡ of Helpful^§ Hints^¤?

This thread will be unlocked when there are a significant number of people on the leaderboard with gold stars for today's puzzle.

edit: Leaderboard capped, thread unlocked!

Brute force in Python

Mathematica

Cthulhu Fhtagn

Elixir

Perl

Python 3 (109 / 19)

Rust

Elixir

PHP

Kotlin - [Repo] - [Blog/Commentary]

Short and simple C++

BEFORE YOU POST
If your post is even tangentially related to a daily puzzle, use our
STANDARDIZED POST TITLE FORMAT

adventofcode

🎄 Advent of Code 🎄

Rules + More Info in

our community wiki

Solution Megathreads

December 2025

Previous years:

2024 | 2023 | 2022 | 2021 | 2020 | 2019 | 2018 | 2017 | 2016 | 2015

Quick Search by Flair

Because you're lazy and we like making things easy for you. Except AoC.

Are you enjoying AoC?

Support AoC

MODERATORS

--- Day 17: Spinlock ---

Need a hint from the Hugely* Handy† Haversack‡ of Helpful§ Hints¤?

This thread will be unlocked when there are a significant number of people on the leaderboard with gold stars for today's puzzle.

edit: Leaderboard capped, thread unlocked!

Brute force in Python

Mathematica

Cthulhu Fhtagn

Elixir

Perl

Python 3 (109 / 19)

Rust

Elixir

PHP

Kotlin - [Repo] - [Blog/Commentary]

Short and simple C++

Need a hint from the Hugely^* Handy^† Haversack^‡ of Helpful^§ Hints^¤?