Day 18: Snailfish

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));
}

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))

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)

• 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.

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, "]"),
        }
    }
}

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
}

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()
}

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));
}

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

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

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

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.

(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))

(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)))))))

#!/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()

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