This page is not created by, affiliated with, or supported by Slack Technologies, Inc.

## 2017-12-16

## Channels

- # adventofcode (93)
- # beginners (104)
- # boot (1)
- # cider (4)
- # cljsjs (2)
- # clojure (174)
- # clojure-austin (1)
- # clojure-greece (5)
- # clojure-spec (13)
- # clojure-uk (32)
- # clojurescript (15)
- # core-logic (13)
- # cursive (13)
- # data-science (8)
- # datomic (11)
- # duct (1)
- # fulcro (22)
- # instaparse (23)
- # jobs (1)
- # lein-figwheel (5)
- # off-topic (13)
- # onyx (13)
- # parinfer (1)
- # pedestal (19)
- # re-frame (33)
- # specter (26)
- # unrepl (22)

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.

```
[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 parser seems to be correct: when I coerce the parsed tree back to a string and compare to the input, it’s equal

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

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.

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

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

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

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

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

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…

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

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

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.

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

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

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

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

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

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

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

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

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)