DEV Community

loading...

[Advent of Code 2020] Day 14 Tutorial (TypeScript)

kais_blog profile image Kai Originally published at kais.blog ・5 min read

This post was originally published at kais.blog. It is part of a series of step-by-step tutorials about the Advent of Code 2020 event.

If you like my content and you want to see more, please follow me on Twitter!

Questions, feedback or just wanna chat? Come and join my Discord!

Prerequisites

I assume you've put your puzzle input into an array called lines where each array item is a line of the input text file. It's up to you to either parse the text file or create an array by hand.

const lines = [
  "mask = 1001X1X011110XX111100001100111001110",
  "mem[16252] = 730",
  "mem[28701] = 63670997",
  "mem[28652] = 9219200",
  
];
Enter fullscreen mode Exit fullscreen mode

Solution

Preface

Starting with Day 10, I'll just publish my solution for both parts without explaining every single step. Unfortunately, I can't continue providing full step-by-step tutorials for each day. The concepts used get more difficult day by day. So, I've concluded that it's better if I wrote separate blog posts about these concepts later.

Also, it's holiday season. This makes it much more difficult creating well-thought-out tutorials. However, I'll try to annotate my code examples a little. This way, you might understand what I've done.

I will now move on to sharing useful tips for web developers regularly. These should help you become a better developer. Also, the shared tips should help with solving problems like those we encounter in Advent of Code. Here's my first post:
14 Awesome JavaScript Array Tips You Should Know About

Puzzle

Just to make sure, you know what I'm talking about, take a look at today's puzzle:

Day 14: Docking Data

Part 1

Today we are tasked with using a weird bitmask system to modify memory addresses, and their corresponding values. So, we'll have to convert the values to bits and apply the bitmask. The bitmask is a bit strange. In addition to the use of 1s and 0s, it's using Xs. However, X means do nothing, so we can more or less ignore it.

Okay, what are we doing today? So, for each line, we check if it specifies a new mask, or a memory address and value. If it's a mask, we'll update our current mask. If it's a memory address and value we'll have to do a bit more. First, we extract the address and value. Second, we convert our value into binary form (expandedValue). Then, we'll apply our mask. X means do nothing, so we... do nothing. 1 and 0 override the current bit. After applying the mask, we'll convert our value back to its decimal form. Then, we'll add this value into "memory" (mem).

With this done, there's only one thing left. We sum up all the values in memory, and we've got our solution:

// Prepare "empty" mask and memory.
let mask = [..."X".repeat(36)];
const mem = new Map<number, number>();

// Prepare `regex` for extracting memory address and value.
const regex = /\[(\d+)] = (\d+)$/;

lines.forEach((line) => {
  // Check if line is specifying a bitmask.
  if (line.startsWith("mask =")) {
    // Update mask.
    mask = [...line.split("=", 2).pop()!.trim()];
    return;
  }

  // Line attempts to write a value to memory.
  // Extract `address` and `value` from `line`.
  const match = regex.exec(line);
  const address = parseInt(match![1]);
  let value = parseInt(match![2]);

  // Expand `value` into binary form.
  const expandedValue = [...value.toString(2).padStart(mask.length, "0")];

  // Apply bitmask to value.
  mask.forEach((bit, i) => {
    if (bit === "X") return;
    expandedValue[i] = bit;
  });

  // Convert `expandedValue` to decimal and add to memory.
  value = parseInt(expandedValue.join(""), 2);
  mem.set(address, value);
});

// Sum all values in memory.
return [...mem.values()].reduce((previous, current) => previous + current);
Enter fullscreen mode Exit fullscreen mode

Part 2

Part 2 changes the rules a bit. Our bitmask has now a different meaning:

  • 0 means now do nothing.
  • 1 overrides the current bit with 1.
  • X means the current bit is floating. A floating bit is 1 or 0.

In part 1 the bitmask was applied to the memory value. However, this time, the bitmask is applied to the memory address. We'll also must take into account that the bitmask can change bits to floating. Thus, a value can be written not to a single memory address but to multiple addresses at once.

Therefore, we've to apply the bitmask and find all possible variants of the address. The implementation from part 1 has changed a little. This time, while looping through the lines, we'll convert the address into binary form and apply the bitmask here. Then, we can make use of a recursive function (findAddressVariants) to find all address variants.

After doing all of this, we can add the value to each memory address variant. Then, we are simply left with summing up the values. We've found the solution:

// Prepare "empty" mask and memory.
let mask = [..."0".repeat(36)];
const mem = new Map<number, number>();

// Prepare `regex` for extracting memory address and value.
const regex = /\[(\d+)] = (\d+)$/;

lines.forEach((line) => {
  // Check if line is specifying a bitmask.
  if (line.startsWith("mask =")) {
    // Update mask.
    mask = [...line.split("=", 2).pop()!.trim()];
    return;
  }

  // Line attempts to write a value to memory.
  // Extract `address` and `value` from `line`.
  const match = regex.exec(line);
  const address = parseInt(match![1]);
  const value = parseInt(match![2]);

  // Expand `address` into binary form.
  const expandedAddress = [...address.toString(2).padStart(mask.length, "0")];

  // Apply bitmask to value.
  mask.forEach((bit, i) => {
    if (bit === "0") return;
    expandedAddress[i] = bit;
  });

  // Use the expanded address to find all address variants.
  const addressVariants = findAddressVariants(expandedAddress);

  // Add all values for the addresses we've found.
  addressVariants.forEach((addressVariant) => {
    mem.set(parseInt(addressVariant.join(""), 2), value);
  });
});

// Sum all values in memory.
return [...mem.values()].reduce((previous, current) => previous + current);
Enter fullscreen mode Exit fullscreen mode
function findAddressVariants(expandedAddress: string[]): string[][] {
  // Copy `expandedAddress` array to allow for modification.
  expandedAddress = expandedAddress.slice();

  // Find first occurrence of a floating bit.
  const i = expandedAddress.indexOf("X");

  // No floating bit found, we can return the address.
  if (i === -1) {
    return [expandedAddress];
  }

  // Find all addresses where this floating bit is `"0"`.
  expandedAddress[i] = "0";
  const with0 = findAddressVariants(expandedAddress);

  // Find all addresses where this floating bit is `"1"`.
  expandedAddress[i] = "1";
  const with1 = findAddressVariants(expandedAddress);

  // Merge results.
  return with0.concat(with1);
}
Enter fullscreen mode Exit fullscreen mode

Conclusion

For me, today's puzzle was a bit simpler than yesterday's. However, you may notice that the difficulty increases. We'll see what the next days will bring. Besides, I'm not sure if you could have used bitwise operations here. Maybe there is some fancy solution that did not immediately occur to me.

Thanks a lot for reading this post. Please consider sharing it with your friends and colleagues. See you tomorrow!

If you like my content and you want to see more, please follow me on Twitter!

Questions, feedback or just wanna chat? Come and join my Discord!

This post was originally published at kais.blog.

Discussion (0)

pic
Editor guide