Subject: Day 16
Author:
Posted on: 2017-12-16 15:46:00 UTC
The solution.
I do have to admit to cheating slightly here. My original, much more naive solution was running (and running, and running), and so I wandered onto Reddit. On the advent of code subreddit, I saw an offhand mention of svaqvat n plpyr (I think it might have been in a title, not sure), which inspired the current, way faster, solution.
- Tomash
So, since Thoth and I realized we might not be the only two people who care about this, here's a link to the Advent of Code. It's a series of 24 two-part programming puzzles that go up once per day in, well, Advent. The puzzles aren't ever, but can be more or less challenging depending on background, which programming language you happened to pick for that one, and so on.
Unfortunately, I can't travel back in time and start a thread for solutions and discussion that goes to the first, but one can start now.
I suppose I should make clear that posts containing solutions should be marked, and the solution should either be linked from offsite, spoiler-blocked past visibility, or rot13'd, as they're spoilers.
Is anyone else participating I don't know about? If so, the private leaderboard I've been using is 210839-00cf4240.
- Tomash
I'm not posting code for day 23, as part a was a rather simple modification of code from an earlier day, and part b boiled down to staring at the input until figured out what it was meant to do, then writing a short program to do it much faster.
Day 24 ended up being a rather unenlightening brute-force. The first implementation I made (yesterday) either had a bug or horrible memory inefficiencies, which is why it happened now.
Day 25 ended up being pretty much writing out the definition of a Turing Machine and filling in the blanks per the input.
And so the challenge came to a close for me.
Was fun.
- Tomash
... back when you posted it at first. I didn't intend to do it, but figured I might have a think about it.
Yeah... I couldn't even understand the question. ^_^ That sort of programming is far beyond me.
So yes, I am very impressed.
hS
They're a lot easier. The first year, I think I only got... ten days in? Less? And the problems vary in difficulty, so...
The code is here and I happen to like it. It's a nice implementation of the exercise with not much in the way of nasty hacks (the grid is sparse because of course it is, and I used C = R^2, but that's notational convenience)
- Tomash
The code
Now, the neat thing here is that you can apply the flips and rotations to the input rules instead of the grid windows. This means you only have to screw around with the entirety of the permutation group on the square once.
The bad news is that, for the hashmaps to behave, extracting out the grid windows is still annoying and looks ugly, as does putting the result where it should be.
But that could be a flaw of using [bool; N^2] for windows instead of [[bool; N]; N].
But I've been raised on the former representation, so oh well.
- Tomash
Firstly, this link heads to the code.
Now, in reference to the title, "loop until the answer stays the same for a while" is a valid technique in nemerical simulation code ... which this is. However, usually it would help to have some assurance that the system won't do arbitrary weird stuff a few more iterations after you stop looking, and that it'll actually settle down eventually. That is, you'd like to be convinced of stability.
However however,
a) The contest organizers assured us the procedure would be stable.
b) In practice, everyone just rolls with it except where the book said you need to watch out for stability issues.
- Tomash
So, first, the code.
Now, the confession. I'm not sure what I was thinking when I made the code first take a step and then check the conditions for the step after that. The two parts of step() should've been in the opposite of the order they're in.
But oh well. It works.
- Tomash
The TXR hackery continues! (seriously, TXR is pretty freaking nice and I've been having a lot of fun with it).
This isn't the shortest or cleanest code I've ever written, but it seems to work reasonably well. And it's gotten cleaner then it was initially. It's also only two screens of code. Which is... pretty decent for me. https://pastebin.com/xUJSbEsf
So, they said the instructions could be arbitrarily interleaved ... what better solution to that than good old-fashioned hardware threads! (Who am I kidding, there's probably better solutions.)
So, without further ado, a program made of gloriously overcomplicating things (or just implementing the spec exactly as written)
Also, the inputs are evil. Registers need to be 64-bits wide or things won't work.
- Tomash
For this puzzle, I used TXR Lisp. TXR is a scripting tool developed by Kaz Kylheku, aka kazinator, aka that guy who never shuts up about TXR on HN.
Credit to him, TXR is a really awesome tool. The associated Lisp dialect is basically CL with a lot of built-in functions and shortcuts and a few semantic changes to make it more convenient for scripting. It also has wrappers for all the POSIX stuff you could ever want. So I solved this with `fork(2)` and `pipe(2)` as the process and IPC mechanisms.
https://pastebin.com/imTJR4t7
You're almost certainly the second person in the world to use that awk macro; very brave.
My only remark after glancing through the code is that: there is a casequal (case based on equal) operator so you can do (casequal expr ("foo" ...) ("bar" ...) (t ...)) instead of coding up a cond with explicit equal comparisons.
Cheers ...
P. S. For the record, periods during which I remain silent about TXR on HN can be easily measured in weeks and months.
and your code generally makes sense (once I'd twigged that the child got to play the role of process 0).
I'm assuming *ischild* is Magic (tm)?
- Tomash
I previously had a variable called `*is-chld*`, but it was literally just (not *cpid*) and was used in only a few places. I thought I'd removed it properly. Guess not.
I still haven't finished day 16, but day 17 was easy!
I took the incredibly naive approach in Lisp. Worked pretty well. It took a minute or two to run, though, and I exhausted the heap and crashed my code on the first runthrough. I had to expand the heap, or it wouldn't work. Come on SBCL, I'm only consing up a 50 million element circular list! :-P
...And I mistakenly named my post "Day 19". https://pastebin.com/mvHvquN5
because a circular linked list in Rust was being annoying.
Solution at at this Pastebin
The solution.
I do have to admit to cheating slightly here. My original, much more naive solution was running (and running, and running), and so I wandered onto Reddit. On the advent of code subreddit, I saw an offhand mention of svaqvat n plpyr (I think it might have been in a title, not sure), which inspired the current, way faster, solution.
- Tomash
So, my code is in this pastebin.
I'm liking that I figured out a way to unify parts A and B, and maybe a bit too unreasonably proud of that one bit where I cast a boolean to an int.
Concrit is appreciated, if anyone has any.
- Tomash
Oh, look at us, all clever and modular-like. :P. Seriously, your code looks quite good.
I wrote in C. So.. not as cool and shiny and modular. But I did get to use function pointers. https://pastebin.com/UcnibFee
Some #define'd constants might've been a good move though.
Or, if you really wanted to be fancy, even though it might be overkill for two cases, a C macro for generating the functions.
(since that's really all I don't like about your solution. Excessive copy-paste)
- Tomash
So, thought about it. And then I said, "no. I won't do it. #define-generated functions are way too complicated a direction to go, it's a bad idea."
...So 15 minutes later, I'm reading the docs for preprocessor macros...
I also changed some other things: `long int` is `long` now (as per... C99, I think?), some things got put in functions, and `initgens` got inlined at its one callsite, as did `comparegens`.
The result is much shorter, and (arguably) cleaner. Although the inlining may be questionable: https://pastebin.com/B4Ttjvn4
...So then, I figured, what the hell, let's golf it.
Every line in the following as 80 chars or less. Really. I swear. It follows basically the same logic as the other version, just with no affordances for readability: https://pastebin.com/kWqsbuKe
I am a monster...
See here. (because I took that as a challenge).
More seriously, in code meant for readability, I prefer spaces around +=, == and the like.
My solution for today was written in Common Lisp. Because Lisp, yey. I've done most of my solutions in either CL or AWK thus far.
It comes in two parts. The first is a slight refactoring of my day 10 solution into something actually callable (and having it return a giant bitvector!), in the file knothash.lisp: https://pastebin.com/j7xYL0ZF
The second part is the actual solution. Yes, I should have parameterized lengths, but I am lazy. The functions total-bits and colorize return the solutions: https://pastebin.com/T8Kh1iMW
is pretty similar.
Jr obgu raqrq hc oehgr-sbepvat gur tebhcf, gubhtu lbhef jnf vacynpr naq zvar jnfa'g
Tvira ubj lbh jrer unaqyvat gur erphefvir pnyyf va `pbybe`, jevgvat n `pynzc` shapgvba zvtug'ir orra n tbbq zbir.
rirelguvat jnf cerggl ernqnoyr, V guvax, nsgre V erserfurq zl zrzbel ba ubj Yvfc tbrf n ovg.
- Tomash
is at this pastebin. It's in Rust, which is what I've been writing all of these in so far just to stay in shape with systems languages (given one of my possible research fields next semester).
It includes a copy-paste of my day 10 part b, code.
What I'm not the biggest fan of in my solution is that the region-find is rather inelegant and it feels like there should be something better than brute force there.
On the positive side, the program is rather clean, I'd say.
Anyone else have concrit? Solutions?
- Tmash