inky has a blog inky writes about stuff

January 7, 2016

Advent of Code, pt 3

Filed under: Uncategorized — Tags: , , — inky @ 9:15 pm

Final post on Advent of Code. Here’s where things get a little hairy.

Day 18
Language: Rust
Prior experience: Very little
Development time: 4-6 hours

I took a week off in between jobs before I started my current job. Naturally I had big plans to do a bunch of stuff but didn’t really accomplish anything except noodling around. One of the things I was noodling with was a mastermind game and solver. I did a version in go pretty quickly, the first thing I’d written there, and then I thought I’d port it to rust. I think I spent three days wrestling with it and never managed to get anything that compiled. I was also pretty fed up with how documentation on rust is perpetually out of date and anything you find by googling is likely to be incorrect. This time I was smarter and followed the same procedure as with the haskell problem, and did a bunch of tiny steps. It helps that this problem is simpler than a mastermind solver, too.

Anyway, I got it working, and it seems fine. I like the theory behind rust, that you have a really strict and careful compiler, and in exchange it can make a lot of clever optimizations. But I don’t feel like the actual language is that great, and it doesn’t come off like it has a coherent philosophy behind it (I am willing to believe it does, I’m just saying it doesn’t seem that way, which means I can’t figure out how to write the code properly). It feels a little like a throwback to my early days with C++, where when I don’t know why something’s not working, I throw in some &s or *s until it does.

Day 19
Language: Racket
Prior experience: None, but a bit of lisp in college and some elisp and I looked at advsys once
Development time: 4 days

Back when I was starting this out, I said that one of my rules was that you had to be able to parse anyone’s input with the same piece of code. It seems like the corollary there is you can’t do any optimizations based on the specific nature of your particular input, but this problem is basically impossible to solve without writing optimizations based on the nature of the productions (ie, that there are only A -> BC productions and A -> B_Ar_C(YD)*_Rn_ productions). And indeed it looks like the intended “best” solution doesn’t involve running productions at all. Unsporting! I don’t know if part 2 was supposed to be so obviously difficult that you were supposed to look for a different way to analyze it, or if being able to do an easy static analysis is more of an easter egg. Anyway, so this is the only problem I feel like I failed at in the game. I wrote a solution for racket in the first part, and one for the second part too but it wasn’t efficient enough. So then I wrote a reference solution in perl, but I just didn’t have the steam to translate it to racket. Especially after I read one of the comments on the reddit post above and saw somebody saying it was no problem to reduce it recursively if you do it backwards. Which, argh, I thought I tried, but apparently I just didn’t do it correctly. Anyway, pretty unsatisfying all round.

Racket was ok to use. I kind of don’t understand the whole scheme/lisp world – it seems like it is pretty common there to have a bunch of similar but not quite identical dialects, which feels like it does no good for anyone. But racket seems like a good enough version as far as it goes. I don’t think I’ve seen a scheme/lisp that didn’t feel vaguely antiquated in its constructs (but maybe this isn’t being out of date so much as evolving on a different branch for a long time) and this wouldn’t woo me away from clojure or even haskell, frankly. Speaking of haskell, if I have one regret here, it’s that I didn’t use curry more – I am pretty sure there are places where the lambdas could have been replaced by something less clunky.

Day 20
Language: Golfscript
Prior experience: None
Development time: 4-6 hours

Golfscript mainly comes up as a thing I see on, since I’m not otherwise an esolang buff. I figured I’d take a look at one of the codegolf languages for this, and decided not to pick Pyth since golfscript has the better name. This seemed like a totally suitable problem – pretty math-y, not super complicated, no big input processing, but I spent a couple hours staring at the golfscript page and really got nowhere. So I gave up and did an implementation in ruby (golfscript is implemented in ruby so I figured I might be able to translate it or something), and then came back a couple days later. On my second try I figured out the deal and was able to get something going, so hooray for persistence. It turns out the mistake I was making was thinking of golfscript as a stack-based language. It is, but if you look at the language primitives, it seems pretty clear the actual intent is you use it like a functional language with map/reduce/filter kind of operators, and only use the stack to store data when you need to. With that mindset things got a lot easier, since I know how to do functional programming, and I feel like I got something pretty reasonable (which doesn’t actually solve the problem fast enough, but everyone says golfscript is slow, and it seems correct on all inputs I tested it with, so I’m going to call it a day). I’m sure pro golfscript people could get the programs way smaller, but at this point I’m happy just to complete the course.

Day 21
Language: C# (under Mono)
Prior experience: Lots
Development time: 1-2 hours

Well, the mono install made the erlang install look compact, but I’m still kind of impressed there’s a working C# compiler/interpreter on linux at all, so I can’t really complain. Like the java problem, apparently using a language I’m used to using for work turns me into an enterprise programmer, and I actually made classes and, like, an OOP design for this one. But c’mon, the problem really seems like it calls out for that. I’m a little disappointed with the code I ended up with to implement the equipment restrictions (one weapon, zero or one pieces of armor, zero to two rings with no repeats). Instead of a bunch of crazy nested loops, it would probably have been cleaner to generate all possible sets and reject the ones that are illegal (but how do you know which sets to generate? I guess everything with 1-4 pieces). I do like using yield, though.

Day 22
Language: Pike
Prior experience: None
Development time: 4-6 hours

There’s no real reason pike didn’t take off more – it’s a high-level scripting language written in the early 90s that starts with ‘p’. Coming from LPC it’s got a cool origin story, and if the object system feels a little hacked in, it’s not the only one. But here in this universe the only reason I’ve heard of it is because a friend of mine is super into it, so this was my first time checking it out. The array declaration syntax is frustrating – it’s bad enough not using square brackets, but requiring two characters ({..}) is really terrible*. It’s typed – maybe that’s why it didn’t catch on – but the typing is flexible enough (including allowing typing something as int|string) that it seems like more a plus than a minus.

*Now it occurs to me that it’s using curly braces because that’s what C uses – I guess I should be thinking of this as a dialect of C or C++ that evolved into a scripting language, rather than something conceived of as a scripting language from the start.

Anyway, overall I don’t see anything that pike does better than other languages, but it seems pretty versatile and friendly, and I could totally see using it quite happily if it was my main thing.

Now, about the problem. I started off thinking the search space was going to be comparable to the last problem – I figured the enemy does about 10 damage a round and has about 50 hitpoints, so combat lasts at most six rounds and has 5^6 states, no biggie, right? What I quickly found out is that there’s no way the player can win if the enemy is doing 10 damage a round, so you have to use the shield spell, so suddenly the number of possible rounds goes way up and the state space explodes. I tried a bunch of possible heuristics, but I finally ended up with an algorithm I was pretty happy with and don’t actually remember seeing before anywhere. I’m sure it has a name, I just don’t know what it is. The idea is, you’re looking for a winning state with the minimum cost. So you start out doing a depth-first search** until you find a winning state, and then you restart, cutting off branches when they exceed the minimum cost. You keep restarting every time you find a cheaper winning state until you’ve walked the whole tree, but you only end up looking at a small subset of possible states.

**Hmm, I guess the code is actually doing a breadth-first search, but really a DFS seems better here, since you want to get to end states as quickly as possible.

This feels like one of the problems in this game that is actually better solved by a human using pencil and paper, which I think is a defect. Or maybe some human-assisted thing – like, I bet some people solved this by writing their code to force the PC to have shield and poison up as much as possible, and narrowed down the space that way.

Day 23
Language: Perl 6
Prior experience: None
Development time: 1-2 hours

Perl 6 got announced for christmas, so that seemed like a sign. It’s interesting how all over the map the long development effort has made it. Like, perl 6 has a terrible process to get the interpreter – you have to download a couple custom things, and build them from source, and then there’s a huge installation process. But once you’re up and running, the documentation is spectacular, with both language docs and forum discussions going back years. I guess this is what happens when you strictly separate the language spec from the interpreter development. Anyway, uh, it’s the perl I know and love, plus some other crazy stuff. I really think people these days tend to underrate perl 5’s readability – it has a bad reputation because dollar signs are scary but I think the language design is very good and more intuitive than it appears at first. Perl 6 pretty much continues this, with language constructs like “my $filename = “blah.txt”; my @lines = $filename.IO.lines;” and “return $reg if $reg eq any(@registers);” I’m not sure how this stuff works, but it does. Oh, and the error messages from the compiler are really good. Someone put in some serious work there.

The problem is fun but I don’t get the “The unknown benefactor is very thankful for releasi– er, helping little Jane Marie with her computer.” quote in the second half. The annotations for the first half make a Neuromancer joke, which I’m not familiar with – is the quote also a joke on the same theme? Because if it’s supposed to be that I just ran a virus, that doesn’t really make sense if the input is randomly generated. Or maybe it’s just pretending to be random? I feel like the theme needs a little work, is all.

Day 24
Language: Python
Prior experience: Lots
Development time: 1-2 hours

There were times earlier when I wanted to bust out python for a problem, figuring I would save it for the really hard ones at the end. Day 24 was not actually the hardest one, but oh well, near the end you don’t have many other choices. Unlike some previous problems, I was pretty happy with the level of optimization required to solve this in a reasonable amount of time. I experimented with a few different solutions before realizing that the goal is to generate the smallest set, so instead of generating all valid sets and finding the smallest, you should generate all possible sets from smallest to biggest, and stop when you find one that’s valid (or, rather, stop when you find out the smallest size, and generate all valid sets of that size). Hmm, even as I write this, I am now thinking it is probably possible to generate only valid sets, but I’m not sure it’s worth the effort, this seems fast enough. Also, once again I correctly predicted part 2 and was pleased to be able to solve it pretty straightforwardly.

Day 25
Language: Perl 5
Prior experience: Lots
Development time: <1 hour

This was a gimme, of course. There are two ways to do a finale problem in a game like this – you can do a really complicated one, or you can do an easy one, and I think we were all burned out on hard problems by this point. If I knew math there would be a way to solve this with modular arithmetic, right? As it was I just had to calculate all the values, but I am pretty sure I could avoid that if I needed. Then the second half wasn’t a puzzle at all. I think it might have been better game design to draw out the ending some – like, maybe we should have had to push a button for each day to submit its stars or something, or it should have been more of a meta-puzzle thing you assemble from the different days, like you have to input the sum of all your answers mod 1225. But anyway, done, hooray!

So I had a good time playing this! I’m not sure what I’ll do if the author runs it again next year – I’m not sure I can dig up another 25 languages without getting into, like, assembler. I’d like to find some other programming skill to work on instead, but there’s nothing obvious. Maybe do everything TDD-style, since that’s new to me.

No Comments

No comments yet.

RSS feed for comments on this post.

Sorry, the comment form is closed at this time.

Powered by WordPress