DEV Community

Cover image for Corruption Checksum
Robert Mion
Robert Mion

Posted on

1 1

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!

Heroku

This site is built on Heroku

Join the ranks of developers at Salesforce, Airbase, DEV, and more who deploy their mission critical applications on Heroku. Sign up today and launch your first app!

Get Started

Top comments (0)

Sentry image

See why 4M developers consider Sentry, “not bad.”

Fixing code doesn’t have to be the worst part of your day. Learn how Sentry can help.

Learn more

👋 Kindness is contagious

Please leave a ❤️ or a friendly comment on this post if you found it helpful!

Okay