9 votes

Day 18: Snailfish

Today's problem description: https://adventofcode.com/2021/day/18

Please post your solutions in your own top-level comment. Here's a template you can copy-paste into your comment to format it nicely, with the code collapsed by default inside an expandable section with syntax highlighting (you can replace python with any of the "short names" listed in this page of supported languages):

<details>
<summary>Part 1</summary>

```python
Your code here.
```

</details>

13 comments

  1. Liru
    Link
    Me, enjoying this day's puzzle, coming into this thread after solving it That being said, it's far from a pretty solution. Another homework assignment to those interested in Rust: clean up my...

    Me, enjoying this day's puzzle, coming into this thread after solving it

    That being said, it's far from a pretty solution. Another homework assignment to those interested in Rust: clean up my mess. :D

    Parts 1+2, Rust

    This is super long compared to other days because I didn't clean it up yet, but I'm posting it because I'm sure someone wants to see how an answer with an idiomatic representation may look like. I tried to confine the confusing parts to the recursive _explode method.

    I spent about an hour wondering why my adding tests weren't passing before I realized I copy-pasted the wrong input for my tests. (Speaking of which, this module's test suite is about as long as the code, solely because so many were provided.)

    use std::{
        fmt::Display,
        num::ParseIntError,
        ops::{Add, AddAssign},
        str::FromStr,
    };
    
    type NumberType = u32;
    
    #[derive(Debug, PartialEq, Eq, Clone)]
    pub enum SnailfishNumber {
        Value(NumberType),
        Pair(Box<SnailfishNumber>, Box<SnailfishNumber>),
    }
    
    use itertools::Itertools;
    use SnailfishNumber::*;
    
    impl Add for SnailfishNumber {
        type Output = SnailfishNumber;
    
        fn add(self, rhs: Self) -> Self::Output {
            let mut res: Self::Output = (self, rhs).into();
            res.reduce_after_add();
            res
        }
    }
    
    impl AddAssign for SnailfishNumber {
        fn add_assign(&mut self, rhs: Self) {
            let a = self.clone();
            *self = a + rhs;
        }
    }
    
    impl Display for SnailfishNumber {
        fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
            match self {
                Value(x) => write!(f, "{}", x),
                Pair(x, y) => write!(f, "[{},{}]", x, y),
            }
        }
    }
    
    impl From<NumberType> for SnailfishNumber {
        fn from(x: NumberType) -> Self {
            Value(x)
        }
    }
    
    impl From<(NumberType, NumberType)> for SnailfishNumber {
        fn from(x: (NumberType, NumberType)) -> Self {
            Pair(Box::new(x.0.into()), Box::new(x.1.into()))
        }
    }
    
    impl From<(SnailfishNumber, SnailfishNumber)> for SnailfishNumber {
        fn from(x: (SnailfishNumber, SnailfishNumber)) -> Self {
            Pair(Box::new(x.0), Box::new(x.1))
        }
    }
    
    impl FromStr for SnailfishNumber {
        type Err = ParseIntError;
    
        fn from_str(s: &str) -> Result<Self, Self::Err> {
            match &s[0..1] {
                "[" => {
                    // find matching brackets and subparse
                    let mut depth = 1;
                    let mut split_idx = 0;
                    for i in s.chars().enumerate().skip(1) {
                        match i {
                            (_, '[') => depth += 1,
                            (_, ']') => depth -= 1,
                            (x, ',') if depth == 1 => split_idx = x,
                            _ => (),
                        }
    
                        if depth == 0 {
                            break;
                        }
                    }
    
                    let left = s[1..split_idx].trim().parse::<SnailfishNumber>()?.into();
                    let right = s[split_idx + 1..s.len() - 1].trim().parse::<SnailfishNumber>()?.into();
                    Ok(Pair(left, right))
                }
                _ => Ok(Value(s.parse()?)),
            }
        }
    }
    
    impl SnailfishNumber {
        pub fn reduce_after_add(&mut self) {
            loop { 
                if !self.explode() {
                    if !self.split() {
                        break;
                    }
                }
            }
        }
    
        pub fn explode(&mut self) -> bool {
            self._explode(0).is_some()
        }
    
        fn _explode(&mut self, depth: u8) -> Option<(Option<NumberType>, Option<NumberType>)> {
            if let Pair(left, right) = self {
                match (&**left, &**right) {
                    (Value(l), Value(r)) if depth >= 4 => {
                        let ret = Some((Some(*l), Some(*r)));
                        *self = Value(0);
                        return ret;
                    }
                    (Value(_), Value(_)) => {
                        return None;
                    }
                    _ => {
                        if let Some((l, r)) = left._explode(depth + 1) {
                            return Some((l, right.add_left(r)));
                        } else if let Some((l, r)) = right._explode(depth + 1) {
                            return Some((left.add_right(l), r));
                        }
                    }
                }
            }
    
            None
        }
    
        
        fn add_left(&mut self, add: Option<NumberType>) -> Option<NumberType> {
            match self {
                Value(x) => {
                    *self = Value(*x + add?);
                    None
                }
                Pair(l, _) => l.add_left(add),
            }
        }
    
        fn add_right(&mut self, add: Option<NumberType>) -> Option<NumberType> {
            match self {
                Value(x) => {
                    *self = Value(*x + add?);
                    None
                }
                Pair(_, r) => r.add_right(add),
            }
        }
    
        pub fn split(&mut self) -> bool {
            match self {
                Value(x) if *x >= 10 => {
                    *self = Self::split_number(*x);
                    true
                }
                Value(_) => false,
                Pair(left, right) => left.split() || right.split(),
            }
        }
    
        fn split_number(n: NumberType) -> SnailfishNumber {
            let left = n / 2;
            let right = n / 2 + if n % 2 == 0 { 0 } else { 1 };
    
            // Number::Pair(Box::new(Number::Value(left)), Box::new(Number::Value(right)))
            (left, right).into()
        }
    
        pub fn magnitude(&self) -> u32 {
            match self {
                Value(x) => *x,
                Pair(x, y) => x.magnitude() * 3 + y.magnitude() * 2,
            }
        }
    }
    
    fn part1(input: &str) -> u32 {
        let sum = input
            .lines()
            .map(str::trim)
            .flat_map(str::parse::<SnailfishNumber>)
            .reduce(|a, b| a + b)
            .unwrap();
    
        sum.magnitude()
    }
    
    fn part2(input: &str) -> u32 {
        let numbers: Vec<_> = input
            .lines()
            .map(str::trim)
            .flat_map(str::parse::<SnailfishNumber>)
            .collect();
    
        numbers
            .iter()
            .permutations(2)
            .map(|x| (x[0].clone() + x[1].clone()).magnitude())
            .max()
            .unwrap()
    }
    
    pub fn run() {
        let input = std::fs::read_to_string("input/18.txt").unwrap();
        let input = input.trim();
    
        println!("{}", part1(input));
        println!("{}", part2(input));
    }
    
    4 votes
  2. [5]
    PapaNachos
    (edited )
    Link
    Uhhhhhhhh... What the actual fuck is this problem? Now that I've finished it: This is conceptually an interesting puzzle, but personally the complexity of it made debugging absolute hell for me. I...

    Uhhhhhhhh... What the actual fuck is this problem?


    Now that I've finished it:
    This is conceptually an interesting puzzle, but personally the complexity of it made debugging absolute hell for me. I had a few small errors that took literal hours to track down and find because I basically had to do the calculations by hand until I found something that wasn't right. So definitely a mixed bag in my case.

    Day 18 Part A - Python

    Lots of regex and string parsing. I broke each operation into its own function, with explode being the bulk of it. I used regex to detect the top level pairs, then did a depth calculation for each pair in order. If it was greater that 4 it went boom. The biggest trick here was keeping them in order. I was hoping it wouldn't be necessary within the explode operation, but it definitely was. The OTHER major mistake I made was how I added numbers to the left of an explosion. I decided the easiest way to find the first number in that direction was to reverse the string and do a number search with regex. That worked fine, but I didn't account for 2 digit numbers having their values flipped. That took a reallllllly long time to track down and basically required me stepping through the calculations one by one.

    import re
    from collections import defaultdict
    
    #data = test_data
    data = real_data
    
    #debug_mode = True
    debug_mode = False
    
    data = data.split('\n')
    
    explode_pattern = re.compile(r'(\[\d+,\d+\])')
    digits = re.compile(r'(\d+)')
    split_pattern = re.compile(r'(\d{2})')
    magnitude_pattern = re.compile(r'\[(\d+),(\d+)\]')
    
    #Add
    def addition(left, right):
        return "[" + left +","+right+"]"
    #Explode
    def explode(explode_string):
        results = explode_pattern.findall(explode_string)
        duplicate_workaround = defaultdict(int)
    
        for top_level in results:
            string_split = explode_string.split(top_level)
            first_num = int(top_level.split(',')[0][1:])
            second_num = int(top_level.split(',')[1][:-1])
            #print(top_level, first_num, second_num)
            duplicate_workaround[top_level] = duplicate_workaround[top_level] + 1
            i = duplicate_workaround[top_level]
            left = top_level.join(map(str,string_split[:i]))
            right = top_level.join(map(str,string_split[i:]))
            depth = left.count('[') - left.count(']')
            #if debug_mode:
            #    print(left, ' <-- ',top_level,' --> ', right, ' Depth = ', depth)
            if depth >= 4:
                #We're exploding, I really hope only 1 needs to be exploded at a time
                #Under certain circumstances this can explode multiple times in a row...
                #...I don't think that's a problem. I really hope it's not
                left_rev = left[::-1]
                left_nums = digits.findall(left_rev)
                if len(left_nums) > 0:
                    summed = str(int(left_nums[0][::-1]) + first_num)[::-1]
                    left_rev = re.sub(digits, summed, left_rev, 1)
                    left = left_rev[::-1]
                    #print(left)
                right_nums = digits.findall(right)
                if len(right_nums) > 0:
                    summed = str(int(right_nums[0]) + second_num)
                    right = re.sub(digits, summed, right, 1)
                    #print(right)
                return left+'0'+right
        return explode_string
    
    #Split
    def split_num(split_string):
        double_digits = split_pattern.findall(split_string)
        if len(double_digits) == 0:
            return split_string
        round_down = str(int(double_digits[0])//2)
        round_up = str(int(double_digits[0])//2 + int(double_digits[0]) % 2)
        replacement_string = '['+round_down+','+round_up+']'
        new_string = re.sub(split_pattern, replacement_string, split_string, 1)
        #print(new_string)
        return new_string
    
    
    #Reduce
    def reduce(reduce_string):
        working_string = str(reduce_string)
        keep_reducing = True
        while keep_reducing:
            keep_reducing = False
            #print(working_string)
            exploded = explode(working_string)
            spliting = split_num(working_string)
            #print(spliting)
            if exploded != working_string:
                if debug_mode:
                    print("Exploding")
                    print("Old: ", working_string)
                    print("New: ", exploded)
                keep_reducing = True
                working_string = str(exploded)
            elif spliting != working_string:
                if debug_mode:
                    print("Splitting")
                    print("Old: ", working_string)
                    print("New: ", spliting)
                keep_reducing = True
                working_string = str(spliting)
            else:
                #print("Done")
                keep_reducing = False
        return working_string
                
    
    
    #Magnitude
    def magnitude(magnitude_string):
        working_string = str(magnitude_string)
        keep_going = True
        while keep_going:
            #print(working_string)
            pair = magnitude_pattern.search(working_string)
            if pair:
                #print(pair[0], pair[1], pair[2])
                replacement_number = str((int(pair[1])*3)+(int(pair[2])*2))
                #print(replacement_number)
                working_string = working_string.replace(pair[0], replacement_number)
            else:
                keep_going = False
        return working_string
    
    #Main Loops
    running_sum = data[0]
    for row in data[1:]:
        running_sum = addition(running_sum, row)
        #print(running_sum)
        running_sum = reduce(running_sum)
        #print(running_sum)
        #print("-------")
    
    
    #running_sum = addition(data[0], data[1])
    #print(running_sum)
    #running_sum = reduce(running_sum)
    print(running_sum)
    print(magnitude(running_sum))
    
    Day 18 Part B - Python

    After the hell that was part A, part B was basically trivial. I replaced the end of my program with this and made my magnitude function so that it output an int instead of a string

    #Main Loops
    max_magnitude = 0
    for row in data:
        for col in data:
            mag1 = magnitude(reduce(addition(row, col)))
            mag2 = magnitude(reduce(addition(col, row)))
            max_magnitude = max(max_magnitude, mag1, mag2)
    print(max_magnitude)
    
    Tips
    • There's a lot going on in this one. Definitely break the problem down into manageable chunks so you can tackle it one piece at a time

    • Read through the problem descriptions a few times to make sure you understand them

    • Order does matter, this is one where you can't really simplify it. A + B is not equal to B + A in snailfish math. Same with reducing the numbers, The order you perform the operations in is important, even if it's just running the same operation twice. If there are multiple candidates, order can make a huge difference

    • Watch carefully when your're writing your explode operation, carefully consider how you want to find the first number to the left of a pair. I didn't consider 2-digit numbers and got burned when I tried to do some fancy string reversal

    • If you're having trouble finding an error, add some debugging code and try walking through the operations one by one to find your mistake. Hopefully whatever's wrong will jump out at you when you get to it

    • The details really matter in this one, not only will a small change cascade out of control, it'll also be hard to track down where things went wrong. The way that the numbers move around and transform makes it so they obfuscate the source of any errors. At least that was my experience.

    3 votes
    1. [4]
      Crespyl
      Link Parent
      I'm glad I'm not the only one having trouble, hah. It seems like it's got to boil down to some kind of clever tree traversal/balance sort of deal, but I gotta admit I'm running out of steam on it....

      I'm glad I'm not the only one having trouble, hah.

      It seems like it's got to boil down to some kind of clever tree traversal/balance sort of deal, but I gotta admit I'm running out of steam on it.

      "Explode" really seems like the sticking point for me, and I've got a working implementation that covers all but the last big example, and it breaks for reasons I've not figured out yet.

      I suspect the biggest trick lies in how you move the "exploding" values back up and then down the tree to the correct place. I almost want to just flatten the tree back into a string or something and manipulate it that way.

      I think I'm going to have to concede this one for the night and come back to it tomorrow.

      4 votes
      1. [3]
        PapaNachos
        (edited )
        Link Parent
        I'm making slow but steady progress. My explode segment is substantially longer than any of my other sections, but I'm pretty sure it works as long as there is only one pair that needs to explode...

        I'm making slow but steady progress. My explode segment is substantially longer than any of my other sections, but I'm pretty sure it works as long as there is only one pair that needs to explode at a time. I used a combination of regex and "normal" string manipulation to get where I needed, but in the process I lose track of the order of the top-level pairs, so I'm relying on there only being one that needs to go boom

        I think I'll be able to finish part A soon, but I have no idea what surprises are waiting in part B

        Edit: OH HEY LOOK THAT ASSUMPTION I MENTION ISN'T VALID asdgasdgaghrjkaehtgjklhsaegrklhawrg FFFFFFFUUUUUUCCCCCCCKKKKK

        4 votes
        1. [2]
          Crespyl
          (edited )
          Link Parent
          Maybe spoilers JFC, I had the explode correct this whole time. /facepalm My problem was the order of operations for the "split" step; each iteration of split should only process one (the leftmost)...
          Maybe spoilers JFC, I had the explode correct this whole time. /facepalm

          My problem was the order of operations for the "split" step; each iteration of split should only process one (the leftmost) value. After that it should return to try an explode step before splitting any additional values.

          And with that out of the way, p2 is easy enough. I'll come back for the writeup tomorrow.

          For anyone else stuck on this one, make sure you've got your order of operations correct, don't get ahead of yourself or make any more changes for a given step than exactly what's specified.

          4 votes
          1. PapaNachos
            (edited )
            Link Parent
            My split code worked fine almost immediately, my explode code is a pile of hot garbage that is really fucking with me and this problem is really hard to debug Edit: So I did some string reversal...

            My split code worked fine almost immediately, my explode code is a pile of hot garbage that is really fucking with me and this problem is really hard to debug

            Edit: So I did some string reversal to find the 'first' number when you go to the left during an explosion, but I didn't account for reversing the digits of a 2-character number. So 17 + 8 became 79. Fuck.

            Edit 2:You were right, part 2 was basically trivial

            2 votes
  3. DataWraith
    (edited )
    Link
    Day 18 (Rust) This is definitively my least-favorite puzzle so far. On Day 16 it was at least possible to write a proper parser, but this seems to depend on the order of inputs in a serialized...

    Day 18 (Rust)

    This is definitively my least-favorite puzzle so far. On Day 16 it was at least possible to write a proper parser, but this seems to depend on the order of inputs in a serialized string. I could probably have jury-rigged something with tree-traversal (in-order? pre-order? post-order?), but it was simpler this way.

    Overall it felt like tedium for tedium's sake (well, it was homework after all...)

    Data structures
    use std::fmt::Display;
    
    #[derive(Debug, Copy, Clone, PartialEq, Eq)]
    pub enum SnailfishNumber {
        Open,
        Comma,
        Close,
        Value(usize),
    }
    
    impl Display for SnailfishNumber {
        fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
            match self {
                SnailfishNumber::Open => write!(f, "["),
                SnailfishNumber::Value(num) => write!(f, "{}", num),
                SnailfishNumber::Comma => write!(f, ","),
                SnailfishNumber::Close => write!(f, "]"),
            }
        }
    }
    
    Parsing
    fn parse(input: &str) -> Vec<SnailfishNumber> {
        let mut result = Vec::new();
    
        for c in input.trim().chars() {
            result.push(match c {
                '[' => SnailfishNumber::Open,
                ']' => SnailfishNumber::Close,
                ',' => SnailfishNumber::Comma,
                // Parsing with base 16 simplifies the test-cases with numbers > 9,
                // since you can just specify them in hexadecimal
                _ => SnailfishNumber::Value(c.to_digit(16).unwrap() as usize),
            })
        }
    
        result
    }
    
    Helper functions
    fn to_string(v: &Vec<SnailfishNumber>) -> String {
        v.iter()
            .map(|sn| format!("{}", sn))
            .collect::<Vec<_>>()
            .join("")
    }
    
    fn add(a: Vec<SnailfishNumber>, b: Vec<SnailfishNumber>) -> Vec<SnailfishNumber> {
        let mut result = Vec::new();
        result.push(SnailfishNumber::Open);
        result.extend(a.into_iter());
        result.push(SnailfishNumber::Comma);
        result.extend(b.into_iter());
        result.push(SnailfishNumber::Close);
    
        reduce(result)
    }
    
    fn reduce(s: Vec<SnailfishNumber>) -> Vec<SnailfishNumber> {
        let mut s = s;
    
        loop {
            let (exploded, has_exploded) = explode(s);
            s = exploded;
    
            if has_exploded {
                continue;
            }
    
            let (split, has_split) = split(s);
            s = split;
    
            if has_split {
                continue;
            }
    
            break;
        }
    
        s
    }
    
    fn explode(s: Vec<SnailfishNumber>) -> (Vec<SnailfishNumber>, bool) {
        // increase_by finds the first Value in the vector and increments it
        fn increase_by(s: &mut Vec<SnailfishNumber>, inc: usize) {
            for i in 0..s.len() {
                if let SnailfishNumber::Value(x) = s[i] {
                    s[i] = SnailfishNumber::Value(x + inc);
                    break;
                }
            }
        }
    
        // increase_by finds the last Value in the vector and increments it
        fn increase_by_rev(s: &mut Vec<SnailfishNumber>, inc: usize) {
            for i in (0..s.len()).rev() {
                if let SnailfishNumber::Value(x) = s[i] {
                    s[i] = SnailfishNumber::Value(x + inc);
                    break;
                }
            }
        }
    
        let mut depth = 0;
    
        for (idx, &c) in s.iter().enumerate() {
            match c {
                SnailfishNumber::Open => depth += 1,
                SnailfishNumber::Close => depth -= 1,
                SnailfishNumber::Comma => (),
                SnailfishNumber::Value(_) => {
                    // If we are nested 4 deep...
                    if depth > 4 {
                        // ...and this is not a sub-pair, ...
                        if s[idx + 2] == SnailfishNumber::Open {
                            continue;
                        }
    
                        let (prev, s2) = s.split_at(idx);
                        let mut prev = prev.to_vec();
                        prev.pop();
    
                        // ... extract the left and right numbers of the pair and...
                        if let SnailfishNumber::Value(left) = s2[0] {
                            if let SnailfishNumber::Value(right) = s2[2] {
                                // Split after the pair
                                let (_, trail) = s2.split_at(4);
                                let mut trail = trail.to_vec();
    
                                // Increase the last number in the prefix
                                increase_by_rev(&mut prev, left);
    
                                // Increase the postfix
                                increase_by(&mut trail, right);
    
                                // Concatenate everything
                                prev.push(SnailfishNumber::Value(0));
                                prev.extend(trail.iter());
    
                                return (prev, true);
                            }
                        }
    
                        unreachable!()
                    }
                }
            }
        }
    
        (s, false)
    }
    
    fn split(s: Vec<SnailfishNumber>) -> (Vec<SnailfishNumber>, bool) {
        let mut result = Vec::new();
    
        for (idx, &c) in s.iter().enumerate() {
            if let SnailfishNumber::Value(num) = c {
                if num > 9 {
                    let left = num / 2;
                    let right = (num + 1) / 2;
                    let (_, trail) = s.split_at(idx + 1);
    
                    result.push(SnailfishNumber::Open);
                    result.push(SnailfishNumber::Value(left));
                    result.push(SnailfishNumber::Comma);
                    result.push(SnailfishNumber::Value(right));
                    result.push(SnailfishNumber::Close);
                    result.extend(trail.into_iter());
    
                    return (result, true);
                } else {
                    result.push(c);
                }
            } else {
                result.push(c);
            }
        }
    
        (s, false)
    }
    
    // use a stack to find the magnitude of an expression
    fn magnitude(s: Vec<SnailfishNumber>) -> usize {
        let mut stack = Vec::new();
    
        for c in s.iter() {
            match c {
                SnailfishNumber::Value(x) => stack.push(*x),
                SnailfishNumber::Comma => (),
                SnailfishNumber::Open => (),
                SnailfishNumber::Close => {
                    let right = stack.pop().unwrap();
                    let left = stack.pop().unwrap();
                    let magnitude = 3 * left + 2 * right;
                    stack.push(magnitude);
                }
            }
        }
    
        stack.pop().unwrap()
    }
    
    Solving
    fn part1(input: Vec<Vec<SnailfishNumber>>) -> usize {
        magnitude(input.into_iter().reduce(|a, b| add(a, b)).unwrap())
    }
    
    fn part2(input: Vec<Vec<SnailfishNumber>>) -> usize {
        let mut max_magnitude = 0;
    
        for i in 0..(input.len() - 1) {
            for j in (i + 1)..(input.len()) {
                let m1 = magnitude(add(input[i].clone(), input[j].clone()));
                let m2 = magnitude(add(input[j].clone(), input[i].clone()));
                max_magnitude = max_magnitude.max(m1);
                max_magnitude = max_magnitude.max(m2);
            }
        }
    
        max_magnitude
    }
    
    fn main() {
        let input = include_str!("../../input-18.txt").trim();
    
        let parsed = input
            .lines()
            .filter_map(|l| {
                if l.trim().is_empty() {
                    None
                } else {
                    Some(parse(l.trim()))
                }
            })
            .collect::<Vec<Vec<SnailfishNumber>>>();
    
        println!("Part I:  {}", part1(parsed.clone()));
        println!("Part II: {}", part2(parsed));
    }
    
    2 votes
  4. Crespyl
    Link
    Alright, here's my messy unoptimized solution: Core logic Split "Split" was the "easiest" part because it seemed like the most straight-forward. Unfortunately, it was "too easy" because I quickly...

    Alright, here's my messy unoptimized solution:

    Core logic

    Split

    "Split" was the "easiest" part because it seemed like the most straight-forward. Unfortunately, it was "too easy" because I quickly implemented a recursive split function that actually introduced a subtle bug that only became apparent when the solutions required snailfish numbers that had multiple "splittable" values at once.

    The specification requires that you only ever split one number at a time, and then check for "explodable" numbers before splitting the next number.

    So here's the (much less elegant) recursive "split-leftmost" piece (plus some supporting helpers):

    def split(n)
      split_once(n)[0]
    end
    
    def split_once(n, did_split=false)
      return [n, did_split] if did_split
    
      if (n.is_a? Fixnum) && n >= 10
        [[(n/2.0).floor, (n/2.0).ceil], true]
      elsif n.is_a? Fixnum
        [n, false]
      elsif n.is_a? Array
        split_nodes = n.map do |node|
          if did_split
            node
          else
            split_node, did_split = split_once(node, did_split)
            split_node
          end
        end
        [split_nodes, did_split]
      end
    end
    
    def can_split?(n)
      split(n) != n
    end
    

    This also introduces the theme of complex return values that include some information about the state of the recursive operation that influences the work further up the stack. This came more naturally after my horrific solution for "explode".

    Explode

    When reading the problem description, my first thought was "hey, this moving numbers left and right deal looks tricky to solve in a tree, maybe it'll be simpler if I just try to keep it as a flat string and work it that way?", and my second thought was "nahh, surely part 2 will be something fiddly that relies on tree traversal, I'll just do it as a tree, how hard could it be?". After banging my head on the wall for hours, solving it with a tree, and then going back and looking at the other string-based solutions, I definitely should've just gone with my first instinct.

    Anyway, here goes:

    def add_to_first(node, value)
      if node.is_a? Array
        [add_to_first(node[0], value), node[1]]
      else
        node + value
      end
    end
    
    def add_to_last(node, value)
      if node.is_a? Array
        [node[0], add_to_last(node[1], value)]
      else
        node + value
      end
    end
    
    def explode(n)
      apply_explode(n, 0)[:value]
    end
    
    def apply_explode(n, depth=0)
      n = n.clone
      return {explode: false, going_left: 0, going_right: 0, value: n} unless n.is_a? Array
    
      if depth >= 4
        raise "tried to explode complex pair #{n} at depth #{depth}" unless n.all? { _1.is_a? Fixnum }
    
        return {explode: true, going_left: n[0], going_right: n[1], value: 0}
      else
    
        try_left = apply_explode(n[0], depth+1)
    
        if try_left[:explode]
          n[1] = add_to_first(n[1], try_left[:going_right])
          return {explode: true, going_left: try_left[:going_left], going_right: 0, value: [try_left[:value], n[1]]}
        end
    
        try_right = apply_explode(n[1], depth+1)
        if try_right[:explode]
          n[0] = add_to_last(n[0], try_right[:going_left])
          return {explode: true, going_left: 0, going_right: try_right[:going_right], value: [n[0], try_right[:value]]}
        end
    
        return {explode: false, going_left: 0, going_right: 0, value: n}
      end
    end
    
    def can_explode?(n)
      explode(n) != n
    end
    

    This isn't really as bad as my first take, even with the overly complex return value hashes, but being super explicit about absolutely everything helped me think through it a bit. For a while I kept thinking/worrying that I was supposed to apply explode to both branches at once and somehow merge the "going_left" and "going_right" values back into the siblings, and it was tracking that down that finally helped me realize that each iteration of "explode" must only explode one pair. This ensures that it's fine to stop recursing as soon as I find one pair that does explode.

    For the longest time I kept trying to wrap my head around how best to find the next/previous simple number in the tree and propagate up and down the tree in some kind of clean recursive style. I think I might've ended up needing a structure with parent-pointers or something to do that properly. Instead, I went with this complex return value hash that indicates whether the node exploded and what values should be moved left or right, and that can propagate back up the call stack until the number lands somewhere.

    Reduce

    def reduce(n)
      loop do
        if can_explode?(n)
          n = explode(n)
        elsif can_split?(n)
          n = split(n)
        else
          return n
        end
      end
    end
    

    Magnitude

    Thankfully, this one is actually as straightforward as it looks

    def magnitude(n)
      return n unless n.is_a? Array
      3 * magnitude(n[0]) + 2 * magnitude(n[1])
    end
    
    Part 1 Ruby

    With all that in place, the actual solution is pretty easy (the input being valid list notation for use with eval is a nice plus).

    def add(a, b)
      [a, b]
    end
    
    def sum_list(list)
      list[1..].reduce(list[0]) { |sum, n| reduce(add(sum, n)) }
    end
    
    def compute_p1(input)
      numbers = input.lines.map(&:chomp).map { eval(_1) }
      sum = sum_list(numbers)
      magnitude(sum)
    end
    
    Part 2 Ruby

    And this is quite simple too, we just leverage the stdlib combination method and check each of (a+b), (b+a).

    def compute_p2(input)
      numbers = input.lines.map(&:chomp).map { eval(_1) }
    
      best = 0
      numbers.combination(2).each do |a, b|
        a_b = magnitude(reduce(add(a,b)))
        best = a_b if a_b > best
        b_a = magnitude(reduce(add(b,a)))
        best = b_a if b_a > best
      end
    
      best
    end
    
    2 votes
  5. [3]
    bhrgunatha
    Link
    Sweary Rant Fuck everything about this question and especially his shitty way of explaining what he wants you to do for a problem. Don't make what is actually quite an interesting task into a...
    Sweary Rant Fuck everything about this question and especially his shitty way of explaining what he wants you to do for a problem. Don't make what is actually quite an interesting task into a monumental brainfuck by using such a difficult, convoluted and tangled explanation. That not what makes a puzzle interesting. We get enough of this ambiguous hard to understand language at work and in our daily lives.

    Today was almost as bad as the goblin game.

    Especially fuck the shitty code I wrote and the 10s run-time.

    I'll revisit this abomination sometime later now that I actually understand what the problem is asking.

    Part 1
    (define (part-01 input)
      (sf/magnitude (sf/sum input)))
    
    (define (sf/sum ls)
      (cond [(null? ls) 0]
            [(null? (rest ls)) (first ls)]
            [else (sf/sum
                   (cons (sf/reduce (sf/add (first ls) (second ls)))
                         (rest (rest ls))))]))
    
    (define (sf/add a b)
      (format "[~a,~a]" a b))
    
    (define (sf/magnitude s)
      (cond [(string? s) (sf/magnitude (read (open-input-string (string-replace s "," " " #:all? #t ))))]
            [(number? s) s]
            [else (+  (* 3 (sf/magnitude (first s)))
                      (* 2 (sf/magnitude (second s))))]))
    
    (define (sf/reduce s)
      (define explode? (sf/explode? s))
      (cond [explode? (sf/reduce (sf/explode s explode?))]
            [else (define split? (sf/split? s))
                  (if split?
                      (sf/reduce (sf/split s split?))
                      s)]))
    
    (define (sf/explode? s)
      (for/fold ([i 0] [d 0] #:result (and (= d 5) i))
                ([c (in-string s)]
                 #:break (> d 4))
        (values (add1 i)
                (cond [(eq? c #\[) (add1 d)]
                      [(eq? c #\]) (sub1 d)]
                      [else d]))))
    
    (define (sf/explode s i)
      (define right (substring s i))
      (define cell-left (substring s 0 (sub1 i)))
      (define cell-numbers (map string->number (rest (regexp-match #px"(\\d+),(\\d+)" right))))
      (define cell-right (string-replace right
                                         (format "~a,~a]" (first cell-numbers) (second cell-numbers))
                                         ""
                                         #:all? #f))
    
      (string-append (replace-left cell-left (first cell-numbers))
                     "0"
                     (replace-right cell-right (second cell-numbers))))
    
    (define (replace-right s n)
      (define ns (numbers s))
      (if (null? ns)
          shard
          (string-replace s
                          (number->string (first ns))
                          (number->string (+ n (first ns)))
                          #:all? #f)))
    
    (define (string-reverse s)
      (list->string (reverse (string->list s))))
    
    (define (replace-left s n)
      (define ns (numbers s))
      (cond [(null? ns) s]
            [else (define sr (string-reverse s))
                  (define nr (string-reverse (number->string (last ns))))
                  (define nrr (string-reverse (number->string (+ n (last ns)))))
                  (define r
                    (string-replace sr nr nrr #:all? #f))
                  (string-reverse r)]))
    
    (define (sf/split? s)
      (for/or ([n (numbers s)])
        (and (> n 9) n)))
    
    (define (sf/split s n)
      (define n/2 (/ n 2))
      (define splitted (sf/add (floor n/2) (ceiling n/2)))
      (string-replace s (number->string n) splitted #:all? #f))
    
    Part 2
    (define (part-02 input)
      (apply max
             (for/list ([c (in-combinations input 2)])
               (define n1 (first c))
               (define n2 (second c))
               (max (sf/magnitude (sf/sum (list n1 n2)))
                    (sf/magnitude (sf/sum (list n2 n1)))))))
    
    1 vote
    1. [2]
      DataWraith
      Link Parent
      I didn't like today's puzzle, but I don't think that's fair. Re-reading the explanation after I cooled off from my own frustration, I think it is quite well done – it's just the puzzle itself that...

      Fuck everything about this question and especially his shitty way of explaining what he wants you to do for a problem. Don't make what is actually quite an interesting task into a monumental brainfuck by using such a difficult, convoluted and tangled explanation.

      I didn't like today's puzzle, but I don't think that's fair. Re-reading the explanation after I cooled off from my own frustration, I think it is quite well done – it's just the puzzle itself that is convoluted and thus needs a long explanation.

      The explanation is very condensed; every single sentence must be read, related to the others, and understood, in order to solve the puzzle. Skipping around or otherwise letting a sentence slip by results in mistakes, but thankfully the examples were plentiful and exhaustive.

      That said, today 1/3rd of my code is unit tests, and writing those takes time you don't have if you compete for the leaderboard...

      1 vote
      1. bhrgunatha
        Link Parent
        I'm glad you replied. This is one thing that sets tildes apart - elsewhere you'd just have downvoted and run away. Please don't take this as argumentative, I just want to point out a couple of...

        I'm glad you replied. This is one thing that sets tildes apart - elsewhere you'd just have downvoted and run away. Please don't take this as argumentative, I just want to point out a couple of things:

        First I won't ignore or suppress my feelings. I was just blowing off steam when those feelings are still their most raw. I concede it might have been somewhat hyperbolic :) - I very much like doing these puzzles.

        Re-reading the explanation after I cooled off from my own frustration, I think it is quite well done – it's just the puzzle itself that is convoluted and thus needs a long explanation.

        Maybe your own frustration and all the other comments about how poorly people understood the problem on their way to solving it are evidence that it isn't well explained. You feel it's a good explanation for a concept that you (now!) fully understand. I still think it's convoluted and obfuscated and I maintain it's a poor explanation for a concept you don't understand.

        I'll turn down the hyperbole in future!

        2 votes
  6. wycy
    Link
    Python Finally finished solving this one. It was a real struggle. Python #!/usr/bin/env python3 import sys from typing import List from typing import Tuple EXPLOSION_DEPTH = 4 class...

    Python

    Finally finished solving this one. It was a real struggle.

    Python
    #!/usr/bin/env python3
    import sys
    from typing import List
    from typing import Tuple
    
    EXPLOSION_DEPTH = 4
    
    class TreeNode(object):
        
        def __init__(self):
            self.parent = None
            self.left   = None
            self.right  = None
            self.value  = None
        
        def __str__(self):
            if self.value is not None:
                return f"{self.value}"
            else:
                return f"[{self.left},{self.right}]"  
        
        def __add__(self,other):
            new,_ = parse_number(f"[{self},{other}]")
            return new
        
        def magnitude(self):
            if self.value is not None:
                return self.value
            else:
                return 3 * self.left.magnitude() + 2 * self.right.magnitude()
    
    def get_data(filename: str) -> List[str]:
        lines = []
        with open(filename,'r') as f:
            lines = f.readlines()
        return [l.strip() for l in lines]
    
    def parse_number(input: str, parent: TreeNode = None) -> Tuple[TreeNode,str]:
        new = TreeNode()
        new.parent = parent
        while True:
            char = input[0]
            input = input[1:]
            if char == "[":
                (new.left,remain) = parse_number(input, parent=new)
                input = remain
            elif char == "]":
                return (new,input)
            elif char == ",":
                (new.right,remain) = parse_number(input, parent=new)
                input = remain
            else:
                # Real number
                new.value = int(char)
                return (new,input)
            if len(input) == 0: break
        return (new,input)
    
    def reduce(number: TreeNode):    
        while True:
            exploded = explode(number,0)
            if exploded: continue
    
            splitted = split(number)
            if splitted: continue
    
            break
    
    def explode(number: TreeNode, depth: int) -> bool:
    
        if depth > EXPLOSION_DEPTH:
    
            right = number.parent.right
    
            # Ascend tree to the left looking for a branch who's
            # .left is not the current branch
            left_ref = number.parent
            down = number
            while left_ref is not None:
                if left_ref.left == down:
                    # continue up left
                    down = left_ref
                    left_ref = left_ref.parent
                else:
                    break
            
            # Ascend tree to the right looking for a branch who's
            # .right is not the current branch
            right_ref = number.parent
            down = number.parent.right
            while right_ref is not None:
                if right_ref.right == down:
                    # continue up right
                    down = right_ref
                    right_ref = right_ref.parent
                else:
                    break
    
            # Descend left tree
            if left_ref is not None:
                left_ref = left_ref.left
                while left_ref is not None:
                    try:
                        left_ref.value += number.value
                        break
                    except:
                        pass
                    left_ref = left_ref.right
    
            # Descend right tree
            if right_ref is not None:
                right_ref = right_ref.right
                while right_ref is not None:
                    try:
                        right_ref.value += right.value
                        break
                    except:
                        pass
                    right_ref = right_ref.left
    
            # Explode
            number.parent.left = None
            number.parent.right = None
            number.parent.value = 0
            return True
    
        else:
    
            if number.left is not None:
                if explode(number.left, depth+1):  return True
            if number.right is not None:
                if explode(number.right, depth+1): return True
            return False
    
    def split(number: TreeNode) -> bool:
    
        if number.value is not None and number.value >= 10:
            # Split
            # To split a regular number, replace it with a pair; the left 
            # element of the pair should be the regular number divided by
            # two and rounded down, while the right element of the pair should 
            # be the regular number divided by two and rounded up. For example, 
            # 10 becomes [5,5], 11 becomes [5,6], 12 becomes [6,6], and so on.
            number.left = TreeNode()
            number.left.parent = number
            number.left.value = number.value // 2
    
            number.right = TreeNode()
            number.right.parent = number
            if number.value % 2 == 0:
                number.right.value = number.value // 2
            else:
                number.right.value = number.value // 2 + 1
    
            number.value = None
    
            return True
    
        else:
    
            if number.left is not None:
                if split(number.left): return True
            if number.right is not None:
                if split(number.right): return True
            return False
    
    def main():
        input = get_data(sys.argv[1])
    
        # Parse input
        numbers = []
        for num in input:
            num,_ = parse_number(num)
            numbers.append(num)
        
        # Part 1
        root = numbers[0]
        for i in range(1,len(numbers)):
            root += numbers[i]
            reduce(root)
        print(f"Part 1: {root.magnitude()}") # 4323
    
        # Part 2
        part2 = 0
        for num1 in numbers:
            for num2 in numbers:
                if num1 == num2: continue
                sum = num1 + num2
                reduce(sum)
                part2 = max(sum.magnitude(),part2)
        print(f"Part 2: {part2}") # 4749
    
    if __name__=="__main__":
        main()
    
    1 vote
  7. jzimbel
    Link
    Elixir I thought this one was fun! I had a few bugs to iron out before I got it working, but the abundance of examples to test against really helped make them easy to find. Both parts defmodule...

    Elixir

    I thought this one was fun! I had a few bugs to iron out before I got it working, but the abundance of examples to test against really helped make them easy to find.

    Both parts
    defmodule AdventOfCode.Solution.Year2021.Day18 do
      def part1(input) do
        input
        |> parse_input()
        |> Enum.reduce(&add(&2, &1))
        |> magnitude()
      end
    
      def part2(input) do
        input
        |> parse_input()
        |> then(fn numbers ->
          indexed_numbers = Enum.with_index(numbers)
    
          for {sn1, i} <- indexed_numbers,
              {sn2, j} <- indexed_numbers,
              i != j,
              do: {sn1, sn2}
        end)
        |> Enum.map(fn {sn1, sn2} -> add(sn1, sn2) end)
        |> Enum.map(&magnitude/1)
        |> Enum.max()
      end
    
      def add(sn1, sn2) do
        reduce({sn1, sn2})
      end
    
      def reduce(sn) do
        with :ok <- try_explode(sn),
             :ok <- try_split(sn) do
          sn
        else
          {:explode, sn, _, _} -> reduce(sn)
          {:split, sn} -> reduce(sn)
        end
      end
    
      def try_explode(sn, level \\ 0)
    
      def try_explode({l, r}, 4) do
        {:explode, 0, {l, false}, {r, false}}
      end
    
      def try_explode({l, r}, level) do
        with {:l, :ok} <- {:l, try_explode(l, level + 1)},
             {:r, :ok} <- {:r, try_explode(r, level + 1)} do
          :ok
        else
          {:l, {:explode, l, l_explode, r_explode}} ->
            {r, r_explode} = put_explode(r, r_explode, :l)
            {:explode, {l, r}, l_explode, r_explode}
    
          {:r, {:explode, r, l_explode, r_explode}} ->
            {l, l_explode} = put_explode(l, l_explode, :r)
            {:explode, {l, r}, l_explode, r_explode}
        end
      end
    
      def try_explode(_n, _level), do: :ok
    
      def try_split({l, r}) do
        with {:l, :ok} <- {:l, try_split(l)},
             {:r, :ok} <- {:r, try_split(r)} do
          :ok
        else
          {:l, {:split, l}} -> {:split, {l, r}}
          {:r, {:split, r}} -> {:split, {l, r}}
        end
      end
    
      def try_split(n) when n >= 10 do
        {:split, {div(n, 2), ceil(n / 2)}}
      end
    
      def try_split(_n), do: :ok
    
      def put_explode(sn, {explode_n, true}, _), do: {sn, {explode_n, true}}
    
      def put_explode(sn, {explode_n, false}, side) do
        put_explode(sn, explode_n, side)
      end
    
      def put_explode({l, r}, explode_n, :l) do
        {l, record} = put_explode(l, explode_n, :l)
        {{l, r}, record}
      end
    
      def put_explode({l, r}, explode_n, :r) do
        {r, record} = put_explode(r, explode_n, :r)
        {{l, r}, record}
      end
    
      def put_explode(n, explode_n, _), do: {n + explode_n, {explode_n, true}}
    
      def magnitude({l, r}), do: 3 * magnitude(l) + 2 * magnitude(r)
      def magnitude(n), do: n
    
      def parse_input(input) do
        if safe?(input) do
          input
          |> String.replace(~w|[ ]|, fn
            "[" -> "{"
            "]" -> "}"
          end)
          |> String.split("\n", trim: true)
          |> Enum.map(&Code.eval_string/1)
          |> Enum.map(&elem(&1, 0))
        else
          raise "I ain't eval-ing that"
        end
      end
    
      def safe?(input), do: Regex.match?(~r/^[\[\]\d,\n]+$/, input)
    end
    
    1 vote