Snailfish

Advent of Code 2021 Day 18

Solve for X where

X = the result of a complex series of addition and multiplication

Where the input is

• A multi-line string
• Each line contains integers and matching pairs of []
• Each line represents a pair of numbers

And the mission is

• Calculate the sum of each line with the one prior according to the prescribed formula
• Reduce the numbers during each summation
• Performing any necessary splits or explosions during the reduction process
• Once the final line accounts for the final sum, calculate each remaining sum's magnitude
• Reduce the final sum into a sum of all magnitudes

This feels doable, but in very small, bite-sized sub-tasks.

Follow me down the rabbit hole

In JavaScript, how do I...

• Parse a string into an array whose structure mimics that which was depicted in the string?
• Merge two arrays into one without flattening the original arrays?
• Determine the depth of a multi-dimensional array?
• Find the leftmost number >= 10 and its position
• Represent a multi-dimensional array as a quasi-binary tree?

Parse string into array

JSON.parse('array-like string')

Merge two arrays into one without flattening

let RA1 = [1, 2]
let RA2 = [[3, 4], 5]

// Option 1
let merged = []
merged.push(a1, a2)

// Option 2
merged = [a1, a2]

Determine the depth of a multi-dimensional array

Discovered on Stack Overflow courtesy of Thomas

function getArrayDepth(value) {
  return Array.isArray(value) ? 
    1 + Math.max(...value.map(getArrayDepth)) :
    0;
}

Find the leftmost number >= 10 and its position

let RA = [1, 2, 3, 2, 1]
RA.find(n => n >= 2) // 2
RA.findIndex(n => n >= 2) // 1

No luck: convert multi-dimensional array into binary tree data structure

• After plenty of Googling, articles and forum answers only offered ways to transform a flat array

I was out of hints and didn't have a clear direction

So I turned to the work of other solvers:

• The subreddit for this challenge
• Solutions from specific JavaScript puzzlers whose code I admired in previous challenges

The chatter was ripe with computer science keywords

• Recursion ("Recursive descent parser", yikes!)
• Binary Trees
• String manipulation
• Find and replace
• List of pairs a.k.a. tuples (in Python)

Signs I was smart in delaying an attempt of my own

• This hint is likely a bug a would have been lucky to get far enough to discover
• This explanation offers clarification of a potential gap in knowledge left by the puzzle instructions

I found one eloquent algorithm in my search for solutions to study

It was an 80-line file written in JavaScript by a puzzler who went back and refactored his original solution to run faster.

Study time!

After spending some time with his code

• Sadly, the conciseness of this code made it harder to easily understand what's happening in each expression
• The combination of array spreading ..., recursion, slicing, stacked ternary operators, anonymous (arrow) functions, nested array return values, array destructuring, and highly-chained calls involving map, reduce and flatMap...all made it difficult to follow, especially given the subject matter is deeply-nested arrays

Even with intense focus and periods of dedicated time, I'm not likely going to fully understand this code.

But, I was able to pluck out foreign language concepts to further study.

New JavaScript language understandings

• flatMap(): should probably be called flattenedMap or mapThenFlatten. It performs map() then flat(). Great for mutating each item in an array into an array, then returning an array where each item is each item from those new arrays spread out.
• ?? operator: if the left operand is null or undefined, return the result of evaluating the right operand expression. Great for condensing a complex if clause.
• Map data type: all the benefits of an object combined with the dependable ordering of an array. Great for storing key-value pairs in the order they were added.
• Skipping values during array destructuring: use an _ or , to skip or ignore any 'garbage' values when destructuring an array:

let [, a] = ['toss', 'keep']; // a = 'keep'

Another puzzle skipped, but not before harvesting as much knowledge as possible

I'm bummed that I didn't crack the code of this or the previous challenge.

I'm glad I worked through a couple of bite-sized algorithms to solve menial tasks.

And I'm glad I spent some time studying the 80-line solution, as it gave me the excuse to research newer JavaScript syntax that I was previously unaware of or not confident using.

I'm comfortable moving on knowing that even had I persisted, I likely would have encountered unavoidable struggles and headaches that I would not have been able to properly diagnose or resolve.

Comments

[David]

Elegant as hell!

const getArrayDepth = (value) => Array.isArray(value) ? 1 + Math.max(0,...value.map(getArrayDepth)) : 0;

This one works with empty arrays, too.