Clojurians Log v2

Hmz. My program for part 1 works for the examples but somehow not for my real input. I get an answer, but it’s wrong.

what is the answer?

do you somehow have a regex only parsing single digits?

[0 1 2 3 4 5 6 7 8 9101112131415]
[a b c d e f g h i j k l m n o p]
[a b c k e f g h i j d l m n o p] :EXCHANGE (3 10) CORRECT
[a b c k e f l h i j d g m n o p] :PARTNER (l g)   CORRECT
[h i j d g m n o p a b c k e f l] :SPIN (9)        CORRECT
[h i j d g m l o p a b c k e f n] :EXCHANGE (6 15) CORRECT
[l o p a b c k e f n h i j d g m] :SPIN (10)       CORRECT  

My answer is "bfcjlogemipdnakh"

My input: https://github.com/borkdude/aoc2017/blob/master/resources/day16.txt

My parser seems to be correct: when I coerce the parsed tree back to a string and compare to the input, it’s equal

@borkdude with your input, I get a different answer

thanks

oh dear, first part takes 80ms, which is nowhere fast enough for part 2 😄

it's time to optimize

Yarg. Yes 🙂

34msecs here…

if you narrow it down to 1ms, it’s still 45 days 🙂

Sorry, 11 days.

So we have to be a bit more clever…

i have some ideas...

but need to go out now, will try later

i wish i understood macros better 😄

https://repl.it/repls/UnhealthyBeautifulPrairiedog

Unfortunately, this finds the wrong answer and I’m too lazy to figure out why

For part 1 or 2?

1

My solutions to day 16, including an exploration / explanation of the algebraic properties that make part 2 viable https://github.com/vvvvalvalval/advent-of-code-2017/tree/master/src

@borkdude same here hehe

I found the bug btw

I’m still looking for mine, I tested the S, X, P fns and my “parser” seems correct

@nooga Looking at your code, I find something peculiar; do you want to know or want to battle it?

but the answer is wrong :f

don’t tell me, I’m going to figure it out

I don’t have time to battle part 2 at the moment…

and it’s probably something stupid

From past experience, this is probably going to be one of those puzzles where a lot of people will drop off; I find no shame in stealing the answer from someone and moving on though 🙂

I still haven’t done day 14, my knot-hash fn is slow and somehow I get wrong answers, too complex to debug for now

ah, my S function is totally wrong 😄

@val_waeselynck removed spoiler

@erwin sure, so did I, I just thought some people might also be interested in the math aspects that make this 'reasonable repetition' possible 🙂

oh, and we might have spoiled the others a bit :s

> since the maximum idempotence exponent for a 16-elements permutation is 5 4 140 I do not understand this part, how do you calculate this?

original message: your explanation for part-2 is difficult to understand ... 😅 I did "dumb" reasoning: the naive implementation is way to slow (8 hours of calculation), lets assume there is reasonable repetition (even though a 16 items permutation is larger then 1.000.000.000), because otherwise this puzzle is no fun 😉

Got it: https://github.com/orestis/adventofcode/blob/master/clojure/aoc/src/aoc/2017_day16.clj

I did a far more naive thing, tried to see if there were repetitions in the states which is somewhat expectable as I calculated at least 10 days of calculations…

And indeed I arrived at the 24 + 16…

@val_waeselynck Can you point me to the math concepts/names that you explain in part 2?

I had some initial idea that some instructions might cancel each other out (e.g. the pairings) but I lacked the formal math to prove it.

i.e. my first hunch was to do what you did for “fun” but had no idea how to reason about it. Would love to learn more 🙂

my idea is to find a cycle and basically start from the last one

Some keywords: Permutations (one-to-one functions of a finite set onto itself), the fact that transpositions and rotations of elements are permutations, the fact that a permutation composed to another permutation is still a permutation, and finally the fact that every permutation can be decomposed into rotations of disjoint support, which is what helps you compute that idempotence exponent (the lowest common multiple of the cycles' lengths).

Not useful to solve the problem per se, but useful to be confident in the fact that the period will be small

@orestis @erwin ^

thanks

Thanks, I will have to dig deeper some time. And I'll also have to see how you did the AOT analysis of the input, as that is a generally useful technique.

@orestis what I called AOT here was just compacting the steps into 2 permutations, not sure it will be much reusable as it leveraged the same algebraic properties I mentionned above 🙂

ha, done

https://repl.it/repls/UnhealthyBeautifulPrairiedog

it crashes this funny repl but works on my machine

I tried to compile the input into something like (fn [initial-state] (-> initial-state (S 1) (X 1 3) ...)) and then evaling it for fun but it just caused a stack overflow in clojure compiler

😂

I could probably get away with series of swap!s on an atom though

Day 16: https://github.com/mfikes/advent-of-code/blob/master/src/advent_2017/day_16.cljc

https://github.com/bhauman/advent-of-clojure-2016/blob/master/src/advent_of_clojure_2017/day16.clj

@nooga your are probably having a cons explosion?

@bhauman where?

does your stack overflow say "lazySeq.Cons" or someting like that?

what happens is that you can build up too much lazy state

and when it finally comes due it explodes

no idea, I scrapped this “compiler” function

but I’d suppose that was rather caused by putting too many expressions in ->

no its normally from nested lazy seqs that grow to large by the time you start to consume them

so basically the code I'm looking at is different from the code you were using earlier

anyway asking for a billion was a dead give away, it would have been brutal if they asked for something just outside of plausible

okay. I thought I'd just let that run overnight. Still hasn't finished.

Great puzzle today. I have yet to clean up my code.

Yeah, while part 1 can be tedious, it is straightforward. Part 2 had nice characteristics.

https://github.com/borkdude/aoc2017/blob/master/src/day16.clj

My InstaParser is a bit slow (~850ms). Wonder how long your folks’ parsing takes?

Could probably optimize it by handwriting it.

@bhauman the code I was talking about looked more or less like this https://repl.it/repls/KookyBestTurkey

Hand-written parser: ~8ms https://github.com/borkdude/aoc2017/blob/master/src/day16.clj#L119

Interesting. I've got a solution which works for part-1, gives me the correct period for part-2, but not the correct answer for part-2. It's two transpositions off. And it doesn't look like an off-by-one error, as neither solution on either side is correct either.

@grzm I was in the same situation and then I noticed 10e9 instead of 1e9

so it was off by 0 this time 😉

@nooga thanks for an idea to confirm. but that's one off-by-zero that I don't have 😞

I do wish Clojure accepted number syntax like 1_000_000_000 for cases like this.

it does accept scientific notation like, well, 1e9 for cases like this

true. doesn't help with 1234765890, though

I always make the mistake of thinking this syntax exists b/c we have such an awesome reader, but alas I'm always wrong

How can it be wrong when it feels so right?

Added a Kern parser implementation for day 16: https://github.com/borkdude/aoc2017/blob/master/src/day16.clj#L115

Nothing like a 26-hours plane trip to catch up on AoC 🙂 I know I'm late to the party, but I wonder what you guys thought of day 11 (Haxagonal Grid)? Did you find it difficult? It took me a lot of head scratching to achieve a clean solution, and even then if feels like it could be simpler (here if you're curious: https://github.com/vvvvalvalval/advent-of-code-2017/blob/master/src/aoc2017/day11.clj)