DEV Community: Christopher Kruse

Running Rust on AWS Lambda on ARM64

Christopher Kruse — Wed, 06 Oct 2021 23:31:14 +0000

TL;DR: Rust on ARM64 Lambda: check out my example repo

I've been a hobbyist Rust developer for a while now, playing with random tools and mostly having false starts on projects that I'd like to build, but then the energy to do so wanes before I can complete them. Because of that, I always look for new applications for Rust to fit somewhere in my day-to-day, so that I can give myself some practice.

I also work very closely with AWS Serverless tooling in my daily work at Stedi. Recently, AWS posted an update to the Lambda service that they were providing Graviton2-based Lambda functions as part of the service, and I immediately thought to myself, "How would I do a Rust lambda that way?"

Lambda gives you the ability to create a "Custom" runtime - all you need to do is provide a executable that acts as a bootstrap for running the function (aptly named "bootstrap" in the runtime code). By building that as a rust binary with the correct architecture, we can run Rust code natively on the Lambda!

Project Setup

I started with a vanilla cargo project, and added the following into the cargo.toml:

[[bin]]
name = "bootstrap"
path = "src/main.rs"

[dependencies]
lambda_runtime = "^0.4"
tokio = "^1"
serde = { version = "^1", features = ["derive"] }
serde_json = "^1"

The [[bin]] section allows us to specify the binary filename for what's built (and saves us renaming the file after compilation). The dependencies are all references and dependencies of the AWS Rust runtime crates - that's where the code for the function we'll be using is pulled from.

we just have one file in the source directory, at src/main.rs:

use lambda_runtime::{handler_fn, Context, Error};
use serde_json::{json, Value};

#[tokio::main]
async fn main() -> Result<(), Error> {
    let funct = handler_fn(func);
    lambda_runtime::run(funct).await?;
    Ok(())
}

async fn func(event: Value, _: Context) -> Result<Value, Error> {
    let first_name = event["firstName"].as_str().unwrap_or("world");
    Ok(json!({"message": format!("Hello, {}!", first_name)}))
}

For those less savvy with Rust code, this defines the 'bootstrap' runtime under main(), and calls the async function func() to act as the lambda function body. Our function responds with a message of "Hello, World!" in a JSON response by default, or can respond with a specific greeting when passed a "firstName" JSON value as part of its input.

Now, you could build this locally, but because of the way that the lambda function is called, local runs will panic:

± cargo run
    Finished dev [unoptimized + debuginfo] target(s) in 0.39s
     Running `target/debug/bootstrap`
thread 'main' panicked at 'Missing AWS_LAMBDA_RUNTIME_API env var: NotPresent', /home/ckruse/.asdf/installs/rust/stable/registry/src/github.com-1ecc6299db9ec823/lambda_runtime-0.4.1/src/lib.rs:57:58

The immediate goal here is to run it in lambda, and not locally, so we'll save testing it out on our own for a later time.

Cross-Compiling

The example that is provided in the AWS Rust runtime repository shows them using a custom linker and rustup target in order to cross-compile for x86-based lambdas. I attempted to dive into how to get a arm64-based linker, but in the process of trying to figure out how to get that linker installed locally (no convenient packages for Ubuntu, sorry), I stumbled across a project that provides cross-compilation tooling for various platforms via Docker. That made my life a lot easier - Using the rust-musl-cross Docker container, all I have to do is wrap the call to cargo build, and it builds for the proper architecture:

#!/bin/sh

build_arch=aarch64-musl

docker run --rm -it -v "$(pwd)":/home/rust/src messense/rust-musl-cross:$build_arch $@

Armed with that (pardon the pun), I can now call ./musl-build cargo build --release, and I get a resulting binary at target/aarch64-unknown-linux-musl/release/bootstrap.

The final step, as called out in the AWS Rust runtime docs, is to bundle that executable up in a Zip file, so that the Lambda service can construct what it needs to on its side. I've made the package.sh file in the repo to handle that and act as a basic build script (I'll probably convert this to a Makefile later when feeling energetic):

#!/bin/sh

mkdir -p dist

if [ ! -d target/aarch64-unknown-linux-musl ]; then
  ./musl-build cargo build --release
fi

# TODO: use vars for arch folder and binary name
cp target/aarch64-unknown-linux-musl/release/bootstrap dist/
cd dist && zip package.zip bootstrap && cd ..

Now, after running that command, I can grab the file at dist/package.zip and go take that to AWS Lambda to run:

With no arguments provided:

With a name provided:

{
  "firstName": "Christopher"
}

Conclusion

I hope you can use this to make a running start building out lambda function code on the new Graviton2-based Lambda runners. Let me know if this helped you out!

Share your favorite reads!

Christopher Kruse — Tue, 25 Jun 2019 23:25:49 +0000

As we go through time, learning and growing our software craft, there are often pieces that catch and become indelibly marked in our minds as pivotal. I hesitate to use the word "game-changer", but the effect is the same - after reading it, you are forever altered in your way of thinking.

I'd love to share a couple of mine that I've encountered, and reference and re-reference to friends and colleagues frequently. These are blog posts that I hope never see removed from the Internet:

_why's Poignant Guide to Ruby:

https://poignant.guide/

I caught this when it was more-or-less originally published, and it sparked my love of programming in a way that was literate. Putting focus on understanding how to write code in a way that made sense to humans, but could also be parsed my machines, was the jump I needed to realize I could do this as a lifetime pursuit.

Execution in the Kingdom of Nouns:

https://steve-yegge.blogspot.com/2006/03/execution-in-kingdom-of-nouns.html

I played around with looking at other ways of writing code outside of OOP (Scala, Lisps, Haskell), but it never really clicked until seeing it presented as Steve presents it here. Obviously it demonizes OOP a little bit, but in the effort to show that there's a better way that exists.

Learn ViM for the last time:

https://danielmiessler.com/study/vim/

Apparently I understand things better when you give me examples in terms of 'verbs' and 'nouns'. :)

Daniel's vim tutorial helped me to finally get out of a spiral of "try to learn vim, put it down, come back in x months, repeat". Once I had the understanding of the commands I entered into the editor were speaking a language that was actively interpreted by vim, it made my familiarity with the editor skyrocket, and made me feel much more comfortable in vim as well.

Even though I no longer use vim directly (I keep my vim config up to date at times, but I've moved to Emacs with the evil package), I'll always send someone learning vim to this page, to help enlighten them.

New Programming Jargon (from StackOverflow):

https://blog.codinghorror.com/new-programming-jargon/

I've had tons of times where I've used one of these terms, and have been met with a look like this:

I then promptly send them to this post, laughs are had, and all is made clear. I'm sure I'll use "Yoda conditions", "Pokemon Exception Handling", and "Smurf naming" for the forseeable future. :)

Clojure for the Brave and True:

https://www.braveclojure.com/clojure-for-the-brave-and-true/

Daniel's introductory book on Clojure bridged a lot of gaps for me when trying to learn the language. The humor reminded me a lot of _why's Poignant Guide, and put the 'fun' in thinking 'functionally'.

Please share some of your blog posts or vignettes that have changed your way of thinking around programming! Looking forward to adding more to my list. :D

Finding my Loaf of Bread

Christopher Kruse — Tue, 07 May 2019 00:00:00 +0000

I made my first loaf of bread last Saturday.

I've been watching a lot of "The Great British Bakeoff" (or "Baking Show" if you're in the US, because of trademark reasons). Watching people on your television make intricate, creative, and most importantly delicious-looking baked goods, the desire to try it yourself becomes irresistable. Both my wife and I have tried some things we've seen on the show, to decent result. However, I've never really been a "Baker" - I've generally avoided the big hot box that sits underneath the stove, and would tell people that me and that box didn't really get along well.

Despite this, the drive to try it out was too much to handle. I made use of the fact that my wife was out of town this past weekend to give me some buffer time: if things turned out well, I'd have a nice surprise for her when she returned; if I screwed up things or made a complete mess of the kitchen, I'd have time to destroy the evidence. :D

My project took about 3 hours from start to finish; I began later than I really should have (around 8pm), but since I wasn't disturbing anyone by my late-night "breadscapade", I kept at it. I won't go into too much of the process, as photos can provide more insight here:

The dough sat for about an hour to rise:

After rising, the recipe I was following directed me to braid 3 strands of the loaf together:

Then, after an egg wash, it was in the oven for a half-hour. The end result:

Needless to say, I'm happy with how everything turned out.

Now, this is being posted on dev.to, so what does any of this have to do with programming?

Reflecting on the process I had doing the above: the timeframe it took, the level of familiarity, determining what I could take away from the experience for next time - I began to wonder what my programming "Loaf of bread" is. Reviewing the criteria I had:

took about 3 hours start-to-finish
dealt with something unfamiliar
a safe way to clean up the mess in case it failed
the ability to chronicle the process
I can share it with others if it turns out well
I should have fun doing it

For me, the hardest thing in converting this metaphor to programming is the time slot. Learning something new in the programming world (new language/framework/technique/etc.) takes a signifigantly longer amount of time, and I'm generally the type to read through and find tutorials and materials to get a sufficient level of understanding before trying to crank something out on my own. Taking only a 3h timeslot and trying to do learn something meaningful in a new language seems impossible to fit. Maybe I need to expand the time. I could reduce the scope on what I'm learning, but then I feel like I don't capture enough to make what I've learned meaningful with just a tiny piece. This is my normal problem with katas - I can figure out how to solve the problem, but it feels external to how you would deal with a "real problem" in that language.

I also struggle with a aversion to failure - that's why I had to make sure I had time alone to try the bread, and have sufficient time in case of disaster. I struggle with wanting to do cool things, but not wanting to mess up things in the process. Even though I consciously know that no software project ever works this way, I subconsiously want the thing I build to have a well-thought-out design, and be more-or-less right the first time. Software has the remarkable ability to evolve; I just need to learn to embrace it. With the bread, if I screwed it up I could toss it out, and nobody would know.

I'm working on ways to handle tracking progress when building something new. I'm usually willing to post in-progress things up on Twitter or the Fediverse, and used some free time on the weekend to set up everything I needed to run livecoding sessions on Twitch. However, there's a big jump between preparing to do that, and actually pulling the trigger.

An example: I've got a project that I've had for a year that I have started a number of times, but never actually created anything meaningful on. In the latest incantation, I was working on it using Elixir (my language to learn for the year, which I'm doing a bad job of considering it's almost half-over). Once I had my livestream stuff set up, I became terribly nervous - I don't know this language, so the majority of the stream is just going to be me reading through docs, which won't be terribly interesting. I over-indexed on this, and then ended up deciding to just move on to the next household project instead of working on it.

I'm inside my head a lot here - In my case, I wouldn't have anyone watching to begin with, so streaming out to the void and reading docs may have been okay. And hey, maybe someone jumping in could assist.

I'd be interested to hear any of your coding "loaves of bread". What kind of projects do you use for trying things out? Is it worth doing a bigger-scope, longer-term thing to build up knowledge? Should I alter my scope of what I consider a "real problem" for a language, so that I can just do?

Making the Shell Less Scary - Starting out

Christopher Kruse — Sun, 31 Mar 2019 00:00:00 +0000

I will fully admit that I grew up comfortable working on a computer without a GUI. From my early days, I had an old computer that I mainly used to play games (some things never change, but current ones don't come on 5 1/4" floppies); in order to get those games to run, I learned from my Mom how to access the correct drive, and the commands to run in order to start up the game.

Today, even though we have fancy GUI apps to do a lot of the work that we need to get done on a daily basis, I still find that it's easier for me to quickly open a terminal window, enter a few commands, and complete whatever task I was doing. Not everything benefits from this approach (imagine doing image editing with a text editor!), but tasks involving finding files, moving files around the system, and working on remote systems works are things that I would much prefer a terminal for.

Today I'm going to dive into a few of the commands that do just the things that I was talking about. These are some of the commands that you would end up using on a day-to-day basis in a terminal window; hopefully I can shine some light on some corners of them that you don't expect.

Directories and Files

Let's say you're an avid photographer - you'll have a lot of photos collected. In order to make sense of your collection, you're going to want to organize those photos. If they were physical photos, you'd want to collect them by the event that you took them at:

Tim's birthday party
Joe's wedding
Vacation photos from Las Vegas
random photos of food
far too many cat pictures
etc.

Additionally, let's say these photos happened over the course of a few years.

Borrowing from the physical realm, we can place these photos into different folders, or directories, in order to keep them organized. Let's lay them out like so:

2018
- Joe's Wedding
- I <3 Food
- My Cat
2019
- Tim's Bday Bash
- Vegas trip
- My Cat
- I <3 Food

You'll notice there are duplicate names here - that's okay, because they're nested within two different folders.

Now, all of these folder names are legit as they stand, but they'll be a little harder to deal with when on the command line with some of the special characters and spaces. It's a standard convention to replace spaces and special characters in names to make it easy to deal with, while retaining most of the meaning that was present in the original names; most of the replacements are things like dashes or underscores. This would be my likely replacement:

2018
- joe-wedding
- i-heart-food
- my-cat
2019
- tim-bday-bash
- vegas-trip
- my-cat
- i-heart-food

Syntactically very similar, and much easier to deal with while typing.

So rather than pulling up a file manager window, let's make this structure out of commands at a terminal.

`mkdir` makes the dirs

the mkdir command is used to make a directory. The basic invocation is very straightforward:

$ mkdir <folder-name>

This command will create a new directory with the given name based on the directory you're currently in (referred to as your 'Current Working Directory' or 'Present Working Directory'). Sometimes the terminal you're using will tell you where you are as part of the prompt; even if not, you can find out by running the command pwd to give you that directory.

$ pwd
/home/ballpointcarrot

So let's make our photo collection structure:

$ mkdir 2018

Wait... Nothing came back. Did it do anything?

add `ls` to the list

ls is a versatile command - it gives you a listing of your PWD. This becomes handy when you're looking around you filesystem, and generally know where something is located. If we do an ls where we are now, you'll see something like:

$ ls
2018/   Desktop/        Downloads/      Notes/          Videos/
Books/  Documents/      Music/          Photos/

Oops... that 2018 isn't in the right spot. Let's move it with mv:

$ mv 2018 Photos

Again, we get no output signifying anything. However, on the next ls:

$ ls
Books/          Documents/      Music/  Photos/
Desktop/        Downloads/      Notes/  Videos/

Now we can see that the 2018 folder is no longer here. We want to make sure that it's in the Photos directory though, so we'll check there, too:

Note: this shows that the ls command can be used on folders - meaning you don't have to be in the folder to use ls. That gets handy when you're searching a lot of subfolders.

$ ls Photos
10262018_0001.JPG  10262018_0035.JPG  10262018_0069.JPG  10262018_0103.JPG  10262018_0137.JPG  10262018_0171.JPG  10262018_0205.JPG  10262018_0239.JPG  10262018_0273.JPG  10262018_0307.JPG
10262018_0002.JPG  10262018_0036.JPG  10262018_0070.JPG  10262018_0104.JPG  10262018_0138.JPG  10262018_0172.JPG  10262018_0206.JPG  10262018_0240.JPG  10262018_0274.JPG  10262018_0308.JPG
10262018_0003.JPG  10262018_0037.JPG  10262018_0071.JPG  10262018_0105.JPG  10262018_0139.JPG  10262018_0173.JPG  10262018_0207.JPG  10262018_0241.JPG  10262018_0275.JPG  10262018_0309.JPG
10262018_0004.JPG  10262018_0038.JPG  10262018_0072.JPG  10262018_0106.JPG  10262018_0140.JPG  10262018_0174.JPG  10262018_0208.JPG  10262018_0242.JPG  10262018_0276.JPG  10262018_0310.JPG
...

Whoa! Where's the 2018 folder? These are all just JPG files (the photos that I've been dumping without organizing into the Photos folder). Fortunately, I can filter out the type of object returned from ls:

$ ls -d */
2018//

There's our folder. Now let's explain that command: the -d within the command tells ls that we just want directories, and not files. However, ls isn't smart enough on its own to just grab the directories on its own; we have to explicitly say grab "all directories", which is where */ comes in - it signifies "anything in the current directory" with the asterisk (also called a star or wildcard), and the forward slash is for anything designated a folder.

Let's get to work on the rest of those folders. First, let's put ourselves in the right place.

`cd` - not just for music

The cd command changes our current working directory. By changing directories, it gives us the ability to change context with what we're doing on the filesystem. In our case, we'll change to the Photos directory, because we're working in the context of organizing our Photos. Makes sense.

$ cd Photos

Again, the command has now output, but we can do a pwd and see that we've changed places:

$ pwd
/home/ballpointcarrot/Photos

Now let's finish up our 2018 folders. Me, being lazy, want to do everything in one shot - fortunately, mkdir lets us do just that:

$ mkdir 2018/joe-wedding 2018/i-heart-food 2018/my-cat

This creates three folders, all nested neatly under the 2018 folder. "Great!", we say, and we go to do 2019:

$ mkdir 2019/tim-bday-bash 2019/vegas-trip 2019/my-cat 2019/i-heart-food
mkdir: cannot create directory ‘2019/tim-bday-bash’: No such file or directory
mkdir: cannot create directory ‘2019/vegas-trip’: No such file or directory
mkdir: cannot create directory ‘2019/my-cat’: No such file or directory
mkdir: cannot create directory ‘2019/i-heart-food’: No such file or directory

Uh oh... because we never created the parent 2019 folder, it's not allowing us to build the rest of the directories. We can outwit it though; mkdir has a parameter option -p, which gives us the ability to make parent directories within the same call:

$ mkdir -p 2019/tim-bday-bash 2019/vegas-trip 2019/my-cat 2019/i-heart-food

All good. Just to double-check:

$ ls 2019
tim-bday-bash/  vegas-trip/     my-cat/         i-heart-food/

Moving the files in

So now we've got our directory structure in the Photos directory, with a boatload of random JPG files. How are we going to get them organized? It looks like a lot of them are around the same dates (look at all the 10262018_xxxx files we have up there). Let's take a look at one or two of them to get a sample, to make sure it's the right event.

Note: This step will be different depending on the platform you're on, so I'll give both.

# OSX example
$ open 10262018_0001.JPG

# Linux example
$ xdg-open 10262018_0001.JPG

Both of these commands do the same thing - they ask the current environment to figure out who the best person to open a JPG file is, and then executes that program. Ideally, you'll see a window with your picture loaded.

Oh look, it's a cat photo. We know where those are supposed to go. I'm going to assume the 300+ photos around this time period are all cat photos (don't judge). We're going go go back to using the mv command. However, instead of individually moving the files one-by-one (which would take forever), we'll make use of our friend the wildcard, and make all of the files move on their own:

$ mv 10262018_* 2018/my-cat

Again, we get nothing back as output, so let's double-check:

$ ls 2018/my-cat
10262018_0001.JPG  10262018_0035.JPG  10262018_0069.JPG  10262018_0103.JPG  10262018_0137.JPG  10262018_0171.JPG  10262018_0205.JPG  10262018_0239.JPG  10262018_0273.JPG  10262018_0307.JPG
10262018_0002.JPG  10262018_0036.JPG  10262018_0070.JPG  10262018_0104.JPG  10262018_0138.JPG  10262018_0172.JPG  10262018_0206.JPG  10262018_0240.JPG  10262018_0274.JPG  10262018_0308.JPG
10262018_0003.JPG  10262018_0037.JPG  10262018_0071.JPG  10262018_0105.JPG  10262018_0139.JPG  10262018_0173.JPG  10262018_0207.JPG  10262018_0241.JPG  10262018_0275.JPG  10262018_0309.JPG
10262018_0004.JPG  10262018_0038.JPG  10262018_0072.JPG  10262018_0106.JPG  10262018_0140.JPG  10262018_0174.JPG  10262018_0208.JPG  10262018_0242.JPG  10262018_0276.JPG  10262018_0310.JPG
...

Great - all our cat photos are now pleasantly sorted.

I'll leave us here for now. I want to make this a continuing series of posts, so please let me know if there's a command that you're interested in. I know that this one may be a little too basic for a lot of dev-types, but hey - everyone has to start somewhere, right? As long as someone makes use of it, I'm happy.

Maintaining Motivation

Christopher Kruse — Tue, 19 Feb 2019 17:08:57 +0000

I've been facing an uphill battle to keep motivation and interest in my day-to-day. My office project has been a bit of a slog to get launched, and by the end of the day, I don't have the drive to come home and try to play with things at home.

How are people combating scenarios like this, and what things do you do to keep excited / refreshed about the things you're working on?

Advent of Code 2018 - Day 3

Christopher Kruse — Mon, 03 Dec 2018 00:00:00 +0000

Solving these problems has been more difficult than I originally imagined - these aren't your FizzBuzz-level problems; they're asking for a little bit more (especially the second halves). I got a little bit of a head start on day three, as I'm three hours behind the release of the problems, and that means I get to have some time before bed to think about them. This proved bad, as I was laying in bed thinking about solving things (which makes sleeping nigh impossible :D).

On this particular night/day, I had some issues with work (and I was on-call for my team at the time), so I got a second chance to look at them early in the morning (3am-ish local time). But, once I was up, I was up, so once the work problem subsided, I took a crack at getting the rest of the problem solved.

This is my first of these writeups to take place after-the-fact, so let me know if there's any issues with how it was covered here vs. the previous days.

Day 3, Part 1

After we saved the cloth from the previous problem, it's now up to the Elves to figure out how to cut it optimally. The problem statement makes the first assertion that the fabric is a square of 1000x1000 square inches. This proved useful to my method of solving the problem, as you'll see below.

Each elf makes a claim on the fabric to designate a rectangle they want to cut. The claims have the following format:

#12 @ 3,4: 5x6

Which is to be interpreted as "Claim number 12, with the top corner location of (x,y) = (3,4), has a width of 5 and a height of 6."

To make sense of this, I used a regular expression to isolate the various numerical terms (while regex is a superpower, it is also a bit of a rabbit-hole, and I won't cover its general concepts here). Unfortunately, while Java 7+ has support for a regex feature called named capture groups, Clojure does not have that support out of the box. However, the regex with the named groups still functions, but I can only get positional arguments. I built out a function that took an input claim, and built out a rather interesting set of responses:

(defrecord Claim [claim-number squares])

(defn convert-to-grid
  "Converts a claim into a sequence of 'taken' squares."
  [claim grid-width]
  ;; Named groups would be great here, but Clojure doesn't support this natively.
  (let [matcher #"#(?<claim>\d+)\s@\s(?<x>\d+),(?<y>\d+):\s(?<width>\d+)x(?<height>\d+)$"
        matches (re-find matcher claim)
        [_ claim horiz vert width height] matches
        x (Integer. horiz)
        y (Integer. vert)
        w (Integer. width)
        h (Integer. height)
        rows (take h (iterate inc y))]
    (->> (map #(range (+ x (* grid-width %)) (+ (+ x w) (* grid-width %))) rows)
         (flatten)
         (set)
         (Claim. (Integer. claim) ))))

Let's walk through this example a little.

The first thing we see is the definition of a clojure record (similar to a struct). Because Clojure lives on the JVM, this builds out effectively a Java class and allows you to instantiate objects of that type. The problem above could have been solved with a simple map, but I wanted to give readers of the codebase an easier way to have a mental model of the transformed claim. Additionally, this helps us keep track of the claim number, which is not important in Part 1, but makes a re-appearance in Part 2.

Because we know the width of the field we'll be working with in units, I made a choice to build out the "rectangle" that a claim represented by identifying the cells that the rectangle makes up. For example, in a 5x5 grid, with a claim of #1 @ 2,0: 3x3:

This leaves us with a set of squares: #{2 3 4 7 8 9 12 13 14}. The practical upshot here is now we can use set logic (difference, intersection, union) to manipulate the rectangles and calculate our details for overlaps. And that's just what I did:

(defn get-overlap
  "returns the amount of overlap based on calculated inputs.
   Answer provided in square units matching the units entered
   (for the case of the problem, square inches)."
  [claims]
  ;; Perform intersection to find any matches, then union to combine; repeat through the list.
  (loop [mapped-area (map #(convert-to-grid % 1000) claims)
         shared-fabric #{}
         intersections #{}]
    (if (empty? mapped-area)
      intersections
      (let [intersect (set/intersection shared-fabric (:squares (first mapped-area)))
            union (set/union shared-fabric (:squares (first mapped-area)))]
        (recur (rest mapped-area) union (set/union intersections intersect))))))

Again we see our friends loop and recur from Day 2. This section highlights one of my favorite things about Clojure - maniuplating data in bulk. We pass into this a vector of claim strings, that are parsed in the function above it. In just one map call, however, we were able to convert each of those strings into a grid area 1000x1000 wide. Once we have objects we can compute easily against, we go about calculating. :)

The set/intersection notation is new to these examples, because clojure.set is outside of Clojure's "Core" namespace - up until now we've been using functions packaged in clojure.core, which is loaded by default for a Clojure runtime. Since clojure.set isn't, we have to import it into the namespace (and in our case, provide it a nice short name to use when calling):

(ns aoc.aoc3
  (:require [clojure.set :as set]))

This allows us to call functions in clojure.set by using set/fn-name. For each iteration of the loop, we do three things:

We check against the "shared fabric". This is done by doing a set intersection between the current rectangle (defined by (first mapped-area)) and all of the rectangles that came before it.
We define the "shared fabric" by adding the current rectangle to the rectangles that have already been added by a set union.
When we cut back into the next iteration, we take the union of all found intersections in previous iterations, and the intersections we've found in this run. This piece is what gives us our total overlap at the end, as we're constantly accumulating more overlap; because it's a set, however, we're not recounting the same values, we're just including them as "overlapped" already.

Once this was done, I was able to solve Part 1 quickly.

Day 3, Part 2 (Sports Team: 0)

Now that we've found the overlapping area, our challenge is to find the rectangle which does not have any overlapping area within the list of claims. This is where keeping that claim number comes in handy.

I wanted to come up with a clever way of using the set notation used above to make a lightning-quick function for processing the list of rectangles to find one with no overlap, but nothing came to mind. (If anyone finds one, let me know and I'll owe you a coffee.) Instead, I used a little more of a brute force method: compare each grid to the list of grids, and cut out when you find no set intersections. This was a little more computationally intensive (O(n^2)), but given the count limit in the sample input, it wasn't too bad to sit for a few seconds while the laptop pounded it out.

I had one hiccup as I was putting this together - how do I managed the list of claims so that I don't run an intersection with myself? That would cause even the "no overlap" rectangle to match (as it's matching itself). What I ended up doing was breaking out the function that handled the overlapping calculation to have a check at the top that said "if you're the same rectangle by claim number, then return nil" - this allows you to pass the full list and not worry about matching yourself.

(defn overlapping-claim [c1 c2]
  (cond
    (= (:claim-number c1) (:claim-number c2)) nil
    (not-empty (set/intersection (:squares c1) (:squares c2))) c2))

(defn find-no-overlap
  "given a set of input claims, find the claim that has no overlap
  with any other claims."
  [claims]
  (let [grid-claims (map #(convert-to-grid % 1000) claims)]
    (loop [idx 0 ignores #{}]
      (if-not (contains? (:claim-id (nth grid-claims idx)) ignores)
        (if-let [overlap (some #(overlapping-claim (nth grid-claims idx) %) grid-claims)]
          (recur (inc idx) (conj ignores (:claim-number overlap)))
          (:claim-number (nth grid-claims idx)))
        (recur (inc idx) ignores)))))

Cool Clojure-y things to point out here:

cond. Think of cond as a bit of a if/else on steroids. It allows you to pass a pair of items: test expression, and success expression. If the test expression passes (ie, returns true), then the success expression is evaluated and returned (immediately - it does not fall through to other condition pairs). This means I don't have to nest if calls, which makes it easier to read (IMO).
if-let. This is basically a conditional binding (think variable) assignment: if the binding value is not nil, then assign the value that binding for the scope of the if-let. It saves you from the all-too-common pattern of:

# ruby
my_var = doThingPossibly()
if my_var
  # do other things
end

# python
if doExpensiveThing():
    repeatItForVariable = doExpensiveThing()
    # do other things

And again, my code is available in a Github Gist. Until tomorrow!

Advent of Code 2018 - Day 2

Christopher Kruse — Sun, 02 Dec 2018 04:55:32 +0000

Welcome back! Today, we're continuing the Advent of Code challenges. I found these challenges through the awesome people I've found at the dev.to community, which has been embracing these challenges, providing discussion boards, and more.

Day 2, Problem the First

The long-and-short of the second day's problem is thus:

You are given a list of box IDs, which are series of letters. In order to verify the contents of the boxes in total, you count the number of IDs with "exactly two of any letter", and separately count "exactly three of any letter" to make a checksum of the values. Using the example from the problem statement:

For example, if you see the following box IDs:

abcdef contains no letters that appear exactly two or three times.
bababc contains two a and three b, so it counts for both.
abbcde contains two b, but no letter appears exactly three times.
abcccd contains three c, but no letter appears exactly two times.
aabcdd contains two a and two d, but it only counts once.
abcdee contains two e.
ababab contains three a and three b, but it only counts once.

As a result, we have four IDs which contain exactly two repeated letters (2, 3, 5, and 6), and three IDs which contain three repeats (2, 4, 7). If you multiply these values together 4 x 3 = 12, so 12 is your checksum value. You are now asked to calculate the checksum value of the test input.

Not to be bitten by the trouble yesterday, I wanted to set up a full project (with the ability to test). This took a fair bit longer than I had intended, because I rabbit-holed into "how do I get this to provide test results automatically?" (where I spent about 20m), and "Why the hell isn't this test executing correctly?" (which took substantially longer).

Once I finally had my environment up and running correctly, I went about putting some test cases down:

(ns aoc.aoc2-test
  (:require [aoc.aoc2 :as sut]
            [clojure.test :refer [deftest testing is]]))

(deftest aoc2-part1
  (testing "the example statement"
    (let [input ["abcdef" "bababc"
                 "abbcde" "abcccd"
                 "aabcdd" "abcdee"
                 "ababab"]]
      (is (= 12 (sut/checksum input)))))
  (testing "a simple second example"
    (let [input ["abab" "abaa" "aab"
                 "aac" "aaa" "abc"]]
      (is (= 6 (sut/checksum input))))))

This uses the example scenario given in the problem, as well as a small example I cooked up myself. Armed with tests that executed on file save, I was ready to build out the solution.

Once again, this problem lends well to the frequencies function provided by Clojure - it will automatically group the values within the string by how frequent they show up. Since we only care about twos and threes, however, we need to search those results for those values. The reduce function (of "map/reduce" fame) is where we want to be - it gives us an easy way to take a list of things and make a scalar value out of it. In our case, we want to reduce each map to its existence of twos and threes; ideally, {:a 3 :b 1 :c 2} would result in {:threes 1 :twos 1}.

Building out a complicated reduce function generally is painful; because the inner function to a reduce is exactly that (a function), I defined it outside the logic. Because clojure values are generally immutable, I needed an easy way to maintain the state during the loop - transient helped out here, because I treat the map as temporarily mutable, but only within the bounds of the function and the lifetime of the transient binding.

Here's what I ended up with for the part 1 solution:

(ns aoc.aoc2)

(defn reduce-twos-threes
  "check the given frequency map n for twos or threes matches, and update
   the memo map to indicate if the string has a match. Used for a reducer."
  [memo n]
  (let [t-memo (transient memo)]
    (if (some (fn [[k v]] (= v 2)) n) (assoc! t-memo :twos (inc (:twos t-memo))))
    (if (some (fn [[k v]] (= v 3)) n) (assoc! t-memo :threes (inc (:threes t-memo))))
    (persistent! t-memo)))

(defn checksum [input]
  (let [sum-maps (map frequencies input)
        twos-threes (reduce reduce-twos-threes {:twos 0 :threes 0} sum-maps)]
    (* (:twos twos-threes) (:threes twos-threes))))

This makes the checksum function read really straightforward: find the frequencies of each input value, find the numbers of twos and threes (stored in a map), then finally multiply the twos and threes values together.

Day 2 Problem 2 (Electric Boogaloo)

Distilling the problem statement again:

Given your list of IDs, the particular IDs you're searching for differ by just one character; for example, "text" and "tent" fit this requirement, because you only need to replace the "x" and "n" characters. The example given in the problem is this:

abcde
fghij
klmno
pqrst
fguij
axcye
wvxyz

where fghij and fguij are "adjacent" boxes.
Any problem where you're comparing closeness of matching strings screams Levenshtein Distance. The Levenshtein distance of two strings is a measure of the minimum number of changes required to turn one string into another - this is generally counting insertion, deletion, and substitution, but our needs solely require substitution (better known as Hamming Distance - two separate mathematicians studying the same area of string differences. This is done by comparing values in each string, and adding 1 to each difference you encounter - a pretty simple comparison function.

(defn hamming
  "Compute the Hamming Distance between two equal length
   strings."
  [str1 str2]
  (if-not (= (count str1) (count str2))
    (throw (IllegalArgumentException. "Strings must be equal size.")))
  (loop [s1 str1
         s2 str2
         score 0]
    (if (empty? s1)
      score
      (recur (rest s1) (rest s2)
             (+ score (if (= (first s1) (first s2)) 0 1))))))

This uses Clojure's tail-recursive optimizing functions loop and recur to compare the strings one-by-one, and calculate their Hamming distance (we've got a check in there to make sure they're the same length, and throw an error if not).

Once that was complete, I built out a way to sift through the list of boxes to find just the ones with a Hamming distance of 1. This returns a two-item sequence, one for each swap of matching (there's probably an optimization there to not go through the entire list):

(defn find-christmas-boxes [input]
  (keep identity (map (fn [base-str]
                        (let [target-box (filter #(= 1 (hamming % base-str)) input)]
                          (if-not (empty? target-box)
                            [base-str (first target-box)]))) input)))

There's a couple of cool things to point out here. First, the base map function will return a lot of nil (Clojure's null value). In order to get rid of those, we use the identity function (which basically says "return true if truthy"; it's effectively a cleaner (not (nil? thing))). Another thing to point out for non-Clojurists is that shorthand function declaration used in the filter call:

;; These two are equivalent:
#(+ % 3) 

(fn [arg] (+ arg 3))

Finally, the AoC puzzle asks for the common characters between the two strings. This is close to the Hamming Distance function above, but we just need to drop a character if it doesn't match. This got reduced to the following:

(defn remove-uncommon-letter [s1 s2]
  (apply str (keep-indexed #(if (= (get s2 %1) %2) %2) s1)))

;; To execute everything:
;; (apply remove-uncommon-letter (first find-christmas-boxes input))
;; where input is the raw input string from the project.

apply is the cool bit here - using apply allows you to use vector (read: array) entries as arguments to a function:

(let [numbers-to-add [1 2 3 4 5 6]]
 (apply + numbers-to-add)) => 21

And hey - no borrowing from anyone else today, and right before day 3 releases. I'm saving that for tomorrow, though. :D The Github Gist for today's problems is right here.

Advent of Code 2018 - Day 1

Christopher Kruse — Sat, 01 Dec 2018 00:00:00 +0000

Originally posted at https://www.ballpointcarrot.net/posts/advent-of-code-2018-1/ - Also, obligatory "first post" points for being my first dev.to post :D

Spurred on by

a lack of posting in this space,
the chance to show off the new backend/theme to my blog (I did work on this while nobody was looking, and started building an RSS feeed!), and
after finding this Tweet by Ali Spittel,

I decided that doing this "Advent of Code" was something to do. First, it gives me a nice thing to practice on. Second, it gives me a reason to make some frequent posts on here (which, given the year+ lack of content, may not be a bad idea). Finally, it helps me build out some public code, which I've been bad at doing - even if they're solutions to set problems. I'll be using GitHub gists for posting my solutions, and embedding them here.

Problem the First

The first problem is summarized as follows: you're an Elf travelling back in time to fix anomalies in history, in order to "save Christmas". However, in order to get the time travel device working correctly, it first needs calibrated.

Given a series of "frequency changes", like +1 -2 +3 -1, the following changes would occur:

Current frequency 0, change of +1; resulting frequency 1.
Current frequency 1, change of -2; resulting frequency -1.
Current frequency -1, change of +3; resulting frequency 2.
Current frequency 2, change of +1; resulting frequency 3.

This provies a resulting frequency of 3.

With those rules in place, the Advent of Code site has you log in (thanks, Login with Github) and get a link for sample input. The input file was larger than I expected, but the rules simple enough to come up with this small Clojure snippet:

(defn calibrate [input-file]
  (let [raw-input (slurp input-file)
        freqs (map #(Integer. %) (clojure.string/split-lines raw-input))]
    (reduce + freqs)))

The above reads the file into a string (using slurp), then converts each individual number (separated with a newline character) into a Java Integer. Finally, everything is summed up via reduce to get the full set of adjustments for a final frequency.

Problem the Second

Within your input, you now need to keep track of the active value, and look for the first time you encounter the same value twice. Additionally, this means that your list can loop; for example, take the input +3, +3, +4, -2, -4. As you run through this the first time, you generate intermediate values of 3, 6, 10, 8 4, and there are no matches within that set. So, you take the last 4 offset, and start the original list over again, returning 7, 10, .... When you've reached 10 again, you have found your "twice match", and return that value. Now, using the same test input, we get to find the first value we hit twice.

Clojure gets to harness the power of lazy infinite sequences here. Using the clojure cycle function, the list of frequencies gets to be repeated indefinitely. Obviously, we can't eager load a list of infinite values - there's not
enough memory space to do that; what we can do, however, is let that list populate as needed, only providing the next
number until we need it.

I built a function that generates a list of the intermediate points, and loops to find a solution::

(defn frequency-adjustments [freqs]
  (reductions + (cycle freqs)))

(defn calibrate [freqs]
  (loop [n 2]
    (let [steps (take n (frequency-adjustments freqs))
          step-counts (frequencies (rest steps))
          repeats (filter (fn [[k v]] (if (= v 2) k)) step-counts)]
      (if-not (empty? repeats)
        (first (keys repeats))
        (recur (inc n))))))

I was happy with how things looked. I went to a REPL and tested the logic with some of the samples, which seemed to get
the answer I was looking for. frequency-adjustments was nice, actually, because you could see effectively a new list
of how each step processes, which was great for visual analysis. I then fired it off with the test data.

And waited. Quite a while in fact.

Turns out that, when you have a high enough input, trying to build the list over and over again is somewhat taxing on
the system doing that calculation. Obviously, this wasn't the solution I was looking for. At this point, I did a little
bit of cheating (hey, it's the Internet, and I'm not proud) and checked the reddit post where people were posting solutions, and came across a separate Clojure
solution by zqvt (slightly
modified to fit my input parameters below):

(defn calibrate2 [freqs]
  (loop [xs (cycle freqs) seen #{} total 0]
    (if (contains? seen total)
      total
      (recur (rest xs) (conj seen total) (+ total (first xs))))));

This generates a set of values we've come across, as well as keeps a running total of where we're at while we're
generating. The key here that I didn't even think about (let alone thought possible) was the use of rest to generate
further sequences while not including the items processed. That was clever, and this solution very quickly provided a
response.

Lessons learned:

My initial thought was to build a set of values that I'd seen going through the list calculated with reductions, but I really wanted to try something that I could do without maintaining state outside of the loop. That led me down the path of regenerating the list each time, which made it impossible to run effectively. I probably should've gone with that easier thought process, as it would've worked faster (and I would've spent less time on the solution).
Good to be posting stuff again, and practice always helps.
Honesty - it hurt to come clean about looking for solutions, but sometimes you have to suck it up. Also, I felt really dumb after seeing the painful performance of my implementation vs. the one that I found. But I wanted to highlight a successful implementation, both to show that there are good ways to do it, and to give myself something to look forward to improving upon. I'm hoping to not need the crutch next time.