DEV Community

Cover image for Corruption Checksum
Robert Mion
Robert Mion

Posted on

Corruption Checksum

Advent of Code 2017 Day 2

Part 1

  1. A delightful treat of ease
  2. Animating my planned algorithm

A delightful treat of ease

  • A list of numbers
  • Find the difference between the largest and smallest
  • Sum up the absolute values of those differences

Sounds easy enough by now!

Animating my planned algorithm

What I intend for my algorithm to do:
Animation of the algorithm I plan to build

Time to build it!

Writing my working algorithm

  • A reduce() to tally up each checksum
  • A regular expression to extract each row's numbers
  • A map() to convert each matched string to a number
  • A sort() to arrange numbers in ascending order
  • pop() and shift() to subtract the first item from the last
return input
    .split('\n')
    .reduce((chucksums, row) => {
      let cells = [...row.matchAll(/\d+/g)]
        .map(match => +match[0])
        .sort((a,b) => a - b)
      return chucksums += cells.pop() - cells.shift()
    }, 0)
Enter fullscreen mode Exit fullscreen mode

Part 2

  1. Nested loops for the win
  2. Animating my planned algorithm

Nested loops for the win

  • After sorting each list, I will compare each value
  • Worst case for my input, each line requires 16+15+14...+1 comparisons: that's under 150, times 16 lines: that's under 2200 total - no biggie

Animating my planned algorithm

Planned algorithm for Part 2

Writing my working algorithm

return input
    .split('\n')
    .reduce((chucksums, row) => {
      let cells = [...row.matchAll(/\d+/g)]
        .map(match => +match[0])
        .sort((a,b) => a - b)
      let divisor = null
      for (let i = 0; i < cells.length - 1; i++) {
        for (let j = i + 1; j < cells.length; j++) {
          if (
              cells[j] / cells[i] == 
              Math.round(cells[j] / cells[i])
             ) {
            divisor = cells[j] / cells[i]
          }
        }
      }
      return chucksums += divisor
    }, 0)
Enter fullscreen mode Exit fullscreen mode
  • Unlike in the animation, my algorithm sorts in ascending order
  • That's because it's more likely to run faster when starting with the smallest number, dividing by increasingly larger numbers

I did it!!

  • I solved both parts!
  • I made a couple GIFs animating how my algorithms work!
  • Both GIFs helped show me some errors and performance gains related to my algorithms!

Bring on Day 1!

Top comments (0)