Effective TypeScript

Every year I do the Advent of Code in a different programming language. If you aren't familiar, it's an online coding competition with a new two-part problem every day from December 1st to the 25th. Thousands of programmers participate and share their solutions. It's a great way to learn a language and bond over coding. In 2019 I used Python, in 2020 I used Rust and in 2021 I used Go. I also post an increasingly-belated writeup of my experience and impressions of the language so, at the end of April, here's 2022! (As a partial excuse, I have been writing on a very different blog!)

This past December I chose TypeScript, specifically Deno, which brands itself as "a new way to TypeScript". While TypeScript certainly isn't a new language for me, Deno is a new way to use it. I was also curious how JavaScript/TypeScript would do on AoC-style coding competitions and, frankly, I hadn't been doing much coding of late and was keen to have an excuse to use my favorite language more.

This post is broken into three parts: thoughts on Deno, thoughts on TypeScript/JavaScript for coding competitions, and my thoughts on this year's Advent of Code.

My code and more notes on each day's puzzles can be found on GitHub at danvk/aoc2022.

Deno

Deno brands itself as a more secure JavaScript runtime that's more standards-compliant and easier to use. The comparison here is obviously Node.js. Deno was created by Ryan Dahl, who also created Node.js, and it's fair to think of it as a "take two" on Node that avoids some of its questionable decisions.

Overall these claims hold up well. Deno is much easier to set up than Node: it already uses TypeScript, it has a built-in linter and formatter, and it comes with a system for unit tests. These are all things you can set up with Node, but it takes an extra step. That's a hurdle for beginners, and an opportunity for mistakes for all of us. For the most part, writing code in Deno feels just like writing TypeScript in any other environment, only with much less configuration.

(Just like a browser, Deno doesn't run your TypeScript directly. It translates it to JavaScript first using swc and then runs that.)

Deno's sandboxing is a great security feature. Unless you specifically allow a capability (such as reading or writing to the file system), Deno won't allow it. This makes it safer to run programs that you download from the internet. Since I was running mostly my own code for the Advent of Code, in practice this meant that every solution started with this shebang line:

#!/usr/bin/env -S deno run --allow-read --allow-write

Deno tries to embrace web standards to the extent that it makes sense. Rather than using a library to make HTTP requests, you use fetch, just like you would in a web browser. Perhaps the most notable example of this comes with dependencies. Rather than a require statement or running npm install, you depend on third-party libraries by using a standard ES import statement from a URL:

import { assert } from "https://deno.land/std@0.166.0/testing/asserts.ts";

The version goes right there in the import URL. If you're used to npm, you probably have a few objections in your head right now! Rest assured, the Deno folks have thought through them:

• What if someone takes over deno.land and swaps in a malicious version of the library? You can use a lock file for integrity checking.
• Won't this be unwieldy? In practice, the Deno team recommends creating a deps.ts file that consolidates all these imports in one place. This replaces package.json. It's a good example of Deno's preference using JS standards. I have some misgivings about this, though, see below.
• What about dev dependencies? I haven't seen anything written about this explicitly, but I assume the suggestion is to have a dev-deps.ts file or some such.
• Won't this cause an explosion of versions in transitive dependencies?

To see why this might happen, imagine that module A depends on lodash@4.17.20 and module B depends on lodash@4.17.21. With deno imports, you wind up with two versions of lodash:

When you import from a URL that includes the full version, all your (transitive) dependencies are pinned. Node.js avoids this by specifying compatible ranges in dependencies. Perhaps A just requires lodash>=4 and B requires lodash>=4.10. In that case, we can get down to a single version:

The Deno answer to this dilemma is an import map, which lets you reach in and tweak the versions. Again, this is a JavaScript standard, but it feels a bit unwieldy. Would you actually do this to reduce the number of dependencies in your code? And how would you know which versions of lodash a module is compatible with unless it specifies.

I didn't personally run into any issues with this in the Advent of Code since I only had one or two dependencies. But projects I've worked on professionally have had thousands, and I'm nervous about any patterns that would lead to an even greater proliferation of dependencies. If you have experience building larger projects in Deno and have run into this (or not), I'd love to hear about it in the comments.

I also have some concerns about the deps.ts system. It's clever to use a plain old TypeScript file as a package.json replacement in this way. But because it's a TypeScript file, my concern is that you'll be tempted to write real code in it, i.e. logic. Why is this a problem? Just look at the mess that is setup.py in Python land. In general it's impossible to know how a package is configured without executing setup.py, which could cause any number of side effects. This makes analysis harder, for example writing tools like dependabot. Simpler configuration enables more accurate, powerful tools. (Deno 1.31 added support for package.json to ease transitioning from Node but still recommends using import maps.)

While Deno works best when you import other Deno modules (from deno.land), the headline feature of Deno 1.28 was support for npm modules. Here's what this looks like:

import { chalk } from "npm:chalk@5";

Easy, right? But what about TypeScript? Often the type declarations for npm libraries are hosted in a different package via DefinitelyTyped. I struggled mightily to get typings for lodash (see some crazy solutions on Stack Overflow) before asking for help on Twitter. Here's where I wound up:

// @deno-types="npm:@types/lodash"
import {default as ld} from "npm:lodash";
export const _ = ld;

So much for standards! But in fairness to Deno, once I had this magic in place I never had to think about it again.

Another pain point: I ran into several different issues with the VS Code extension, including one that changed my code to give me a wrong answer! To the Deno team's credit, they fixed both issues that I reported quickly, before Christmas. Deno is a relatively new project that is moving fast, but this also means you're more likely to run into glitches like this.

In the end, Deno is pretty nice to work with. If we were starting from scratch, it would be a much better choice than Node.js. But the Node/npm ecosystem has a ten year headstart on Deno, and I'd like to give the npm integration story a bit more time to play out before I commit to using Deno on a larger project.

For a more glowing endorsement of Deno, see A Love Letter to Deno by Alex Kladov.

TypeScript/JavaScript for Coding Competitions

TypeScript is a more natural fit for web programming and servers than for coding competitions, which are more the home turf for Python. So I was curious to see how doing AoC in TypeScript would feel.

JavaScript is famous for its footguns and TypeScript/Deno inherit many of these. One of them got me on the very first problem:

let sums = [2, 1, 10];
sums.sort();
console.log(sums);
// logs [1, 10, 2] -- the sort is lexicographic!

Yes, this is one of many reasons why we always use lodash!

I'd hoped that this year's Advent of Code would force me to play around more with BigInt (for huge numbers) and web workers (for parallelism), but neither of these proved to be necessary this year.

I did make extensive use of ES2015's Set and Map classes. These make amends for the "original sin of JavaScript", namely the conflation of objects and associative arrays. While Set and Map do fix many of the issues with objects (accessing prototype, supporting non-string keys), they have some footguns of their own.

For example, I learned back in 2019 that a map with (x, y) tuples as keys is often a more convenient way to represent a grid than a 2D array. Python handles this pattern nicely with its built-in tuple type:

grid = {}
grid[(1, 2)] = 3
print(grid[(1, 2)])
# prints 3

The equivalent in JS/TS doesn't work as you'd hope:

const grid = new Map<[number, number], number>();
grid.set([1, 2], 3);
console.log(grid.get([1, 2]));
// logs undefined

The issue is that Map and Set keys are (roughly) compared using ===, which tests for reference equality, not value equality:

> [1, 2] === [1, 2]
false

This situation will be improved greatly if the Records and Tuples proposal is ratified by TC39 (playground link):

console.log(#[1, 2] === #[1, 2]);
// logs true

const grid = new Map();
grid.set(#[1, 2], 3);
console.log(grid.get(#[1, 2]));
// logs 3

Here's hoping! Without this, my implementations of standard algorithms like shortest path required lots of serialization and deserialization code.

Another JS/TS feature that I really embraced was Iterators and Generators. Say you have a sum function that takes an array of numbers:

function sum(xs: number[]): number {
  let total = 0;
  for (const x of xs) {
    total += x;
  }
  return total;
}

What if you want this to accept the output of a generator function:

function* squares(n: number) {
  for (let i = 0; i < n; i++) {
    yield n ** 2;
  }
}

TypeScript will give you an error if you try to compose these:

const sumto5 = sum(squares(5));
//                 ~~~~~~~~~~ Argument of type 'Generator<number, void, unknown>'
//                            is not assignable to parameter of type 'number[]'.

Interestingly, though, this works at runtime and gives the correct answer (125)! To make it type check, we just need to loosen the parameter type for sum:

function sum(xs: Iterable<number>): number {
  let total = 0;
  for (const x of xs) {
    total += x;
  }
  return total;
}
const sumto5 = sum(squares(5));  // ok

Whenever I write functions that accept arrays now, I'm going to ask "could this take an Iterable instead?" Often the answer is yes, and this gives you more flexibility in how you call the function. I found this particularly nice for callbacks that returned arrays, which are often cleaner to write as generators. See this commit.

Iterators are a great feature, but they are somewhat held back by their lack of support in lodash. There's a TC39 proposal to add iterator helpers to the standard library.

Because JavaScript doesn't have a built-in deque structure, I just used an Array in a very suboptimal way when I implemented Dijkstra. After wrapping up the whole competition, I tried plugging in a priority queue. Suddenly some of my code ran 100x faster! Asymptotic performance: sometimes it matters!

Overall using TypeScript for the Advent of Code was OK but not great. It was a good excuse to try out a few new features of JavaScript, but it left me really wanting a few other proposals to get adopted!

Advent of Code 2022

This was probably the easiest Advent of Code I've done (easier than 2018, 2019, 2020, 2021). Again, there were no dependencies between days. There was also no matrix math, which was a change from previous years.

I usually do some kind of warmup project in a new language before day 1, traditionally implementing a Boggle Solver. Since I'd already implemented Boggle in TypeScript, I decided to do the first few puzzles of the 2018 Advent of Code instead. This was fun and very effective at preparing me for the 2022 Advent of Code. But it was a dangerous decision! Once I started the 2018 puzzles, I couldn't stop. So I wound up doing two Advents of Code simultaneously. This really highlighted that the 2018 Advent of Code was more difficult than 2022.

I tend to solve AoC problems in the morning: I'm usually asleep well before midnight when they're posted on the east coast. But I'd always been curious to try solving one at midnight to see what my global rank would be. I finally did it on day 15 this year. It was a roller coaster experience. Debugging while sleepy was unpleasant and really took me back to college. But I did manage to finish both parts before 1 AM and got my first-ever top 1000 finish:

I was lucky -- had I tried this on day 16, which was much harder, I would have been up until 3 AM! Falling asleep after racing to solve a puzzle isn't easy.

I'd hoped to stay up late enough to solve the final puzzle live. I was in Costa Rica at that point so it only would have been 11 PM and the Christmas is usually an easy puzzle. But by 10 PM I was in bed and couldn't keep my eyes open, so I just wrapped things up the next morning. I was finisher #5127 overall.

There were a few standout problems this year:

• Day 22: The Cube. Not hard, just very annoying. Though I did enjoy seeing photos of everyone's cubes.
• Day 24: Blizzards, a fun application of Dijkstra where the state space isn't just your coordinate.
• Day 20: Memorable for a pernicious off-by-one error.
• Day 19: Robot Factories. This was the hardest one of the year for me. I never produced a fully correct solution, but I did discover beam search which is something that will stick with me.
• Day 16: Valves; this was probably the second hardest problem.
• Day 9: Snake; really have to trust your implementation on this one. I was very glad to not have a bug!

Overall, though, my favorite problem was probably 2018 day 23.

So there you have it, Advent of Code 2022 in Deno. See you next December (or maybe April!).