Posts
-
Advent of Code 2019 in 110 ms: optimizing Intcode
Read moreI realize that throughout the previous posts I promised to get back to performance optimization for the Intcode engine, but never did. This is mostly due to how these optimizations are very language- and implementation specific, which didn’t fit well with the algorithmic focus of the rest of the series. But in the interest of completeness, I’ll go through that here.
-
Advent of Code 2019 in 110 ms: day 3 revisited
Read moreAfter I posted this series to the Advent of Code subreddit, Reddit user askalski - who has previously posted optimized solutions in C and C++, and was one of my inspirations for doing the same - suggested a better solution for day 3: processing the wires as line segments instead of point sets. This reduces runtime by 99.9%, down to 28 μs.
-
Advent of Code 2019 in 130 ms: closing thoughts
Read moreAnd so this series of posts comes to a close. I hope I was able to help you learn something - I certainly did while developing these solutions. Even writing these posts, as I went through the solutions again I found an additional 34 ms of time save even after I’d decided that 164 ms was a good enough time to settle on.
-
Advent of Code 2019 in 130 ms: day 25
Read moreDay 25: Cryostasis
The final challenge is a text-based adventure game in Intcode, and much like previous Intcode challenges benefits a lot from minimizing the amount of Intcode you need to run. My solution runs in 5.7 ms, using an initial depth-first search phase and then making use of Gray code to minimize the number of inventory changes while cracking the combination for the lock.
-
Advent of Code 2019 in 130 ms: day 24
Read moreDay 24: Planet of Discord
Day 24 is a variant of Conway’s game of life. My solution runs in 2.6 ms and gains its performance from efficient data structures, including a custom bit field representation of Boolean matrices similar to the key sets in day 18.
-
Advent of Code 2019 in 130 ms: days 20 - 23
Read moreDay 20: Donut Maze
Day 20 is a maze problem similar to day 18. My solution runs in 11 ms and uses the same performance tricks. The only real difference is in the rules for generating new states, and that this solution doesn’t use custom duplication keys since the keys for the hash set of visited locations are already quite small.
-
Advent of Code 2019 in 130 ms: day 19
Read moreDay 19: Tractor Beam
Day 19 is another Intcode challenge, and in terms of performance optimization it is much like day 15 in that the focus is on minimizing the number of calls to the Intcode program. My solution uses linear approximation followed by binary search, and runs in 1.3 ms.
-
Advent of Code 2019 in 130 ms: day 18
Read moreDay 18: Many-Worlds Interpretation
Challenge 18 also took quite a bit of effort to optimize. Basically, it’s a maze optimization problem, but with the added twist that you need to collect keys to open doors, and in part 2 you’re exploring 4 partitions of the map in parallel.
-
Advent of Code 2019 in 130 ms: day 17
Read moreDay 17: Set and Forget
Day 17 is an interesting exercise in sequence compression, but the runtime optimization of my solution, running in 1.9 ms, is more about implementation efficiency and a fast Intcode engine than about algorithmic sophistication.
-
Advent of Code 2019 in 130 ms: day 16
Read moreDay 16: Flawed Frequency Transmission
Challenge 16 is probably the one I’ve spent the most time on optimizing, but my solution still takes 8.6 ms to run. There’s quite a lot to unpack here, so this one gets a whole post of its own!
-
Advent of Code 2019 in 130 ms: days 11 - 15
Read moreDay 11: Space Police
Day 11 is again mostly about running an Intcode program. My solution runs in 2.2 ms and doesn’t do anything special.
-
Advent of Code 2019 in 130 ms: days 6 - 10
Read moreDay 6: Universal Orbit Map
Challenge 6 is about constructing and then traversing a tree. My solution runs in 260 μs.
-
Advent of Code 2019 in 130 ms: days 1 - 5
Read moreDay 1: The Tyranny of the Rocket Equation
The first challenge was, as usual, the simplest, and has the shortest runtime by far: 2 μs. There’s not much to say about my solution - the performance is all thanks to Rust’s very efficient standard library. Since it’s already so much faster than all the other solutions, I didn’t really bother optimizing it further.
-
Advent of Code 2019 in 130 ms: introduction
Read moreLast year I decided to solve Advent of Code in Rust, because it’s a very interesting language I would like to learn better. As Rust claims to be “blazingly fast and memory-efficient”, this choice of course got me thinking more about performance than I usually do when solving Advent of Code problems. Previously I’ve solved Advent of Code in Scala and Clojure, and while I did make an effort for my solutions to be fast enough to not be annoying, I was generally happy if I got them down to about a second or less per problem. But I have seen some other people showing off highly optimized solutions, so this time, armed with the power of a modern language designed for extreme performance and zero-cost abstractions, I wanted to see how low I could go.
-
The design of the "Devious Digital Device" for Midnight Sun CTF 2019
Read moreAfter last year’s success, Calle asked me to again make a low-level logic circuit challenge for this year’s Midnight Sun CTF, and so this post will cover the “Devious Digital Device” challenge featured in Midnight Sun CTF 2019. I’ll start with a description of the board and how to solve the challenge, and then step back and walk through the design and development process.
-
PicoCTF 2018 writeup: A Simple Question
Read moreHere’s a walkthrough of my approximate solution path for the problem “A Simple Question” in PicoCTF 2018. This was a fun problem about nontrivial but not particularly advanced SQL injection. There are probably many other good resources on better techniques than those presented here - I am not an avid CTF player, only dabbling in it a little from time to time - but I hope this can serve as a guide for taking the first steps beyond the bare basics of SQL injection.
-
Build log: The "Crazy Circuit Conundrum" for Midnight Sun CTF
Read moreMy friend Calle Svensson (@ZetaTwo) recently arranged the Midnight Sun CTF, and wanted to include a challenge about reverse-engineering a custom low-level logic circuit. He asked me to help, since I have tinkered with just that a bunch lately, and I was very happy to. The result of this became the “Crazy Circuit Conundrum” challenge, and in this post I’ll tell the story of this challenge came to be. This obviously included a bunch of soldering and PCB design, but also some brief Boolean logic reasoning and algorithm design, and of course some mistakes.
-
This UUID is mine
Read moreI, Emil Lundberg, hereby at the time 2017-05-15T12:57:11+02:00 claim this UUID as an identifier for my person:
-
Musings on data, formats and types
Read moreLately I’ve been attending a study group on learning the Clojure programming language, and with me being a firm believer in statically typed languages there have of course been some discussions of the virtues of statically versus dynamically typed languages. Thinking of it on my way home tonight, I came to think that perhaps it’s not really that much about static versus dynamic types, but rather about documenting the format of data. I would like to expand on this topic in this post.
-
Would you ask a man that question?
Read moreConsider this scenario: You’re interviewing a man about his hobby building robots. Would you in this interview ask him a question like “What do you think is your sexiest quality?”
-
Project Fulla: Crypto utility USB key - Part 3: Automation
Read moreIn the last few posts I’ve shown how to make a USB key for use as an encrypted gateway to unlocking and booting a Linux system. While the setup works, there are a few steps left that could be automated. Wouldn’t it be nice to have everything set up to just update itself without manual intervention on every kernel update?
-
Project Fulla: Crypto utility USB key - Part 2: Crypto setup
Read moreIn the last post I showed how to set up an encrypted - including
/boot- Arch Linux system on a USB drive. In this post I will show how to also set up this same USB drive for use as a “keyring” holding detached LUKS headers and boot files for other machines. -
Project Fulla: Crypto utility USB key - Part 1: Preparation
Read moreFor the last couple of years, I’ve carried a couple of USB drives with me: one with a LUKS encrypted volume holding GPG keys, an Arch Linux LiveUSB system and some other useful things, and one holding the
/bootpartition and LUKS header for decrypting and booting up my laptop. I’ve been meaning to merge the two into one, and finally got around to doing it. This post is the first in a series of three where I will lay out what I wanted to do, and how I did it. -
How to load styles from NPM modules using Webpack
Read moreI spent some time figuring out how to load Bootstrap styles from
node_modulesin a Webpack build, so here’s how I finally got it to work. The demo project used here is available on GitHub with a step-by-step walkthrough of the changes. -
Stegosaurus: Stupid simple steganography
Read moreToday I managed to nerd snipe myself with steganography, so I threw a little webapp together that wraps
steghidewith a Node.js HTTP server. It’s just a simple proof of concept, so don’t use it for anything actually important.
subscribe via RSS