Published on

Advent of Code 2023 - Day 1

Authors
  • avatar
    Name
    Alvin Li
    Twitter

This series of posts is a writeup of my solutions to the Advent of Code 2023 problems. While time and space complexities are not the main concerns of these problems, I will try to include them in my writeups.

Part 1

Problem

Given a string, combine the first digit and the last digit (in that order) to form a single two-digit number. Then find the sum of all numbers formed this way.

For example:

1abc2
pqr3stu8vwx
a1b2c3d4e5f
treb7uchet

In this example, the values of these four lines are 12, 38, 15, and 77. Adding these together produces 142.

Solution

This problem is fairly straightforward. We can use a regular expression to find the first and last digits of each line, and then add them together.

First way

We need to find all the digits in the string, so the simplest way to do this is to use the regex /\d/g to match all the digits. The g flag tells the regex to match all occurrences of the pattern, rather than just the first one.

We can then use the first and the last one to form a string, and then convert that string to a number using parseInt.

From the 4th line of the example treb7uchet, we can see that it should produce the number 77. The regex above matches only one 7, but accessing the "first" and the "last" number will give us exactly 77. So there should be no more edge cases to consider.

function part1(input) {
  let result = 0
  for (const line of input.split('\n')) {
    const nums = line.match(/\d/g)
    if (nums) {
      result += parseInt(nums[0] + nums[nums.length - 1])
    }
  }
  return result
}

Second way

Rather than using regex, we can iterate through the string and check if each character is a digit.

By breaking down the string into an array of characters with line.split, we can use filter to remove all non-digit characters.

Here we use a string comparison to check if the character is a digit. This is because we know that the characters are all ASCII characters, and the digits are all consecutive. So we can just check if the character is between 0 and 9. Ref: MDN page on string comparision

function part1(input) {
  let result = 0
  for (const line of input.split('\n')) {
    const nums = line.split('').filter((c) => c >= '0' && c <= '9')
    if (nums.length > 0) {
      result += parseInt(nums[0] + nums[nums.length - 1])
    }
  }
  return result
}

Part 2

The problem becomes more complex: one, two, three, four, five, six, seven, eight, and nine also count as valid "digits".

two1nine
eightwothree
abcone2threexyz
xtwone3four
4nineeightseven2
zoneight234
7pqrstsixteen

In this example, the values are 29, 83, 13, 24, 42, 14, and 76. Adding these together produces 281.

Solution

We can see that the digit words can overlap. For example, zoneight234 contains one, eight, 2, 3 and 4. We need a way to keep the previous digit-checking and take care of the words.

First attempt

We can use an iterative approach to look the string from left to right. Here are the psuedo code for processing each line:

create a list to keep track of numbers found
start from the first character, go through each index
  if the current character is a digit
    add it to the list
  if the string looking from the current index starts with any of the digit words
    find the corresponding digit
    add the digit to the list
take the first and last digit from the list and convert it to number
... same steps as before ...

Digit words

Considering the following array of digit words:

const digitWords = ['zero', 'one', 'two', 'three', 'four', 'five', 'six', 'seven', 'eight', 'nine']

Notice the zero entry at the beginning. I chose this arragement because of two main reasons:

  1. There is no appearance of zero or 0 in the example input, so we can just ignore it.
  2. The index of the digit word in the array is the same as the digit it represents.

With such, we can update the pseudo to a more precise version:

create a list to keep track of numbers found
start from the first character, go through each index
  if the current character is a digit
    add it to the list
  // if the string looking from the current index starts with any of the digit words
  //  find the corresponding digit
  //  add the digit to the list
  go through each digit word
    if the string looking from the current index starts with the digit word
      add the index of the digit word to the list
take the first and last digit from the list and convert it to number
... same steps as before ...

And the corresponding code:

function part2(input) {
  let result = 0
  for (const line of input.split('\n')) {
    const nums = []
    for (let i = 0; i < line.length; i++) {
      const c = line[i]
      if (c >= '0' && c <= '9') {
        nums.push(c)
      }
      for (let j = 0; j < digitWords.length; j++) {
        const word = digitWords[j]
        if (line.startsWith(word, i)) {
          nums.push(`${j}`)
        }
      }
    }
    if (nums.length > 0) {
      result += parseInt(nums[0] + nums[nums.length - 1])
    }
  }
  return result
}

It is important to note that we need to push the string representation of the index of the digit word, rather than the index itself. Otherwise nums[0] + nums[nums.length - 1] will actually add up the two numbers rather than concatenating them.

Optimization

The above solution should be short and simple enough to understand, but there are still some room for improvement in terms of performance.

Time complexity

Consider n as the number of lines and m as the longest string in the input. The time complexity of the above solution is O(n * m).

This is because for each input line (n), we need to iterate through each character in each line (m), and for each character, we need to iterate through each digit word. However the number of digit words is constant, so we can consider it as constant time.

First optimization

If we look at the logic of checking digits THEN checking digit words, we can see that the two logic are mutually exclusive. If we find a digit, we don't need to check for digit words. So we can actually skip the digit word checking if we find a digit.

Although the time complexity is still O(n * m), the program is expected to run faster if there are more digits in the string

Second optimization

We can also see that we only need the first and the last digit/word in each line. So we can actually stop checking the line once we find the first digit/word. But then we will need to check from both directions.

We can use a variable to keep track of the direction we're checking, default to forward. Once we found something in the forward direction, we switch the direction to backward and start checking from the end of the string.

Again, the time complexity is still O(n * m), but the program will be much faster if the digits are located towards both ends

The complete optimized code is as follows:

export function part2(input) {
  let result = 0
  for (const line of input.split('\n')) {
    const nums = []
    let mode = 'forward' // 'forward' or 'backward'

    let currentIndex = 0
    while (currentIndex >= 0 && currentIndex < line.length) {
      const c = line[currentIndex]

      // Indicates whether a match has been found or not
      let found = ''
      if (c >= '0' && c <= '9') {
        found = c
      } else {
        for (let j = 0; j < digitWords.length; j++) {
          const word = digitWords[j]
          /**
           * If we're going backwards, we need to start from the end of the word
           * e.g. trying to check for 'three' in 'abcone2threeooo' from the end
           *      'abcone2threeooo'
           *                  ^ current index index is 11
           *              ^ we need to start from 11 - 5 + 1 = 7
           *      'abcone2threeooo'.startsWith('three', 11) === true
           */
          const startPos = mode === 'forward' ? currentIndex : currentIndex - word.length + 1
          if (line.startsWith(word, startPos)) {
            found = j.toString()
            break
          }
        }
      }

      // The flow will be forward -> backward -> end
      if (mode === 'forward') {
        if (found) {
          // finish finding forward direction, time for backward
          nums.push(found)
          mode = 'backward'
          currentIndex = line.length - 1
          continue
        }
        // nothing found, keep going forward until index reaches the end
        currentIndex++
      } else {
        if (found) {
          // finish finding background direction, time to end
          nums.push(found)
          break
        }
        // nothing found, keep going forward until index reaches the end
        currentIndex--
      }
    }

    if (nums.length > 0) {
      result += parseInt(nums[0] + nums[nums.length - 1])
    }
  }
  return result
}

Space complexity

In the algorithm we have a growing list of numbers, which is in the space complexity of O(m), where m is length of the longest line in the input.

However, with the above optimizations, we will at most push twice into the array, once for the forward direction and once for the backward direction. So the space complexity has become O(1). Hooraay!

Conclusion

AOC 2023 Day 1 was fairly simple, but it could be quite a challenge to do it both fast (human clock) and fast (computer clock). If you like to see more of these writeups, please share my post and comment below. Thanks for reading!

p.s.

I am seeking a good way to 1. put a live javascript runner in my blog post, and 2. make a newsletter for my blog. If you have any suggestions, please let me know :)

Discuss on Twitter • View on GitHub