Advent of Code 2020 Day 16 - Solution + Tutorial (TypeScript)

published
All TypeScript Solutions for Advent of Code 2020

I'll try to update asap. Please bear in a mind that I'll probably lag one or multiple days behind.

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 = [
  "departure location: 28-787 or 804-964",
  "departure station: 41-578 or 594-962",
  "departure platform: 50-718 or 733-949",];

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 16: Ticket Translation

Part 1

Today, we are given a list of fields and their ranges of valid values. Also, we are given tickets with some values. However, we don't know which value references which field.

For part 1 our task is to find all invalid values from all nearby tickets (see your puzzle input). Well, how to do this? First, let's retrieve all fields from the puzzle input. I've created the parseFields function to do this. After parsing, we have a map where the field names are the keys. The corresponding values are functions (here called validateFns) to validate the values of the tickets. To create these functions I've created a little helper function isBetween. This function is used for creating a function that allows to validate values for the respective field.

With this done, we can look for all invalid values. We extract the nearbyTickets from our puzzle input and check which value is never valid. Therefore, we have to test whether the value is valid for any function from our validateFns.

Now, we know all invalidValues. The last step is to add them together. Here's the full solution:

// Parse fields into a map.
// Then, we have all field names with their corresponding validate function.
const fields = parseFields(lines);

// Get all validate functions from our map.
const validateFns = [...fields.values()];

const invalidValues: number[] = [];

const nearbyTickets = lines.slice(lines.indexOf("nearby tickets:") + 1);

// For each nearby ticket, check if any value is invalid.
// Add invalid values to the `invalidValues` array.
nearbyTickets.forEach((nearbyTicket) => {
  const values = nearbyTicket.split(",").map(Number);

  invalidValues.push(
    ...values.filter(
      (value) => !validateFns.some((validate) => validate(value))
    )
  );
});

// Sum up all invalid values.
return invalidValues.reduce((previous, current) => previous + current);
// Type definition for a validate function.
type ValidateFn = (value: number) => boolean;
// Helper function for creating validate functions.
const isBetween = (min: number, max: number) => (value: number) =>
  value >= min && value <= max;
function parseFields(lines: string[]): Map<string, ValidateFn> {
  const fields = new Map<string, ValidateFn>();

  // Extract name and the rules from a field definition.
  const regex = /^([a-z ]+): (\d+-\d+) or (\d+-\d+)/;

  let i = 0;
  let match = regex.exec(lines[i]);

  // Extract all fields.
  while (match) {
    const [, name, ...rules] = match;

    // Create validate functions for the field.
    const validateFns = rules.map((rule) => {
      const [ruleMin, ruleMax] = rule.split("-").map(Number);
      return isBetween(ruleMin, ruleMax);
    });

    // Create a validate function for the field.
    // If validate function returns `true`, then `value` is valid.
    const validateFn = (value: number) =>
      validateFns.some((validate) => validate(value));

    // Add our field to the map.
    fields.set(name, validateFn);

    i++;
    match = regex.exec(lines[i]);
  }

  return fields;
}

Part 2

Part 2 tasks us with finding out, which ticket value belongs to which field. Therefore, let's parse our fields again. So, we have a map with field names, and their validate functions.

First, we'll use this similar to part 1. We can throw away all tickets with invalid values. After that, we'll have to determine somehow, which value belongs to which field. To make working with the tickets easier, I've transposed our validNearbyTickets into another array called columns. Now, each element of our columns array is another array that contains all the values for a single field.

This columns array allows us, to check which fields are possible for which value. Using the reducePossibilities function I've written, we can start reducing the possibilities until we exactly know which values belong to which field.

Now, we just have to look up the values on our ticket for fields starting with *departure". Multiplying all these values is our puzzle solution. Here's the full solution:

// Parse fields into a map.
// Then, we have all field names with their corresponding validate function.
const fields = parseFields(lines);

// Get all validate functions from our map.
const validateFns = [...fields.values()];

const nearbyTickets = lines.slice(lines.indexOf("nearby tickets:") + 1);

// For each nearby ticket, check if any value is invalid.
// If the nearby ticket contains invalid values, throw it away.
const validNearbyTickets = nearbyTickets
  .map((nearbyTicket) => nearbyTicket.split(",").map(Number))
  .filter(
    (values) =>
      !values.some(
        (value) => !validateFns.some((validate) => validate(value))
      )
  );

// Use transposition. Thus, each element contains all values for a single field.
const columns = validNearbyTickets[0].map((x, i) =>
  validNearbyTickets.map((x) => x[i])
);

const columnsWithPossibleFields = new Map<number, Set<string>>();

// Check which fields these values could belong to.
columns.forEach((values, i) => {
  const possibleFields = new Set<string>();

  for (const [name, validateFn] of fields.entries()) {
    const valid = values.every((value) => validateFn(value));

    if (valid) {
      possibleFields.add(name);
    }
  }

  columnsWithPossibleFields.set(i, possibleFields);
});

// Reduce possiblities until it's clear to which fields the values belong.
reducePossibilities([...columnsWithPossibleFields.values()]);

// Map a column (with its values) to a single field.
const columnToField = new Map<number, string>();
for (const [column, possibleFields] of columnsWithPossibleFields.entries()) {
  columnToField.set(column, [...possibleFields.values()][0]);
}

const myTicket = lines[lines.indexOf("your ticket:") + 1]
  .split(",")
  .map(Number);

const result: number[] = [];

// Get all values from our ticket where field name starts with `"departure"`.
for (const [column, field] of columnToField.entries()) {
  if (!field.startsWith("departure")) continue;
  result.push(myTicket[column]);
}

// Return the product of those values.
return result.reduce((previous, current) => previous * current);
function reducePossibilities(sets: Set<string>[]): void {
  // Sort sets so the smallest set comes first.
  sets.sort((a, b) => a.size - b.size);

  const smallestSet = sets.shift();

  if (!smallestSet) {
    return;
  }

  if (smallestSet.size > 1) {
    throw new Error();
  }

  const value = [...smallestSet.values()][0];

  // Delete the value from this set from all other sets.
  sets.forEach((set) => {
    set.delete(value);
  });

  // Keep on reducing until we can't continue anymore.
  reducePossibilities(sets);
}
// Type definition for a validate function.
type ValidateFn = (value: number) => boolean;
// Helper function for creating validate functions.
const isBetween = (min: number, max: number) => (value: number) =>
  value >= min && value <= max;
function parseFields(lines: string[]): Map<string, ValidateFn> {
  const fields = new Map<string, ValidateFn>();

  // Extract name and the rules from a field definition.
  const regex = /^([a-z ]+): (\d+-\d+) or (\d+-\d+)/;

  let i = 0;
  let match = regex.exec(lines[i]);

  // Extract all fields.
  while (match) {
    const [, name, ...rules] = match;

    // Create validate functions for the field.
    const validateFns = rules.map((rule) => {
      const [ruleMin, ruleMax] = rule.split("-").map(Number);
      return isBetween(ruleMin, ruleMax);
    });

    // Create a validate function for the field.
    // If validate function returns `true`, then `value` is valid.
    const validateFn = (value: number) =>
      validateFns.some((validate) => validate(value));

    // Add our field to the map.
    fields.set(name, validateFn);

    i++;
    match = regex.exec(lines[i]);
  }

  return fields;
}

Conclusion

Today's puzzle brought back memories of Day 2. Validation. However, it was quite a bit different this time. The most difficult part was probably reducing all the possibilities to find a field's values. Nevertheless, we did it.

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!
All TypeScript Solutions for Advent of Code 2020

I'll try to update asap. Please bear in a mind that I'll probably lag one or multiple days behind.