Fork me on GitHub
#adventofcode
<
2017-12-16
>
borkdude09:12:24

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.

theeternalpulse09:12:37

what is the answer?

erwin09:12:30

do you somehow have a regex only parsing single digits?

borkdude09:12:56

[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  

borkdude09:12:28

My answer is "bfcjlogemipdnakh"

borkdude09:12:36

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

erwin10:12:23

@borkdude with your input, I get a different answer

ihabunek10:12:11

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

orestis10:12:59

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

orestis10:12:05

Sorry, 11 days.

orestis10:12:16

So we have to be a bit more clever…

ihabunek10:12:31

i have some ideas...

ihabunek10:12:43

but need to go out now, will try later

ihabunek10:12:27

i wish i understood macros better 😄

ihabunek10:12:54

it's time to optimize

orestis10:12:24

Yarg. Yes 🙂

orestis10:12:50

34msecs here…

nooga10:12:05

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

orestis10:12:13

For part 1 or 2?

val_waeselynck10:12:27

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

fellshard01:12:36

Do you have any links to where I can read up on this? I understand how the cyclic nature would lead you to the right answer, but I'm not sure I see how we can assume the dance itself is idempotent.

fellshard02:12:20

Ohh, wait. Because the possible permutations operations are limited, there are far fewer than 1e13 operations that can be performed?

nooga10:12:25

@borkdude same here hehe

borkdude10:12:38

I found the bug btw

nooga10:12:28

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

orestis10:12:37

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

nooga10:12:38

but the answer is wrong :f

nooga10:12:01

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

orestis10:12:11

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

nooga10:12:12

and it’s probably something stupid

orestis10:12:45

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 🙂

nooga10:12:23

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

nooga10:12:19

ah, my S function is totally wrong 😄

val_waeselynck11:12:05

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

val_waeselynck11:12:44

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

erwin11:12:54

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

erwin11:12:34

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 😉

orestis11:12:53

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…

orestis11:12:16

And indeed I arrived at the 24 + 16…

orestis11:12:27

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

orestis11:12:18

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.

orestis11:12:01

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 🙂

nooga11:12:38

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

val_waeselynck11:12:29

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

val_waeselynck11:12:47

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

orestis11:12:04

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.

val_waeselynck12:12:41

@U7PBP4UVA 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 🙂

val_waeselynck02:12:37

@U1YPTG4UF re: your question, see this thread 🙂

nooga12:12:09

it crashes this funny repl but works on my machine

nooga12:12:51

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

nooga12:12:33

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

bhauman14:12:43

@nooga your are probably having a cons explosion?

bhauman14:12:42

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

bhauman14:12:06

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

bhauman14:12:20

and when it finally comes due it explodes

nooga14:12:25

no idea, I scrapped this “compiler” function

nooga14:12:57

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

bhauman14:12:26

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

bhauman14:12:01

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

bhauman14:12:11

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

grzm14:12:26

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

borkdude14:12:52

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

mfikes14:12:38

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

borkdude16:12:38

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

borkdude16:12:13

Could probably optimize it by handwriting it.

nooga16:12:32

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

grzm20:12:13

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.

nooga21:12:03

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

nooga21:12:36

so it was off by 0 this time 😉

grzm21:12:26

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

grzm21:12:58

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

nooga21:12:44

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

grzm21:12:26

true. doesn't help with 1234765890, though

bhauman21:12:52

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

grzm21:12:05

How can it be wrong when it feels so right?

val_waeselynck23:12:04

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)