r/adventofcode • u/daggerdragon • Dec 16 '17
SOLUTION MEGATHREAD -๐- 2017 Day 16 Solutions -๐-
--- Day 16: Permutation Promenade ---
Post your solution as a comment or, for longer solutions, consider linking to your repo (e.g. GitHub/gists/Pastebin/blag or whatever).
Note: The Solution Megathreads are for solutions only. If you have questions, please post your own thread and make sure to flair it with Help.
Need a hint from the Hugely* Handyโ Haversackโก of Helpfulยง Hints^ยค?
[Update @ 00:08] 4 gold, silver cap.
- Click here for a massive Star Wars spoiler!
[Update @ 00:18] 50 gold, silver cap.
- Click here for a gigantic Harry Potter spoiler!
[Update @ 00:26] Leaderboard cap!
- And finally, click here for the biggest spoilers of all time!
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!
13
Upvotes
11
u/BumpitySnook Dec 16 '17
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.
10
u/glguy Dec 16 '17
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
7
u/askalski Dec 16 '17
Perl regex.
5
u/xiaowuc1 Dec 16 '17
find the bug :)
https://gist.github.com/anonymous/cd3dd8e1f09f8950496269dbb47a7e7b
5
u/Chris_Hemsworth Dec 16 '17
Nobody uses IDL.
5
u/vyper248 Dec 16 '17
Javascript
First Part is about 8ms
Second Part is about 122ms
4
u/tangentialThinker Dec 16 '17
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.
4
u/GassaFM Dec 16 '17 edited Dec 16 '17
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), andq, actions that permute domain (Partner). Then, the permutation after one dance isq^{-1} * p. And more importantly, the permutation afterkdances isq^{-k} * p^k. So we can use binary exponentiation for the separate partspandq, and then multiply the results.I feel silly for not realizing that one could instead search for the period. Still, glad this approach finally worked.
4
u/Tandrial Dec 16 '17 edited Dec 16 '17
Kotlin
4
u/jonathan_paulson Dec 16 '17 edited Dec 16 '17
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
7
u/sblom Dec 16 '17 edited Dec 16 '17
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.
3
u/DFreiberg Dec 16 '17
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
jwhether or not the order was alphabetical, and if it was, I calculated 109 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.
3
u/hxka Dec 16 '17
3
u/[deleted] Dec 16 '17 edited Dec 16 '17
Perl 6
This takes about
4718ยน14 secondsยฒ on my machine, so not fast by any means, but it does the job.ยน - 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 theswapfunction. 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]);3
u/p_tseng Dec 16 '17
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.
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.
3
u/flup12 Dec 16 '17 edited Dec 16 '17
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 thanList(<function1>, <function1>, ...)Did the parsing using regexes:
And then it's time to dance!
3
u/AndrewGreenh Dec 16 '17
TypeScript I like how short this one turned out after lots of work.
2
u/willkill07 Dec 16 '17 edited Dec 16 '17
C++
I feel disgusting... brute forced part 2 [in only 6 minutes]
2
u/Unihedron Dec 16 '17 edited Dec 16 '17
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!
postscript
2
u/VikeStep Dec 16 '17 edited Dec 16 '17
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
2
u/omegaphoenix16 Dec 16 '17
Part 1: 117, Part 2: 26 import sys
2
u/mal607 Dec 16 '17 edited Dec 16 '17
Python 2: (Edited after posting results and incorporating insights from other solutions)
2
u/Smylers Dec 16 '17 edited Dec 16 '17
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,(Requires at least version 5.20 for the
signaturesfeature. They really help make dispatch tables more readable.)PS: I finally remembered about
\Kin the regexp today โ thanks /u/askalski!.Edit: Added a line so that it prints the answer for part 1 as well as part 2.
2
u/CaptainCa Dec 16 '17
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()
2
u/streetster_ Dec 16 '17 edited Dec 16 '17
q/kdb+
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.
2
u/sim642 Dec 16 '17
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.
2
u/mschaap Dec 16 '17 edited Dec 16 '17
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...
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.)
2
u/xkufix Dec 16 '17
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:
2
u/[deleted] Dec 16 '17
match OCaml Fun with More sequences;;
Parsed input with Menhir/Lexer into Dance type:
Then just sequences for finding cycling then getting the proper result.
2
u/m1el Dec 16 '17
Analytical solution with numpy:
2
u/localtoast Dec 16 '17
No F# answers?
Here's mine; wtf, I love memoization now https://github.com/a-red-christmas/aoc2017-fs/blob/master/day16/Program.fs
2
u/Vindaar Dec 16 '17
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.
2
u/chunes Dec 16 '17
Factor
2
u/Jaco__ Dec 17 '17
Some mildly clunky Haskell
1
u/vash3r Dec 16 '17 edited Dec 16 '17
Python 2 (22/48). Using Pypy, I didn't really need to find a stricter bound for the cycle.
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
12ignoring the partner swaps or60including them, so calculating15*14*13*12*3*11is overkill.1
u/mserrano Dec 16 '17
Python 2 for #1 on part 1:
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:
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!
1
u/miran1 Dec 16 '17
Python
Missed the leaderboard (#116) because I left brute force version running for way too long.
1
u/TheAngryGerman Dec 16 '17
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...
1
u/if0nz Dec 16 '17
Java I lost too much time for understanding how to perform the modulo ):
1
u/mahousenshi Dec 16 '17
Yet another python3 solution
1
u/iamnotposting Dec 16 '17 edited Dec 16 '17
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
1
u/KeinZantezuken Dec 16 '17 edited Dec 16 '17
C#/Sharp (there is a way better/faster solution to work with strings but I aint bothering)
'36' is the n iteration value after which the string of letters is back to original state.
1
u/hpzr24w Dec 16 '17
C++ 959/580
Switched from Visual Studio on Win 10 to VisualCode/Clang/lldb on El Capitan and was a bit slower than usual.
1
u/[deleted] Dec 16 '17
C++ A couple custom things but not really.
1
u/apistoletov Dec 16 '17
Python 3 โ golfed, 527 bytes (tab indentation), prints answers in ~1 second
1
u/WhoSoup Dec 16 '17 edited Dec 16 '17
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. :(
1
u/Philboyd_Studge Dec 16 '17 edited Dec 16 '17
Java. This was a fun one.
1
u/spacetime_bender Dec 16 '17
Part 2 C++ Similar to what others have done, first find cycle then perform the dances on the remainder
1
u/jeroenheijmans Dec 16 '17
JavaScript:
Here's the important part:
I spent most of my time re-reading the question because I had an off-by-1 error because the
returnstatement (copied from solution 1) would do one last dance before returning...FWIW, here's the helpers:
1
u/TheAngryGerman Dec 16 '17
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.
1
u/wlandry Dec 16 '17
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 ;)
1
u/sickening_sprawl Dec 16 '17
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
itvariable 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.1
u/JeffJankowski Dec 16 '17
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...
1
u/ephemient Dec 16 '17 edited Apr 24 '24
This space intentionally left blank.
1
u/u794575248 Dec 16 '17 edited Dec 16 '17
Python 3
d: dance onceD: input stringp: current standing['a', 'b', ...]m: one of dance move type{'s', 'x', 'p'}P: list of previous standings['abc...', 'kbe...', ...]1
u/udoprog Dec 16 '17
Rust
Full solution here: https://github.com/udoprog/rust-advent-of-code-2017/blob/master/src/day16.rs
1
u/aurele Dec 16 '17
Rust much too long
1
u/autid Dec 16 '17 edited Dec 16 '17
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)
1
u/_A4_ Dec 16 '17 edited Dec 17 '17
JavaScript ES6 (Part 2)
Uses an array of functions created with
Function.prototype.bind. Also shows how to easily swap variables in JS.1
u/Fluffy_ribbit Dec 16 '17
Ruby. I am like a little baby.
1
u/BOT-Brad Dec 16 '17
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'.
Part 2 (~16 seconds ๐)
Felt like my CPU needed a workout.
1
u/raevnos Dec 16 '17
Kawa Scheme:
1
u/Axsuul Dec 16 '17
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
1
u/Markavian Dec 16 '17
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
1
u/[deleted] Dec 16 '17
Elixir
Had to see the tip of memoization today, not proud, but well, here's my still pretty slow solution:
syntax highlighted
1
u/rkachowski Dec 16 '17
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...
1
u/akka0 Dec 16 '17
ReasonML: had a pretty hard time with this one, took a long time to realize that there might be cycles
1
u/[deleted] Dec 16 '17
single pipeline powershell:
1
u/[deleted] Dec 16 '17
Crystal. Took me a while to think that there might be cycles. After that it was straightforward. Just part 2 here:
1
u/[deleted] Dec 16 '17
1
u/akho_ Dec 16 '17
Python 3; no cycle detection
1
u/StevoTVR Dec 16 '17
NodeJS
Part 1:
Part 2:
1
u/InterlocutoryRecess Dec 16 '17 edited Dec 16 '17
Swift (#434/ [then my daughter woke up!])
Performance: I wrote this in an Xcode "Command Line Tool" project. When I'm done debugging, I turn on optimizations in the build settings.
1
u/tobiasvl Dec 16 '17
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
abcdefghijklmnopto 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?1
u/lypnol Dec 16 '17
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.
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.
1
u/miran1 Dec 16 '17 edited Dec 16 '17
Nim
Repo with solutions (both Nim and Python)
ย
1
u/wzkx Dec 16 '17 edited Dec 16 '17
J
Part 1
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.
1
u/RockyAstro Dec 16 '17
Icon (https://www.cs.arizona.edu/icon)
Both parts:
Part 2 took me a bit longer then it should have... screwed up by not correctly reading the instructions.
1
u/thomastc Dec 16 '17
Day 16 in F#. This language feels like an imperative train crashed into a functional building. Completely inelegant. And yet, it's effective.
1
u/wzkx Dec 16 '17 edited Dec 17 '17
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.
1
u/iopred Dec 16 '17
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):
1
u/erlangguy Dec 16 '17
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.
1
u/cthulhucomplex Dec 16 '17 edited Dec 17 '17
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.
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
1
u/dylanfromwinnipeg Dec 16 '17
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#
And here's the handful of extension helper functions I used:
1
u/lasseebert Dec 16 '17
Elixir
Repo: https://github.com/lasseebert/advent_of_code_2017/blob/master/lib/advent/dec_16.ex#L43-L109
1
u/[deleted] Dec 16 '17
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.
1
u/NeilNjae Dec 16 '17
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
intMapto store the history of the reached states in the iterated dance, wrapped that in aStatemonad as the history updated, and wrapped that in aReadermonad 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.
1
u/chicagocode Dec 16 '17
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! :)
1
u/NeilNjae Dec 16 '17
Haskell. All they joys of a monad transformer stack! For part 1, I used a
Statemonad to track the position of the dancers while doing the dance. For part 2, I used anintMapto store the history of the reached states in the iterated dance, wrapped that in aStatemonad as the history updated, and wrapped that in aReadermonad 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
1
u/SurplusSix Dec 16 '17
Racket again
Not sure about efficiency, seems not great as this being part 2 took 6 secs to run, and that was only 60 cycles.
1
u/aceshades Dec 17 '17
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
pastemode.1
u/Basillicum Dec 17 '17 edited Dec 17 '17
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
For part 2 I've added:
1
u/redbeard0531 Dec 17 '17 edited Dec 17 '17
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:
If you just want to see the raw asm, the main loop compiles to this:
1
u/matusbzk Dec 17 '17
Haskell
Link to git
1
u/__Abigail__ Dec 17 '17 edited Dec 17 '17
Perl
1
u/ramendik Dec 18 '17
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.
1
u/Tetsumi- Dec 18 '17
C. Both part.
the state is stored into a 64 bits unsigned (4 bits per program) to avoid hashing.
1
u/mastokley Jan 18 '18
Clojure.
0
u/[deleted] Dec 16 '17
[deleted] โ view deleted comment
0
u/[deleted] Dec 16 '17
[deleted] โ view deleted comment
0
u/[deleted] Dec 16 '17
[deleted] โ view deleted comment
0
u/[deleted] Dec 16 '17
[deleted] โ view deleted comment