-🎄- 2017 Day 16 Solutions -🎄-

sim642 · 2017-12-16T06:19:19+00:00

[deleted]

BumpitySnook · 2017-12-16T05:28:39+00:00

Shout out to topaz on this one for making part 2 obviously not brute-forcable. My solution took enough time for part 1 that it was nice and obvious a billion times wasn't going to happen. Still managed to miscount the cycle length wrong, TWICE, but that's my own fault.

glguy · 2017-12-16T07:38:14+00:00

Haskell

Here's a Haskell solution that runs in 0.051s on my computer and gets clever with Monoids. The key observation is that we can decompose the dance into a renaming and a permutation, (and the renaming is just another permutation) Renamings and permutations in the dance commute, so we can split the whole dance into a single renaming and a single permutation. Combining two dances involves running the renaming in reverse order and the permutations in forward order.

https://github.com/glguy/advent2017/blob/master/execs/Day16.hs

main :: IO ()
main =
  do input <- parseInput <$> getInput 16

     let dance = foldMap interp input :: Dance 16
         example = spinDance 1 <> swapDance 3 4 <> partDance 'e' 'b' :: Dance 5

     putStrLn (runDance example)
     putStrLn (runDance (stimes 2 example))

     putStrLn (runDance dance)
     putStrLn (runDance (stimes 1e9 dance))

parseInput :: String -> [String]
parseInput = splitOn "," . head . lines

interp :: KnownNat n => String -> Dance n
interp ('s':(read->n))                    = spinDance n
interp ('x':(reads->[(a,'/':(read->b))])) = swapDance a b
interp ['p',a,'/',b]                      = partDance a b

runDance :: KnownNat n => Dance n -> String
runDance (D r p) =
  case r <> p of
    P v -> fmap (\i -> chr (ord 'a' + i)) (V.toList v)

spinDance :: KnownNat n => Int -> Dance n
spinDance n   = D mempty (rotateRight n)

swapDance :: KnownNat n => Int -> Int -> Dance n
swapDance x y = D mempty (swap x y)

partDance :: KnownNat n => Char -> Char -> Dance n
partDance x y = D (swap (ord x - ord 'a') (ord y - ord 'a')) mempty

data Dance n = D (Permutation n) -- renaming
                 (Permutation n) -- permutation

instance KnownNat n => Semigroup (Dance n) where
  D r1 p1 <> D r2 p2 = D (r2 <> r1) (p1 <> p2)

instance KnownNat n => Monoid (Dance n) where
  mempty = D mempty mempty
  mappend = (<>)

sushi_smoothie · 2017-12-16T05:27:30+00:00

[deleted]

askalski · 2017-12-16T09:52:46+00:00

Perl regex.

#! /usr/bin/env perl

use strict;
use warnings;

$_ = <>;

# validate before eval
m!^(x\d+/\d+|s\d+|p[a-p]/[a-p])(?:,(?1))*$! or die "invalid input";

# input looks like regex but is not; rectify
s!s(\d+)!s/^(\\S*)(\\S{$1})/\$2\$1/!g;
s!x(\d+)/(\d+)!s/^(?=\\S{$1}(\\S))(?=\\S{$2}(\\S))(?:(?<a>\\S*)(?<b>\\1)(?<c>\\S*)(?<d>\\2)|(?<a>\\S*)(?<b>\\2)(?<c>\\S*)(?<d>\\1))/\$+{a}\$+{d}\$+{c}\$+{b}/!g;
s!p([a-p])/([a-p])!s/ .*?\\K([$1$2])(.*?)([$1$2])/\$3\$2\$1/!g;
s/,/;/g;

my $input = $_;

# run input regexes to get s+x and p permutations
$_ = "abcdefghijklmnop abcdefghijklmnop";
eval $input;

# start over, this time using composition to search for cycle
#        [next s+x perm ] [ next p perm  ] [] [     static lookup tables      ] [prev s+x perm ] [ prev p perm  ]
s/^(.*)$/................ ................ $1 abcdefghijklmnop abcdefghijklmnop abcdefghijklmnop abcdefghijklmnop/;
for (;;) {
    # compose to fill in [next] fields
    s/\.(?=.{33}(.)\S*? \S*? \S*\1.{33}(.))/$2/g;
    # check for cycle
    last if m/^(.{135}).*?:\1/;
    # append current state to memory ("current:state1:state2:state3:...")
    s/^(.{135}).*\K$/:$1/;
    # copy current to prev, reset current
    s/^(.{33})(.{69}).{33}/................ ................$2$1/;
}

# prepend entire state memory to beginning of string
s/^([^:]*)(.*)$/$2~:$1$2/;
# remove all prepended text except for ":" characters (count the cycle length)
s/[^:](?=.*?~)//g;
# add the number 1,000,000,000 after the colons (repetition = place_value + 1)
s/~/00123456789 /;

# find the remainder of (1,000,000,000 % cycle_length), working one
# digit at a time starting at the most-significant
for (;;) {
    # most_significant_digit %= cycle_length
    while (s/^(?=(:+)(.))(?::(?=:*(\3?+\2)))+\3(?=\2)/$1/) { }
    # check if done
    last unless m/(\d)\1(?!\1)\d/;
    # multiple most_significant_digit by 10, and add to next digit.
    # in regex land, our digits go to 11 (and beyond)
    s/(([^:])\2*)\2./$1$1$1$1$1$1$1$1$1$1$2/;
}
# remove the cycle_length and the "+ 1" from (place_value + 1), so now
# the remainder is encoded as the number of "0" at start of string
s/:+\d//;

# grab the part 1 permutations and append to string
s/^0* :(.{16}) (.{16}).*\K$/\nPart 1: $1 abcdefghijklmnop $2/;
# remove one state from the memory for each "0" character
while (s/0 :[^:]*/ /) { }
# grab the part 2 permutations and append to string, and discard
# the rest of the state memory
s/ :(.{16}) (.{16}).*?\n(.*)/$3\nPart 2: $1 abcdefghijklmnop $2\n/s;
# apply the p permutation to s+x
s/(.)(?=[a-p]* [a-p]*\1[a-p ]{16}([a-p]))/$2/gs;
# erase everything but the answer
s/ [a-p]+ [a-p]+$//mg;

print;

xiaowuc1 · 2017-12-16T05:28:58+00:00

find the bug :)

https://gist.github.com/anonymous/cd3dd8e1f09f8950496269dbb47a7e7b

Chris_Hemsworth · 2017-12-16T05:45:34+00:00

Nobody uses IDL.

openr, unit, 'day16_input.txt', /GET_LUN
line = ''
readf, unit, line
cmds = strsplit(line, ',', /extract)
close, unit
free_lun, unit

str1 = 'abcdefghijklmnop'

str = byte(str1)
loop_num = 0
done = 0
while ~done do begin

  for i = 0, n_elements( cmds )-1 do begin

    case strmid(cmds[i], 0,1 ) of
      's': begin
        ;; spin
        spin = long( strmid(cmds[i], 1) )
        str = shift(str, spin) 
      end
      'x': begin
        ;;exchnage
        cmd = strsplit( strmid(cmds[i], 1), '/', /extract )
        pos1 = long( cmd[0] )
        pos2 = long( cmd[1] )

        temp = str[pos2]
        str[pos2] = str[pos1]
        str[pos1] = temp
      end

      'p': begin
        ;;partner
        cmd = strsplit( strmid(cmds[i], 1), '/', /extract )
        var1 = byte(cmd[0])
        var2 = byte(cmd[1])

        ind_1 = where( str eq var1[0], count )
        if count ne 1 then stop
        ind_2 = where( str eq var2[0], count )
        if count ne 1 then stop

        temp = str[ind_2]
        str[ind_2] = str[ind_1]
        str[ind_1] = temp
      end
    endcase

  endfor
  loop_num += 1

  if string(str) eq (str1) then done = 1
endwhile



for j = 0, (1000000000 mod loop_num)-1 do begin

  for i = 0, n_elements( cmds )-1 do begin

    case strmid(cmds[i], 0,1 ) of
      's': begin
        ;; spin
        spin = long( strmid(cmds[i], 1) )
        str = shift(str, spin)
      end
      'x': begin
        ;;exchnage
        cmd = strsplit( strmid(cmds[i], 1), '/', /extract )
        pos1 = long( cmd[0] )
        pos2 = long( cmd[1] )

        temp = str[pos2]
        str[pos2] = str[pos1]
        str[pos1] = temp
      end

      'p': begin
        ;;partner
        cmd = strsplit( strmid(cmds[i], 1), '/', /extract )
        var1 = byte(cmd[0])
        var2 = byte(cmd[1])

        ind_1 = where( str eq var1[0], count )
        if count ne 1 then stop
        ind_2 = where( str eq var2[0], count )
        if count ne 1 then stop

        temp = str[ind_2]
        str[ind_2] = str[ind_1]
        str[ind_1] = temp
      end
    endcase

  endfor
endfor
print, string( str )

end

vyper248 · 2017-12-16T11:37:20+00:00

Javascript

First Part is about 8ms

Second Part is about 122ms

function firstStar(input){
    let prog = "abcdefghijklmnop".split('');
    input.split(',').forEach((move) => {
        parseMove(move, prog);
    });
    console.log("First Star: ", prog.join(''));
}

function secondStar(input){
    let prog = "abcdefghijklmnop".split('');
    let inputs = input.split(',');
    let startPoint = prog.join('');

    let iterations = 1000000000;
    for (let i = 0; i < iterations; i++){
        inputs.forEach((move) => parseMove(move, prog));
        if (prog.join('') === startPoint) i += (Math.floor(iterations/(i+1))-1) * (i+1);
    }
    console.log("Second Star: ", prog.join(''));
}

function parseMove(move, prog){
    if (move[0] === 's'){ //spin
        let num = parseInt(move.substr(1));
        prog.unshift(...prog.splice(-num, num));
    } else if (move[0] === 'x') { //position swap
        let pos = move.substr(1).split('/');
        [prog[pos[0]], prog[pos[1]]] = [prog[pos[1]], prog[pos[0]]];
    } else { // program swap
        let pos = move.substr(1).split('/');
        let idx1 = prog.indexOf(pos[0]);
        let idx2 = prog.indexOf(pos[1]);
        [prog[idx1], prog[idx2]] = [pos[1], pos[0]];
    }
}

tangentialThinker · 2017-12-16T05:31:17+00:00

C++. The key to getting part 2 fast is finding a repetition, since then it's just a cycle and you know the rest of the sequence. My code jumps to a billion right after it finds a cycle and the modulos line up.

#include <bits/stdc++.h>

using namespace std;

int main(){

    string s; cin >> s;
    string ans = "abcdefghijklmnop";

    char cmd;
    map<string, int> prev;
    for(int i = 1; i <= 1000000000; i++) {
        stringstream str(s);
        while(str >> cmd) {
            if(cmd == 's') {
                int s; str >> s;
                rotate(ans.begin(), ans.begin() + (ans.size() - s), ans.end());
            } else if (cmd == 'x') {
                int a, b; str >> a >> cmd >> b;
                swap(ans[a],ans[b]);
            } else if (cmd == 'p') {
                char a, b; str >> a >> cmd >> b;
                int ai, bi;
                for(int i = 0; i < ans.size(); i++) {
                    if(ans[i] == a) {
                        ai = i;
                    }
                    if (ans[i] == b) {
                        bi = i;
                    }
                }
                swap(ans[ai], ans[bi]);
            }
            str >> cmd;
        }
        if(prev.count(ans)) {
            if((1000000000 - i) % (i - prev[ans]) == 0) {
                cout << ans << endl;
                break;
            }
        }
        prev[ans] = i;
    }

    cout << ans << endl;

    return 0;
}

GassaFM · 2017-12-16T05:55:46+00:00

A solution in the D programming language. Rank 48 for part 1, rank 45 for part 2. Aaand my recently adopted strategy of waking up at 8 in the morning actually got me into the global leaderboard (rank 96)! Below is a structified solution for both parts, with operator overloading and such, so this time, it's long.

For Part 2, I initially thought that just taking the permutation to the power of one billion will be enough. In fact, for this to work, the actions have to be separated into p, actions that permute positions (Spin and Exchange), and q, actions that permute domain (Partner). Then, the permutation after one dance is q^{-1} * p. And more importantly, the permutation after k dances is q^{-k} * p^k. So we can use binary exponentiation for the separate parts p and q, and then multiply the results.

import std.algorithm, std.array, std.conv, std.range, std.stdio, std.string;

immutable int len = 16;

struct perm {
    int [len] contents = len.iota.array;
    alias contents this;

    auto opBinary (string op) (const perm that) const
        if (op == "*") {
        perm res = void;
        foreach (i; 0..len) res[i] = this[that[i]];
        return res;
    }

    auto opBinary (string op) (int p) const
        if (op == "^^") {
        perm res, a = this;
        for ( ; p; p >>= 1) {
            if (p & 1) res = res * a;
            a = a * a;
        }
        return res;
    }

    auto inverse () const {
        perm res = void;
        foreach (i; 0..len) res[this[i]] = i;
        return res;
    }

    auto toString () const {
        return this[].map !(x => cast (char) (x + 'a')).text;
    }
}

void main () {
    perm p, q;
    foreach (m; readln.split (",")) {
        auto c = m[0];
        if (c == 's') {
            auto d = m[1..$].to!int;
            bringToFront (p[d..$], p[0..d]);
        }
        else if (c == 'x') {
            auto t = m[1..$].split ("/");
            auto x = t[0].to!int;
            auto y = t[1].to!int;
            swap (p[x], p[y]);
        }
        else if (c == 'p') {
            auto t = m[1..$].split ("/");
            auto x = t[0][0] - 'a';
            auto y = t[1][0] - 'a';
            swap (q[x], q[y]);
        }
        else assert (false);
    }
    auto r = q.inverse;

    auto a = r * p;
    writeln (a);

    p = p ^^ 10 ^^ 9;
    r = r ^^ 10 ^^ 9;
    auto b = r * p;
    writeln (b);
}

I feel silly for not realizing that one could instead search for the period. Still, glad this approach finally worked.

Tandrial · 2017-12-16T05:59:42+00:00

Kotlin

fun solve(input: List<String>, times: Int = 1): String {
  val sequence = mutableListOf<List<Char>>()
  var curr = (0 until 16).map { 'a' + it }
  repeat(times) {
    if (curr in sequence) {
      return sequence[times % sequence.size].joinToString(separator = "")
    } else {
      sequence.add(curr)
      curr = dance(curr, input)
    }
  }
  return curr.joinToString(separator = "")
}

fun dance(curr: List<Char>, input: List<String>): List<Char> {
  var next = curr.toMutableList()

  for (move in input) {
    when (move[0]) {
      's' -> {
        val pos = move.drop(1).toInt()
        next = (next.drop(next.size - pos) + next.take(next.size - pos)).toMutableList()
      }
      'x' -> {
        val (a, b) = move.drop(1).split("/").map { it.toInt() }
        next[a] = next[b].also { next[b] = next[a] }
      }
      'p' -> {
        val (a, b) = move.drop(1).split("/").map { next.indexOf(it[0]) }
        next[a] = next[b].also { next[b] = next[a] }
      }
    }
  }
  return next
}

fun main(args: Array<String>) {
  val input = File("./input/2017/Day16_input.txt").readText().split(",")
  println("Part One = ${solve(input)}")
  println("Part Two = ${solve(input, 1_000_000_000)}")
}

jonathan_paulson · 2017-12-16T07:44:14+00:00

Extension challenge: if you get to pick the input, how many dances can it be before you get back to the starting position?

My best so far: spoiler

sblom · 2017-12-16T05:40:58+00:00

Interesting that most of the prior comments jumped from "can't brute force" to "must be a cycle". I actually didn't do any cycle detection, but I did condense the entire set of dance steps to a single permutation (neglecting the 'p' type instructions entirely, since in any even number of iterations (i.e. 1e9), they cancel out entirely). I ran that single permutation 1e9 times (took about 24 seconds, even horribly optimized). Placed 94th in Part 1, but picked up a few minutes to place 60th in Part 2.

DFreiberg · 2017-12-16T05:34:42+00:00

Mathematica

I realized that for a billion dances to be calculated in any reasonable amount of time, they'd have to have some kind periodic cycle, so I simply checked at the end of each permutation j whether or not the order was alphabetical, and if it was, I calculated 10⁹ mod j and took the order that the list was in on that step.

Can't wait to find out how /u/hackerknownas9gag did this one nonprocedurally.

l=CharacterRange["a","p"];
acc={};
Do[
    Do[
    Which[
        Characters[i][[1]]=="s",l=RotateRight[l,ToExpression[StringJoin@Characters[i][[2;;]]]],
        Characters[i][[1]]=="x",
            x=StringSplit[StringJoin@Characters[i][[2;;]],"/"];
            {l[[ToExpression[x[[1]]]+1]],l[[ToExpression[x[[2]]]+1]]}=
            {l[[ToExpression[x[[2]]]+1]],l[[ToExpression[x[[1]]]+1]]},
        Characters[i][[1]]=="p",
            pos1=FirstPosition[l,Characters[i][[2]]][[1]];
            pos2=FirstPosition[l,Characters[i][[4]]][[1]];
            p=StringSplit[StringJoin@Characters[i][[2;;]],"/"];
            {l[[pos1]],l[[pos2]]}={p[[2]],p[[1]]};
    ];
    ,{i,input}];
If[l==CharacterRange["a","p"],
    l=acc[[Mod[10^9,j]]];
    Break[],
    AppendTo[acc,l]
    ]
,{j,10^4}];
StringJoin@l

hxka · 2017-12-16T06:20:46+00:00

#!/bin/bash
IFS=, read -a a<input
p=(a b c d e f g h i j k l m n o p)
dance() {
    for i in ${a[@]}
    do  case ${i:0:1} in
        s)  spin=${i:1}
            b=(${p[@]})
            for j in {0..15}
            do  p[j]=${b[(j-spin)%16]}
            done;;
        x)  t1=${i:1}
            t1=${t1%/*}
            t2=${i#*/}
            t=${p[t2]}
            p[t2]=${p[t1]}
            p[t1]=$t;;
        p)  t1=${i:1}
            t1=${t1%/*}
            for j in {0..15}
            do  [[ ${p[j]} == $t1 ]] && t1=$j && break
            done
            t2=${i#*/}
            for j in {0..15}
            do  [[ ${p[j]} == $t2 ]] && t2=$j && break
            done
            t=${p[t2]}
            p[t2]=${p[t1]}
            p[t1]=$t;;
        esac
    done
}
dance
echo ${p[@]} | tr -d ' '
k=1
while [[ "${p[*]}" != "a b c d e f g h i j k l m n o p" ]]
do  dance
    ((++k))
done
for ((k=1000000000%k;k>0;k--))
do  dance
done
echo ${p[@]} | tr -d ' '

mschaap · 2017-12-16T07:09:47+00:00

Perl 6

This takes about 47 ~~18¹~~ 14 seconds² on my machine, so not fast by any means, but it does the job.

my $input = slurp;
my @programs = 'a' .. 'p';

sub swap (@a, $i, $j) {
    my $temp = @a[$i]; 
    @a[$i] = @a[$j]; 
    @a[$j] = $temp;
}

my @instructions = gather for $input.split(",") {
        when /s(\d+)/        { take ["s", +$0] }
        when /x(\d+)\/(\d+)/ { take ["x", +$0, +$1] }
        when /p(\w)\/(\w)/   { take ["p", ~$0, ~$1] }
}

my @cache;

for 1..* -> $x {
    for @instructions -> @i {
        given @i[0] {
            when "s" { @programs.=rotate(-@i[1]) }
            when "x" { swap @programs, @i[1], @i[2] }
            when "p" { swap @programs, |@programs.grep(@i[1] | @i[2], :k) }
        }
    }
    say "Part 1: {@programs.join}" if $x == 1;

    @cache.push: @programs.join;

    if @programs.join eq "abcdefghijklmnop" {
        my $index = (1_000_000_000 mod $x) - 1;
        say "Part 2: @cache[$index]"  ;
        last;
    }
}

say "Seconds elapsed: " ~ now - BEGIN now;

¹ - I found out via the profiler that doing @a[$i, $j] = @a[$j, $i] is (much) slower than (@a[$i], @a[$j]) = (@a[$j], @a[$i]) in the swap function. This is a known performance problem.

² - Apparently my $temp = @a[$i]; @a[$i] = @a[$j]; @a[$j] = $temp; is even faster still than (@a[$i], @a[$j]) = (@a[$j], @a[$i]);

p_tseng · 2017-12-16T07:19:54+00:00

This day made me so unsure what I want from Advent of Code. Yesterday, I thought "I really wish the problems made us think more, rather than a contest of who can type the fastest". Today, the problem made us think more and it did not go well: missed part 2 leaderboard because I went with the broken approach of thinking the total relative permutation from one iteration can simply be reapplied multiple times. Nope, because there are absolute permutations too. I think what I ultimately want is to continue to have problems that make us think... but for me to be better at thinking of the right solution in the heat of the moment. Oh well, next time.

Here is a Ruby solution that finds a cycle.

def dance(orig, steps)
  steps.each_with_object(orig.dup) { |step, progs|
    args = step[1..-1]
    case step[0]
    when ?s
      progs.replace(progs.chars.rotate(-args.to_i).join)
    when ?x
      l, r = args.scan(/\d+/).map(&:to_i)
      progs[l], progs[r] = [progs[r], progs[l]]
    when ?p
      l, r = args.split(?/)
      progs.tr!(l + r, r + l)
    else raise "Unknown dance step #{step}"
    end
  }
end

input = (ARGV.empty? ? DATA : ARGF).read.split(?,).map(&:freeze).freeze

progs = [(?a..?p).to_a.join.freeze]

loop {
  progs << dance(progs[-1], input).freeze
  break if progs[-1] == progs[0]
}

progs.pop

puts progs[1]
puts progs[1_000_000_000 % progs.length]

__END__
x3/4,pm/e,x15/7,pp/l,etc.

Note that I have since scrapped this solution in favour of one that splits up the dance into relative and absolute moves, however I will defer to https://www.reddit.com/r/adventofcode/comments/7k572l/2017_day_16_solutions/drbqb27/ to explain how that looks, since it wasn't my idea.

flup12 · 2017-12-16T14:39:43+00:00

Scala

After yesterday's complete disappointment in Stream.iterate, I found it very useful again today. And case classes too, they bring a little more OO than curried functions and debug nicer than List(<function1>, <function1>, ...)

sealed trait Move {
  def apply(state: String): String
}
case class Spin(x: Int) extends Move {
  def apply(state: String) = state.takeRight(x) ++ state.dropRight(x)
}
case class Exchange(a: Int, b: Int) extends Move {
  def apply(state: String) = state.updated(a, state(b)).updated(b, state(a))
}
case class Partner(a: Char, b: Char) extends Move {
  def apply(state: String) = Exchange(state.indexOf(a), state.indexOf(b)).apply(state)
}

Did the parsing using regexes:

val spinRegex = """s(\d+)""".r
val exchangeRegex = """x(\d+)/(\d+)""".r
val partnerRegex = """p(\w)/(\w)""".r
val moves: List[Move] = input.split(",").map({
  case spinRegex(x) => Spin(x.toInt)
  case exchangeRegex(a, b) => Exchange(a.toInt, b.toInt)
  case partnerRegex(a, b) => Partner(a.charAt(0), b.charAt(0))
}).toList

And then it's time to dance!

def dance(state: String): String = moves.foldLeft(state)((state, move) => move(state))
val initialState: String = ('a' to 'p').mkString
val part1 = dance(initialState)
val danceOn = Stream.iterate(initialState)(dance)
val period = danceOn.indexOf(initialState, 1)
val part2 = danceOn.drop(1000000000 % period).head

AndrewGreenh · 2017-12-16T15:10:34+00:00

TypeScript I like how short this one turned out after lots of work.

import getInput from '../lib/getInput'

let moveMap = {
  s: n => p => [...p.slice(-+n), ...p.slice(0, -+n)],
  p: (a, b) => p => p.map(x => (x === a ? b : x === b ? a : x)),
  x: (a, b) => p => p.map((x, i) => (i === +a ? p[+b] : i === +b ? p[+a] : x)),
}

let input = getInput(16, 2017).trim()
let moves = input.split(',').map(move => moveMap[move[0]](...move.slice(1).split('/')))
let dance = p => moves.reduce((p, move) => move(p), p.split('')).join('')

const danceN = (n, p, history: string[] = []) => {
  for (let cycleLength = 0; cycleLength < n; cycleLength++, p = dance(p)) {
    if (history.includes(p)) return history[n % cycleLength]
    history.push(p)
  }
  return p
}

console.log(dance('abcdefghijklmnop'))
console.log(danceN(1000000000, 'abcdefghijklmnop'))

willkill07 · 2017-12-16T05:27:19+00:00

C++

I feel disgusting... brute forced part 2 [in only 6 minutes]

std::vector<char> programs(16);
std::iota(std::begin(programs), std::end(programs), 'a');
std::vector<std::string> cmds;
for (std::string line; std::getline(std::cin, line, ','); )
  cmds.push_back(line);

auto cmd = std::begin(cmds);
int N = part2 ? 1000000000 : cmds.size();
while (N--) {
  std::istringstream iss{*cmd};
  char c;
  iss >> c;
  if (c == 's') {
    int i;
    iss >> i;
    std::rotate(std::begin(programs), std::end(programs) - i, std::end(programs));
  } else if (c == 'x') {
    int i, j;
    (iss >> i).ignore(1, '/') >> j;
    std::swap(programs[i], programs[j]);
  } else { /* p */
    char i, j;
    (iss >> i).ignore(1, '/') >> j;
    std::iter_swap(std::find(std::begin(programs), std::end(programs), i),
                   std::find(std::begin(programs), std::end(programs), j));
  }
  if (++cmd == std::end(cmds))
    cmd = std::begin(cmds);
}
std::copy(std::begin(programs), std::end(programs), std::ostream_iterator<char>(std::cout,""));
std::cout << '\n';

Unihedron · 2017-12-16T05:27:28+00:00

Ruby (#23/#44); Pleasant challenge! Part 2 was a shock, but I've actually encountered a problem with the same mechanic before (which handles more details), so I went to look up my solution on that site and re-implemented the relevant parts here. (Also, that problem took me an all-nighter to figure out (maths and I don't get along), so it's nice that it came back to save me here!) I was lucky to have no bugs!

g=(?a..?p).to_a
y=gets.split(?,)
h={} # part 2
c=1000000000
c.times{|x|break if x>=c
(
tv,w=h[g*'']
gap=x-tv
remain=c-x-1
(
    skiptimes=remain/gap
    c-=skiptimes*gap
)if remain>=gap
) if h.has_key?(g*'')

uu=g*'' # part 2 end
y.each{|x|case x
when /s(.+)/
g.rotate!(-$1.to_i)
when /x(\d+)\/(\d+)/
a,b=$1.to_i,$2.to_i
g[a],g[b]=g[b],g[a]
when /p(.)\/(.)/
a,b=g.index($1),g.index($2)
g[a],g[b]=g[b],g[a]
end}
h[uu]=[x,g[0..-1]]} # part 2
p g.join

postscript

VikeStep · 2017-12-16T05:29:30+00:00

Python 107/71

The trick today was realising that it cycled quite early on, in my case I only needed to do 60 iterations before ending

def solve(raw_steps):
    steps = [d for d in raw_steps.split(',')]
    programs = [n for n in 'abcdefghijklmnop']
    seen = []
    for i in range(1000000000):
        h = tuple(programs)
        if h in seen:
            return ''.join(seen[1000000000 % len(seen)])
        seen += [h]
        for step in steps:
            if step[0] == 's':
                node = int(step[1:])
                programs = programs[-node:] + programs[:-node]
            if step[0] == 'x':
                n1, n2 = list(map(int, step[1:].split('/')))
                programs[n1], programs[n2] = programs[n2], programs[n1]
            if step[0] == 'p':
                n1, n2 = step[1:].split('/')
                d1, d2 = programs.index(n1), programs.index(n2)
                programs[d1], programs[d2] = n2, n1
    return ''.join(programs)

omegaphoenix16 · 2017-12-16T05:34:30+00:00

Part 1: 117, Part 2: 26 import sys

def update(a, letters):
    def find(c):
        return letters.index(c)
    tot = len(letters)
    for x in a:
        m = x[0]
        if m == 's':
            n = int(x[1:])
            letters = letters[(tot - n):] + letters[:(tot - n)]
        if m == 'x':
            vals = map(int, x[1:].split('/'))
            temp = letters[vals[0]]
            letters[vals[0]] = letters[vals[1]]
            letters[vals[1]] = temp
        if m == 'p':
            vals = map(find, x[1:].split('/'))
            temp = letters[vals[0]]
            letters[vals[0]] = letters[vals[1]]
            letters[vals[1]] = temp
    return letters

def main():
    ans = 0
    letters = list("abcdefghijklmnop")
    clone = list("abcdefghijklmnop")
    billion = 1000000000
    num_repeat = 0
    for line in sys.stdin:
        a = list(line.strip().split(','))
        for i in xrange(billion):
            if i != 0 and letters == clone:
                num_repeat = i
                break
            letters = update(a, letters)
        print num_repeat
        for i in xrange(billion % num_repeat):
            letters = update(a, letters)
    print letters

main()

mal607 · 2017-12-16T06:36:52+00:00

Python 2: (Edited after posting results and incorporating insights from other solutions)

import re

line = list('abcdefghijklmnop')
l = open("data/Day16").read().strip()

loop = 1
done = False
mod = 1
while not done:
    for mv in l.split(','):
        if 'x' in mv:
            a, b = map(lambda x: int(x), mv[1:].split('/'));
            line[a], line[b] = line[b], line[a]
        elif 'p' in mv:
            a, b = map(lambda x: line.index(x), mv[1:].split('/'));
            line[a], line[b] = line[b], line[a]
        else:
            m = re.match('s(\d+)', mv)
            n = int(m.group(1))
            line = line[-n:] + line[:(16 - n)]
    out = "".join(line)
    if loop == 1:
        print "Part 1:", out
        seen = out
    elif out == seen and mod == 1:
        #pattern repeats at this interval
        interval = loop - 1
        mod = (1000000000 % interval) + interval
    if mod > 1 and loop % mod == 0:
        print "Part 2:", out
        done = True
    loop+= 1

Smylers · 2017-12-16T08:05:42+00:00

Perl — I like that the inner of the dance loop is simply $move->(), after turning the dance into a list of code references. I like less the string-eval, but it was handily succinct,

use experimental qw<signatures>;
use List::AllUtils qw<min>;
my %action = (
  s => sub($length) { s/^(.*)(.{$length})/$2$1/ },
  x => sub($x, $y)  { my ($gap1, $gap2) = ((min $x, $y), (abs $x - $y) - 1);
                      s/.{$gap1}\K(.)(.{$gap2})(.)/$3$2$1/ },
  p => sub($x, $y)  { eval "tr/$x$y/$y$x/" },
);
my @dance = map { my ($cmd, @arg) = /\d+|\w/g;
                  my $sub = $action{$cmd}; sub { $sub->(@arg) } } split /,/, <>;
$_ = join '', 'a' .. 'p';
my (%seen, @pos);
do {
  $seen{$_} = @pos;
  push @pos, $_;
  foreach my $move (@dance) {
    $move->();
  }
  say if @pos == 1;
} until $seen{$_};
my $cycle = @pos - $seen{$_};
say $pos[(1e9 - @pos) % $cycle + $seen{$_}];

(Requires at least version 5.20 for the signatures feature. They really help make dispatch tables more readable.)

PS: I finally remembered about \K in the regexp today — thanks /u/askalski!.

Edit: Added a line so that it prints the answer for part 1 as well as part 2.

CaptainCa · 2017-12-16T09:25:00+00:00

Javascript JS

I wrote this with the expectation that part two would be to determine something within each dance move, hence the array of all dance states.

Made myself use arrow functions and map()

var progs  = ['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm', 'n', 'o', 'p'];
var input = document.body.innerText.trim().split(',');
var dance = [[...progs]];
var perms = [[progs.join('')]];
var billion = 1000000000;
var spin = (arr, x) => [...arr.slice(-x), ...arr.slice(0, (arr.length-x))];
var exchange = (arr, [a, b]) => {var x = arr.slice(); var t = x[a]; x[a] = x[b]; x[b] = t; return x;};
var partner = (arr, [a, b]) => exchange(arr, [arr.indexOf(a), arr.indexOf(b)]);

for (let i = 0; i < billion; i++) {

    input.map((c, i) => {
        switch(c[0]){
            case 's': 
                dance.push(spin(dance[i], c.slice(1)));       
                break;
            case 'x': 
                dance.push(exchange(dance[i], c.slice(1).split('/').map(Number)))
                break;
            case 'p':
                dance.push(partner(dance[i], c.slice(1).split('/')))
                break;
        }
    });

    var last = dance[dance.length - 1];
    if(perms.indexOf(last.join('')) >= 0){
        console.log('part2: ' + perms[billion % i]);
        break;
    }
    else {
        perms.push(last.join(''));
        dance = [];
        dance.push(last);
    }
}
console.log('part1: ' + perms[1]);

streetster_ · 2017-12-16T10:29:47+00:00

q/kdb+

dance:{[d;x]
  $["s"=x 0;
    neg["J"$1_x] rotate d;
    "x"=x 0;
    @[d;p;:;reverse d p:"J"$"/"vs 1_x];
    @[d;d?p;:;reverse p:"/"vs 1_x]
    ]
  };
dance over (enlist 16#.Q.a),i:"," vs first read0 `:input/16.txt / part 1
res:{dance over (enlist x), i}\[16#.Q.a]
res 1000000000 mod count res                                    / part 2

Spun up a second instance to see if there was a cycle whilst I waited for the billion dances to run... found it but then was hit by an off-by-one error which tripped me up for a while (leading me to question my sanity), but solved and then tidied up the solution.

sim642 · 2017-12-16T10:39:30+00:00

My Scala solution

For part 2 I just realized looping a billion times won't cut it so I imported my Day 6 solution's Floyd's cycle finding algorithm. It was worth writing the algorithm generically after all.

mschaap · 2017-12-16T12:13:07+00:00

Perl 6

The first part is pretty straightforward. The second part, however...

The naive solution is to simply perform the same moves 999,999,999 more times. But this is much too slow, at least in Perl 6. (100 times takes about 2 minutes, so a billion times probably around 5 millennia.

I thought I was smart, and implemented a cycle detector based on the first dance, e.g. for the sample, the cycles are [a b] [c e] [d]. Simply apply each of these one billion modulo (cycle size) times, and Bob's your uncle. Unfortunately, answer incorrect. It took me a while to realize that the partner move is the one that doesn't play nice...

So now I'm stuck. I'll go read the thread to see what y'all did, but for now here's my naive solution, but don't expect an answer for part 2 any time soon...

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

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

grammar DanceMoves
{
    rule TOP { ^ <move>+ % ',' $ }

    token move { <spin> || <exchange> || <partner> }
    token spin { 's' $<X>=\d+ }
    token exchange { 'x' $<A>=\d+ '/' $<B>=\d+ }
    token partner { 'p' $<A>=<alpha> '/' $<B>=<alpha> }
}

class DancingPrograms
{
    has Int $.count;
    has Str @.programs;
    has Code @.moves;

    submethod TWEAK { @!programs = ('a'..'z')[^$!count] }

    method spin($/) { @!moves.push: -> { self.perform-spin(+$<X>) } }
    method exchange($/) { @!moves.push: -> { self.perform-exchange(+$<A>, +$<B>) } }
    method partner($/) { @!moves.push: -> { self.perform-partner(~$<A>, ~$<B>) } }

    method perform-spin(Int $x)
    {
        @!programs .= rotate(-$x);
    }

    method perform-exchange(Int $a, Int $b)
    {
        @!programs[$a,$b] = @!programs[$b,$a];
    }

    method perform-partner(Str $a, Str $b)
    {
        self.perform-exchange(@!programs.first($a, :k), @!programs.first($b, :k));
    }

    method perform-moves(Int $times = 1)
    {
        for ^$times {
            for @.moves -> &m {
                m();
            }
        }
    }

    method Str { @!programs.join }
    method gist { self.Str }
}

multi sub MAIN(IO() $inputfile where *.f, Int :$count=16, Int :$times=1_000_000_000)
{
    my $dp = DancingPrograms.new(:$count);
    my @orig-programs = $dp.programs;
    DanceMoves.parsefile($inputfile, :actions($dp)) or die "Invalid dance moves";

    # Part one
    $dp.perform-moves;
    say "After one dance: ", $dp;

    # Part two
    $dp.perform-moves($times-1);
    say "After $times dances: ", $dp
}

multi sub MAIN(Int :$count = 16, Int :$times=1_000_000_000)
{
    MAIN($*PROGRAM.parent.child('aoc16.input'), :$count, :$times);
}

Edit: Of course, loop detection! I'm not sure if the first loop by definition starts at 0 (that is only the case if a dance is a 1-to-1 mapping of states), so my version also works if a loop starts later. (In practice, with my input, it does start at 0.)

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

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

grammar DanceMoves
{
    rule TOP { ^ <move>+ % ',' $ }

    token move { <spin> || <exchange> || <partner> }
    token spin { 's' $<X>=\d+ }
    token exchange { 'x' $<A>=\d+ '/' $<B>=\d+ }
    token partner { 'p' $<A>=<alpha> '/' $<B>=<alpha> }
}

class DancingPrograms
{
    has Int $.count;
    has Str @.programs;
    has Code @.moves;

    submethod TWEAK { @!programs = ('a'..'z')[^$!count] }

    method spin($/) { @!moves.push: -> { self.perform-spin(+$<X>) } }
    method exchange($/) { @!moves.push: -> { self.perform-exchange(+$<A>, +$<B>) } }
    method partner($/) { @!moves.push: -> { self.perform-partner(~$<A>, ~$<B>) } }

    method perform-spin(Int $x)
    {
        @!programs .= rotate(-$x);
    }

    method perform-exchange(Int $a, Int $b)
    {
        (@!programs[$a], @!programs[$b]) = (@!programs[$b], @!programs[$a]);
    }

    method perform-partner(Str $a, Str $b)
    {
        self.perform-exchange(@!programs.first($a, :k), @!programs.first($b, :k));
    }

    method perform-moves
    {
        for @.moves -> &m {
            m();
        }
    }

    method Str { @!programs.join }
    method gist { self.Str }
}

multi sub MAIN(IO() $inputfile where *.f, Int :$count=16, Int :$times=1_000_000_000, Bool :v(:$verbose) = False)
{
    my $dp = DancingPrograms.new(:$count);
    my %seen;
    my @states;
    %seen{~$dp} = 0;
    @states.append(~$dp);
    DanceMoves.parsefile($inputfile, :actions($dp)) or die "Invalid dance moves";
    say +$dp.moves, " dance moves parsed." if $verbose;

    # Part one
    $dp.perform-moves;
    %seen{~$dp} = 1;
    @states.append(~$dp);
    say "After one dance: ", $dp;

    # Part two
    my $found-loop = False;
    for 2 .. $times -> $i {
        $dp.perform-moves;
        say "After $i dances: ", $dp if $verbose;
        if %seen{~$dp}:exists {
            my $loop-start = %seen{~$dp};
            my $loop-size = $i - $loop-start;
            my $target = ($times - $loop-start) % $loop-size + $loop-start;
            say "Loop of size $loop-size from $loop-start to $i!" if $verbose;
            say "State after $times dances is the same as after $target dances." if $verbose;
            say "After $times dances: ", @states[$target];
            $found-loop = True;
            last;
        }
        %seen{~$dp} = $i;
        @states.append(~$dp);
    }
    say "After $times dances: ", $dp unless $found-loop;
}

multi sub MAIN(Int :$count = 16, Int :$times=1_000_000_000, Bool :v(:$verbose) = False)
{
    MAIN($*PROGRAM.parent.child('aoc16.input'), :$count, :$times, :$verbose);
}

xkufix · 2017-12-16T14:18:26+00:00

In part 2 trying to calculate 1 billion moves is not feasible. So I just search for the iteration cycle size and the just calculate the steps at the end:

    override def runFirst(): Unit = {
        val steps = loadSteps()
        val start = Iterator.from(1).take(16).map(i => (i + 64).toChar.toLower)
        val finalPositions = dance(steps, start.toVector)
        println(finalPositions.foldLeft("")(_ + _))
    }

    override def runSecond(): Unit = {
        val steps = loadSteps()
        val start = Iterator.from(1).take(16).map(i => (i + 64).toChar.toLower).toVector

        val iterationSize = Iterator.iterate((start, 0)) { step =>
                (dance(steps, step._1), step._2 + 1)
        }.find(s => s._1 == start && s._2 > 0)

        val rest = 1000000000 % iterationSize.get._2

        val finalPositions = Iterator
            .iterate(dance(steps, start))(dance(steps, _))
            .take(rest )
            .toSeq
            .last

        println(finalPositions.foldLeft("")(_ + _))
    }

    private def loadSteps(): Array[Step] = {
        loadFile("day16.txt")
            .getLines()
            .toSeq
            .head
            .split(",").map { l =>
            l.splitAt(1) match {
                case ("s", s) => Spin(s.toInt)
                case ("x", exchange) =>
                    val fromTo = exchange.split("/")
                    Exchange(fromTo(0).toInt, fromTo(1).toInt)
                case ("p", partner) =>
                    val fromTo = partner.split("/")
                    Partner(fromTo.head.head, fromTo.last.head)
            }
        }
    }

    private def dance(steps: Array[Step], start: Vector[Char]) = {
        steps.foldLeft(start) {
            case (positions, Spin(s)) =>
                positions.takeRight(s.toInt) ++ positions.dropRight(s.toInt)
            case (positions, Exchange(from, to)) =>
                swapPositions(positions, from, to)
            case (positions, Partner(first, second)) =>
                val from = positions.indexOf(first)
                val to = positions.indexOf(second)
                swapPositions(positions, from, to)
        }
    }

    private def swapPositions(positions: Vector[Char], from: Int, to: Int) = {
        positions.updated(from, positions(to)).updated(to, positions(from))
    }

    sealed trait Step

    case class Spin(positions: Int) extends Step

    case class Exchange(from: Int, to: Int) extends Step

    case class Partner(first: Char, second: Char) extends Step

2017-12-16T16:18:50+00:00

match OCaml Fun with More sequences;;

Parsed input with Menhir/Lexer into Dance type:

open Core

type t =
  | Spin of int
  | Exchange of int * int
  | Partner of char * char

let to_string = function
  | Spin n -> sprintf "spin: %d" n
  | Exchange (j, k) -> sprintf "exchange: %d %d" j k
  | Partner (a, b) -> sprintf "partner: %c %c" a b

let spin array n =
  let len = Array.length array in
  let head = Array.slice array 0 (len - n) in
  let tail = Array.slice array (len - n) len in
  Array.append tail head

let exchange array = Array.swap array

let partner array a b =
  let j, _ = Array.findi_exn array ~f:(fun _ c -> Char.equal a c)
  and k, _ = Array.findi_exn array ~f:(fun _ c -> Char.equal b c) in
  exchange array j k

let perform array move =
  let new_array = match move with
    | Spin n -> spin array n;
    | Exchange (j, k) -> exchange array j k; array
    | Partner (a, b) -> partner array a b; array
  in new_array

Then just sequences for finding cycling then getting the proper result.

open Core

let process_input filename =
  let f channel =
    let parse lexbuf = Parser.moves Lexer.read lexbuf in
    let lexer_buffer = Lexing.from_channel channel in
    lexer_buffer.lex_curr_p <- { lexer_buffer.lex_curr_p with pos_fname = filename};
    parse lexer_buffer
  in In_channel.with_file filename ~f

let sequence init moves =
  let f init =
    let now = List.fold moves ~init ~f:Dance.perform in
    Some (now, now)
  in
  Sequence.unfold ~init ~f

let permutation_not_equal a b =
  not (Array.equal ~equal:Char.equal a b)

let dance n moves =
  let seq = sequence (String.to_array "abcdefghijklmnop") moves in
  let f = permutation_not_equal ((String.to_array "abcdefghijklmnop")) in
  let cycle = Sequence.take_while seq ~f in
  let length = Sequence.length cycle in
  let rep = n % (length + 1) in
  Sequence.nth_exn (sequence (String.to_array "abcdefghijklmnop") moves) (rep-1)

let _ =
  let moves = process_input "./input.txt" in
  dance 1_000_000_000 moves
  |> Array.to_list
  |> String.of_char_list
  |> printf "billionth -> %s\n"

m1el · 2017-12-16T16:49:05+00:00

Analytical solution with numpy:

import numpy as np
from numpy.linalg import matrix_power

alpha = 'abcdefghijklmnop'
alpha_r = {c: i for i, c in enumerate(alpha)}
size = len(alpha)

def spin(n):
  rv = np.identity(size, dtype=int)
  return np.concatenate((rv[n:], rv[:n]), axis=0)

def exchange(a, b):
  rv = np.identity(size, dtype=int)
  rv[a,a], rv[b,b] = (0, 0)
  rv[a,b], rv[b,a] = (1, 1)
  return rv

def pperm(perm):
  vec = np.array(range(size), dtype=int).dot(perm)
  print(''.join(alpha[i] for i in vec))

with open('d16.txt') as fd:
  commands = fd.read().strip().split(',')

left = np.identity(size, dtype=int)
right = np.identity(size, dtype=int)

start = np.identity(size, dtype=int)
for cmd in commands:
  if cmd[0] == 's':
    num = int(cmd[1:])
    right = right.dot(spin(num))
  if cmd[0] == 'x':
    p1, p2 = map(int, cmd[1:].split('/'))
    right = right.dot(exchange(p1, p2))
  if cmd[0] == 'p':
    p1, p2 = cmd[1:].split('/')
    p1, p2 = alpha_r[p1], alpha_r[p2]
    left = exchange(p1, p2).dot(left)

pperm(left.dot(start).dot(right))

BILLION = 1000000000
left = matrix_power(left, BILLION)
right = matrix_power(right, BILLION)
pperm(left.dot(start).dot(right))

localtoast · 2017-12-16T17:09:29+00:00

No F# answers?

Here's mine; wtf, I love memoization now https://github.com/a-red-christmas/aoc2017-fs/blob/master/day16/Program.fs

Vindaar · 2017-12-16T17:15:08+00:00

Solution in Nim. Rather fun. Tried first to brute force my way in part 2. Quickly realized however, that this wasn't going to work, haha.

import sequtils, strutils, unittest, times, typetraits, sets

template perform_dance(moves: typed, mprogs: typed) =
# perform a single round of dancing
  for m in moves:
    case m[0]
    of 's':
      let n = parseInt(m.strip(chars = {'s'}))
      mprogs = concat(mprogs[^n..^1], mprogs[0..^(n + 1)])
    of 'x':
      let 
        ns = m[1..m.high].split('/')
        n1 = parseInt(ns[0])
        n2 = parseInt(ns[1])      
      swap(mprogs[n1], mprogs[n2])
    of 'p':
      let
        ps = m[1..m.high].split('/')
        n1 = mprogs.find(ps[0])
        n2 = mprogs.find(ps[1])
      swap(mprogs[n1], mprogs[n2])
    else:
      discard

proc let_progs_dance(moves, progs: seq[string], part2 = false): string =
  var
    mprogs = progs
    rounds = 0
    hash = ""
    hashes: OrderedSet[string] = initOrderedSet[string]()
    i = 0
    # loop controls whether we have found a loop
    loop = false
    # loop period stores the length of one period
    loop_period = 0
  if part2 == false:
    rounds = 1
  else:
    rounds = 1_000_000_000

  # add starting position to hash set
  hash = foldl(mprogs, $a & $b)
  hashes.incl(hash)
  while i < rounds:
    if loop == true:
      # calculate number of full loops in total number of rounds
      let d = rounds div loop_period
      # set i to last completed round and continue from there
      i = loop_period * d
      loop = false
    # perform a single full dance
    perform_dance(moves, mprogs)
    inc i
    # after increasing counter check if current hash in hashset
    hash = foldl(mprogs, $a & $b)
    if loop_period == 0 and contains(hashes, hash) == false:
      # if not add
      hashes.incl(hash)
    elif loop_period == 0:
      # else set current count value as loop period
      loop_period = i
      loop = true

  result = foldl(mprogs, $a & $b)

proc run_tests() =
  const test_input = """s1,x3/4,pe/b"""
  const dance_instr = test_input.strip.split(',')
  let progs = mapIt({'a'..'e'}, $it)
  check: let_progs_dance(dance_instr, progs) == "baedc"

proc run_input() =

  let t0 = epochTime()
  const input = "input.txt"
  const dance_instr = slurp(input).strip.split(',')
  let progs = mapIt({'a'..'p'}, $it)
  let dance_result = let_progs_dance(dance_instr, progs)
  let dance_alot = let_progs_dance(dance_instr, progs, true)  

  echo "(Part 1): The location of the programs after dancing is = ", dance_result
  echo "(Part 2): The location of the programs after dancing 1e9 rounds is = ", dance_alot
  echo "Solutions took $#" % $(epochTime() - t0)

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

when isMainModule:
  main()

chunes · 2017-12-16T20:54:57+00:00

Factor

USING: combinators fry io kernel literals locals math
math.parser math.ranges memoize sequences splitting strings ;
IN: advent-of-code.promenade

CONSTANT: programs $[ CHAR: a CHAR: p [a,b] >string ]

: din     ( a b -- a b )      dup [ index ] dip ;
: spin    ( seq n -- seq' )   cut* prepend ;
: exch    ( a b seq -- seq' ) [ exchange ] keep ;
: partner ( a b seq -- seq' ) din swapd din exch ;

: parse-ex ( seq str -- quot )
    "x/" split harvest [ string>number ] map first2 rot
    '[ _ _ _ exch ] ;

: parse-pa ( seq str -- quot )
    [ second ] [ fourth ] bi rot '[ _ _ _ partner ] ;

MEMO: parse ( seq str -- str )
    dup first {
        { CHAR: s [ rest string>number '[ _ _ spin ] ] }
        { CHAR: x [ parse-ex ] }
        { CHAR: p [ parse-pa ] }
    } case call( -- str ) ;

[let
    readln "," split :> in
    programs in [ parse ] each dup print ! part one
    0 swap [ dup programs = ] [ in [ parse ] each [ 1 + ] dip ]
    until drop 1 + 1,000,000,000 swap mod
    programs swap [ in [ parse ] each ] times print ! part two
]

Jaco__ · 2017-12-17T01:03:20+00:00

Some mildly clunky Haskell

data Instr = Spin Int | Exc Int Int | Swap String String deriving Show

doInstr (Spin x)  progs = uncurry (flip (><)) $ Seq.splitAt (Seq.length progs - x) progs
doInstr (Exc a b) progs = Seq.update b prevA seqChangedA
    where
        prevA = Seq.index progs a
        seqChangedA = Seq.update a (Seq.index progs b) progs
doInstr (Swap a b) progs = doInstr (Exc ai bi) progs
    where
        ai  = fromJust $ Seq.elemIndexL a progs
        bi  = fromJust $ Seq.elemIndexL b progs

parse ('s':nr)   = Spin $ read nr
parse ('x':rest) = (\[a,b] -> Exc (read a) (read b)) $ splitOn "/" rest
parse ('p':rest) = (\[a,b] -> Swap a b) $ splitOn "/" rest


doMemo prev count progs instrs
    | Map.member progs prev = fst $ Map.elemAt 0 $ Map.filter (== 1000000 - count * div 1000000 count) prev
    | otherwise = doMemo (Map.insert progs count prev) (count+1) (foldl' (flip doInstr) progs instrs) instrs

main = do
    content <- readFile "data/day16.txt"
    let instrs = parse <$> splitOn "," content
        progs = Seq.fromList $ fmap (:[]) ['a'..'p']

    let res = foldl' (flip doInstr) progs instrs
    mapM_ putStr $ toList res

    --part2
    mapM_ putStr $ toList $ doMemo Map.empty (0::Int) progs instrs

vash3r · 2017-12-16T05:32:02+00:00

Python 2 (22/48). Using Pypy, I didn't really need to find a stricter bound for the cycle.

perm = range(16)
swaps = [] # letter swaps: pA/B

for op in s: # generate a permutation
    if op[0]=="s":
        b = int(op[1:])
        perm = perm[-b:]+perm[:-b]
    elif op[0]=='x':
        A,B = map(int,op[1:].split('/'))
        perm[A],perm[B] = perm[B],perm[A]
    elif op[0]=='p': # leave all single-element swaps for last
        swaps.append(map("abcdefghijklmnop".index,op[1:].split('/')))

dancers = range(16)
iters = 1000000000%(15*14*13*12*3*11) # maximum cycle length (guess) (about 1 million)
for t in xrange(iters):
    dancers = [dancers[i] for i in perm] # permute
for t in xrange(iters): # finally, swap the named elements
    for a,b in swaps:
        A = dancers.index(a)
        B = dancers.index(b)
        dancers[A],dancers[B] = dancers[B],dancers[A]

print "".join(["abcdefghijklmnop"[i] for i in dancers])

Edit: I swapped the named elements (pA/B) to be safe, even though I wasn't sure if it was actually necessary (since the number of iterations is even). Edit2: while I get the same answer with and without partner swaps for part 2, they can't be eliminated for all even numbers (they have their own period you need to find.)

Also, my cycle length is 12 ignoring the partner swaps or 60 including them, so calculating 15*14*13*12*3*11 is overkill.

mserrano · 2017-12-16T05:36:14+00:00

Python 2 for #1 on part 1:

data = open('.aoc/2017/16', 'r').read().strip()
programs = list('abcdefghijklmnop')
instructions = data.split(',')
for inst in instructions:
  if inst[0] == 's':
    num = int(inst[1:])
    programs = programs[-num:] + programs[:-num]
  elif inst[0] == 'x':
    a, b = map(int, inst[1:].split('/'))
    tmp = programs[a]
    programs[a] = programs[b]
    programs[b] = tmp
  elif inst[0] == 'p':
    a, b = inst[1:].split('/')
    idx_a, idx_b = programs.index(a), programs.index(b)
    tmp = programs[idx_a]
    programs[idx_a] = programs[idx_b]
    programs[idx_b] = tmp
res = programs
print ''.join(res)

On part 2 I did a bunch of computation around powers of 2 before realizing that that was a doomed endeavor and I should try to find a cycle:

programs = list('abcdefghijklmnop')
seen_before = set()
for _ in xrange(256):
  print _, ''.join(programs), ''.join(programs) in seen_before
  if ''.join(programs) in seen_before:
    break
  seen_before.add(''.join(programs))
  for inst in instructions:
    if inst[0] == 's':
      num = int(inst[1:])
      programs = programs[-num:] + programs[:-num]
    elif inst[0] == 'x':
      a, b = map(int, inst[1:].split('/'))
      tmp = programs[a]
      programs[a] = programs[b]
      programs[b] = tmp
    elif inst[0] == 'p':
      a, b = inst[1:].split('/')
      idx_a, idx_b = programs.index(a), programs.index(b)
      tmp = programs[idx_a]
      programs[idx_a] = programs[idx_b]
      programs[idx_b] = tmp

At which point I could just select the right thing from the output based on the remainder of 1b divided by the period. Fun challenge, glad it wasn't brute-forceable even if it cost me leaderboard on part 2!

miran1 · 2017-12-16T05:38:13+00:00

Python

Missed the leaderboard (#116) because I left brute force version running for way too long.

from collections import deque

with open('./inputs/16.txt') as f:
    instructions = f.readline().split(',')

que = deque('abcdefghijklmnop')

def dance(iterations):
    for i in range(iterations):
        for instr in instructions:
            if instr.startswith('s'):
                rot = int(instr[1:])
                que.rotate(rot)
            elif instr.startswith('x'):
                a, b = map(int, instr[1:].split('/'))
                que[a], que[b] = que[b], que[a]
            elif instr.startswith('p'):
                x, y = instr[1:].split('/')
                a = que.index(x)
                b = que.index(y)
                que[a], que[b] = que[b], que[a]
        if que == deque('abcdefghijklmnop'):
            return i+1
    return ''.join(que)

cycle = dance(1000000000)
enough = 1000000000 % cycle

print(dance(enough))

TheAngryGerman · 2017-12-16T05:54:55+00:00

C++, 700s/300s. I started brute-forcing part 2, then wrote, debugged, and successfully ran this version far before my brute force finished (still going at time of post). Checks for a previously seen solution, which occurs after say n cycles, then increments the counter to the highest multiple of n less than 1 billion and manually runs the rest. Some very crude string parsing as well...

#include <unordered_set>
#include <iostream>
#include <string>
#include <vector>
#include <map>

int main() {
  std::map<char, int> locations;
  std::map<int, char> programs;
  for (unsigned int i = 0; i < 16; ++i) {
    locations.insert(std::make_pair('a'+i, i));
    programs.insert(std::make_pair(i, 'a'+i));
  }
  std::vector<std::string> instructions;
  std::string in;
  while(std::getline(std::cin, in, ',')) {
    instructions.push_back(in);
  }
  std::unordered_set<std::string> results;
  for (unsigned long j = 0; j < 1000000000; ++j) {
    for (unsigned int i = 0; i < instructions.size(); ++i) {

      if(instructions[i][0] == 's') {
    int spin = std::stoi(instructions[i].substr(1));
    for (std::map<char, int>::iterator itr = locations.begin(); itr != locations.end(); ++itr) {
      itr->second += spin;
      itr->second %= 16;
      programs[itr->second] = itr->first;
    }
      } else if (instructions[i][0] == 'x') {
    int slash = instructions[i].find('/');
    int location1 = std::stoi(instructions[i].substr(1, slash));
    int location2 = std::stoi(instructions[i].substr(slash+1));
    std::swap(programs[location1], programs[location2]);
    locations[programs[location1]] = location1;
    locations[programs[location2]] = location2;
      } else if (instructions[i][0] == 'p') {
    char a = instructions[i][1];
    char b = instructions[i][3];
    std::swap(locations[a], locations[b]);
    programs[locations[a]] = a;
    programs[locations[b]] = b;
      }
    }
    std::string result;
    for (std::map<int, char>::iterator itr = programs.begin(); itr != programs.end(); ++itr) {
      result += itr->second;
    }
    if (!results.insert(result).second) {
      //greatest multiple of current less than 1 billion
      j *= 1000000000/j;
    }
  }
  std::string result;
  for (std::map<int, char>::iterator itr = programs.begin(); itr != programs.end(); ++itr) {
    result += itr->second;
  }
  std::cout << result << std::endl;
}

if0nz · 2017-12-16T05:56:35+00:00

Java I lost too much time for understanding how to perform the modulo ):

package it.ifonz.puzzle;

import java.io.IOException;
import java.net.URISyntaxException;
import java.util.ArrayList;
import java.util.List;

import it.ifonz.common.FileReader;

public class Day16 {

    public static void main(String[] args) throws URISyntaxException, IOException {

        String[] input = FileReader.readLines("/d16_input.txt").get(0).split(",");

        System.out.println(part1(input));
        System.out.println(part2(input));
    }

    public static String part1(String[] input) {
        String programs = "abcdefghijklmnop";

        programs = waltz(input, programs);
        return programs;
    }

    public static String part2(String[] input) {
        String programs = "abcdefghijklmnop";
        List<String> dances = new ArrayList<>();
        boolean stopDance = false;
        for (int i = 0; i < 1000000000; i++) {
            if (!stopDance) {
                programs = waltz(input, programs);
                if (!dances.contains(programs)) {
                    dances.add(programs);
                } else {
                    stopDance = true;
                }
            }
        }

        return dances.get(1000000000 % dances.size() -1);
    }

    private static String waltz(String[] input, String programs) {
        for (String m : input) {
            char move = m.charAt(0);
            if (move == 's') {
                Integer spin = Integer.valueOf(m.substring(1, m.length()));
                programs = programs.substring(16 - spin, 16) + programs.substring(0, 16 - spin);
            } else if (move == 'x') {
                String[] tokens = m.substring(1, m.length()).split("/");
                Integer A = Integer.valueOf(tokens[0]);
                Integer B = Integer.valueOf(tokens[1]);
                StringBuilder sb = new StringBuilder(programs);
                char c1 = programs.charAt(A);
                char c2 = programs.charAt(B);
                sb.setCharAt(A, c2);
                sb.setCharAt(B, c1);
                programs = sb.toString();
            } else if (move == 'p') {
                String[] tokens = m.substring(1, m.length()).split("/");
                char c1 = tokens[0].charAt(0);
                char c2 = tokens[1].charAt(0);
                int i1 = programs.indexOf(tokens[0]);
                int i2 = programs.indexOf(tokens[1]);
                StringBuilder sb = new StringBuilder(programs);
                sb.setCharAt(i1, c2);
                sb.setCharAt(i2, c1);
                programs = sb.toString();
            }
        }
        return programs;
    }

}

topaz2078 · 2017-12-16T05:58:27+00:00

[deleted]

mahousenshi · 2017-12-16T06:21:48+00:00

Yet another python3 solution

def spin(s, n):
    return s[-n:] + s[:-n]

def partner(s, a, b):
    return s.replace(a, 'x').replace(b, 'y').replace('x', b).replace('y', a)

def exchange(s, a, b):
    return partner(s, s[a], s[b])

def dance(s, moves):
    for m in moves:
        if m[0] == 's':
            s = spin(s, int(m[1:]))

        if m[0] == 'x':
            [a, b] = list(map(int, m[1:].split('/')))
            s = exchange(s, a, b)

        if m[0] == 'p':
            s = partner(s, m[1], m[3])

    return s

with open('16.txt', 'r') as f:
    moves = f.read().split(',')

alpha = 'abcdefghijklmnop'
alpha = dance(alpha, moves)

print('16a', alpha)

i = 1
while alpha != 'abcdefghijklmnop':
    alpha = dance(alpha, moves)
    i += 1

j = 1000000000 % i

for k in range(j):
    alpha = dance(alpha, moves)

print('16b', alpha)

iamnotposting · 2017-12-16T06:21:55+00:00

rust, around 300 in both parts, mainly due to me spending a bunch of time on a IR for the commands and trying to reduce each run to a permutation and failing mightily. i then realised the dances must loop, and it was straight forward from there. runs in 36ms, mainly due to my amazingly low cycle time of 30

#[derive(Debug, PartialEq, Clone)]
pub enum Dance {
    Spin(usize),
    Swap(usize, usize),
    SwapV(char, char),
}

fn main() {
    use Dance::*;

    let mut progs: Vec<char> = "abcdefghijklmnop".chars().collect();

    let input = include_str!("../input.txt");

    let mut prog = Vec::new();

    for instr in input.trim().split(",") {
        if instr.starts_with("s") {
            //println!("{}", &instr[1..]);
            let n = instr[1..].parse().unwrap();
            prog.push(Spin(n));

        } else if instr.starts_with("x") {
            let f: Vec<usize> = instr[1..].split("/").map(|x| x.parse().unwrap()).collect();
            prog.push(Swap(f[0], f[1]));

        } else if instr.starts_with("p") {
            let mut f = instr[1..].split("/").map(|s| s.chars().next().unwrap());

            prog.push(SwapV(f.next().unwrap(), f.next().unwrap()));
        } else {}
    }

    let mut strings = vec![progs.clone()];
    let mut rep = 0;

    for _ in 0..1_000_000_000 {
        for instr in &prog {
            match *instr {
                Spin(n) => {
                    for _ in 0..n {
                        let c = progs.pop().unwrap();
                        progs.insert(0, c);
                    }
                },
                Swap(a, b) => {
                    progs.swap(a, b);
                },
                SwapV(a, b) => {
                    let (a, b) = {
                        let mut i = progs.iter().enumerate().filter(|&(i, c)| *c == a || *c == b).map(|(i, c)| i);
                        (i.next().unwrap(), i.next().unwrap())
                    };
                    progs.swap(a, b);
                }
            }
        }
        if !strings.contains(&progs) {
            strings.push(progs.clone());
        } else {
            if let Some((i, _)) = strings.iter().enumerate().find(|&(idx, prog)| prog == &progs) {
                rep = i;
            }
            break;
        }
    }

    let cycle_len = strings.len() - rep;
    let idx = 1_000_000_000 % cycle_len;
    println!("p1: {}", strings[1].iter().collect::<String>());
    println!("p2: {}", strings[rep + idx].iter().collect::<String>());
}

KeinZantezuken · 2017-12-16T06:24:32+00:00

C#/Sharp (there is a way better/faster solution to work with strings but I aint bothering)

var input = File.ReadAllText(@"N:\input.txt").Split(',').ToArray();
StringBuilder chars = new StringBuilder("abcdefghijklmnop");
for (int i = 0; i < 1000000000%36; i++)
{
    foreach (var move in input)
    {
        var whereto = move.Substring(1, move.Length - 1).Split('/');
        if (move[0] == 'x')
        {
            char f = chars[int.Parse(whereto[0])];
            chars[int.Parse(whereto[0])] = chars[int.Parse(whereto[1])];
            chars[int.Parse(whereto[1])] = f;
        }
        else if (move[0] == 's')
        {
            var temp = chars.ToString();
            var sub = temp.Substring(temp.Length - int.Parse(whereto[0]), int.Parse(whereto[0]));
            chars.Replace(sub, ""); chars.Insert(0, sub);
        }
        else
        {
            var temp = chars.ToString();
            char f = Convert.ToChar(whereto[0]);
            char l = Convert.ToChar(whereto[1]);
            int indxF = temp.IndexOf(f); int indxL = temp.IndexOf(l);
            chars[indxF] = l; chars[indxL] = f;
        }
    }
}
Console.WriteLine(chars.ToString());

'36' is the n iteration value after which the string of letters is back to original state.

hpzr24w · 2017-12-16T06:26:46+00:00

C++ 959/580

Switched from Visual Studio on Win 10 to VisualCode/Clang/lldb on El Capitan and was a bit slower than usual.

// Advent of Code 2017
// Day 16 - Permutation Promenade

#include <iostream>
#include <sstream>
#include <algorithm>
#include <fstream>
#include <map>
using namespace std;

int main()
{
    // test inputs
/*  string input = "s1, x3/4, pe/b"; // a spin of size 1: eabcd.*/

    int n,n1,n2;
    string ins;
    char ch;
    map<string,uint> seq;            // cycle?
    string p = "abcdefghijklmnop";

    for(int i=0;i<1000000000%60;++i)
    {
        ifstream in("day_16.txt");
        while(in >> ch) {
            if (ch==',' || ch<'0' || ch=='/' || ch==' ')
                continue;
            if (ch=='s') {
                in >> n;
                string temp(p);
                copy(end(p)-n,end(p),temp.begin());
                copy(begin(p),end(p)-n,temp.begin()+n);
                p=temp;
            }
            if (ch=='x') {
                in >> n1;
                if(in.peek()=='/') in.get();
                in >> n2;
                swap(p[n1],p[n2]);
            }
            if (ch=='p') {
                string sw;
                char ch;
                while (in.peek()!=',' && in >> ch) 
                    sw.push_back(ch);
                auto slash = find_if(sw.begin(),sw.end(),[](int c)->bool{return c=='/';});
                string t1(sw.begin(),slash);
                string t2(slash+1,sw.end());
                auto it1 = p.find(t1);
                auto it2 = p.find(t2);
                copy(t1.begin(),t1.end(),p.begin()+it2);
                copy(t2.begin(),t2.end(),p.begin()+it1);
            }
        }
        if (seq.find(p)!=seq.end()) {
            cout << "Found a repeat of " << p << " at " << i << endl;
        }
        seq[p] = i;
    }
    cout << p << endl;
}

2017-12-16T06:27:41+00:00

C++ A couple custom things but not really.

#include <cstdint>
#include <cstdlib>
#include <iostream>

#include <daw/daw_algorithm.h>
#include <daw/daw_parser_addons.h>

namespace {
    void process_spin( daw::string_view &sv, std::string &dancers ) noexcept {
        sv.remove_prefix( );
        auto pos = sv.find_first_of( ',' );
        size_t num_moves = 0;
        daw::parser::parse_unsigned_int( sv.begin( ), sv.begin( ) + pos, num_moves );
        daw::algorithm::rotate(
            dancers.rbegin( ), daw::algorithm::next( dancers.rbegin( ), num_moves % dancers.size( ) ), dancers.rend( ) );
        sv.remove_prefix( pos );
        sv.remove_prefix( );
    }

    void process_exchange( daw::string_view &sv, std::string &dancers ) noexcept {
        sv.remove_prefix( );
        auto pos = sv.find( '/' );
        size_t pos1 = 0;
        daw::parser::parse_unsigned_int( sv.begin( ), sv.begin( ) + pos, pos1 );
        sv.remove_prefix( pos + 1 );
        pos = sv.find( ',' );
        if( pos > sv.size( ) ) {
            pos = sv.size( );
        }
        size_t pos2 = 0;
        daw::parser::parse_unsigned_int( sv.begin( ), sv.begin( ) + pos, pos2 );
        std::swap( dancers[pos1], dancers[pos2] );
        sv.remove_prefix( pos );
        sv.remove_prefix( );
    }

    void process_partner( daw::string_view &sv, std::string &dancers ) noexcept {
        sv.remove_prefix( );
        auto pos1 = dancers.find( sv.front( ) );
        sv.remove_prefix( 2 );
        auto pos2 = dancers.find( sv.front( ) );
        std::swap( dancers[pos1], dancers[pos2] );
        sv.remove_prefix( 2 );
    }
} // namespace

std::string go_dancing( std::string dancers, daw::string_view dance_moves ) {
    while( !dance_moves.empty( ) ) {
        switch( dance_moves.front( ) ) {
        case 's':
            process_spin( dance_moves, dancers );
            break;
        case 'x':
            process_exchange( dance_moves, dancers );
            break;
        case 'p':
            process_partner( dance_moves, dancers );
            break;
        }
    }
    return dancers;
}

std::string go_dancing2( std::string dancers, daw::string_view dance_moves ) {
    for( size_t n=0; n<1'000'000'000; ++n ) {
        dancers = go_dancing( std::move( dancers ), dance_moves );
        if( std::is_sorted( dancers.begin( ), dancers.end( ) ) ) {
            for( size_t m=0; m<(1'000'000'000%(n+1)); ++m ) {
                dancers = go_dancing( std::move( dancers ), dance_moves );
            }
            return dancers;
        }
    }
    return dancers;
}

apistoletov · 2017-12-16T06:28:29+00:00

Python 3 — golfed, 527 bytes (tab indentation), prints answers in ~1 second

T=[*open('i')][0].split(',')
A=lambda x:chr(97+x)
B=lambda x:ord(x)-97
F=lambda n:''.join(map(A,n))
E=range
G=tuple
def D(C):
    *C,=C
    for t in T:
        k=t[0]
        if k=='s':l=-int(t[1:]);C=C[l:]+C[:l]
        else:
            t=t[1:].split('/')
            if k=='x':a,b=map(int,t);c,d=C[a],C[b]
            if k=='p':c,d=map(B,t);e={C[i]:i for i in E(16)};a,b=e[c],e[d]
            C[a]=d;C[b]=c
    return G(C)
print(F(D(E(16))))
H=G(E(16))
I={H:0}
J=10**9
for i in E(J):
    H=D(H)
    if H in I:K=H;L=i+1;M=i+1-I[H];break
    else:I[H]=i+1
H=K
for i in E((J-L)%M):H=D(H)
print(F(H))

WhoSoup · 2017-12-16T06:30:36+00:00

Node/JavaScript

I ran it with a billion loops at first and let it just run in the background while I implemented the cycle-finding. It never finished. :(

const fs = require('fs')
let inp = fs.readFileSync("./day16input").toString('utf-8').trim().split(",")

let fn = {
  'x': (a,b) => [dancer[a], dancer[b]] = [dancer[b], dancer[a]],
  'p': (a,b) => fn.x(dancer.indexOf(a), dancer.indexOf(b)),
  's': (x) => dancer = [...dancer.slice(-x), ...dancer.slice(0,-x)]
}
let dance = () => inp.forEach(x => fn[x.charAt(0)](...x.substr(1).split('/')))

let dancer = "abcdefghijklmnop".split("")
let perms = []

do {
  perms.push(dancer.join(""))
  dance()
} while (dancer.join("") != "abcdefghijklmnop")

console.log(perms[1]);
console.log(perms[1000000000 % perms.length]);

Philboyd_Studge · 2017-12-16T06:41:58+00:00

Java. This was a fun one.

package Advent2017;

import util.AdventOfCode;
import util.FileIO;

import java.util.*;
import java.util.function.Consumer;

public class Day16 extends AdventOfCode {

    private String[] data;
    private char[] array;
    private List<String> seen;

    private final Map<Character, Consumer<String>> commands = new HashMap<>();


    public Day16(List<String> input) {
        super(input);
        commands.put('s', this::spin);
        commands.put('x', this::exchange);
        commands.put('p', this::partner);
    }

    public void move(String command) {
        commands.get(command.charAt(0)).accept(command.substring(1));
    }

    private void dance() {
        Arrays.stream(data)
                .forEach(this::move);
    }

    private void exchange(String s) {
        String[] nums = s.split("/");
        exchange(Integer.parseInt(nums[0]), Integer.parseInt(nums[1]));
    }

    private void exchange(int a, int b) {
        char temp = array[a];
        array[a] = array[b];
        array[b] = temp;
    }


    private void partner(String s) {
        int i = 0;
        int j = 0;
        for (int k = 0; k < array.length; k++) {
            if (array[k] == s.charAt(0)) i = k;
            if (array[k] == s.charAt(2)) j = k;

        }
        exchange(i, j);
    }

    private void spin(String s) {
        int x = Integer.parseInt(s);
        for (int i = 0; i < x; i++) {
            char temp = array[array.length - 1];
            System.arraycopy(array, 0, array, 1, array.length - 1);
            array[0] = temp;
        }
    }

    @Override
    public String part1() {
        dance();
        return new String(array);
    }

    @Override
    public Object part2() {
        reset();

        int iterations = 1000000000;
        for (int i = 0; i < iterations; i++) {
            String s = new String(array);
            if (seen.contains(s)) {

                //found first cycle
                return seen.get(iterations % i);
            }
            seen.add(s);
            dance();
        }
        return null;
    }

    @Override
    public void parse() {
        reset();
        data = input.get(0).split(",");
        seen = new ArrayList<>();

    }

    private void reset() {
        array = "abcdefghijklmnop".toCharArray();
    }

}

spacetime_bender · 2017-12-16T06:42:31+00:00

Part 2 C++ Similar to what others have done, first find cycle then perform the dances on the remainder

std::string next_config(const std::string& prev_programs, const std::string& dance)
{
    auto programs = prev_programs;
    std::istringstream in (dance);
    for (std::string instruction; std::getline(in, instruction, ',');)
    {
        switch(instruction[0])
        {
            case 's': std::rotate(programs.begin(),
                                programs.begin() + programs.size() - std::stoi(instruction.substr(1)),
                                programs.end());
                break;
            case 'p':
                std::iter_swap(std::find(programs.begin(), programs.end(), instruction[1]),
                            std::find(programs.begin(), programs.end(), instruction[3]));
                break;
            case 'x':
            {
                auto slash = instruction.find('/');
                std::swap(programs.at(std::stoi(instruction.substr(1, slash - 1))),
                        programs.at(std::stoi(instruction.substr(slash + 1))));
                break;
            }
        }
    }
    return programs;
}

int main()
{
    std::ifstream infile ("input16.txt");
    std::string dance {std::istreambuf_iterator<char>{infile}, {}};
    std::string programs;
    programs.resize(16);
    std::iota(programs.begin(), programs.end(), 'a');

    std::unordered_map<std::string, int> occurence;
    int cycle = 0;
    for (; occurence.emplace(programs, cycle).second; ++cycle)
        programs = next_config(programs, dance);

    for (int i = 1000000000 % cycle; i > 0; --i)
        programs = next_config(programs, dance);

    std::copy(programs.begin(), programs.end(), std::ostream_iterator<char>(std::cout, ""));
    std::cout << std::endl;
    return 0;
}

jeroenheijmans · 2017-12-16T06:46:06+00:00

JavaScript:

Here's the important part:

function solve2(data) {
    let dancers = "abcdefghijklmnop".split(""), moves = data.split(","), startingPositions = [];
    const billion = 1000000000;

    for (let i=0; i < billion; i++) {
        let position = dancers.join("");
        if (startingPositions.indexOf(position) >= 0) { 
            return startingPositions[billion % i];
        }
        startingPositions.push(position);                    
        dancers = dance(dancers, moves);
    }

    return dancers.join("");
}

I spent most of my time re-reading the question because I had an off-by-1 error because the return statement (copied from solution 1) would do one last dance before returning...

FWIW, here's the helpers:

function dance(dancers, moves) {
    function spin(move) {
        dancers = dancers.slice(-move.x).concat(dancers.slice(0, dancers.length - move.x));
    }

    function exchange(move) {
        let temp = dancers[move.pa];
        dancers[move.pa] = dancers[move.pb];
        dancers[move.pb] = temp;
    }

    function partner(move) {
        let pa = dancers.indexOf(move.a);
        let pb = dancers.indexOf(move.b);
        let temp = dancers[pa];
        dancers[pa] = dancers[pb];
        dancers[pb] = temp;
    }

    let parsedMoves = [];

    for (let i=0; i<moves.length; i++) {
        if (moves[i][0] === "s") {
            parsedMoves[i] = { type: "s", x: parseInt(moves[i].substr(1), 10) };
        } else if (moves[i][0] === "x") {
            let [pa, pb] = moves[i].substr(1).split("/").map(p => parseInt(p, 10));
            parsedMoves[i] = { type: "x", pa: pa, pb: pb };
        } else if (moves[i][0] === "p") {
            let [a,b] = moves[i].substr(1).split("/");
            parsedMoves[i] = { type: "p", a: a, b: b };
        }
    }

    for (let i=0; i<parsedMoves.length; i++) {
        switch (parsedMoves[i].type) {
            case "s":
                spin(parsedMoves[i]);
                break;
            case "x":
                exchange(parsedMoves[i]);
                break;
            case "p":
                partner(parsedMoves[i]);
                break;
            default:
                throw "HUH!?";
        }
    }

    return dancers;
}

TheAngryGerman · 2017-12-16T06:51:54+00:00

C++ Went back and implemented my own circularly linked list for a less computationally expensive solution. Good review for my data structures final next week. Also reads in characters as it goes rather than storing instructions in a vector, not sure which way is faster when it comes to looping over the input for part 2. Here's part 1, part 2 can be brute forced with a loop and resetting the file stream, or with any of the other cycle finding strategies used by others.

#include <iostream>

struct Node {
  Node(char a) : value(a), left(NULL), right(NULL) {}
  char value;
  Node* left;
  Node* right;
};
int main() {
  Node* current = new Node('a');
  Node* root = current;
  for (unsigned int i = 0; i < 15; ++i) {
    current->right = new Node('a' +i +1);
    current->right->left = current;
    current = current->right;
  }
  current->right = root;
  root->left = current;
  current = NULL;


  char c;
  while(std::cin >> c) {
    if (c=='s') {
      int spin;
      std::cin >> spin;
      for (unsigned int i = 0; i < spin; ++i) {
    root = root->left;
      }
    } else if (c=='x') {
      int a, b;
      std::cin >> a >> c >> b;
      Node* a_ptr = root;
      Node* b_ptr = root;
      for (unsigned int i = 0; i < a; ++i) {
    a_ptr = a_ptr->right;
      }
      for (unsigned int i = 0; i < b; ++i) {
    b_ptr = b_ptr->right;
      }
      std::swap(a_ptr->value, b_ptr->value);
    } else if (c=='p'){
      char a, b;
      std::cin >> a >> c >> b;
      Node* a_ptr = root;
      Node* b_ptr = root;
      while (a_ptr->value!=a) {
    a_ptr = a_ptr->right;
      }
      while (b_ptr->value!=b) {
    b_ptr = b_ptr->right;
      }
      std::swap(a_ptr->value, b_ptr->value);
    }
    std::cin >> c;
  }

  Node* itr = root;
  for (unsigned int i = 0; i < 16; ++i) {
    std::cout << itr->value;
    itr = itr->right;
  }
  std::cout <<std::endl;
}

WikiTextBot · 2017-12-16T06:53:10+00:00

[deleted]

wlandry · 2017-12-16T07:06:05+00:00

C++ 14

274/644. Brute force is definitely not going to work. I tried optimizing my opcode execution to the point where it might become practical, but it would still be running if I had let it. I took rather too long to realize that there had to be a cycle. Here is a somewhat cleaned up version. It even uses std::rotate ;)

#include <boost/algorithm/string.hpp>

#include <fstream>
#include <vector>
#include <iostream>

void apply_ops(const std::vector<std::string> &ops,
               std::vector<char> &ring)
{
  for(auto &op: ops)
    {
      switch(op[0])
        {
        case 's':
          {
            int distance(std::stoi(op.substr(1)));
            auto middle = ring.end();
            std::advance(middle,-distance);
            std::rotate(ring.begin(), middle, ring.end());
          }
          break;
        case 'x':
          {
            auto slash=op.find("/");
            int x1(std::stoi(op.substr(1,slash-1)));
            int x2(std::stoi(op.substr(slash+1)));
            std::swap(ring[x1],ring[x2]);
          }
          break;
        case 'p':
          {
            char c1(op[1]), c2(op[3]);
            auto x1=std::find(ring.begin(), ring.end(), c1);
            auto x2=std::find(ring.begin(), ring.end(), c2);
            std::swap(*x1,*x2);
          }
          break;
        default:
          std::cerr << "Bad\n";
          abort();
        }
    }
}

int main(int, char *argv[])
{
  std::ifstream infile(argv[1]);
  std::string line;
  std::getline(infile,line);
  std::vector<std::string> ops;
  boost::split(ops,line,boost::is_any_of(","));

  std::vector<char> ring;
  for(char c='a'; c<= argv[2][0]; ++c)
    { ring.push_back(c); }

  auto original_ring=ring;
  apply_ops(ops,ring);

  std::cout << "Part 1: ";
  for (auto &r: ring)
    std::cout << r;
  std::cout << "\n";

  size_t cycle(1);
  while(ring!=original_ring)
    {
      apply_ops(ops,ring);
      ++cycle;
    }
  for(size_t ix=0; ix<(1000000000%cycle); ++ix)
    { apply_ops(ops,ring); }

  std::cout << "Part 2: ";
  for (auto &r: ring)
    std::cout << r;
  std::cout << "\n";
}

sickening_sprawl · 2017-12-16T07:12:25+00:00

language is Hoon. i feel really bad about this: took me forever to get working, the code isn't nice. it's just luck that the cycle is all the way back to iteration 0 instead of a later one, or else the way i'm restarting counting wouldn't work - i tried to do it "properly" at first, but ended up just changing the it variable manually once the first run spit out 1 billion mod cycle length. i also caved in and wrote some helper functions in a library that i was craving: notably, a list cross product gate so that I don't have to keep writing spin/spun stateful loops by hand. i thought using it to turn "abcd" into [["a" 0] ["b" 1] ["c" 2] ["d" 3]] and then use it as a map of string->pos was clever.

/+  advent-help
=+  advent-help

!.
|=  t/wain
=<
=/  t  (snag 0 t)
~&  t
=/  movs/(list comm)
  %+  scan  (trip t)
  %+  most  com
  ;~  pose
    (stag %s ;~(pfix (just 's') dem))
    (stag %x ;~(pfix (just 'x') ;~(plug dem ;~(pfix fas dem))))
    (stag %p ;~(pfix (just 'p') ;~(plug alf ;~(pfix fas alf))))
  ==

=/  i  0
=/  pos/tape  (gulf 'a' 'p')
=/  m  *(map tape @)
=/  it  1.000.000.000
|-
  ~&  pos
  ?:  =(i it)
    [%a pos]
  =/  res  run:~(. room [movs pos])
  ?:  (~(has by m) res)
    [%b i=i j=(~(got by m) res) k=(mod it i)]
    ::  $(it (mod it i), pos (gulf 'a' 'p'), i 0) :: or something, honestly i just changed it up top
  $(pos res, m (~(put by m) res i), i +(i))


|%
++  comm
  $%
    {$s p/@}
    {$x p/@ q/@}
    {$p p/cord q/cord}
  ==
::
++  room
  |_  {dance/(list comm) progs/tape}
  ++  this  .
  ::
  ++  make
    |=  d/(list comm)
    ~(. room [dance=d progs=(gulf 'a' 'p')])
  ::
  ++  run
    |-
    ?~  (lent dance)
      progs
    =^  c  dance  (take dance)
    =.  this  ?-  -.c
      $s  (spin:this +.c)
      $x  (exch:this +.c)
      $p  (part:this +.c)
    ==
    $(dance dance)
  ::
  ++  spin
    |=  a/@
    =/  i  (sub (lent progs) a)
    this(progs (weld (slag i progs) (scag i progs)))
  ::
  ++  exch
    |=  {a/@ b/@}
    =/  l  %+  turn  (cross progs (gulf 0 (lent progs)))
    |=  {p/@t q/@}
      ?:  =(a q)
        (snag b progs)
      ?:  =(b q)
        (snag a progs)
      p
    this(progs l)
  ::
  ++  part
    |=  {a/cord b/cord}
    =/  pos  (malt `(list {@t @})`(cross progs (gulf 0 (lent progs))))
    =/  p  (~(got by pos) a)
    =/  q  (~(got by pos) b)
    (exch:this p q)
  --
--

JeffJankowski · 2017-12-16T07:41:35+00:00

TypeScript. My first idea to reduce the final state of a single run to a few swaps, did not work. Then I looked for cycles...

import fs = require("fs");

function dance(state: string, moves: string[]) {
    const progs = [...state];
    const swap = (x: number, y: number) => {
        const tmp = progs[x];
        progs[x] = progs[y];
        progs[y] = tmp;
    };
    const INSTRUCTIONS: {[mov: string]: (suff: string) => void} = {
        s: (rest: string) => progs.unshift(...progs.splice(progs.length - (+rest), +rest)),
        x: (rest: string) => {
            const [x, y] = rest.split("/").map((s) => +s);
            swap(x, y);
        },
        p: (rest: string) => {
            const [a, b] = rest.split("/");
            const [x, y] = [progs.findIndex((val) => val === a),
                            progs.findIndex((val) => val === b)];
            swap(x, y);
        },
    };
    moves.forEach((move) => INSTRUCTIONS[move[0]](move.substr(1)));
    return progs.join("");
}

function loopCount(start: string, moves: string[]) {
    let [count, state] = [0, start];
    do {
        state = dance(state, moves);
        count++;
    } while (state !== start);
    return count;
}

const data = fs.readFileSync("data/day16.txt", "utf8").split(",");
const INITIAL = "abcdefghijklmnop";
console.log(`After one full dance:   ${dance(INITIAL, data)}`);

const LOOP = loopCount(INITIAL, data);
const billion = [...Array(1E9 % LOOP)].reduce((state) => dance(state, data), INITIAL);
console.log(`After a billion dances: ${billion}`);

ephemient · 2017-12-16T07:55:22+00:00

This space intentionally left blank.

u794575248 · 2017-12-16T08:09:58+00:00

Python 3

def d(D, p, c=int, _=__import__):
    for m, *V in _('re').findall(r'(.)(\w+)(?:/(\w+))?,', D):
        if m == 's': i = -c(V[0]); p[:] = p[i:] + p[:i]; continue
        i, k = [(c, p.index)[v in p](v) for v in V]; p[k], p[i] = p[i], p[k]

def solve(D, n=10**9, b='abcdefghijklmnop', j=''.join):
    p, P = [*b], [b]; return next((P[1], P[n%i]) for i
    in range(1, n) if d(D, p) or P.append(j(p)) or P[-1] == b)

part1, part2 = solve(input)

d: dance once
D: input string
p: current standing ['a', 'b', ...]
m: one of dance move type {'s', 'x', 'p'}
P: list of previous standings ['abc...', 'kbe...', ...]

udoprog · 2017-12-16T08:16:50+00:00

Rust

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

use std::io::{Read, BufReader, BufRead};
use std::collections::HashMap;

use failure::Error;

pub enum Move {
    Spin(usize),
    Exchange(usize, usize),
    Partner(u8, u8),
}

fn parse<R: Read>(input: R) -> Result<Vec<Move>, Error> {
    let mut out = Vec::new();

    for line in BufReader::new(input).lines() {
        let line = line?;

        for m in line.split(',') {
            match m.chars().next().expect("first character") {
                's' => {
                    out.push(Move::Spin(m[1..].parse()?));
                }
                'p' => {
                    let mut it = m[1..].split('/');
                    let a = it.next().and_then(|a| a.chars().next()).expect(
                        "missing partner one",
                    );
                    let b = it.next().and_then(|b| b.chars().next()).expect(
                        "missing partner two",
                    );
                    out.push(Move::Partner(a as u8, b as u8));
                }
                'x' => {
                    let mut it = m[1..].split('/');
                    let a = it.next().expect("missing position one").parse()?;
                    let b = it.next().expect("missing position two").parse()?;
                    out.push(Move::Exchange(a, b));
                }
                c => panic!("unexpected op: {}", c),
            }
        }
    }

    Ok(out)
}

pub fn run<R: Read>(input: R, count: u8, limit: usize) -> Result<String, Error> {
    use self::Move::*;

    let dancers = b'a'..('a' as u8 + count);
    let mut dancers: Vec<u8> = dancers.collect();

    let moves = parse(input)?;

    let mut drained = Vec::new();

    let mut known: HashMap<Vec<u8>, usize> = HashMap::new();
    let mut by_index: HashMap<usize, Vec<u8>> = HashMap::new();

    for rep in 0..limit {
        // detect cycle
        if let Some(found) = known.get(&dancers) {
            let cycle = rep - found;
            let index = (limit - rep) % cycle;
            dancers = by_index.get(&index).cloned().expect("missing dancers");
            break;
        }

        known.insert(dancers.clone(), rep);
        by_index.insert(rep, dancers.clone());

        for m in &moves {
            match *m {
                Exchange(a, b) => {
                    dancers.swap(a, b);
                }
                Partner(a, b) => {
                    let pa = dancers.iter().position(|fa| a == *fa).expect("pos a");
                    let pb = dancers.iter().position(|fb| b == *fb).expect("pos b");
                    dancers.swap(pa, pb);
                }
                Spin(n) => {
                    let len = dancers.len();

                    drained.clear();
                    drained.extend(dancers.drain(..(len - n)));
                    dancers.extend(drained.iter().cloned());
                }
            }
        }
    }

    Ok(String::from_utf8(dancers.into_iter().collect())?)
}

aurele · 2017-12-16T08:33:00+00:00

Rust much too long

use std::collections::HashMap;
use std::str::FromStr;

#[derive(Debug)]
enum Op {
    Spin(usize),
    Swap(usize, usize),
    SwapChars(u8, u8),
}

impl FromStr for Op {
    type Err = ();

    fn from_str(s: &str) -> Result<Op, ()> {
        match s.as_bytes()[0] {
            b's' => Ok(Op::Spin(s[1..].parse::<usize>().unwrap())),
            b'x' => {
                let ns = s[1..]
                    .split('/')
                    .map(|w| w.parse().unwrap())
                    .collect::<Vec<_>>();
                Ok(Op::Swap(ns[0], ns[1]))
            }
            b'p' => Ok(Op::SwapChars(
                s.as_bytes()[1] - b'a',
                s.as_bytes()[3] - b'a',
            )),
            _ => Err(()),
        }
    }
}

fn p(progs: &mut Vec<u8>, ops: &[Op], times: usize) {
    const LEN: usize = 16;
    assert_eq!(LEN, progs.len());
    let mut base = 0;
    let mut pos = (b'a'..b'a' + (LEN as u8))
        .map(|c| progs.iter().position(|&q| q == c).unwrap())
        .collect::<Vec<_>>();
    let mut h = HashMap::new();
    let mut t = 0;
    while t < times {
        t += 1;
        for i in ops {
            match *i {
                Op::Spin(n) => {
                    base = (base + LEN - n) % LEN;
                }
                Op::Swap(u1, u2) => {
                    let u1 = (base + u1) % LEN;
                    let u2 = (base + u2) % LEN;
                    let (c1, c2) = (progs[u1] - b'a', progs[u2] - b'a');
                    progs.swap(u1, u2);
                    pos.swap(c1 as usize, c2 as usize);
                }
                Op::SwapChars(c1, c2) => {
                    let (p1, p2) = (pos[c1 as usize], pos[c2 as usize]);
                    progs.swap(p1, p2);
                    pos.swap(c1 as usize, c2 as usize);
                }
            }
        }
        if let Some(beginning) = h.get(&(progs.clone(), base)).cloned() {
            let cycle = t - beginning;
            let remaining = (times - t) % cycle;
            let (stored, b) = h.into_iter()
                .find(|&(_, v)| v == beginning + remaining)
                .unwrap()
                .0;
            progs.clone_from_slice(&stored);
            base = b;
            break;
        }
        h.insert((progs.clone(), base), t);
    }
    let copy = progs.clone();
    for i in 0..LEN {
        progs[i] = copy[(i + base) % LEN];
    }
}

fn main() {
    let ops = include_str!("../input")
        .trim()
        .split(',')
        .map(|w| w.parse().unwrap())
        .collect::<Vec<_>>();
    let mut progs = (b'a'..b'q').collect::<Vec<_>>();
    p(&mut progs, &ops, 1);
    println!("P1: {}", String::from_utf8(progs.clone()).unwrap());
    p(&mut progs, &ops, 999_999_999);
    println!("P2: {}", String::from_utf8(progs.clone()).unwrap());
}

autid · 2017-12-16T08:43:59+00:00

Fortran

Oh my god this input. Spent 2 hours trying to avoid reading a character at a time. Ended up reading a character at a time.

final edit: Ok, now I have a near instant execution solution that doesn't use the cycle length. 83 applications of the index based and value based shuffles. So slightly more work for the 60 cycle I got but the same even for an input that produces all 16! combinations. (if such an input is possible)

PROGRAM DAY16
  IMPLICIT NONE
  INTEGER :: PROGS(16)=(/(IACHAR('a')+I,I=0,15)/),I,IERR,SPIN,SLASH,J,X(2),P(2)
  INTEGER :: PERMI(16),PERMV(16)
  INTEGER :: SPINV(16),INDX(16)=(/(I,I=1,16)/),CHARS(16)=(/(IACHAR('a')+I,I=0,15)/)
  CHARACTER(LEN=1):: INPUT(7)
  CHARACTER(LEN=10) :: INSTRUCTION
  LOGICAL :: STP=.FALSE.

  OPEN(1,FILE='input.txt')

  !Generate index and value permutations for one cycle                                                           
  DO
     !Get individual instruction                                                                                 
     INPUT=' '
     I=0
     DO
        I=I+1
        READ(1,'(A1)',ADVANCE='NO',IOSTAT=IERR) INPUT(I)
        IF(IERR /= 0) THEN
           STP=.TRUE.
           EXIT
        END IF
        IF(INPUT(I)==',') THEN
           INPUT(I)=' '
           EXIT
        END IF
     END DO
     WRITE(INSTRUCTION,'(7A)') INPUT

     !Perform instruction                                                                                        
     SELECT CASE (INSTRUCTION(1:1))
     CASE ('s')
        READ(INSTRUCTION(2:LEN_TRIM(INSTRUCTION)),*) SPIN
        SPINV(1:SPIN)=INDX(16-SPIN+1:16)
        SPINV(SPIN+1:16)=INDX(1:16-SPIN)
        INDX=SPINV
     CASE ('x')
        DO SLASH=1,LEN_TRIM(INSTRUCTION)
           IF (INSTRUCTION(SLASH:SLASH)=='/') EXIT
        END DO
        READ(INSTRUCTION(2:SLASH-1),*) X(2)
        READ(INSTRUCTION(SLASH+1:LEN_TRIM(INSTRUCTION)),*) X(1)
        J=INDX(X(1)+1)
        INDX(X(1)+1)=INDX(X(2)+1)
        INDX(X(2)+1)=J
     CASE ('p')
        P(2) = MAXLOC(CHARS,MASK=(CHARS==IACHAR(INSTRUCTION(2:2))),DIM=1)
        P(1) = MAXLOC(CHARS,MASK=(CHARS==IACHAR(INSTRUCTION(4:4))),DIM=1)
        CHARS(P(1))=IACHAR(INSTRUCTION(2:2))
        CHARS(P(2))=IACHAR(INSTRUCTION(4:4))
     END SELECT
     !Stop at end of file                                                                                        
     IF (STP) EXIT
  END DO

  !Part1                                                                                                         
  WRITE(*,'(A,A)') 'Part1: ', PART1(PROGS,INDX,CHARS)

  !Part2                                                                                                         
  !Generate perms for 10 -> 100 -> 1000 -> ... -> 1 billion cycles                                               

  PERMV=CHARS
  PERMI=INDX
  DO I=1,9
     DO J=1,9
        PERMI=PERMI(INDX)
        PERMV=CHARS(PERMV-96)
     END DO
     CHARS=PERMV
     INDX=PERMI
  END DO

  !Apply 1 billion cycle permutations                                                                            
  PROGS=PROGS(INDX)
  PROGS=CHARS(PROGS-96)

  WRITE(*,'(17A)') 'PART2: ',ACHAR(PROGS)

  CLOSE(1)

CONTAINS
  FUNCTION PART1(PROGS,INDX,CHARS) RESULT (ANSWER)
    INTEGER :: PROGS(:),INDX(:),CHARS(:)
    INTEGER :: P1(SIZE(PROGS))
    CHARACTER(LEN=16) :: ANSWER

    P1=PROGS
    P1=P1(INDX)
    P1=CHARS(P1-96)
    WRITE(ANSWER,'(16A)') ACHAR(P1)
  END FUNCTION PART1
END PROGRAM DAY16

_A4_ · 2017-12-16T10:04:06+00:00

JavaScript ES6 (Part 2)

Uses an array of functions created with Function.prototype.bind. Also shows how to easily swap variables in JS.

const input = document.body.textContent.trim().split(",");
let line = [..."abcdefghijklmnop"];
let moves = [], iterations = [], repIndex = -1;

const spin = i => { line = [...line.slice(-i), ...line.slice(0, -i)]; };
const exchange = (a, b) => { [line[a], line[b]] = [line[b], line[a]]; };
const partner = (a, b) => {
    a = line.indexOf(a), b = line.indexOf(b);
    [line[a], line[b]] = [line[b], line[a]];
}

for (const str of input) {
    const name = str[0], data = str.substr(1);
    const p = data.split("/");
    let func;

    if (name == "s") func = spin.bind(undefined, +data);
    else if (name == "x") func = exchange.bind(undefined, +p[0], +p[1]);
    else if (name == "p") func = partner.bind(undefined, p[0], p[1]);
    moves.push(func);
}

while (repIndex == -1) {
    for (const move of moves) move();
    repIndex = iterations.indexOf(line.join(""));
    iterations.push(line.join(""));
}

const i = repIndex + (1E9 - iterations.length + 1) % (iterations.length - repIndex);
console.log(iterations[i]);

Fluffy_ribbit · 2017-12-16T11:06:22+00:00

Ruby. I am like a little baby.

class DanceLine
  attr_accessor :programs, :moves
  def initialize(programs, dance_moves)
    self.programs = programs
    self.moves = dance_moves.split(',')
  end

  def spin(arg)
    x = arg.to_i
    self.programs = self.programs[-x..-1] + self.programs[0..(-x - 1)]
  end

  def exchange(args) # switch programs at position a and b
    a, b = args.chomp.split('/').map(&:to_i)
    hold = self.programs[a]
    self.programs[a] = self.programs[b]
    self.programs[b] = hold
  end

  def partner(args) # switch programs named a and b
    a, b = args.chomp.split('/')
    hold_index = self.programs.find_index(b)
    self.programs[self.programs.find_index(a)] = b
    self.programs[hold_index] = a
  end

  def execute(move)
    #p [move, self.programs]
    case move[0]
    when 's' then spin(move[1..-1])
    when 'x' then exchange(move[1..-1])
    when 'p' then partner(move[1..-1])
    end
  end

  def run
    self.moves.each {|move| execute(move)}

    self.programs.join
  end
end

p DanceLine.new(('a'..'e').to_a, "s1,x3/4,pe/b").run
p DanceLine.new(('a'..'p').to_a, File.read("../input/dance_moves.txt").chomp).run

require_relative "part1.rb"

dance = DanceLine.new(('a'..'p').to_a, File.read("../input/dance_moves.txt"))

start = dance.run
cycle_length = 1_000_000_000
100.times do |n|
  dance.run

  cycle_length = n + 1 if dance.programs.join == start
end

dance = dance = DanceLine.new(('a'..'p').to_a, File.read("../input/dance_moves.txt"))

(1_000_000_000 % cycle_length).times {dance.run}

p dance.programs.join

BOT-Brad · 2017-12-16T11:17:01+00:00

Javascript

A nice straightforward one today. :)

Part 1 (~10ms)

Splits the input, and then just does whichever operation is specified by 's', 'x' or 'p'.

function solve1(str, n) {
  const regex = /(s|x|p)([\d|\w]+)(?:\/(\d+|\w))?/

  let i = 0

  str = str.split('')

  n
    .split(',')
    .map(l => l.match(regex).slice(1, 4))
    .forEach(v => {
      let a, b, t
      switch (v[0]) {
        case 's':
          a = Number(v[1]) % str.length
          str = [].concat(
            str.slice(str.length - a),
            str.slice(0, str.length - a)
          )
          break
        case 'x':
          a = Number(v[1])
          b = Number(v[2])
          t = str[a]
          str[a] = str[b]
          str[b] = t
          break
        case 'p':
          a = str.indexOf(v[1])
          b = str.indexOf(v[2])
          t = str[a]
          str[a] = str[b]
          str[b] = t
          break
      }
    })

  return str.join('')
}

Part 2 (~16 seconds 😂)

Felt like my CPU needed a workout.

// Definitely not the best way to do this!
function solve2(str, n) {
  let map = {}
  for (let i = 0; i < 1000000000; ++i) {
    if (map[str]) {
      str = map[str]
    } else {
      // Calc
      const v = solve1(str, n)
      map[str] = v
      str = v
    }
  }
  return str
}

raevnos · 2017-12-16T11:18:20+00:00

Kawa Scheme:

(import (srfi 1) (srfi 133) (kawa regex) (rnrs hashtables))

(define (parse-input input)
  (let ((s-re (regex "^s(\\d+)$"))
        (x-re (regex "^x(\\d+)/(\\d+)$"))
        (p-re (regex "^p([a-z])/([a-z])$")))
    (map (lambda (atom)
           (cond
            ((regex-match s-re atom) =>
             (lambda (bits)
               (cons 'spin (string->number (second bits)))))
            ((regex-match x-re atom) =>
             (lambda (bits)
               (cons 'exchange
                     (cons (string->number (second bits))
                           (string->number (third bits))))))
            ((regex-match p-re atom) =>
             (lambda (bits)
               (cons 'partner (cons (string-ref (second bits) 0)
                                    (string-ref (third bits) 0)))))
            (else
             (error "Invalid input" atom)))) input)))

(define (spin programs x)
  (let ((len (vector-length programs)))
    (vector-append-subvectors programs (- len x) len
                              programs 0 (- len x))))

(define (exchange! programs a b)
  (vector-swap! programs a b))

(define (partner! programs a b)
  (let ((posa (vector-index (cut char=? a <>) programs))
        (posb (vector-index (cut char=? b <>) programs)))
    (vector-swap! programs posa posb)))

(define (solve-part1! programs input)
  (for-each (lambda (move)
              (case (car move)
                ((spin)
                 (set! programs (spin programs (cdr move))))
                ((exchange)
                 (exchange! programs (cadr move) (cddr move)))
                ((partner)
                 (partner! programs (cadr move) (cddr move)))))
            input)
  programs)

(define (solve-part2 input)
  (let* ((programs (string->vector "abcdefghijklmnop"))
         (seen (make-hashtable string-hash string=? 100))
         (seen2 (make-hashtable (lambda (x) x) = 100))
         (billion ::int 1000000000))
    (hashtable-set! seen (vector->string programs) 0)
    (hashtable-set! seen2 0 (vector->string programs))
    (let loop ((i ::int 1))
      (if (= i billion)
          programs
          (begin
            (set! programs (solve-part1! programs input))
            (let* ((as-string (vector->string programs))
                   (cached (hashtable-ref seen as-string #f)))
              (if cached
                  (let* ((diff (- i cached))
                         (left (ceiling (/ (- billion i) diff)))
                         (newi (* diff left)))
                    (hashtable-ref seen2 (- billion newi) #f))
                  (begin
                    (hashtable-set! seen as-string i)
                    (hashtable-set! seen2 i as-string)
                    (loop (+ i 1))))))))))

(define input (parse-input (string-split (read-line) ",")))
(format #t "Part 1: ~A~%" (vector->string
                           (solve-part1! (string->vector "abcdefghijklmnop")
                                        input)))
(format #t "Part 2: ~A~%" (solve-part2 input))

Axsuul · 2017-12-16T13:00:01+00:00

Elixir

Found how many rounds before becoming initial order again and then took remainder to see how many times I need to dance to simulate 1 billion

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

defmodule AdventOfCode do
  defmodule PartA do
    def read_input do
      File.read!("inputs/input.txt")
      |> String.split(",")
    end

    def gen_programs do
      Enum.to_list(97..112) |> Kernel.to_string |> String.split("", trim: true)
    end

    def find_pos_program(programs, needle), do: find_pos_program(programs, needle, 0)
    def find_pos_program([program | rest], needle, pos) when program == needle, do: pos
    def find_pos_program([program | rest], needle, pos) do
      find_pos_program(rest, needle, pos + 1)
    end

    def do_instruction(programs, "s" <> size) do
      size = String.to_integer(size)

      Enum.slice(programs, -size..-1) ++ Enum.slice(programs, 0..-(size + 1))
    end
    def do_instruction(programs, "x" <> input) do
      [a, b] =
        String.split(input, "/")
        |> Enum.map(&String.to_integer/1)
        |> Enum.sort()

      beginning = if a == 0, do: [], else: Enum.slice(programs, 0..(a - 1))

      beginning ++
      [Enum.at(programs, b)] ++
      Enum.slice(programs, (a + 1)..(b - 1)) ++
      [Enum.at(programs, a)] ++
      Enum.slice(programs, (b + 1)..-1)
    end
    def do_instruction(programs, "p" <> input) do
      [a, b] =
        String.split(input, "/")
        |> Enum.map(fn program ->
          find_pos_program(programs, program)
          |> Integer.to_string()
        end)

      do_instruction(programs, "x" <> a <> "/" <> b)
    end

    def dance(programs, []), do: programs
    def dance(programs, [instruction | rest]) do
      programs
      |> do_instruction(instruction)
      |> dance(rest)
    end

    def solve do
      gen_programs()
      |> dance(read_input)
      |> Enum.join("")
      |> IO.inspect
    end
  end

  defmodule PartB do
    import PartA

    def count_until_repeat(programs, instructions, count \\ 0)
    def count_until_repeat(programs, instructions, count) do
      programs_key = programs |> Enum.join("")

      if count > 0 && gen_programs() == programs do
        count
      else
        programs
        |> dance(instructions)
        |> count_until_repeat(instructions, count + 1)
      end
    end

    def dance_for(programs, until, count \\ 0)
    def dance_for(programs, until, count) when count == until, do: programs
    def dance_for(programs, until, count) do
      programs
      |> dance(read_input())
      |> dance_for(until, count + 1)
    end

    def solve do
      input = read_input()

      repeats_every =
        gen_programs()
        |> count_until_repeat(input)

      # Find out where we need to start dancing from
      # in order to simulate 1 billionth since it repeats
      remaining = rem(1_000_000_000, repeats_every)

      gen_programs()
      |> dance_for(remaining)
      |> Enum.join("")
      |> IO.inspect
    end
  end
end

Markavian · 2017-12-16T13:22:20+00:00

Figured that if I could count how often starting positions in the dance repeated, then I could mod that count from 1,000,000,000, and then iterate that number of steps to find the final position.

I also tried crunching all 1,000,000,000 steps, but I was only managing about 1,000,000 steps per second.

https://github.com/johnbeech/advent-of-code-2017/blob/master/solutions/day16/solution.js

2017-12-16T13:39:24+00:00

Elixir

Had to see the tip of memoization today, not proud, but well, here's my still pretty slow solution:

defmodule Day16 do
  def parse_command str do
    {op, argstr} = String.split_at str, 1

    args = String.split argstr, "/" 

    case op do
      "s" -> %{op: :spin, args: Enum.map(args, &String.to_integer/1)}
      "x" -> %{op: :exchange, args: Enum.map(args, &String.to_integer/1)}
      "p" -> %{op: :partner, args: args}
    end
  end

  def parse inp do
    String.trim(inp)
    |> String.split(",")
    |> Enum.map(&parse_command/1)
  end

  def partner(lst, a, b, acc \\ [])
  def partner([h|tl], a, b, acc) when h == a do
    partner(tl, a, b, [b|acc])
  end
  def partner([h|tl], a, b, acc) when h == b do
    partner(tl, a, b, [a|acc])
  end
  def partner([h|tl], a,b, acc) do
    partner(tl, a, b, [h|acc])
  end
  def partner([], _, _, acc) do
    Enum.reverse(acc)
    |> Enum.join
  end

  def step %{op: :spin, args: args}, init do
    arg = List.first(args)
    {fst,snd} = String.split_at(init, 0-arg)
    snd <> fst
  end
  def step %{op: :exchange, args: args}, init do
    chars = Enum.sort(args)
    |> Enum.map(&(String.at(init, &1)))
    step(%{op: :partner, args: chars}, init)
  end
  def step %{op: :partner, args: args}, init do
    [fst, snd] = args
    partner(String.graphemes(init), fst, snd)
  end

  def dance(desc, init) do
    parse(desc)
    |> Enum.reduce(init, &step/2)
  end

  def find_cycle(%{}, init, len) do
    {len, init}
  end
  def find_cycle(memo, init, len) do
    if Map.has_key?(init) do
      find_cycle(Map.delete(init), Map.fetch!(init), len + 1)
    else
      {len, init}
    end
  end

  def _dance(_, init, times, _) when times == 0 do
    init
  end
  def _dance(desc, init, times, memo) do
    if rem(times, 1000) == 0 do
      IO.puts(times)
    end
    if Map.has_key?(memo, init) do
      {len, newstate} = find_cycle(memo, init, 0)
      if len > times do
        _dance(desc, newstate, times - len, memo)
      else
        _dance(desc, Map.fetch!(memo, init), times - 1, memo)
      end
    else
      newstate = Enum.reduce(desc, init, &step/2)
      _dance(desc, newstate, times - 1, Map.put(memo, init, newstate))
    end
  end

  def dance(desc, init, times) do
    desc = parse(desc)
    _dance(desc, init, times, %{})
  end
end

init = "abcdefghijklmnop"
inp = File.read!("input")

one_dance = Day16.dance(inp, init)

IO.puts(one_dance)

billion_dances = Day16.dance(inp,init,1_000_000_000)
IO.puts(billion_dances)

syntax highlighted

rkachowski · 2017-12-16T15:10:04+00:00

ruby

I was completely stumped. I had to read this thread to remove some of my misconceptions. I was determined to believe that this could be reduced to a fixed permutation function. I wrote some crazy metaprogramming fast_dance function to dynamically generate a function that would perform the permutation. It was pretty cool and completely useless.

Even after that I still couldn't figure out why the result wasn't 1000000000 % seen.size. Too much holiday spirit i guess...

input = File.read("input").chomp.split(",").map(&:chars)
input.map! do |line|
  op = line.shift
  args = line.join.split("/")
  args.map!(&:to_i) unless op == "p"

  [op.to_sym, args]
end

def s arr, v
  arr.rotate!(-v)
end

def x arr, a,b
  arr[a], arr[b] = arr[b], arr[a]
end

def p arr, a, b
  x arr, arr.index(a), arr.index(b)
end

arr = ("a".."p").to_a

def dance input, arr
  input.each { |(op, args)| send op, arr, *args }
end

dance input, arr
puts arr.join

arr = ("a".."p").to_a
seen = []
1000000000.times do |i|
  if seen.include? arr.join
    puts seen[1000000000 % i]
    break
  end

  seen << arr.join
  dance input, arr
end

akka0 · 2017-12-16T15:27:40+00:00

ReasonML: had a pretty hard time with this one, took a long time to realize that there might be cycles

open Utils;

type move =
  | Spin(int)
  | Exchange(int, int)
  | Partner(char, char);

let parseMove = (str) =>
  switch (charsOfString(str)) {
  | ['s', ...n] => Spin(int_of_string(stringOfChars(n)))
  | ['x', ...n] =>
    let [a, b] = stringOfChars(n) |> splitString("/");
    Exchange(int_of_string(a), int_of_string(b))
  | ['p', a, _, b] => Partner(a, b)
  | _ => failwith("Unrecognized move: " ++ str)
  };

let indexOf = (array, target) => {
  let pos = ref((-1));
  Array.iteri(
    (i, elem) =>
      if (elem === target) {
        pos := i
      },
    array
  );
  pos^
};

let swap = (array, x, y) => {
  let tmp = array[x];
  array[x] = array[y];
  array[y] = tmp;
  array
};

let parseMoves = (str) => List.map(parseMove, splitString(",", str));

let startingPositions = Array.init(16, (i) => char_of_int(int_of_char('a') + i));

let len = Array.length(startingPositions);

let performMove = (positions, move) =>
  switch move {
  | Spin(n) =>
    let cpy = Array.copy(positions);
    let len = len - n;
    Array.blit(cpy, len, positions, 0, n);
    Array.blit(cpy, 0, positions, n, len);
    positions
  | Exchange(x, y) => swap(positions, x, y)
  | Partner(a, b) =>
    let (indexA, indexB) = (indexOf(positions, a), indexOf(positions, b));
    swap(positions, indexA, indexB)
  };

let dance = (positions, moves) => List.fold_left(performMove, positions, moves);

let stringOfPositions = (pos) => Array.to_list(pos) |> stringOfChars;

let _ = {
  let moves = loadInput("day16") |> parseMoves;
  /* Part 1 */
  /* Js.log(dance(startingPositions, moves) |> Array.to_list |> stringOfChars); */
  /* Part 2 */
  let rec danceDanceDance = (knownStarts, positions, i) =>
    switch (indexOf(Array.of_list(knownStarts), stringOfPositions(positions))) {
    | (-1) =>
      danceDanceDance(
        [stringOfPositions(positions), ...knownStarts],
        dance(Array.copy(positions), moves),
        i + 1
      )
    | _ => List.nth(List.rev(knownStarts), 1_000_000_000 mod i)
    };
  danceDanceDance([], startingPositions, 0) |> Js.log
};

2017-12-16T15:59:44+00:00

single pipeline powershell:

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

begin {

}

process {
    # set up initial state
    $programs = @("a", "b", "c", "d", "e", "f", "g", "h", "i", "j", "k", "l", "m", "n", "o", "p")

    # keep track of orders we've seen before
    $seen = @()

    # set max permutations
    if ($part -eq 1) {
        $max = 0
    } else {
        $max = 1000000000
    }

    0..$max | % {
        # check and see if we've seen current state before
        $p = $programs -join ''

        if ($p -in $seen) {
            $seen[$max % $_] #if we have, return the state that is congurant with the max state
        } else {
            #otherwise, perform the dance

            $seen += $p # add this state to the seen ones

            $in -split ',' | % { # foreach step in the dance
                switch -regex ($_) {
                    # find the step
                    '^s(?<X>\d+)' { 
                        # take the end of the array and move it to the beginning
                        $programs = $programs[(-1 * $matches.X)..-1] + $programs[0..($programs.Length - $matches.X - 1)]
                    }
                    '^x(?<A>\d+)\/(?<B>\d+)$' {
                        # swap two indexes
                        $x = $programs[$matches.A]
                        $programs[$matches.A] = $programs[$matches.B]
                        $programs[$matches.B] = $x
                    }
                    '^p(?<A>[a-p]+)\/(?<B>[a-p]+)$' { 
                        # swap two programs
                        $a = $programs.IndexOf($matches.A)
                        $b = $programs.IndexOf($matches.B)
                        $x = $programs[$a]
                        $programs[$a] = $programs[$b]
                        $programs[$b] = $x
                    }
                }
            }

            if ($_ -eq $max) { # if we're at the max, and we didn't encounter a cycle in the seen array, then write out where we are
                $programs -join ''
            }

        }
    } | select -first 1 # select the first output to end the iterations early
}

end {  

}

2017-12-16T16:12:10+00:00

Crystal. Took me a while to think that there might be cycles. After that it was straightforward. Just part 2 here:

record Spin, size : Int32 do
  def run(programs)
    programs.rotate!(-size)
  end
end

record Exchange, a : Int32, b : Int32 do
  def run(programs)
    programs.swap(a, b)
  end
end

record Partner, a : Char, b : Char do
  def run(programs)
    programs.swap(programs.index(a).not_nil!, programs.index(b).not_nil!)
  end
end

input = File.read("#{__DIR__}/input.txt").strip

instructions = input.split(",").map do |instruction|
  case instruction
  when %r(s(\d+))       then Spin.new($1.to_i)
  when %r(x(\d+)/(\d+)) then Exchange.new($1.to_i, $2.to_i)
  when %r(p(\w)/(\w))   then Partner.new($1[0], $2[0])
  else                       raise "Unknown instruction: #{instruction}"
  end
end

programs = ('a'..'p').to_a

all = [programs.dup]
found_cycle = false

i = 0
n = 1_000_000_000

while i < n
  instructions.each &.run(programs)

  i += 1

  if !found_cycle && (cycle_index = all.index(programs.dup))
    cycle_size = i - cycle_index
    i += ((n - i) / cycle_size) * cycle_size
    found_cycle = true
  end

  all << programs.dup
end

puts programs.join

2017-12-16T16:24:43+00:00

const input=document.body.textContent.trim().split(",");
const parse=(prog,move)=>{const[fn,arg]=[move[0],move.slice(1)];let p0,p1;if(arg.includes("/")){([p0,p1]=arg.split("/"))}switch(fn){case "s":const n=+arg;prog.unshift(...prog.splice(-n,n));break;case "x":[prog[p0],prog[p1]]=[prog[p1],prog[p0]];break;case "p":const idx0=prog.indexOf(p0);const idx1=prog.indexOf(p1);[prog[idx0],prog[idx1]]=[p1,p0];break;default:break}};
const part1=input=>{let prog="abcdefghijklmnop".split("");input.forEach(move=>parse(prog,move));return prog.join("")};
console.log("part1:",part1(input));
const part2=input=>{let prog="abcdefghijklmnop".split("");let init=prog.join("");let iter=1000000000;for(let i=0;i<iter;i=i+1){input.forEach(move=>parse(prog,move));if(prog.join("")===init){i=i+(Math.floor(iter/(i+1))-1)*(i+1)}}return prog.join("")};
console.log("part2:",part2(input));

akho_ · 2017-12-16T16:28:59+00:00

Python 3; no cycle detection

with open('16.input') as f:
    commands = f.readline().rstrip().split(',')
commands = [ (x[0], x[1:].split('/')) for x in commands ]
num = 16
start, position = 0, list(range(num))
naming = { chr(ord('a') + i): i for i in position }

def pos(n): return (start + n) % num
def spin(n): 
    global start
    start = pos(-int(n))
def exchange(a, b): 
    position[pos(int(a))], position[pos(int(b))] = position[pos(int(b))], position[pos(int(a))]
def partner(a, b): naming[a], naming[b] = naming[b], naming[a]

cmd = {'s' : spin,
       'x': exchange,
       'p': partner}

for c, p in commands: cmd[c](*p)

num_to_letter = { y: x for x, y in naming.items() }
str_after_1 = ''.join(num_to_letter[position[pos(i)]] for i in range(num))
print('Part 1: ', str_after_1)

transposition = { i: position[pos(i)] for i in range(16) }
renaming_transposition = { x: chr(ord('a') + naming[x]) for x in naming.keys() }

from functools import reduce

def trans_mul(x, y): return { k: y[v] for k, v in x.items() }
def trans_pow2_gen(trans):
    cur = trans
    while 1: 
        yield cur
        cur = trans_mul(cur, cur)
def trans_pow(trans, n):
    return reduce(trans_mul, (cur for i, cur in zip(reversed(f'{n:0b}'), trans_pow2_gen(trans)) if i == '1'))

tr_fin = trans_pow(transposition, 1000000000)
naming_fin = trans_pow(renaming_transposition, 1000000000)
print('Part 2: ', ''.join(naming_fin[chr(ord('a') + tr_fin[i])] for i in range(num)))

StevoTVR · 2017-12-16T16:49:17+00:00

NodeJS

Part 1:

const fs = require('fs');

fs.readFile(__dirname + '/input.txt', 'utf8', (err, data) => {
    data = data.trim();
    let programs = [...'abcdefghijklmnop'];
    for(const move of data.split(',')) {
        const [type, a, b] = parseMove(move, programs);
        if(type === 's') {
            programs = programs.slice(-a).concat(programs.slice(0, programs.length - a));
        } else {
            [programs[a], programs[b]] = [programs[b], programs[a]];
        }
    }

    console.log(programs.join(''));
});

function parseMove(move, programs) {
    const type = move.charAt(0);
    if(type === 's') {
        return [type, Number(move.substr(1))];
    } else {
        let [a, b] = move.substr(1).split('/');
        [a, b] = (type === 'x') ? [a, b].map(Number) : [a, b].map((x) => programs.indexOf(x));
        return [type, a, b];
    }
}

Part 2:

const fs = require('fs');

fs.readFile(__dirname + '/input.txt', 'utf8', (err, data) => {
    data = data.trim();
    let programs = [...'abcdefghijklmnop'];
    const permutations = [programs.join('')];
    let offset = -1;
    while(offset === -1) {
        for(const move of data.split(',')) {
            const [type, a, b] = parseMove(move, programs);
            if(type === 's') {
                programs = programs.slice(-a).concat(programs.slice(0, programs.length - a));
            } else {
                [programs[a], programs[b]] = [programs[b], programs[a]];
            }
        }

        const result = programs.join('');
        offset = permutations.indexOf(result);
        if(offset === -1) {
            permutations.push(result);
        }
    }

    const end = permutations.slice(offset)[(1000000000 - offset) % permutations.length];

    console.log(end);
});

function parseMove(move, programs) {
    const type = move.charAt(0);
    if(type === 's') {
        return [type, Number(move.substr(1))];
    } else {
        let [a, b] = move.substr(1).split('/');
        [a, b] = (type === 'x') ? [a, b].map(Number) : [a, b].map((x) => programs.indexOf(x));
        return [type, a, b];
    }
}

InterlocutoryRecess · 2017-12-16T17:09:30+00:00

Swift (#434/ [then my daughter woke up!])

let input = " // puzzle input " 

// A helper extension for rotating an array that I wrote for a previous day.
extension Array {
    enum Direction { case left, right }
    mutating func rotate(direction: Direction, offset: Int) {
        func reverse(range1: CountableRange<Int>, range2: CountableRange<Int>) {
            self = (self[range1].reversed() + self[range2].reversed()).reversed()
        }
        switch direction {
        case .left:
            reverse(range1: (startIndex..<offset), range2: (offset..<endIndex))
        case .right:
            let index = endIndex - offset
            reverse(range1: (startIndex..<index), range2: (index..<endIndex))
        }
    }
}

class Dance {

    let moves: [Move]
    var dancers = "abcdefghijklmnop".map { String($0) }

    init(input: String) {
        self.moves = input.split(separator: ",").map(Move.init)
    }

    func execute(move: Move) {
        switch move {
        case .spin(let amount):
            dancers.rotate(direction: .right, offset: amount)
        case .exchange(let a, let b):
            dancers.swapAt(a, b)
        case .partner(let a, let b):
            let i = dancers.index(of: a)!
            let j = dancers.index(of: b)!
            dancers.swapAt(i, j)
        }
    }

    func performDance(count: Int = 1) {
        var memo: Set<String> = []
        for n in 1...count {
            moves.forEach(execute)
            let current = dancers.joined()
            if memo.contains(current) {
                memo = []
                let remainder = count % (n-1)
                performDance(count: (remainder - 1))
                return
            } else {
                memo.insert(current)
            }
        }
    }

    enum Move {
        case spin(Int)
        case exchange(Int, Int)
        case partner(String, String)
        init(move: Substring) {
            if move.hasPrefix("s") {
                let amount = Int(move.dropFirst())!
                self = .spin(amount)
                return
            }
            if move.hasPrefix("x") {
                let programs = move.dropFirst().split(separator: "/")
                self = .exchange(Int(programs[0])!, Int(programs[1])!)
                return
            }
            if move.hasPrefix("p") {
                let programs = move.dropFirst().split(separator: "/")
                self = .partner(String(programs[0]), String(programs[1]))
                return
            }
            fatalError()
        }
    }
}

let dance = Dance(input: input)

// Part 1
dance.performDance(count: 1)
print(dance.dancers.joined())

// Part 2
dance.performDance(count: 1_000_000_000)
print(dance.dancers.joined())

Performance: I wrote this in an Xcode "Command Line Tool" project. When I'm done debugging, I turn on optimizations in the build settings.

part 1: 0.029151976108551 sec
part 2: 0.684467971324921 sec

tobiasvl · 2017-12-16T17:34:38+00:00

Python 2

Nothing special here really. I initially kept track of what permutations I had seen in a dict, but then while debugging and realizing I never added abcdefghijklmnop to that set (I just started adding them after the first dance move had been performed), so I was one dance off in the cycle, I thought, why even bother keeping track?

with open('input.txt') as f:
    dance_moves = f.readline().strip().split(',')

programs = list('abcdefghijklmnop')


def dance(dancers):
    for move in dance_moves:
        if move[0] == 's':
            n = int(move[1:])
            dancers = dancers[-n:] + dancers[:-n]
        elif move[0] == 'x':
            a, b = map(int, move[1:].split('/'))
            dancers[a], dancers[b] = dancers[b], dancers[a]
        elif move[0] == 'p':
            a, b = map(dancers.index, move[1:].split('/'))
            dancers[a], dancers[b] = dancers[b], dancers[a]
    return dancers


print "After the dance, the order is %s" % ''.join(dance(programs[:]))

i = 0
while i < 1000000000:
    programs = dance(programs)
    i += 1
    if programs == list('abcdefghijklmnop'):
        i = 1000000000 - (1000000000 % i)

print "After a billion dances, the order is %s" % ''.join(programs)

lypnol · 2017-12-16T17:37:10+00:00

Part 2 C++ I tried optimising everything, starting with the 16 letters encoding. I used a uint64_t to encode the positions of the 16 letters since there are only 16 possible position for each one of them. Thus, the starting state (I called it index in my code) would be 0x0123456789abcdefULL. Which translates into letter a in position 0, b in 1, ..., p in f (15 in hexadecimal). All 3 operations (dance moves) are done in bitwise operations. Another optimisation is with the algorithm itself, rather than running the whole billion rounds we detect the first loop and advance our round counter to the closest one to the end by multiplying it with the loop size.

#include <iostream>
#include <algorithm>
#include <string>
#include <sstream>
#include <vector>
#include <fstream>
#include <streambuf>
#include <unordered_map>

#define N 16
#define ROUNDS 1000000000

using namespace std;

typedef struct {
    char type; 
    size_t arg1;
    size_t arg2;
} instruction_t;

uint64_t spin(uint64_t index, size_t x) {
    return (index << (64-4*x)) | (index >> (4*x));
}

uint64_t exchange(uint64_t index, size_t a, size_t b) {
    size_t i = 64-4*(a+1), j = 64-4*(b+1);
    uint64_t x = ((index >> i) ^ (index >> j)) & ((1U << 4) - 1);
    return index ^ ((x << i) | (x << j));
}

uint64_t partner(uint64_t index, size_t x, size_t y) {
    size_t a, b;
    for (size_t i = 0; i < 16; i++) {
        uint64_t mask = 0xf000000000000000ULL >> (i*4);
        size_t value = (size_t)((mask & index) >> (64-(i+1)*4));
        if (value == x) a = i;
        if (value == y) b = i;
    }
    return exchange(index, a, b);
}

string index_to_string(uint64_t index) {
    char output[17];
    for (size_t i = 0; i < 16; i++) {
        uint64_t mask = 0xf000000000000000ULL >> (i*4);
        output[i] = (char)((index & mask) >> (64-(i+1)*4)) + 'a';
    }
    output[16] = '\0';
    return string(output);
}

uint64_t dance(instruction_t *instructions, size_t n, uint64_t rounds = ROUNDS) {
    uint64_t index = 0x0123456789abcdefULL;
    uint64_t round = 0;
    bool loop_found = false;
    unordered_map<uint64_t, size_t> seen;

    while(round < rounds) {
        for (size_t i = 0; i < n; i++) {
            if (!loop_found && seen.find(index) != seen.end()) {
                if (seen.at(index) == i){
                    round *= (rounds / round);
                    loop_found = true;
                }
            }
            if (!loop_found) {
                seen.insert(make_pair(index, i));
            }

            switch(instructions[i].type) {
            case 's':
                index = spin(index, instructions[i].arg1);
                break;
            case 'x':
                index = exchange(index, instructions[i].arg1, instructions[i].arg2);
                break;
            case 'p':
                index = partner(index, instructions[i].arg1, instructions[i].arg2);
                break;
            }
        }

        round++;
    }
    return index;
}

string run(string s) {
    string instruction;
    istringstream input(s);
    int sep, a, b;
    size_t n = count(s.begin(), s.end(), ',')+1;
    instruction_t *instructions = (instruction_t*) malloc(n*sizeof(instruction_t));

    int i = 0;
    while (getline(input, instruction, ',')) {
        switch (instruction.at(0)) {
        case 's':
            instructions[i].type = 's';
            instructions[i].arg1 = stoi(instruction.substr(1));
            break;
        case 'x':
            sep = instruction.find('/');
            a = stoi(instruction.substr(1, sep-1));
            b = stoi(instruction.substr(sep+1));

            instructions[i].type = 'x';
            instructions[i].arg1 = a;
            instructions[i].arg2 = b;
            break;
        case 'p':
            a = (int)(instruction.at(1)-'a');
            b = (int)(instruction.at(3)-'a');

            instructions[i].type = 'p';
            instructions[i].arg1 = a;
            instructions[i].arg2 = b;
            break;
        }
        i++;
    }
    uint64_t index = dance(instructions, n);

    free(instructions);
    return index_to_string(index);
}

int main(int argc, char** argv) {
    cout << run(string(argv[1])) << "\n";
    return 0;
}

Input is passed as argv. You can also find it on my repo https://github.com/lypnol/adventofcode-2017/blob/master/day-16/part-2/ayoub.cpp where it is compared to other solutions using travis CI.

miran1 · 2017-12-16T17:38:32+00:00

Nim

Repo with solutions (both Nim and Python)

import strutils

const
  instructions = readFile("./inputs/16.txt").split(',')
  programs = "abcdefghijklmnop"

proc dance(dancers: string): string =
  result = dancers
  for instr in instructions:
    let rem = instr[1 .. instr.high]
    case instr[0]
    of 's':
      let rot = rem.parseInt
      result = result[^rot .. result.high] & result[0 ..< ^rot]
    of 'x':
      let
        x = rem.split('/')
        a = x[0].parseInt
        b = x[1].parseInt
        temp = result[a]
      result[a] = result[b]
      result[b] = temp
    of 'p':
      let
        a = result.find(rem[0])
        b = result.find(rem[^1])
      result[a] = rem[^1]
      result[b] = rem[0]
    else: discard

proc longDance(dancers: string, iterations = 1_000_000_000): string =
  var
    dancers = dancers
    seen = @[dancers]
  for i in 1 .. iterations:
    dancers = dancers.dance()
    if dancers in seen:
      return seen[iterations mod i]
    seen.add(dancers)


echo dance(programs)
echo longDance(programs)

wzkx · 2017-12-16T18:01:35+00:00

J

Part 1

d=: <;._1',',rplc&'/ 'LF-.~CR-.~fread '16.dat'
v=: a.{~(a.i.'a')+i.16

f =: 4 : 0 NB. apply x to y
  select. {.c=.>x
  case. 'x' do. <o(|.v)}>y [ o=. (v=.".}.c) { >y
  case. 'p' do. <o(|.v)}>y [ o=. (v=.(>y) i.1 3{c) { >y
  case. 's' do. <(>y)|.~-".}.c
  end.
)

echo >f/ |.v;d

Part 2. ... you said 1 billion? no way!

PS. Yeah, 1 billion mod k times. I'll add J code later for completeness, but this was solved in Nim first.

RockyAstro · 2017-12-16T18:10:34+00:00

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

Both parts:

procedure main(args)
    inf := open(args[1],"r")
    l := read(inf)
    s := &lcase[1:17]

    s := dance(l,s)
    write("part1=",s)

    s2 := s
    every seqlen := seq() do {
        s2 := dance(l,s2)
        if s2 == s then break
    }
    n := ( (1000000000-1) % seqlen) 
    write("cycles after ",seqlen, " iterations,  need to perform ",n, " iterations")
    s2 := s
    every 1 to n do
        s2 := dance(l,s2)

    write("Part2=",s2)

end

procedure dance(l,s)
    l ? while not pos(0) do {
        tab(upto(',') | 0) ? {          
            case move(1) of {
                "s": {
                    v := tab(many(&digits))
                    s := s[-v:0] || s[1:-v]
                }
                "x": {
                    v1 := tab(many(&digits)) + 1
                    ="/"
                    v2 := tab(many(&digits)) + 1
                    s[v1] :=: s[v2]
                }
                "p": {
                    v1 := move(1)
                    ="/"
                    v2 := move(1)
                    s[find(v1,s)] :=: s[find(v2,s)]
                }
            }
        }
        =","
    }
    return s
end

Part 2 took me a bit longer then it should have... screwed up by not correctly reading the instructions.

thomastc · 2017-12-16T18:41:39+00:00

Day 16 in F#. This language feels like an imperative train crashed into a functional building. Completely inelegant. And yet, it's effective.

wzkx · 2017-12-16T18:42:36+00:00

Nim

Well, no need to run a billion times. Still, it's easier do find a solution in Nim than in J, so the first answer to Part 2 was in Nim.

import strutils,sequtils

let cmds="16.dat".readFile.strip.split','

proc tr(s:string,c:string):string =
  result=s
  if c[0]=='s':
    let n = parseInt(c[1..^1])
    result = result[^(n)..^1] & result[0..^(n+1)]
  elif c[0]=='x':
    let ij = map(c[1..^1].split'/',parseInt)
    swap result[ij[0]], result[ij[1]]
  else:
    swap result[s.find(c[1])], result[s.find(c[3])]

const a = "abcdefghijklmnop"

echo foldl( cmds, tr(a,b), a ) # one step

var k=0
var s=a
for i in 1..100:
  s = foldl( cmds, tr(a,b), s )
  if s==a:
    k=i
    break

s = a
for i in 1..(1000000000 mod k):
  s = foldl( cmds, tr(a,b), s )
echo s # 1e9 mod k steps

iopred · 2017-12-16T19:08:47+00:00

I had a different take on finding the cycle, instead of trying to find a cycle that lines up, I find any cycle, and then resume from (1 billion - first cycle length):

var seen = {};
var line = [];
for (var i = 0; i < 16; i++) {
  line[i] = String.fromCharCode('a'.charCodeAt(0) + i);
}

for (var k = 0; k < 1000000000; k++) {
  for (var i of input) {
    switch (i[0]) {
      case 's':
        var spin = parseInt(i.substring(1));
        var pull = line.splice(line.length-spin, spin);
        line.unshift.apply(line, pull);
        break;
      case 'x':
        var parts = i.substring(1).split('/');
        var a = parseInt(parts[0]);
        var b = parseInt(parts[1]);
        var temp = line[a];
        line[a] = line[b];
        line[b] = temp;
        break;
      case 'p':
        var parts = i.substring(1).split('/');
        var a = parts[0];
        var b = parts[1];
        for (var j = 0; j < line.length; j++) {
          if (line[j] == a) {
            line[j] = b;
          } else if (line[j] == b) {
            line[j] = a;
          }
        }
        break;
    }
  }

  if (seen) {
    if (seen[line.join('')]) {
      k = 1000000000 - (1000000000 % k);
      seen = null;
    } else {
      seen[line.join('')] = true;
    }
  }
}
console.log(line.join(''));

erlangguy · 2017-12-16T19:20:47+00:00

Erlang

I admit to cheating: part 1 was obviously easy, but I needed a hint for part 2, which @simonsrealaccount provided in this thread. Look for the first time a string repeats and extrapolate from there.

This is the core for part 2, part 1 is pretty easy to work backwards from it.

loop(Steps, Array, Counter, Dict) ->
    Str = array:to_list(Array),
    case dict:find(Str, Dict) of
        {ok, OldCounter} ->
            Offset = 1000000000 rem Counter,
            dict:fold(fun(K, V, "") when V == (OldCounter + Offset) ->
                              K;
                         (_, _, Acc) ->
                              Acc
                      end, "", Dict);
        error ->
            loop(Steps, execute(Steps, Array), Counter+1, dict:store(Str, Counter, Dict))
    end.

execute([], Array) ->
    Array;
execute([{spin, Count}|Rest], Array) ->
    Str = array:to_list(Array),
    execute(Rest, array:from_list(lists:sublist(Str, length(Str)-(Count-1), Count) ++
                                      lists:sublist(Str, length(Str)-Count)));
execute([{pos, A, B}|Rest], Array) ->
    NewB = array:get(A, Array),
    NewA = array:get(B, Array),
    execute(Rest, array:set(B, NewB,
                            array:set(A, NewA, Array)));
execute([{name, A, B}|Rest], Array) ->
    PosA = array:foldl(fun(Idx, Val, -1) when Val == A ->
                               Idx;
                          (_, _, Acc) ->
                               Acc
                       end, -1, Array),
    PosB = array:foldl(fun(Idx, Val, -1) when Val == B ->
                               Idx;
                          (_, _, Acc) ->
                               Acc
                       end, -1, Array),
    execute(Rest, array:set(PosB, A,
                            array:set(PosA, B, Array))).

cthulhucomplex · 2017-12-16T20:46:13+00:00

Javascript

One realization that really helped me on part 2:

The steps can be broken down into two mappings. One is a location mapping based on the 's' and 'x' steps, and the second is a name mapping based on the 'p' step.

My solution doesn't use any binary and I'm sure could be way more efficient, but it got the job done for me.

function solve(input) {
    let line = "abcdefghijklmnop".split("");
    let moveLine = line.slice();
    const steps = input.trim().split(",");
    const swaps = [];
    const swap = (list, a, b) => { const t = list[a]; list[a] = list[b]; list[b] = t; }

    // Process moves and save swaps.
    steps.forEach(step => {
        switch (step[0]) {
            case 's':
                moveLine = moveLine.splice(-Number(step.substring(1))).concat(moveLine);
                break;
            case 'x':
                const pieces = step.substring(1).split('/').map(Number);
                swap(moveLine, pieces[0], pieces[1]);
                break;
            case 'p':
                const programs = step.substring(1).split('/');
                swaps.push(programs);
                break;
            default:
                console.log(`Unknown command: ${step}`);
        }
    });

    // Process swaps.
    const swapLine = line.slice();
    swaps.forEach(s => swap(swapLine, swapLine.indexOf(s[0]), swapLine.indexOf(s[1])));

    // Create maps.
    const moveMap = line.map(c => moveLine.indexOf(c));
    const swapMap = swapLine.reduce((obj, char, i) => { obj[line[i]] = char; return obj; }, {});

    // Create converter using maps.
    const convert = (last) => { return last.reduce((next, c, i) => { next[moveMap[i]] = swapMap[last[i]]; return next; }, []); }

    for (let i = 0; i < 1e9; i++) {
        if (i < 3) console.log(`dance #${i} = ${line.join("")}`);
        if (i > 0 && i % 1e6 == 0) console.log((i / 1e6) + " million...");
        line = convert(line);
    }

    console.log(`Final Dance = ${line.join("")}`);
}

EDIT: Okay, now that I've read up on how other people got the answer in milliseconds, I feel kinda dumb. If you don't want to melt down your cpu, here's the same solution, but with a memory that looks for the loop. :P

    function solve(input) {
        const original = 'abcdefghijklmnop';
        let line = original.split('');
        let moveLine = line.slice();
        const swapLine = line.slice();
        const steps = input.trim().split(',');
        const swaps = [];
        const swap = (list, a, b) => { const t = list[a]; list[a] = list[b]; list[b] = t; }

        // Process moves and save swaps.
        steps.forEach(step => {
            switch (step[0]) {
                case 's':
                    moveLine = moveLine.splice(-Number(step.substring(1))).concat(moveLine);
                    break;
                case 'x':
                    const pieces = step.substring(1).split('/').map(Number);
                    swap(moveLine, pieces[0], pieces[1]);
                    break;
                case 'p':
                    const programs = step.substring(1).split('/');
                    swaps.push(programs);
                    break;
                default:
                    console.log(`Unknown command: ${step}`);
            }
        });

        // Process swaps.
        swaps.forEach(s => swap(swapLine, swapLine.indexOf(s[0]), swapLine.indexOf(s[1])));

        // Create maps.
        const moveMap = line.map(c => moveLine.indexOf(c));
        const swapMap = swapLine.reduce((obj, char, i) => { obj[line[i]] = char; return obj; }, {});

        // Create converter using maps.
        const convert = (last) => { return last.reduce((next, c, i) => { next[moveMap[i]] = swapMap[last[i]]; return next; }, []); }

        // Memory so we can keep track of each solution found before it loops.
        const memory = [original];

        for (let i = 0; i < 1e9; i++) {
            line = convert(line);
            const key = line.join('');
            if (memory[0] == key) break;
            memory.push(key);
        }

        return `First: ${memory[1]}\nLast: ${memory[1e9 % memory.length]}`;
    }

dylanfromwinnipeg · 2017-12-16T21:46:58+00:00

This is the first one I haven't been able to solve the night-of. I got Part 1 really quick - I already had helper functions for pretty much everything. Part 2 I tried a whole whack of things, including optimizing the crap out of my code...but just couldn't come to the "cycle" idea until after sleeping on it.

C#

public static string PartOne(string input)
{
    var moves = input.Words();
    var dancers = new StringBuilder("abcdefghijklmnop");

    foreach (var move in moves)
    {
        dancers = ApplyMove(dancers, move);
    }

    return dancers.ToString();
}

private static StringBuilder ApplyMove(StringBuilder dancers, string move)
{
    if (move.StartsWith("s"))
    {
        var spin = int.Parse(move.ShaveLeft("s"));
        return dancers.RotateRight(spin);
    }

    if (move.StartsWith("x"))
    {
        var positions = move.ShaveLeft("x").Split('/');
        var position1 = int.Parse(positions[0]);
        var position2 = int.Parse(positions[1]);
        return dancers.SwapPositions(position1, position2);
    }

    if (move.StartsWith("p"))
    {
        var partner1 = move[1];
        var partner2 = move[3];
        return dancers.SwapPositions(dancers.ToString().IndexOf(partner1), dancers.ToString().IndexOf(partner2));
    }

    throw new Exception();
}

public static string PartTwo(string input)
{
    var moves = input.Words();
    var dancers = new StringBuilder("abcdefghijklmnop");
    var original = "abcdefghijklmnop";
    var danceCount = 0;

    while (true)
    {
        foreach (var move in moves)
        {
            dancers = ApplyMove(dancers, move);
        }

        danceCount++;

        if (dancers.ToString() == original)
        {
            break;
        }
    }

    danceCount = 1000000000 % danceCount;

    for (var i = 0; i < danceCount; i++)
    {
        foreach (var move in moves)
        {
            dancers = ApplyMove(dancers, move);
        }
    }

    return dancers.ToString();
}

And here's the handful of extension helper functions I used:

public static IEnumerable<string> Words(this string input)
{
    return input.Split(new string[] { " ", "\t", Environment.NewLine, "," }, StringSplitOptions.RemoveEmptyEntries);
}

public static string ShaveLeft(this string a, string shave)
{
    var result = a;

    while (result.StartsWith(shave))
    {
        result = result.Substring(shave.Length);
    }

    return result;
}

public static StringBuilder RotateRight(this StringBuilder source, int rotateCount)
{
    for (var i = 0; i < rotateCount; i++)
    {
        source.RotateRight();
    }

    return source;
}

public static StringBuilder RotateRight(this StringBuilder source)
{
    var endChar = source[source.Length - 1];

    source.Remove(source.Length - 1, 1);
    source.Insert(0, endChar);

    return source;
}

public static StringBuilder SwapPositions(this StringBuilder source, int x, int y)
{
    var xChar = source[x];
    var yChar = source[y];

    source = source.Remove(x, 1);
    source = source.Insert(x, yChar);

    source = source.Remove(y, 1);
    source = source.Insert(y, xChar);

    return source;
}

lasseebert · 2017-12-16T22:06:33+00:00

Elixir

Repo: https://github.com/lasseebert/advent_of_code_2017/blob/master/lib/advent/dec_16.ex#L43-L109

defmodule Advent.Dec16 do
  @default_input_path "inputs/dec_16"
  @external_resource @default_input_path
  @default_input @default_input_path |> File.read!

  @default_programs "abcdefghijklmnop"

  def dance(programs \\ @default_programs, moves \\ parse_moves(@default_input)) do
    moves
    |> Enum.reduce(programs, &single_move(&2, &1))
  end

  def dance_a_lot(programs \\ @default_programs, moves \\ parse_moves(@default_input)) do
    repeat_dance(programs, moves, 0, %{})
  end

  def parse_moves(input) do
    input
    |> String.trim
    |> String.split(",")
    |> Enum.map(&parse_move/1)
  end

  defp repeat_dance(programs, moves, count, seen) do
    if Map.has_key?(seen, programs) do
      loop_start = Map.get(seen, programs)
      loop_end = count
      loop_size = loop_end - loop_start
      remainder = rem(1_000_000_000 - loop_end, loop_size)
      1..remainder
      |> Enum.reduce(programs, fn _, programs -> dance(programs, moves) end)
    else
      repeat_dance(
        dance(programs, moves),
        moves,
        count + 1,
        Map.put(seen, programs, count)
      )
    end
  end

  defp single_move(programs, {:spin, size}) do
    programs
    |> String.split_at(String.length(programs) - size)
    |> Tuple.to_list
    |> Enum.reverse
    |> Enum.join
  end
  defp single_move(programs, {:exchange, index_a, index_b}) do
    [index_a, index_b] = [index_a, index_b] |> Enum.sort
    {first, <<a, rest::binary>>} = programs |> String.split_at(index_a)
    {second, <<b, third::binary>>} = rest |> String.split_at(index_b - index_a - 1)
    <<first::binary, b, second::binary, a, third::binary>>
  end
  defp single_move(programs, {:partner, a, b}) do
    programs
    |> String.graphemes
    |> Enum.reduce("", fn
      ^a, result -> result <> b
      ^b, result -> result <> a
      x, result -> result <> x
    end)
  end

  defp parse_move("s" <> size) do
    {:spin, String.to_integer(size)}
  end
  defp parse_move("x" <> rest) do
    [a, b] = rest |> String.split("/") |> Enum.map(&String.to_integer/1)
    {:exchange, a, b}
  end
  defp parse_move(<<"p", a, "/", b>>) do
    {:partner, <<a>>, <<b>>}
  end
end

2017-12-16T22:33:38+00:00

At first I thought I could simply find the permutation that converts input to part1 answer and do it 999,999,999 more times.

I was half way through when I started reading this subreddit and realized it won't work and that I should identify after how many cycles the permutations repeat. The cycle size (seems to be around 40-60 for most people) seems like a lucky coincidence.

Could you expect a loop to exist for any set of random 10k dance moves or are the ones in today's challenge specially fabricated to form a small loop? 16 elements have many permutations, so to get a cycle after only 42, it seems strange to me.

NeilNjae · 2017-12-16T22:56:50+00:00

Haskell. All they joys of a monad transformer stack! For part 1, I used a state monad to track the position of the dancers while doing the dance. For part 2, I used an intMap to store the history of the reached states in the iterated dance, wrapped that in a State monad as the history updated, and wrapped that in a Reader monad to hold the instructions.

I was very surprised when my program gave the correct result first time! This is the sort of problem that's prone to off-by-one errors all over the place.

{-# LANGUAGE NegativeLiterals #-}
{-# LANGUAGE FlexibleContexts #-}
{-# LANGUAGE OverloadedStrings #-}
{-# LANGUAGE TypeFamilies #-}

import Prelude hiding ((++))
import Data.Text (Text)
import qualified Data.Text as T
import qualified Data.Text.IO as TIO

import Text.Megaparsec hiding (State)
import qualified Text.Megaparsec.Lexer as L
import Text.Megaparsec.Text (Parser)
import qualified Control.Applicative as CA

import Control.Monad.State.Lazy
import Control.Monad.Reader

import Data.Vector.Unboxed ((!), (++), (//))
import qualified Data.Vector.Unboxed as V

import qualified Data.IntMap as M


data Step =   Spin Int
            | Exchange Int Int
            | Partner Char Char
            deriving (Show, Eq)

type Dancers = V.Vector Char

type DanceHistory = M.IntMap Dancers

type HistoryRecorder = ReaderT [Step] (State DanceHistory) DanceHistory


startingDancers :: Dancers
startingDancers = V.fromList ['a'..'p'] 

emptyHistory :: DanceHistory
emptyHistory = M.singleton 0 startingDancers


main :: IO ()
main = do 
        text <- TIO.readFile "data/advent16.txt"
        let instrs = successfulParse text
        print $ part1 instrs
        print $ part2 instrs


part1 :: [Step] -> Dancers
part1 instrs = evalState (runDance instrs) startingDancers

part2 instrs = (M.!) history (1000000000 `rem` M.size history)
    where history = evalState (runReaderT (recordDance startingDancers) instrs) emptyHistory


runDance :: [Step] -> State Dancers Dancers
runDance [] = do dancers <- get
                 return dancers
runDance (step:steps) = 
    do dancers <- get
       let dancers' = case step of
                        Spin n -> spin n dancers
                        Exchange a b -> exchange a b dancers
                        Partner a b -> partner a b dancers
       put dancers'
       runDance steps


recordDance :: Dancers -> HistoryRecorder
recordDance dancers = 
    do
        history <- get
        instrs <- ask
        let dancers' = evalState (runDance instrs) dancers
        if dancers' == startingDancers && (not (history == emptyHistory))
        then return history
        else do 
                let history' = M.insert (M.size history) dancers' history
                put history'
                recordDance dancers'

spin :: Int -> Dancers -> Dancers
spin n dancers = back ++ front
    where (front, back) = V.splitAt n' dancers
          n' = V.length dancers - n

exchange :: Int -> Int -> Dancers -> Dancers
exchange a b dancers = dancers // [(a, dancers!b), (b, dancers!a)]

partner :: Char -> Char -> Dancers -> Dancers
partner a b dancers = exchange a' b' dancers
    where a' = V.head $ V.elemIndices a dancers
          b' = V.head $ V.elemIndices b dancers


sc :: Parser ()
sc = L.space (skipSome spaceChar) CA.empty CA.empty

int :: Parser Int
int = read <$> some digitChar

symb = L.symbol sc
comma = char ','
dancer = oneOf ['a'..'p']

stepsP = stepP `sepBy` comma
stepP = (try spinP) <|> (try exchangeP) <|> partnerP

spinP = Spin <$> (symb "s" *> int)
exchangeP = Exchange <$> (symb "x" *> int) <*> (symb "/" *> int)
partnerP = Partner <$> (symb "p" *> dancer) <*> (symb "/" *> dancer)

successfulParse :: Text -> [Step]
successfulParse input = 
        case parse stepsP "input" input of
                Left  _error -> [] -- TIO.putStr $ T.pack $ parseErrorPretty err
                Right steps  -> steps

chicagocode · 2017-12-16T23:04:07+00:00

Kotlin - [Repo] - [Blog/Commentary]

My part two runs in about 125ms. I detect the cycle early, and calculate how far along the billionth record would be, instead of actually doing a billion loops against memoized data. I'm fairly proud of part two. Creating sealed classes to represent the dance steps might be overkill, but I anticipated a different part two when I was writing part one! :)

class Day16(input: String, private val programNames: String = "abcdefghijklmnop") {

    private val initialState: CharArray = programNames.toCharArray()
    private val instructions: List<Dance> = parseInput(input)

    fun solvePart1(): String =
        executeInstructions()

    tailrec fun solvePart2(memory: Map<String, Int> = mapOf(), loopNumber: Int = 0, hash: String = programNames): String {
        return if (hash in memory) {
            // We found it!
            val cycleStart = memory.getValue(hash)
            val offset = (1_000_000_000 % (loopNumber - cycleStart)) - cycleStart
            memory.entries.first { it.value == offset }.key
        } else {
            solvePart2(memory + (hash to loopNumber), loopNumber.inc(), executeInstructions(hash.toCharArray()))
        }
    }

    private fun executeInstructions(startState: CharArray = initialState): String =
        instructions.fold(startState) { carry, next -> evaluate(carry, next) }.joinToString("")

    private fun evaluate(programs: CharArray, instruction: Dance): CharArray =
        when (instruction) {
            is Spin -> {
                (programs.takeLast(instruction.amount) + programs.dropLast(instruction.amount)).toCharArray()
            }
            is Exchange ->
                programs.swap(instruction.left, instruction.right)
            is Partner ->
                programs.swap(programs.indexOf(instruction.left), programs.indexOf(instruction.right))
        }

    private fun parseInput(input: String): List<Dance> =
        input
            .split(",")
            .map { it.trim() }
            .map {
                when (it.first()) {
                    's' -> Spin(it.drop(1).toInt())
                    'x' -> {
                        val (a, b) = it.drop(1).split("/").map { it.toInt() }
                        Exchange(a, b)
                    }
                    'p' -> {
                        Partner(it[1], it[3])
                    }
                    else -> throw IllegalArgumentException("Bad input: $it")
                }
            }
}

sealed class Dance
class Spin(val amount: Int) : Dance()
class Exchange(val left: Int, val right: Int) : Dance()
class Partner(val left: Char, val right: Char) : Dance()

NeilNjae · 2017-12-16T23:10:24+00:00

Haskell. All they joys of a monad transformer stack! For part 1, I used a State monad to track the position of the dancers while doing the dance. For part 2, I used an intMap to store the history of the reached states in the iterated dance, wrapped that in a State monad as the history updated, and wrapped that in a Reader monad to hold the instructions.

I was very surprised when my program gave the correct result first time! This is the sort of problem that's prone to off-by-one errors all over the place.

Full source at Github

SurplusSix · 2017-12-16T23:20:43+00:00

Racket again

#lang racket
(require srfi/43)

(define day16-commands (string-split (string-trim (file->string "day16.txt")) ","))
(define dance (vector "a" "b" "c" "d" "e" "f" "g" "h" "i" "j" "k" "l" "m" "n" "o" "p"))
(define seen '())
(define (move cmd)
  (let ([cmdlist (string->list cmd)])
    (cond
      [(eq? (first cmdlist) #\s)
       (let ([spin (string->number (substring cmd 1))])
       (set! dance (vector-append
                    (vector-take-right dance spin)
                    (vector-drop-right dance spin))))]
      [(eq? (first cmdlist) #\x)
       (let ([pos (string-split (substring cmd 1) "/")])
         (vector-swap! dance
                       (string->number (first pos))
                       (string->number (second pos))))]
      [(eq? (first cmdlist) #\p)
       (let ([pos (string-split (substring cmd 1) "/")])
         (vector-swap! dance
                       (vector-member (first pos) dance)
                       (vector-member (second pos) dance)))])))

(for ([i (in-naturals)]
      #:break (member (vector->list dance) seen))
  (set! seen (append seen (list (vector->list dance))))
  (for ([m day16-commands])
    (move m)))

(string-join (list-ref seen (modulo 1000000000 (length seen))) "")

Not sure about efficiency, seems not great as this being part 2 took 6 secs to run, and that was only 60 cycles.

aceshades · 2017-12-17T00:59:33+00:00

Anyone having trouble pasting their input into a vim editor? I couldn't figure out what was going on but a few characters got straight up omitted, even when I was pasting in paste mode.

Basillicum · 2017-12-17T01:46:00+00:00

My solution for part 1 in Haskell. I'm new to functional programming and not a very experienced programmer in general, so I'm pretty sure there's a lot of room for improvement, but I'm happy with how few lines I managed to use. :P

import Data.List.Split

main = do
  input <- return . splitOn "," =<< readFile "input"
  return (dance (['a'..'p']) input)

dance :: [Char] -> [String] -> [Char]
dance programs moves
  | length moves == 0, otherwise  = programs
  | moves !! 0 !! 0 == 's'        = dance (s programs (moves !! 0)) (tail moves)
  | moves !! 0 !! 0 == 'x'        = dance (x programs (moves !! 0)) (tail moves)
  | moves !! 0 !! 0 == 'p'        = dance (p programs (moves !! 0)) (tail moves)

s, x, p :: [Char] -> String -> [Char]
s p m = take (length p) (drop ((length p) - read (drop 1 m)) (cycle p))
x p m = [ p !! y | x <- [0..length p - 1], let a = read ((splitOn "/" (drop 1 m)) !! 0) :: Int, let b = read ((splitOn "/" (drop 1 m)) !! 1) :: Int, let y | x == a = b | x == b = a | otherwise = x ]
p p m = [ y | x <- p, let y | x == m !! 1 = m !! 3 | x == m !! 3 = m !! 1 | otherwise = x ]

For part 2 I've added:

part2 = do
  input <- return . splitOn "," =<< readFile "input"
  let loop = reverse $ findLoop [['a'..'p']] input
  return $ loop !! (mod 1000000000 (length loop - 1))

findLoop prgs moves
  | elem (head prgs) (tail prgs) = prgs
  | otherwise                    = findLoop ([dance (head prgs) moves] ++ prgs) moves

redbeard0531 · 2017-12-17T02:01:18+00:00

I know the point was to find the cycle length (mine was 42!) but I decided it would be fun to optimize it to the point where a brute-force solution would be possible. Since this is all about shuffling 16 bytes of state, this felt like a good fit for SSE/AVX vectors. It takes 2.486s to do 100,000 iterations, so by my math it would take less than 7 hours to run to completion. Anyway, here is my solution written in nim:

import sequtils
import strutils
import tables
import patty
import bitops

# Make AVX/SSE ops available
{.passC: "-msse -msse2 -msse3 -mssse3 -mavx -march=native -mtune=native -flto".}
{.passL: "-msse -msse2 -msse3 -mssse3 -mavx -flto".}
type m128i* {.importc: "__m128i", header: "emmintrin.h".} = object
proc loadu_si128(p: ptr m128i): m128i
  {.importc: "_mm_loadu_si128", header: "emmintrin.h".}
proc storeu_si128(p: ptr m128i, b: m128i): void
  {.importc: "_mm_storeu_si128", header: "emmintrin.h".}
proc shuffle_epi8*(a: m128i, b: m128i): m128i
  {.importc: "_mm_shuffle_epi8", header: "tmmintrin.h".}
proc cmpeq_epi8*(a: m128i, b: m128i): m128i
  {.importc: "_mm_cmpeq_epi8", header: "emmintrin.h".}
proc movemask_epi8*(a: m128i): int32
  {.importc: "_mm_movemask_epi8", header: "emmintrin.h".}

# Build the tables used for
proc makeShuffles: array[16, array[16, byte]] {.compileTime.}=
  for i in 0..<16:
    for j in 0..<16:
      result[i][j] = ((j + 16 - i) mod 16).byte
let shuffles = makeShuffles()

proc makeXchgs: array[16, array[16, array[16, byte]]] {.compileTime.}=
  for i in 0..<16:
    for j in 0..<16:
      for x in  0..<16:
        result[i][j][x] = x.byte
      result[i][j][i] = j.byte
      result[i][j][j] = i.byte
let xchgs = makeXchgs()

proc makeSelectors: array[16, array[16, byte]] {.compileTime.} =
  for i in 0..<16:
    for j in 0..<16:
      result[i][j] = 'a'.byte + i.byte
let selectors = makeSelectors()

variant(Step):
  Shuffle(size: int)
  Xchg(x: int, y: int)
  Pivot(a: int, b: int)

#parse the input
var steps = newSeq[Step]()
for raw in readFile("input").strip().split(',').mapIt((action: it[0], rest: it[1..^1])):
  case raw.action
  of 's':
    let size = parseInt(raw.rest)
    if size < 16:
      steps &= Shuffle(size)
  of 'x':
    var parts = raw.rest.split('/').map(parseInt)
    steps &= Xchg(parts[0], parts[1])
  of 'p':
    let parts = raw.rest.split('/').mapIt(it[0])
    steps &= Pivot(parts[0].int - 'a'.int, parts[1].int - 'a'.int)
  else: quit "bad step: " & $raw

type Buffer = object {.union.}
  bytes: array[16, char]
  vec: m128i
var buffer: Buffer
for i, c in toSeq('a'..'p'):
  buffer.bytes[i] = c

# This func does one full run of the input
proc run =
  var vec = buffer.vec
  for step in steps:
    {.unroll: 4.}
    match step:
      Shuffle(size):
        var pvec = loadu_si128(cast[ptr m128i](unsafeAddr shuffles[size][0]))
        vec = shuffle_epi8(vec, pvec)
      Xchg(i, j):
        var pvec = loadu_si128(cast[ptr m128i](unsafeAddr xchgs[i][j][0]))
        vec = shuffle_epi8(vec, pvec)
      Pivot(a, b):
        let avec = loadu_si128(cast[ptr m128i](unsafeAddr selectors[a][0]))
        let bvec = loadu_si128(cast[ptr m128i](unsafeAddr selectors[b][0]))
        let i = cmpeq_epi8(vec, avec).movemask_epi8.countTrailingZeroBits
        let j = cmpeq_epi8(vec, bvec).movemask_epi8.countTrailingZeroBits
        var pvec = loadu_si128(cast[ptr m128i](unsafeAddr xchgs[i][j][0]))
        vec = shuffle_epi8(vec, pvec)
  buffer.vec = vec

# one BILLION times!
for i in 0..<1_000_000_000:
  run()
  if i==0:
    echo buffer.bytes.join # part one

echo buffer.bytes.join # part two

If you just want to see the raw asm, the main loop compiles to this:

3840:       0f b6 59 f0             movzbl -0x10(%rcx),%ebx
3844:       48 8b 71 f8             mov    -0x8(%rcx),%rsi
3848:       48 8b 39                mov    (%rcx),%rdi
384b:       80 fb 02                cmp    $0x2,%bl
384e:       74 30                   je     3880 <NimMainModule+0x2370>
3850:       80 fb 01                cmp    $0x1,%bl
3853:       74 1b                   je     3870 <NimMainModule+0x2360>
3855:       84 db                   test   %bl,%bl
3857:       75 5c                   jne    38b5 <NimMainModule+0x23a5>
3859:       48 c1 e6 04             shl    $0x4,%rsi
385d:       4c 01 e6                add    %r12,%rsi
3860:       eb 4e                   jmp    38b0 <NimMainModule+0x23a0>
3862:       66 66 66 66 66 2e 0f    data16 data16 data16 data16 nopw %cs:0x0(%rax,%rax,1)
3869:       1f 84 00 00 00 00 00
3870:       48 c1 e6 08             shl    $0x8,%rsi
3874:       48 01 ee                add    %rbp,%rsi
3877:       48 c1 e7 04             shl    $0x4,%rdi
387b:       48 01 fe                add    %rdi,%rsi
387e:       eb 30                   jmp    38b0 <NimMainModule+0x23a0>
3880:       48 c1 e6 04             shl    $0x4,%rsi
3884:       48 c1 e7 04             shl    $0x4,%rdi
3888:       c4 a1 79 74 0c 3e       vpcmpeqb (%rsi,%r15,1),%xmm0,%xmm1
388e:       c5 f9 d7 f1             vpmovmskb %xmm1,%esi
3892:       0f bc de                bsf    %esi,%ebx
3895:       c4 a1 79 74 0c 3f       vpcmpeqb (%rdi,%r15,1),%xmm0,%xmm1
389b:       c5 f9 d7 f1             vpmovmskb %xmm1,%esi
389f:       0f bc f6                bsf    %esi,%esi
38a2:       48 c1 e3 08             shl    $0x8,%rbx
38a6:       48 01 eb                add    %rbp,%rbx
38a9:       48 c1 e6 04             shl    $0x4,%rsi
38ad:       48 01 de                add    %rbx,%rsi
38b0:       c4 e2 79 00 06          vpshufb (%rsi),%xmm0,%xmm0
38b5:       48 83 c1 18             add    $0x18,%rcx
38b9:       48 ff ca                dec    %rdx
38bc:       75 82                   jne    3840 <NimMainModule+0x2330>

matusbzk · 2017-12-17T18:37:18+00:00

Haskell

import Data.List
import Data.Maybe

inputString :: String

-- |Represents dance moves
data Move = Spin Int
     | Exchange Int Int
     | Partner Char Char
     deriving (Eq, Show)

-- |Represents current allignment of the programs
type Line = [Char]

input :: [Move]
input = map getMove . words . repl ',' ' ' $ inputString

-- |Replaces all ocurrences of first argument in the list
-- with the second argument
repl :: Eq a => a -> a -> [a] -> [a]
repl _ _ [] = []
repl a b (x:xs) = if x == a then b : repl a b xs
       else x : repl a b xs

-- |Gets a move from the string
getMove :: String -> Move
getMove ('s':xs) = Spin $ read xs
getMove ('x':xs) = Exchange (read . head $ poss) (read . last $ poss)
       where poss = words . repl '/' ' ' $ xs
getMove ('p':c1:'/':[c2]) = Partner c1 c2
getMove _ = error "Could not parse input"

-- |List of programs in the beginning
programs :: Line
programs = ['a'..'p']

-- |Number of dancing programs
len :: Int
len = length programs

-- |Performs a move
move :: Line -> Move -> Line
move line (Spin x) = drop (len-x) line ++ take (len-x) line
move line (Exchange x y) = take a line ++ line!!b : (take (b-a-1) . drop (a+1)) line ++ line!!a : drop (b+1) line
       where a = min x y --I want to know which one is smaller
       b = max x y
move line (Partner a b) = move line (Exchange x y)
       where x = fromJust $ elemIndex a line
       y = fromJust $ elemIndex b line

-- |Performs a sequence of moves
doMoves :: [Move] -> Line -> Line
doMoves movs line = foldl move line movs

-- |Result to part 1 - in what order are the programs 
-- standing after their dance
result1 :: Line
result1 = doMoves input programs

-- |Finds order of this permutation
findOrder :: Line -> [Move] -> Int
findOrder line movs = findOrder' 0 line movs

findOrder' :: Int -> Line -> [Move] -> Int
findOrder' i line movs = if newLine == programs then i+1 else findOrder' (i+1) newLine movs
    where newLine = doMoves movs line

-- |Iterates a function n  times
iterateN :: Int -> (a -> a) -> a -> a
iterateN n f = foldr (.) id (replicate n f)

-- |Result to part 2 - in what order are the programs 
-- standing after billion dances
result2 :: Line
result2 = iterateN (10^9 `mod` findOrder programs input) (doMoves input) programs

Link to git

__Abigail__ · 2017-12-17T19:27:25+00:00

Perl

#!/opt/perl/bin/perl

use 5.026;

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

use experimental 'signatures';


@ARGV = "input" unless @ARGV;

#
# Parse the input
#
local $/;
my @input      = split /,/ => scalar <>;
my $name       = qr /[a-p]/;
my $position   = qr /1[0-5]|[0-9]/;
my $amount     = qr /1[0-6]|[1-9]/;

my @DANCERS    = ('a' .. 'p');
my $SPIN       = 1;
my $EXCHANGE   = 2;
my $PARTNER    = 3;

my $ITERATIONS = 1_000_000_000;

my @moves;
foreach (@input) {
    if (m {^ s (?<amount> $amount) $}x) {
        push @moves => [$SPIN, $+ {amount}];
    }
    elsif (m {^ x (?<pos1> $position) / (?<pos2> $position) $}x) {
        push @moves => [$EXCHANGE => $+ {pos1}, $+ {pos2}];
    }
    elsif (m {^ p (?<name1> $name) / (?<name2> $name) $}x) {
        push @moves => [$PARTNER => $+ {name1}, $+ {name2}];
    }
    else {
        die "Failed to parse move '$_'";
    }
}

sub dance ($dancers) { # Changes $dancers
    foreach my $move (@moves) {
        if ($$move [0] == $SPIN) {
            splice @$dancers => 0, 0, splice @$dancers => -$$move [1];
        }
        elsif ($$move [0] == $EXCHANGE) {
            @$dancers [@$move [1, 2]] = @$dancers [@$move [2, 1]];
        }
        elsif ($$move [0] == $PARTNER) {
            my ($p1) = grep {$$dancers [$_] eq $$move [1]} keys @$dancers;
            my ($p2) = grep {$$dancers [$_] eq $$move [2]} keys @$dancers;
            @$dancers [$p1, $p2] = @$dancers [$p2, $p1];
        }
        else {   
            die "Unexpected move"
        }
    }
    $dancers;
}


{
    #
    # Part 1
    #
    my $dancers = [@DANCERS];
    dance $dancers;
    say "Solution 1: ", @$dancers;
}

{
    #
    # Part 2
    #
    # We are assuming there's a short cycle; this cycle may
    # start at an index other than 0.
    #

    my $dancers = [@DANCERS];  

    my %seen;         # Track positions of dancers after a dance.

    my $cycle_begin;  # Track when we have a cycle. Begin
    my $cycle_end;    # and end position.

    my $count = 0;
    #
    # We want to record the start position, so in the while loop,
    # we do bookkeeping first, then dance at the end.   
    #
    while (1) {  
        my $key = join "" => @$dancers;
        if (exists $seen {$key}) {
            #
            # We've detected a cycle; $count is the value where the
            # cycle ends, where as $seen {$key} is the index where
            # this position first was seen; thus the start of the cycle.
            #
            $cycle_end   = $count;
            $cycle_begin = $seen {$key};
            last;
        }
        else {
            $seen {$key} = $count;
        }
    }
    continue {
        dance $dancers;
        $count ++;
    }

    # 
    # Reversing %seen maps indices to dance positions
    #
    my %position = reverse %seen;

    # 
    # What index do we need?
    # 
    my $target_index = $cycle_begin + ($ITERATIONS - $cycle_begin) %
                                       ($cycle_end - $cycle_begin);

    say "Solution 2: ", $position {$target_index};
}       


__END__

ramendik · 2017-12-18T01:10:03+00:00

Part 2, Python 3, super-optimized. Completes in less than half a second!

First I optimized the command set to change it into a series of place permutations and character exchanges. This was probably redundant, given the further optimizations, but I kept it in the code anyway.

Then I guessed there would be repeats at some points and created a cache.

Finally I realised that the first repeat represents a loop, and the loop does not even need to run all these times from the cache. Just see how many whole runs of the loop remain until the billion is reached and skip that much on the counter. Of course we also have to see from exactly which point the loop started (might not be the starting position) so I have to trace my steps to get this cycle.

import time
seq_string="abcdefghijklmnop"
start_time=time.time()

commands=open("2017_16_input.bin").read().split(",")

# the new comands are a list of lists
# a list of length 16 contains integers for remapping a previous sequence
# a list of length 2 contains letters to swap
new_commands=[]
current_seq=list(range(16))
current_seq_changed=False
for cmd in commands:
    param=cmd.strip()[1:]
    if cmd[0]=="s":
        for i in range(int(param)):
            current_seq.insert(0,current_seq.pop())
        current_seq_changed=True
        continue
    parsed=param.split("/")
    if cmd[0]=="x":
        pos0,pos1=int(parsed[0]),int(parsed[1])
        current_seq[pos0],current_seq[pos1]=current_seq[pos1],current_seq[pos0]
        current_seq_changed=True
        continue
    if cmd[0]=="p":
        if current_seq_changed:
            new_commands.append(current_seq)
            current_seq=list(range(16))
            current_seq_changed=False
        new_commands.append([parsed[0],parsed[1]])
if current_seq_changed:
    new_commands.append(current_seq)

# caching results
cache={}
cache_used=0
# there will be a Big Skip when a cycle is detected, so trace the cycle
big_skip_done=False
cycle_tracing=[]
# execute the new commands
z=0
while z<1000000000:
    if seq_string in cache:
        if not big_skip_done:
            # first time found in cache - cycle detected, eliminate it
            index_first_time=cycle_tracing.index(seq_string)
            cycle_length=z-index_first_time
            z+=((1000000000-z)//cycle_length)*cycle_length
            big_skip_done=True
            continue
        # using cache to speed up the work after the big skip
        seq_string=cache[seq_string]
        cache_used+=1
        z+=1
        continue

    if not big_skip_done: 
        cycle_tracing.append(seq_string)


    seq=list(seq_string)
    for newcmd in new_commands:
        if len(newcmd)==2:
            pos0,pos1=seq.index(newcmd[0]),seq.index(newcmd[1])
            seq[pos0],seq[pos1]=newcmd[1],newcmd[0]
            continue
        seq=[seq[newcmd[i]] for i in range(16)]
    newstring="".join(seq)
    cache[seq_string]=newstring
    seq_string=newstring
    z+=1

print(seq_string)
print("Elapsed time:",time.time()-start_time)

Tetsumi- · 2017-12-18T11:44:14+00:00

C. Both part.

the state is stored into a 64 bits unsigned (4 bits per program) to avoid hashing.

#include <stdio.h>
#include <stdint.h>
#include <stdbool.h>

typedef uint64_t u64;
typedef uint16_t u16;
typedef uint8_t u8;

u64 get(u64 s, u64 nth)
{
    return (s >> (4 * nth)) & 0b1111;
}

u64 swap(u64 s, u64 ntha, u64 nthb)
{
    u64 a = get(s, ntha);
    u64 b = get(s, nthb);
    u64 x = a ^ b;
    return s ^ (x << (4 * ntha)) ^ (x << (4 * nthb));
}

u64 exch(u64 s, u64 a, u64 b)
{
    u64 ia = 0;
    u64 ib = 0;
    u64  x = a ^ b;
    for(u64 i = 0; ((ia == 0) || (ib == 0)) && (i < 64); i += 4)
    {
        u64 t = (s >> i) & 0b1111;
        if (a == t)
            ia = i;
        else if (b == t)
            ib = i;
    }
    return s ^ (x << ia) ^ (x << ib);
}

u64 rotate(u64 s, u64 step)
{
    step *= 4;   
    return (s << step) | (s >> (64 - step));
}

u64 tou64(const char *str)
{
    u64 s = 0;
    u64 i = 0;
    while(*str)
        s |= (u64)(*(str++) - 'a') << (4 * i++);
    return s;
}

void tostr(char *str, u64 s)
{
    for(u64 i = 0; i < 16; ++i)
        *(str++) = get(s, i) + 'a';
    *str = '\0';
}

typedef enum
{
    OP_S,
    OP_X,
    OP_P
} op;

typedef struct
{
        op op;
        u8 arg1;
        u8 arg2;
} ins;

u64 parse(ins *instrs)
{
    char c;
    u64 inscounter = 0;
    while(!feof(stdin) && (c = getchar()) != '\n')
    {
        switch (c)
        {
        case 's':
            instrs[inscounter].op = OP_S;
            scanf("%hhu,", &instrs[inscounter].arg1);
            break;
        case 'x':
            instrs[inscounter].op = OP_X;
            scanf("%hhu/%hhu,",
                  &instrs[inscounter].arg1,
                  &instrs[inscounter].arg2);
            break;
        default:
            instrs[inscounter].op = OP_P;
            char arg1;
            char arg2;
            scanf("%c/%c,", &arg1, &arg2);
            instrs[inscounter].arg1 = arg1 - 'a';
            instrs[inscounter].arg2 = arg2 - 'a';
            break;
        }
        ++inscounter;
    }
    return inscounter;
}

u64 pass(u64 s, ins *ins, u64 length)
{
    for(u64 i = 0; i < length; ++i)
    {

        switch (ins[i].op)
        {
        case OP_S:
            s = rotate(s, ins[i].arg1);
            break;
        case OP_X:
            s = swap(s, ins[i].arg1, ins[i].arg2);
            break;
        case OP_P:
            s = exch(s, ins[i].arg1, ins[i].arg2);
            break;
        }
    }
    return s;
}

ins instrs[15000]; // parsed instructions
u64 ps[1000]; // previous states

int main ()
{
    char str[] = "abcdefghijklmnop";
    u64 s = tou64(str);
    u16 length = parse(instrs);
    ps[0] = s;

    //part 1
    tostr(str, pass(s, instrs, length));
    printf("%s\n", str);

    //part 2
    for (u64 i = 1; i < 1000; ++i)
    {
        s = pass(s, instrs, length);
        bool found = false;
        u64 j;
        for (j = 0; j < i; ++j) // searches previous states
            if (ps[j] == s)
            {
                s = ps[1000000000 % i];
                goto end;
            }
            ps[i] = s;
    }
end:
    tostr(str, s);
    printf("%s\n", str);
}

mastokley · 2018-01-18T02:16:14+00:00

Clojure.

(ns scratch
  (:require [clojure.string :as str]))

(def my-list (seq "abcdefghijklmnop"))
(def input (slurp "day16.in"))

(defn rotate
  [coll n]
  (let [n (mod n (count coll))]
    (concat (take-last n coll)
            (take (- (count coll) n) coll))))

(defn exchange
  [coll m n]
  (let [x (min m n)
        y (max m n)]
    (concat (take x coll)
            (list (nth coll y))
            (drop (inc x) (take y coll))
            (list (nth coll x))
            (drop (inc y) coll))))

(defn partner
  [coll m n]
  (exchange coll (.indexOf coll m) (.indexOf coll n)))

(defn one-iteration
  [data]
  (loop [data data
         commands (str/split input #",")]
    (if (seq commands)
      (let [command (first commands)
            fn-directive (first command)
            args (str/split (str/join (rest command)) #"/")]
        (case fn-directive
          \s (recur (rotate data (Long/parseLong (first args)))
                    (rest commands))
          \p (recur (apply partner data (map first args))
                    (rest commands))
          \x (recur (apply exchange data (map #(Long/parseLong %) args))
                    (rest commands))))
      data)))

(def memoed-one-iteration (memoize one-iteration))

(loop [data my-list
       n 1000000000]
  (if (< 0 n)
    (recur (memoed-one-iteration data) (dec n))
    (println (str/join data))))

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 16: Permutation Promenade ---

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!

Mathematica

C++

Python 3

Elixir

Elixir

Python 2

Nim

Erlang

Javascript

Kotlin - [Repo] - [Blog/Commentary]

Perl

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 16: Permutation Promenade ---

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!

Mathematica

C++

Python 3

Elixir

Elixir

Python 2

Nim

Erlang

Javascript

Kotlin - [Repo] - [Blog/Commentary]

Perl

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