Categories
Advent of Code

Advent of Code 2020, Day 8

I liked day 8. It made me feel clever when I worked it out. Spoilers follow as usual, and my solution is here.

There are a few classes of puzzle that show up time and time again in Advent of Code. One of these is the virtual machine puzzle. That’s where it gives you some computer code, and the task is to make something that can run it.

Remember I mentioned Intcode from 2019? That was a virtual machine puzzle writ large. It was built up over multiple puzzle-days and ended up as a fully functional computer, capable of performing any computation and even able to talk to external hardware. It was a masterpiece of puzzle design.

This is not that complicated. Today, we’ve got a simple instruction set. There are three things our hypothetical computer can do: add a number to another number, jump forward or backward in its instruction list, or just do nothing and move on to the next step. It’s not really a proper computer, just a slightly convoluted adding machine.

(Maybe I should go into exactly what a universal computer and Turing-completeness mean some time. Be a fun writing exercise.)

Something this simple wouldn’t take me long at all in a language I already know, but as previously established, I’ve been learning Haskell this year. Haskell is a pure functional programming language. What this means is it doesn’t follow step-by-step instructions like another language like C or Python would. It feeds the results of various functions into each other in a long pipeline. This makes having it pretend to be a step-by-step computer… challenging.

A challenge I greatly enjoyed.

The thing with a pure functional programming language is that it doesn’t really have state. If you run the same function with the same inputs twice, you will get the same output both times, always. There are two ways around this.

The first of these you’ve already seen me use. It’s recursion – the function calls itself for the next step with slightly different input. That would have worked here, because the pretend adding machine only keeps track of two numbers internally – the results of its adding, and the instruction number it’s on. It’d be pretty easy to keep passing those to the next step.

That is insufficiently needlessly elaborate.

The second way, which is what I actually did, is to use something called a monad. It’s a way for a functional language like Haskell to pretend to have state. Behind the scenes, it’s still doing recursion for you. It’s just easier to write. My friend Emi did an excellent introduction to the topic on their own site, and I heartily encourage you to have a read.

To summarise: when working with monads, you have actions instead of functions. Those take the existing state, do something with it, and give back the resulting changed state. You step through various actions not unlike how you would in an imperative programming language.

Definitely hit a few pitfalls on the way, though! This is a new way of working in Haskell, with its own syntax and rules that are slightly different from non-monadic stuff.

I fell into the trap of thinking the return function does the same thing a return does in an imperative language – drops you out of the function with the value you give it. Nope, nope, nope, it’s just badly named. What it actually does is give you an action that will always produce the value you give it, regardless of the current state.

Categories
Advent of Code

Advent of Code 2020, Day 7

Day 7 was a bit more challenging than the last couple. As usual, spoilers for day 7 follow.

This time around, the subject of our airline-based adventures was the baggage restrictions. Each bag is given a certain colour coding, and must contain a selection of bags of other colour codings based on a simple set of rules. The rules are a mere six hundred lines long, so not that different from real baggage restrictions.

Two parts to it. For the first part, we have to work out which other bags can contain our bag (coded “shiny gold”) either directly or indirectly. For the second, follow the rules to their “topologically impractical” conclusion and work out how many bags our bag must contain to comply with the rules.

My solution is in the usual place.

Rather than copy-paste the common bits or do it all in one file this time, I decided to try writing my own Haskell module that the solution files could import. That’s Bag.hs in the repository.

The Bag module contains the functions for reading the ruleset from the text file it comes in and turning it into a form I can work with programmatically. It also includes the first time I’ve used a custom Haskell type. It’s defined as follows:

type Bag = (String, [(String, Int)])

If you’re not familiar with Haskell – and I’m assuming most folks reading this aren’t – what this means is that whenever I write the word Bag in a function, what I actually mean is a string paired with a list of values, each of which is a pair of a string and an integer.

This encodes rules like “drab indigo bags contain 4 pale bronze bags, 2 mirrored lavender bags.” In my Bag type, that’d look like ("drab indigo", [ ("pale bronze", 4), ("mirrored lavender", 2) ]). Much respect for anyone carrying around a pair of mirrored lavender bags, by the way.

There’s a reason I structured things this way. My solution hinges on a function called lookup which is a basic part of the Haskell language. It lets you treat a list of pairs like a dictionary – lookup “drab indigo” in the list of rules, and it’ll give you back that it has to contain pale bronze and mirrored lavender bags – the list that’s the second part of that pair.

In other languages you’d write something like rules["drab indigo"]. It’s exactly the same thing.

A bit of parsing later, with my list of rules in hand, I’m ready to actually do something with them. Weirdly, part 1 was actually harder than part 2.

Part 1 involved finding any bag that can hold “shiny gold” bags by filtering the list of rules based on whether there was a “shiny gold” part in the bag contents list. Then recursively doing the same for any bags that hold one of those and so on.

Part 2 was the same thing in reverse, more or less. Check what a shiny gold bag has to hold. Then check what those bags have to hold, and so on, until we get all the way down to bags that are empty. As it turns out, with the particular set of rules I was given, I need to bring 158730 other bags to put in my shiny gold one.

Could’ve been worse, I guess. If I had decided to be cool and bring a pair of mirrored lavender bags, I’d have needed over 22 million bags total. Ever feel like you might have overpacked a bit?

Both parts of this puzzle are complete! They provide two gold stars: **

Categories
Advent of Code

Advent of Code 2020, Day 6

Not much to write about for day 6, though the premise is again very relatable. It’s nice to help people out when you’re the only one that can make sense of a system, though I believe more in teaching them how to understand the system than doing the work for them. I’d far rather have someone say to me, “let me show you how to do it,” than, “let me do it for you.”

The puzzle was pretty simple, though, as you can see from my solution. For part 1, take several groups of answers and count how many answers in each group were given by at least one person.

So I just borrowed my dnlsplit function from day 4 to break up the groups, and took the union of all the lists in each group. From there, the answer is just the length of each list. Easy.

Part 2, it turns out that, oh no, we misread the instructions! It’s answers that everyone in the group gave, not anyone. Well, it’s a one-word change to the code, too! Instead of the union of the lists, we just take their intersection.

I should probably have done something clever to just spit out both answers in one go, but I’m sleepy today so I just copy-pasted the part 1 code to part 2. It’s not like I’ve got code quality metrics to meet, just having a bit of fun.


EDIT: Okay, so you know I said I wasn’t going to make it do both answers in one go? I made it do both answers in one go.

I changed my groups function from just finding the union or intersection as it was before to finding both and spitting them out as a two-element list. Easy enough, but now I can’t just do sum . map length to get the total number of answers any more.

What to do about that? Well, the Data.List module I was already using for union and intersection also has a function called transpose. That takes a table in the form of a two-dimensional list, like the one I just made, and flips its rows and columns.

So now, instead of a long list of sets of two answers, I’ve got two long lists of answers. That is something I can sum, just doing map (sum . map length) to apply the same calculation I was doing before to both lists of answers. That gives me the answers to both parts at once!


EDIT 2: Despite how simple today’s puzzle was, I just can’t seem to leave this one alone. After talking to Emi, I realised I could do away with that transpose by using a recursive function to just construct the two lists in one go rather than building pairs and then switching them around.

The result actually isn’t any more complicated. Have a look.

Categories
Advent of Code

Advent of Code 2020, Day 5

Curiously, day 5 was actually simpler than day 4. My solution is over on my git repo, and as always, this post contains spoilers for day 5 and earlier.

First of all, I’m continuing to love the writing introducing the problems. Let me just quote the first paragraph verbatim:

You board your plane only to discover a new problem: you dropped your boarding pass! You aren’t sure which seat is yours, and all of the flight attendants are busy with the flood of people that suddenly made it through passport control.

This is just brilliant, I think. Yep, the current issue is the obvious solution to the avoidable problem is unavailable because of the solution to the last avoidable problem. Our protagonist is actually a lot like me: forgetful, accident-prone, and tends towards the most complicated possible solution to a given problem. It’s like Eric Wastl knows his audience.

The puzzle itself wasn’t actually anything special, its introduction and framing aside. It’s a simple binary space partition, which is once again the sort of problem Haskell excels at. Read the encoded instructions character by character, and move the upper or lower bound of the search space depending on which character it is until you get one answer. Trivially easy with a recursive function.

Part 2 didn’t add much. Find the seat number that’s missing from the list. My solution to that was just to sort the list (it’s only got 800 elements or so) and look for two elements that aren’t numerically adjacent. Since I figured out how to deal with comparing two adjacent list elements yesterday, also pretty easy.

My seat’s in row 69, column 5, by the way. Come over and say hi if you’re on the flight once the seat belt lights go off.

Both parts of this puzzle are complete! They provide two gold stars: **

I’m a little disappointed that there hasn’t been some sort of ongoing thread like there was with 2019’s Intcode interpreter. Throughout the month, you were slowly building up a more and more capable interpreter for some made-up machine code, each day’s solution building on the last one. There hasn’t been anything like that here so far, and the fact that we’ve got to day 5 without seeing any sign of one isn’t promising.

I’m also starting to feel like using Haskell for Advent of Code might be cheating a bit. It seems perfectly geared towards exactly the sorts of puzzles that have been coming up… though just watch when day 19 comes along, the really hard puzzles kick in, and I have to eat those words.

Categories
Advent of Code

Advent of Code 2020, Day 4

I’ve been doing Advent of Code again this year, and this time I’m using it to learn Haskell. You can see my adventures with the first three days over in this thread on fedi, but my day 4 writeup ran a bit long, so I’m posting here instead.

If you’re doing Advent of Code yourself this year, then be aware that this post contains a detailed discussion of my solution to day 4, so consider this your spoiler warning.

My solution here: https://git.ninetailed.net/terrana/advent-of-code/src/branch/master/2020/day04/

First of all, I just want to say I love the premise behind this one, the puzzle aside. “This line is taking ages. I’m going to hack their system to still work properly but do it better to speed it up.” To borrow a popular fediverse idiom, that’s strong white hat energy.

After that, we get into some heavier string processing than has shown up so far this year. The input is a set of sets of key:value pairs. Individual sets of pairs are separated with either spaces or new lines, while the groups are separated by a blank line.

All my string processing in Haskell so far has been character-by-character, which is easy enough because Haskell treats strings as lists of characters. Looking for a specific pair of characters that appear together, however, is a bit harder. There’s a library that can do this for you easily enough, but I wanted to roll my own, because… well, that’s just what I’m like. Learn more this way, have more fun.

To do that, I had to learn about guards. This is a second level of pattern matching in Haskell’s function definitions that let you specify a predicate for which branch to go down. In a procedural language, this would be a set of if-else blocks. Here, it’s baked into the definition of the function itself.

-- Split a string into two across the first double newline found
dlfsplitonce :: String -> (String, String)
dlfsplitonce [] = ([], [])
dlfsplitonce (ca:cb:rest)
    | ca == '\n' && cb == '\n' = ([], rest)
    | otherwise                = (ca:before, after)
        where (before, after) = dlfsplitonce (cb : rest)
dlfsplitonce c = (c, [])

Isn’t that neat? That set of definitions handles four distinct cases, which combine to, as the comment says, split a string across the first double newline it finds. For an empty string, it just spits out two empty strings, easy enough.

For a string at least 2 characters long, if the first two are newlines, it spits out an empty string and the rest of the original string after those two newlines. That sounds like it’d only work if the newlines are at the very start, but bear with me.

If those first two characters aren’t newlines, then it gets recursive. It chops the first character off the original string, feeds the rest back into itself, then sticks the first character on the front of the result. Sticking something on the front of a list is very cheap and efficient in Haskell, so what it does here is effectively jump ahead to where it finds its pattern, then rebuild the first part of the string character by character until it has the two chunks again.

That last case? Just a special handler for when it reaches the end of the string with no match. Then it just spits out the entire original string in the first part, and nothing in the second.

Wow. That was actually harder to explain than it was to write in the first place.

From there, we have to check that seven required fields are present in a given set (my solution would break if there were duplicate keys, but there aren’t any in the test data), and that each of those has a valid value according to a set of rules.

Most of those were easy enough. Check if a number is in a given range, check if the value is all hex digits, and so on. Only one really gave me much trouble, and that was a height field, which could be specified in inches or cm, with the unit as a suffix, and the number having a different allowable range for each unit.

That might have been really hard… except I already taught myself how to look for a specific two-character sequence in a string and split on that earlier. So that actually paid off!

Both parts of this puzzle are complete! They provide two gold stars: **
Categories
Gushing About Tech

The Basics of Home Networking (or: Why IPv6 is Awesome)

I was getting excited over on Fedi about finally having native IPv6 support on my home Internet connection, no tunnels necessary, and after someone asked, that led into an explanation of the basics of IP addressing, NAT, port forwarding, and routers generally. It was a bit long to dump onto people’s timelines, but that sort of long-form infodump is exactly what I put this site up for, so here we go.

I’m going to try to keep the assumed level of knowledge low so as not to exclude anyone, so if you already know some of the basics, feel free to skip ahead a bit. Seriously, I won’t mind. Or even notice. I’m not even tracking how many people load these pages up, never mind actually read them.

IP Addresses: v4 and v6

Oh, wow, did you see what happened to my voice there? That was cool. I bet it had a dramatic echo and everything. I sound Authoritative and Well-Read with all these fancy Section Headings.

So why is any of this IP address stuff and all those other acronyms even important? Well, it all comes down to knowing where to send things.

The Internet runs on the Internet Protocol, appropriately enough. Everything on the Internet has an IP address, and data tagged with an IP address will go to that thing, wherever it is. Hence, address.

Most of the Internet you know runs on IPv4 – version 4 of the Internet Protocol. No one talks about versions 1, 2, or 3, and even mentioning them can draw the ire of the Elders of the Internet, and you do not want that kind of attention. Version 5 is likewise verboten.

(More seriously, versions 1-3 and 5 were experimental and never made it into the real world. I don’t know much about them.)

An IPv4 address is a 32-bit number, and that means there are about 4 billion of them in total. That sounds like a lot, right? Nope. Not even close to enough. The way addresses were allocated in the early days was massively wasteful, and even if they were distributed fairly, there are 7.8 billion people in the world. It’s hard enough sharing a postal address with someone else, and at least letters have your name on them.

No, I haven’t been reading your mail. I’m offended that you’d even ask.

Anyway, not enough IPv4 addresses. Clearly what we need is a bigger number so we can have more of them! And that’s all IPv6 is: 128-bit addresses so we can have more of them. So many that each one of those 7.8 billion people could have a few zillion IPv4 Internets of their own and not even use a fraction of a percent of what’s available.

Overkill? Maybe. But better than running out again. And we did run out of IPv4 addresses. Luckily, IPv6 was finalized in 1998, and following that was swiftly adopted worldwide and effectively solved the problem— ahahaha, no. About three quarters of all Internet traffic is still IPv4.

NAT: Network Address Translation

So how did the world actually deal with there not being enough IP addresses? Well, they learned to share. That’s called NAT.

This is something that almost all IPv4 routers do, and that’s (mostly) a good thing.

In the early days, everyone on the Internet had their own block of addresses that they could assign as they liked, but that hasn’t been true since 1990 or so, due to the address shortage I spent the entire previous section going on about.

What this means is that your router gets one and only one IP address that can be reached from the Internet. Any time you connect to something else out there through the router, you appear to be connecting from that one address, and when replies come back to you, the router keeps track of which connections belong to whom and send them to the right place. Hence, “router”.

So how do you connect in, to a specific device, when there isn’t already a connection from that device out? Like running a server? Well, that’s the problem with NAT. You more or less can’t. The router doesn’t know what to do with an incoming request with no context behind it.

Unless you tell it. And that’s where port forwarding comes in.

Port Forwarding (you want me to do what to my router?)

Almost all traffic on the Internet is either TCP or UDP, and while the specifics are a bit beyond the scope of what I’m talking about here, those protocols have a port number associated with them. Think of it like an extra number on the end of the IP address.

It’s like having your name on the letter. Because computers can do more than one thing, that port number is intended for the receiving computer to know which program should handle the incoming data.

But we can also make use of this when working with a NAT router. When a connection comes in on a specific port, a router can be configured to always send that on to one specific address on the internal network.

For example, you can have the router send everything on TCP port 80 (HTTP) to whichever computer is running your web server. Others on your home network can still browse the web, but unprompted external connections can be sent to that one server box.

So, if you know the port number the program you’re working with listens to, and the internal IP address of the computer running it, you can configure the router to send all the traffic for that program to that computer.

Notably, you cannot have two servers for the same thing running on the same network without doing some complicated shenanigans with proxies that I won’t go into. As much as I love a good shenanigan, this post is way too long as it is.

DHCP: Why It’s Not That Simple

Now, if it’s just a temporary thing for a game, you can find out your machine’s local IP address, plug it in, and off you go. Unfortunately, the nature of private Local-Area Networks means there’s a bit of extra work if you want a permanent server, and that’s because of DHCP.

Dynamic Host Configuration Protocol is how computers on a network get their IP addresses. When they connect to the network, or their current address expires, they send out a DHCP request to anyone who’ll listen.

Your router is also a DHCP server, which means it is listening for such broadcasts. When it gets one, it’ll assign the computer an IP address, usually in the 192.168.x.x range (though there are others) which is reserved for LANs like this. Such assignments are temporary – after a set period, usually 24 hours, the computer has to ask for its assignment to be renewed.

Most DHCP servers will try to keep a computer’s address consistent, but it’s best-effort only, and there is no guarantee the address will remain stable over time.

So if you’re running a permanent server on a private network, you need to assign it a static IP address in the router. That *does* guarantee that that computer will always receive the same address, and that no one else will ever have that address.

It makes sense on small home networks, but for bigger setups it can be a problem to permanently take an address out of service, as there are only 250 or so to go around on a given network due to the way IPv4 was designed.

Big company networks with more computers than that? Actually composed of several sub-networks that talk to each other through routers, which all just works because that’s what the Internet Protocol was designed to do without NAT getting in the way.

(Yes, I know CIDR with variable subnets is a thing, but that’s way above the level I’m going for in this post. Don’t worry about it.)

Wrapping It All Up

IPv6 was designed to make all of this unnecessary. There is no NAT in IPv6. There is no port forwarding in IPv6. There is a greatly reduced need for proxy shenanigans and subnetworks can be bigger than the entire IPv4 Internet.

So why aren’t we all using IPv6? Money.

IPv6 isn’t backwards-compatible with IPv4. What that means is that you need to run the two separate systems side by side until everyone’s on IPv6 and you can turn IPv4 off for good. You can run them on the same physical wires, but you need two completely different sets of software and, in some cases, switching hardware.

That’s more expensive than having a single IP system you can use for both, and NAT really doesn’t hurt most home users that much. I care because I’m running things on my home network that I want to be reachable from the Internet, but non-technical users don’t have any such need.

What that means is that people aren’t willing to pay for IPv6, so penny-pinching companies naturally don’t want to invest in setting them up.

What about companies that actually need lots of IP addresses to make things available on the Internet and would pay for IPv6? Well, aside from the fact that most of them already do support IPv6, they can also afford to buy blocks of IPv4 addresses at a premium.

Should You Care?

I can’t answer that. I do and I think I’m right to do so, but I’m not exactly your typical Internet user. I literally write blog posts about computer networking, as it turns out.

But if you’ve read this and decided that you should care, or at least want more information to decide if you do, the World IPv6 Launch site is a good place to start.

If not, don’t worry about it. There are more important things in this world to worry about than IP addresses. Look after yourself first.

Categories
Games Technical Difficulties

Heroes of Might and Magic 3 is a fine game that is far harder to get working than it should be

I’ve been playing Heroes of Might and Magic 2 recently. It’s one of the games I grew up with, and it holds many fond memories for me. It is also, as anyone following me on the Fediverse will know, how I discovered my lifelong fascination with griffins.

After a bit of that, today I decided to try and get Heroes of Might and Magic 3 running. While I strongly prefer Heroes 2’s aesthetic in most ways, Heroes 3 is mechanically the better game. If I could make Heroes 3 look like Heroes 2, I would be very happy indeed.

Now, getting Heroes 2 running was pretty easy, since it’s from 1996. Stick it into DOSBox and go. Heroes 3 was an entirely different matter. It came out in 1999, so it was Windows 9x native, and games of that era are often troublesome to get running on a modern system.

(As an aside, all these things are available on GOG and those folks already did all this work, but I’m not paying for these games again for the sake of a weekend’s nostalgia when I have my original CDs right here.)

First hurdle, the installer. It just didn’t work. Try running it and… nothing. Nothing at all. No window, no error message, not so much as a stray griffin feather. So out comes my first troubleshooting tool, Process Explorer, to see how far it gets.

Well. That’s not good. It’s just sitting there, not doing anything.

It turns out it’s an InstallShield installer, and those had a few quirks. For reasons I may go into another time, they use a 16-bit starter executable to bootstrap the main installer, and 16-bit support was dropped from 64-bit versions of Windows, which is all of them nowadays. The 32-bit launcher you can see there is trying to run the 16-bit one that’ll run the main 32-bit installer. But it failed, because my system can’t run 16-bit executables and it’s apparently just… sitting there, scratching its head.

After fruitlessly trying to unwrap and run the 32-bit installer I knew was buried in there, I eventually stumbled across a program called i5comp that some kind soul (thank you, fOSSiL, whoever you are!) wrote to access the InstallShield cab data format.

So, armed with this, I decompressed the game files and tried running it. To my great surprise, it actually started up first time, ran through the infuriatingly unskippable intro cinematic…

Good grief, what happened to your FACE? Oh, wait, it’s 1999 and that’s just what CG cutscenes looked like in those days.

…and dropped me to the main menu. Well, that was easier than I expected. That said, I like to play my games windowed these days, so I hit F4 (which was the standard key for this back then for some reason, except when it was alt-enter, ctrl-shift-f, or F11) and…

This game runs in 65536 color mode. You must switch the desktop to this mode before playing the game.

Oh. Well, that’s a problem. Does my current setup even support 16-bit colour mode on the desktop? It’s doing fine in full screen exclusive mode, but the other stuff I’m running might not take kindly to having the majority of its colour space taken away.

That was my immediate thought, anyway. Then I remembered that DxWnd exists. I haven’t had a lot of luck with it in the past, but it turns out that Heroes 3 is just undemanding enough that it wraps it up in a nice little window, no problem.

Then I scale the window up to 1200×900, disable the Windows cursor and off it goes!

Just look at that dragon. You only wish you looked this good.

That should have been it, but there was one more wrinkle. I load up a scenario, play my first turn, all goes well, but then it complains that it “can’t create save AUTOSAVE.CGM”. That’s not good. These games can run kind of long and I’m going to have problems if I can’t save.

This turned out to be because I hadn’t run the installer. Who could ever have thought that’d come back to bite me? Normally an installer does all sorts of nice things like creating the directory the save files will live in, and it’s unhappy because the place it wants to put its saves doesn’t exist.

So I go digging around to find out where saves are supposed to live. Fifteen minutes with DDG later, I find my way to a thread on the GOG forums in which someone else asked the same thing for a different reason. Seems it’s just a subdirectory inside the game’s main install directory (pretty common in 1999) called… “games”? I can sort of see it, but why games rather than saves?

Doesn’t matter. I create that and off we go, saves work just fine! Everything now works and I can get a game of Heroes 3 going!

…well, that was exhausting. I think I’m going to unwind with Minecraft a bit and come back to this later.

Categories
Meta

Hello world!

Wow, I have a blog? When did that happen? Who is responsible for this travesty?