• Advent of Code 2019 in 110 ms: optimizing Intcode

    I 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.

    Read more
  • Advent of Code 2019 in 110 ms: day 3 revisited

    After 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.

    Read more
  • Advent of Code 2019 in 130 ms: closing thoughts

    And 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.

    Read more
  • Advent of Code 2019 in 130 ms: day 25

    Day 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.

    Read more
  • Advent of Code 2019 in 130 ms: day 24

    Day 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.

    Read more
  • Advent of Code 2019 in 130 ms: days 20 - 23

    Day 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.

    Read more
  • Advent of Code 2019 in 130 ms: day 19

    Day 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.

    Read more
  • Advent of Code 2019 in 130 ms: day 18

    Day 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.

    Read more
  • Advent of Code 2019 in 130 ms: day 17

    Day 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.

    Read more
  • Advent of Code 2019 in 130 ms: day 16

    Day 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!

    Read more
  • Advent of Code 2019 in 130 ms: days 11 - 15

    Day 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.

    Read more
  • Advent of Code 2019 in 130 ms: days 6 - 10

    Day 6: Universal Orbit Map

    Challenge 6 is about constructing and then traversing a tree. My solution runs in 260 μs.

    Read more
  • Advent of Code 2019 in 130 ms: days 1 - 5

    Day 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.

    Read more
  • Advent of Code 2019 in 130 ms: introduction

    Last 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.

    Read more
  • The design of the "Devious Digital Device" for Midnight Sun CTF 2019

    After 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.

    Read more
  • PicoCTF 2018 writeup: A Simple Question

    Here’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.

    Read more
  • Build log: The "Crazy Circuit Conundrum" for Midnight Sun CTF

    My 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.

    Read more
  • This UUID is mine

    I, Emil Lundberg, hereby at the time 2017-05-15T12:57:11+02:00 claim this UUID as an identifier for my person:

    Read more
  • Musings on data, formats and types

    Lately 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.

    Read more
  • Would you ask a man that question?

    Consider 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?”

    Read more
  • Project Fulla: Crypto utility USB key - Part 3: Automation

    In 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?

    Read more
  • Project Fulla: Crypto utility USB key - Part 2: Crypto setup

    In 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.

    Read more
  • Project Fulla: Crypto utility USB key - Part 1: Preparation

    For 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 /boot partition 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.

    Read more
  • How to load styles from NPM modules using Webpack

    I spent some time figuring out how to load Bootstrap styles from node_modules in 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.

    Read more
  • Stegosaurus: Stupid simple steganography

    Today I managed to nerd snipe myself with steganography, so I threw a little webapp together that wraps steghide with a Node.js HTTP server. It’s just a simple proof of concept, so don’t use it for anything actually important.

    Read more

subscribe via RSS