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!

SurveyJS custom survey software

JavaScript UI Libraries for Surveys and Forms

SurveyJS lets you build a JSON-based form management system that integrates with any backend, giving you full control over your data and no user limits. Includes support for custom question types, skip logic, integrated CCS editor, PDF export, real-time analytics & more.

Learn more

Top comments (0)

Sentry blog image

Identify what makes your TTFB high so you can fix it

In the past few years in the web dev world, we’ve seen a significant push towards rendering our websites on the server. Doing so is better for SEO and performs better on low-powered devices, but one thing we had to sacrifice is TTFB.

Read more

👋 Kindness is contagious

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

Okay