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)

Thank you.

 
Thanks for visiting DEV, we’ve worked really hard to cultivate this great community and would love to have you join us. If you’d like to create an account, you can sign up here.