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!

AWS Security LIVE!

Join us for AWS Security LIVE!

Discover the future of cloud security. Tune in live for trends, tips, and solutions from AWS and AWS Partners.

Learn More

Top comments (0)

SurveyJS custom survey software

JavaScript Form Builder UI Component

Generate dynamic JSON-driven forms directly in your JavaScript app (Angular, React, Vue.js, jQuery) with a fully customizable drag-and-drop form builder. Easily integrate with any backend system and retain full ownership over your data, with no user or form submission limits.

Learn more

👋 Kindness is contagious

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

Okay