Task 18

Thorn Thaler - <

2025-07-25

1 Setup

1.1 Libraries

library(httr)
library(xml2)
library(magrittr)
library(tibble)
library(dplyr)
library(tidyr)
library(purrr)
library(stringr)
library(R6)
library(glue)
library(data.tree)

1.2 Retrieve Data from AoC

session_cookie <- set_cookies(session = keyring::key_get("AoC-GitHub-Cookie"))
base_url <- paste0("https://adventofcode.com/2021/day/", params$task_nr)
puzzle <- GET(base_url,
                  session_cookie) %>% 
    content(encoding = "UTF-8") %>% 
    xml_find_all("///article") %>% 
    lapply(as.character)

puzzle_data <- GET(paste0(base_url, "/input"),
                         session_cookie) %>% 
    content(encoding = "UTF-8") %>% 
    str_split("\n") %>% 
    `[[`(1L) %>% 
    head(-1L)

2 Puzzle Day 18

2.1 Part 1

2.1.1 Description

— Day 18: Snailfish —

You descend into the ocean trench and encounter some snailfish. They say they saw the sleigh keys! They’ll even tell you which direction the keys went if you help one of the smaller snailfish with his math homework.

Snailfish numbers aren’t like regular numbers. Instead, every snailfish number is a pair - an ordered list of two elements. Each element of the pair can be either a regular number or another pair.

Pairs are written as [x,y], where x and y are the elements within the pair. Here are some example snailfish numbers, one snailfish number per line: 

[1,2]
[[1,2],3]
[9,[8,7]]
[[1,9],[8,5]]
[[[[1,2],[3,4]],[[5,6],[7,8]]],9]
[[[9,[3,8]],[[0,9],6]],[[[3,7],[4,9]],3]]
[[[[1,3],[5,3]],[[1,3],[8,7]]],[[[4,9],[6,9]],[[8,2],[7,3]]]]

This snailfish homework is about addition. To add two snailfish numbers, form a pair from the left and right parameters of the addition operator. For example, [1,2] + [[3,4],5] becomes [[1,2],[[3,4],5]].

There’s only one problem: snailfish numbers must always be reduced, and the process of adding two snailfish numbers can result in snailfish numbers that need to be reduced.

To reduce a snailfish number, you must repeatedly do the first action in this list that applies to the snailfish number:

  • If any pair is nested inside four pairs, the leftmost such pair explodes.
  • If any regular number is 10 or greater, the leftmost such regular number splits.

Once no action in the above list applies, the snailfish number is reduced.

During reduction, at most one action applies, after which the process returns to the top of the list of actions. For example, if split produces a pair that meets the explode criteria, that pair explodes before other splits occur.

To explode a pair, the pair’s left value is added to the first regular number to the left of the exploding pair (if any), and the pair’s right value is added to the first regular number to the right of the exploding pair (if any). Exploding pairs will always consist of two regular numbers. Then, the entire exploding pair is replaced with the regular number 0.

Here are some examples of a single explode action:

  • [[[[[9,8],1],2],3],4] becomes [[[[0,9],2],3],4] (the 9 has no regular number to its left, so it is not added to any regular number).
  • [7,[6,[5,[4,[3,2]]]]] becomes [7,[6,[5,[7,0]]]] (the 2 has no regular number to its right, and so it is not added to any regular number).
  • [[6,[5,[4,[3,2]]]],1] becomes [[6,[5,[7,0]]],3].
  • [[3,[2,[1,[7,3]]]],[6,[5,[4,[3,2]]]]] becomes [[3,[2,[8,0]]],[9,[5,[4,[3,2]]]]] (the pair [3,2] is unaffected because the pair [7,3] is further to the left; [3,2] would explode on the next action).
  • [[3,[2,[8,0]]],[9,[5,[4,[3,2]]]]] becomes [[3,[2,[8,0]]],[9,[5,[7,0]]]].

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.

Here is the process of finding the reduced result of [[[[4,3],4],4],[7,[[8,4],9]]] + [1,1]: 

after addition: [[[[[4,3],4],4],[7,[[8,4],9]]],[1,1]]
after explode:  [[[[0,7],4],[7,[[8,4],9]]],[1,1]]
after explode:  [[[[0,7],4],[15,[0,13]]],[1,1]]
after split:    [[[[0,7],4],[[7,8],[0,13]]],[1,1]]
after split:    [[[[0,7],4],[[7,8],[0,[6,7]]]],[1,1]]
after explode:  [[[[0,7],4],[[7,8],[6,0]]],[8,1]]

Once no reduce actions apply, the snailfish number that remains is the actual result of the addition operation: [[[[0,7],4],[[7,8],[6,0]]],[8,1]].

The homework assignment involves adding up a list of snailfish numbers (your puzzle input). The snailfish numbers are each listed on a separate line. Add the first snailfish number and the second, then add that result and the third, then add that result and the fourth, and so on until all numbers in the list have been used once.

For example, the final sum of this list is [[[[1,1],[2,2]],[3,3]],[4,4]]: 

[1,1]
[2,2]
[3,3]
[4,4]

The final sum of this list is [[[[3,0],[5,3]],[4,4]],[5,5]]: 

[1,1]
[2,2]
[3,3]
[4,4]
[5,5]

The final sum of this list is [[[[5,0],[7,4]],[5,5]],[6,6]]: 

[1,1]
[2,2]
[3,3]
[4,4]
[5,5]
[6,6]

Here’s a slightly larger example: 

[[[0,[4,5]],[0,0]],[[[4,5],[2,6]],[9,5]]]
[7,[[[3,7],[4,3]],[[6,3],[8,8]]]]
[[2,[[0,8],[3,4]]],[[[6,7],1],[7,[1,6]]]]
[[[[2,4],7],[6,[0,5]]],[[[6,8],[2,8]],[[2,1],[4,5]]]]
[7,[5,[[3,8],[1,4]]]]
[[2,[2,2]],[8,[8,1]]]
[2,9]
[1,[[[9,3],9],[[9,0],[0,7]]]]
[[[5,[7,4]],7],1]
[[[[4,2],2],6],[8,7]]

The final sum [[[[8,7],[7,7]],[[8,6],[7,7]]],[[[0,7],[6,6]],[8,7]]] is found after adding up the above snailfish numbers: 

  [[[0,[4,5]],[0,0]],[[[4,5],[2,6]],[9,5]]]
+ [7,[[[3,7],[4,3]],[[6,3],[8,8]]]]
= [[[[4,0],[5,4]],[[7,7],[6,0]]],[[8,[7,7]],[[7,9],[5,0]]]]

  [[[[4,0],[5,4]],[[7,7],[6,0]]],[[8,[7,7]],[[7,9],[5,0]]]]
+ [[2,[[0,8],[3,4]]],[[[6,7],1],[7,[1,6]]]]
= [[[[6,7],[6,7]],[[7,7],[0,7]]],[[[8,7],[7,7]],[[8,8],[8,0]]]]

  [[[[6,7],[6,7]],[[7,7],[0,7]]],[[[8,7],[7,7]],[[8,8],[8,0]]]]
+ [[[[2,4],7],[6,[0,5]]],[[[6,8],[2,8]],[[2,1],[4,5]]]]
= [[[[7,0],[7,7]],[[7,7],[7,8]]],[[[7,7],[8,8]],[[7,7],[8,7]]]]

  [[[[7,0],[7,7]],[[7,7],[7,8]]],[[[7,7],[8,8]],[[7,7],[8,7]]]]
+ [7,[5,[[3,8],[1,4]]]]
= [[[[7,7],[7,8]],[[9,5],[8,7]]],[[[6,8],[0,8]],[[9,9],[9,0]]]]

  [[[[7,7],[7,8]],[[9,5],[8,7]]],[[[6,8],[0,8]],[[9,9],[9,0]]]]
+ [[2,[2,2]],[8,[8,1]]]
= [[[[6,6],[6,6]],[[6,0],[6,7]]],[[[7,7],[8,9]],[8,[8,1]]]]

  [[[[6,6],[6,6]],[[6,0],[6,7]]],[[[7,7],[8,9]],[8,[8,1]]]]
+ [2,9]
= [[[[6,6],[7,7]],[[0,7],[7,7]]],[[[5,5],[5,6]],9]]

  [[[[6,6],[7,7]],[[0,7],[7,7]]],[[[5,5],[5,6]],9]]
+ [1,[[[9,3],9],[[9,0],[0,7]]]]
= [[[[7,8],[6,7]],[[6,8],[0,8]]],[[[7,7],[5,0]],[[5,5],[5,6]]]]

  [[[[7,8],[6,7]],[[6,8],[0,8]]],[[[7,7],[5,0]],[[5,5],[5,6]]]]
+ [[[5,[7,4]],7],1]
= [[[[7,7],[7,7]],[[8,7],[8,7]]],[[[7,0],[7,7]],9]]

  [[[[7,7],[7,7]],[[8,7],[8,7]]],[[[7,0],[7,7]],9]]
+ [[[[4,2],2],6],[8,7]]
= [[[[8,7],[7,7]],[[8,6],[7,7]]],[[[0,7],[6,6]],[8,7]]]

To check whether it’s the right answer, the snailfish teacher only checks the magnitude of the final sum. The magnitude of a pair is 3 times the magnitude of its left element plus 2 times the magnitude of its right element. The magnitude of a regular number is just that number.

For example, the magnitude of [9,1] is 39 + 21 = 29; the magnitude of [1,9] is 31 + 29 = 21. Magnitude calculations are recursive: the magnitude of [[9,1],[1,9]] is 329 + 221 = 129.

Here are a few more magnitude examples:

  • [[1,2],[[3,4],5]] becomes 143.
  • [[[[0,7],4],[[7,8],[6,0]]],[8,1]] becomes 1384.
  • [[[[1,1],[2,2]],[3,3]],[4,4]] becomes 445.
  • [[[[3,0],[5,3]],[4,4]],[5,5]] becomes 791.
  • [[[[5,0],[7,4]],[5,5]],[6,6]] becomes 1137.
  • [[[[8,7],[7,7]],[[8,6],[7,7]]],[[[0,7],[6,6]],[8,7]]] becomes 3488.

So, given this example homework assignment: 

[[[0,[5,8]],[[1,7],[9,6]]],[[4,[1,2]],[[1,4],2]]]
[[[5,[2,8]],4],[5,[[9,9],0]]]
[6,[[[6,2],[5,6]],[[7,6],[4,7]]]]
[[[6,[0,7]],[0,9]],[4,[9,[9,0]]]]
[[[7,[6,4]],[3,[1,3]]],[[[5,5],1],9]]
[[6,[[7,3],[3,2]]],[[[3,8],[5,7]],4]]
[[[[5,4],[7,7]],8],[[8,3],8]]
[[9,3],[[9,9],[6,[4,9]]]]
[[2,[[7,7],7]],[[5,8],[[9,3],[0,2]]]]
[[[[5,2],5],[8,[3,7]]],[[5,[7,5]],[4,4]]]

The final sum is: 

[[[[6,6],[7,6]],[[7,7],[7,0]]],[[[7,7],[7,7]],[[7,8],[9,9]]]]

The magnitude of this final sum is 4140.

Add up all of the snailfish numbers from the homework assignment in the order they appear. What is the magnitude of the final sum?

2.1.2 Solution

The first working solution used R6 reference classes and was R based. While technically working, it was far from being efficient. The recursive class definition coupled wiht environments, required a lot of copying arguments back and forth and was thus awfully slow. In order to hone my C++ skills and to learn how to use Rcpp, I re-wrote the whole solution in C++ and instead of a running time of several hours I was rewarded with instantaneous results. Again, the long running time resulted from my choice of R6 together with a recursive class design, which is not a good match, knowing R's copy-on-modify semantics.

#include <Rcpp.h>
#include <iostream>
#include <memory>
using namespace Rcpp;

enum Position { left, right, root };

class Node : public std::enable_shared_from_this<Node> {
  public:
    [[nodiscard]] static std::shared_ptr<Node> create() {
      return std::shared_ptr<Node>(new Node());
    };

    bool is_regular() const { return !this->left_ && !this->right_; };

    bool is_root() const { return !this->parent_.lock(); };

    std::shared_ptr<Node> ptr() { return shared_from_this(); };

    unsigned int depth() const {
      unsigned int depth = 0;
      std::shared_ptr<Node> pa = this->parent_.lock();
      while (pa) {
        depth++;
        pa = pa->parent_.lock();
      }
      return depth;
    }

    int value() const { return this->value_; };

    Position position() {
      if (!this->is_root()) {
        std::shared_ptr<Node> pa = this->parent_.lock();
        if (this->ptr() == pa->left_) {
          return Position::left;
        } else {
          return Position::right;
        }
      } else {
        return Position::root;
      }
    };

    long magnitude() {
      long res = 0;
      if (this->is_regular()) {
        res = this->value_;
      } else {
        res = 3 * this->left_->magnitude() + 2 * this->right_->magnitude();
      }
      return res;
    };

    std::shared_ptr<Node> set_value(const int value) {
      this->value_ = value;
      return this->ptr();
    };

    std::shared_ptr<Node> set_child(std::shared_ptr<Node> kid, const Position pos) {
      kid->parent_ = this->ptr();
      if (pos == Position::left) {
        this->left_ = kid;
      } else {
        this->right_ = kid;
      }
      return this->ptr();
    };

    std::shared_ptr<Node> set_childs(const std::array<std::shared_ptr<Node>, 2>& kids) {
      this->set_child(kids[0], Position::left);
      this->set_child(kids[1], Position::right);
      return this->ptr();
    };

    std::shared_ptr<Node> next() {
      bool exploded = false;
      return this->next(exploded);
    };

    std::shared_ptr<Node> explode() {
      std::shared_ptr<Node> left_nb = neighbor(Position::left);
      std::shared_ptr<Node> right_nb = neighbor(Position::right);
      int left_val = this->left_->value_, right_val = this->right_->value_;
      if (left_nb) {
        left_nb->value_ += left_val;
      }
      if (right_nb) {
        right_nb->value_ += right_val;
      }
      this->left_.reset();
      this->right_.reset();
      this->value_ = 0;
      return this->ptr();
    };

    std::shared_ptr<Node> split() {
      int val = this->value_;
      std::shared_ptr<Node> left, right;
      left = Node::create();
      left->set_value(floor(val / 2.0));
      right = Node::create();
      right->set_value(ceil(val / 2.0));
      std::array<std::shared_ptr<Node>, 2> kids = {left, right};
      this->set_childs(kids);
      return this->ptr();
    };

    friend std::ostream& operator<<(std::ostream& os, const Node& rhs);

  private:
    // Do not allow direct init to force use of create
    Node() = default;
    int value_;
    std::weak_ptr<Node> parent_;
    std::shared_ptr<Node> left_;
    std::shared_ptr<Node> right_;

    std::shared_ptr<Node> neighbor(const Position dir) {
      std::shared_ptr<Node> me = this->ptr();
      std::shared_ptr<Node> pa = this->parent_.lock();
      while (pa && me->position() == dir) {
        me = pa;
        pa = pa->parent_.lock();
      }
      if (pa) {
        Position new_dir = dir;
        while (!pa->is_regular()) {
          if (new_dir == Position::left) {
            pa = pa->left_;
          } else {
            pa = pa->right_;
          }
          new_dir = dir == Position::left ? Position::right : Position::left;
        }
      }
      return pa;
    };

    std::shared_ptr<Node> next(bool& exploded) {
      std::shared_ptr<Node> node, node2;
      if (!exploded) {
        if (this->is_regular()) {
          if (this->value() >= 10) {
            node = this->ptr();
          }
        } else {
          if (this->depth() == 4) {
            exploded = true;
            node = this->ptr();
          } else {
            node = this->left_->next(exploded);
            if (!exploded) {
              node2 = this->right_->next(exploded);
              if (node2 && (!node || exploded)) {
                node = node2;
              }
            }
          }
        }
      }
      return node;
    };
};

std::ostream& operator<<(std::ostream& os, const Node& rhs) {
  if (rhs.is_regular()) {
    os << rhs.value();
  } else {
    os << "[" << *rhs.left_ << "," << *rhs.right_ << "]";
  }
  return os;
};

class Snailfish {
  public:
    Snailfish* breed_snailfish(List sf) {
      this->root_ = Node::create();
      this->breed_snailfish(sf, this->root_);
      return this;
    };

    Snailfish* reduce(bool verbose = false) {
      std::shared_ptr<Node> next_node = this->root_->next();
      while (next_node) {
        if (next_node->is_regular()) {
          if (verbose) {
            Rcout << "after splitting @" << *next_node << ":\t\t";
          }
          next_node->split();
          if (verbose) {
            Rcout << *this << std::endl;
          }
        } else {
          if (verbose) {
            Rcout << "after exploding @" << *next_node << "\t\t";
          }
          next_node->explode();
          if (verbose) {
            Rcout << *this << std::endl;
          }
        }
        next_node = this->root_->next();
      }
      return this;
    };

    Snailfish& operator+=(const Snailfish& rhs) {
      std::shared_ptr<Node> new_root = Node::create();
      std::array<std::shared_ptr<Node>, 2> kids = {this->root_, rhs.root_};
      new_root->set_childs(kids);
      this->root_ = new_root;
      return *this;
    }

    long magnitude() { return this->root_->magnitude(); }

    friend std::ostream& operator<<(std::ostream& os, const Snailfish& rhs);

  private:
    std::shared_ptr<Node> root_;

    void breed_snailfish(List sf, std::shared_ptr<Node> parent) {
      if (sf.length() != 2) {
        stop("'sf' must be a list of length 2");
      }
      SEXP left_el = sf[0], right_el = sf[1];
      SEXPTYPE left_type = TYPEOF(left_el), right_type = TYPEOF(right_el);
      std::shared_ptr<Node> left_node = Node::create();
      std::shared_ptr<Node> right_node = Node::create();

      if (left_type == INTSXP) {
        // leaf node
        left_node->set_value(*INTEGER(left_el));
      } else if (left_type == REALSXP) {
        left_node->set_value((int)*REAL(left_el));
      } else if (left_type == VECSXP) {
        breed_snailfish(left_el, left_node);
      }

      if (right_type == INTSXP) {
        // leaf node
        right_node->set_value(*INTEGER(right_el));
      } else if (right_type == REALSXP) {
        right_node->set_value((int)*REAL(right_el));
      } else if (right_type == VECSXP) {
        breed_snailfish(right_el, right_node);
      }
      std::array<std::shared_ptr<Node>, 2> kids = {left_node, right_node};
      parent->set_childs(kids);
    };
};

std::ostream& operator<<(std::ostream& os, const Snailfish& rhs) {
  os << *rhs.root_;
  return os;
};

Snailfish operator+(Snailfish lhs, const Snailfish& rhs) {
  lhs += rhs;
  return lhs;
}

// [[Rcpp::export]]
long add_snailfish(const List& sfs, int verbose = 0) {
  Snailfish sf0, sfi;
  sf0.breed_snailfish(sfs[0]);
  for (auto i = 1; i < sfs.length(); i++) {
    sfi.breed_snailfish(sfs[i]);
    sf0 = sf0 + sfi;
    sf0.reduce(verbose > 1);
    if (verbose > 0) {
      Rcout << sf0 << std::endl;
    }
  }
  return sf0.magnitude();
};

// [[Rcpp::export]]
long max_magnitude(const List& sfs, int verbose = 0) {
  Snailfish sf0, sf1, sfsum;
  long max = 0;
  for (auto i = 0; i < sfs.length(); i++) {
    for (auto j = 0; j < sfs.length(); j++) {
      if (i != j) {
        sfsum = *sf0.breed_snailfish(sfs[i]) + *sf1.breed_snailfish(sfs[j]);
        if (verbose > 0) {
          Rcout << sfsum << std::endl;
        }
        sfsum.reduce(verbose > 1);
        max = (sfsum.magnitude() > max) ? sfsum.magnitude() : max;
      }
    }
  }
  return max;
};
puzzle_data %>% 
    str_replace_all("\\[", "list(") %>% 
    str_replace_all("\\]", ")") %>% 
    map(~ eval(parse(text = .x))) %>% 
    add_snailfish()
## [1] 3216

2.2 Part 2

2.2.1 Description

— Part Two —

You notice a second question on the back of the homework assignment:

What is the largest magnitude you can get from adding only two of the snailfish numbers?

Note that snailfish addition is not commutative - that is, x + y and y + x can produce different results.

Again considering the last example homework assignment above: 

[[[0,[5,8]],[[1,7],[9,6]]],[[4,[1,2]],[[1,4],2]]]
[[[5,[2,8]],4],[5,[[9,9],0]]]
[6,[[[6,2],[5,6]],[[7,6],[4,7]]]]
[[[6,[0,7]],[0,9]],[4,[9,[9,0]]]]
[[[7,[6,4]],[3,[1,3]]],[[[5,5],1],9]]
[[6,[[7,3],[3,2]]],[[[3,8],[5,7]],4]]
[[[[5,4],[7,7]],8],[[8,3],8]]
[[9,3],[[9,9],[6,[4,9]]]]
[[2,[[7,7],7]],[[5,8],[[9,3],[0,2]]]]
[[[[5,2],5],[8,[3,7]]],[[5,[7,5]],[4,4]]]

The largest magnitude of the sum of any two snailfish numbers in this list is 3993. This is the magnitude of [[2,[[7,7],7]],[[5,8],[[9,3],[0,2]]]] + [[[0,[5,8]],[[1,7],[9,6]]],[[4,[1,2]],[[1,4],2]]], which reduces to [[[[7,8],[6,6]],[[6,0],[7,7]]],[[[7,8],[8,8]],[[7,9],[0,6]]]].

What is the largest magnitude of any sum of two different snailfish numbers from the homework assignment?

2.2.2 Solution

puzzle_data %>% 
    str_replace_all("\\[", "list(") %>% 
    str_replace_all("\\]", ")") %>% 
    map(~ eval(parse(text = .x))) %>% 
    max_magnitude()
## [1] 4643

2.3 Old R Solution

2.3.1 Solution - Part 1

To solve this puzzle, we have to create a proper data structure first. We rely on R6 and use a tree inspired structure, where each element contains references to its childs and its parent. A child can be either a regular number, NULL or another Snailfish node. With this recursive structure we can easily traverse in either direction. Additionally, we tell nodes whether they are a left or a right node, which is necessary to find the neighbors for exploding nodes.

This data structure is definitely an overkill and due to the involvement of environments (the very basis of R6) a rather slow solution.

Snailfish <- R6Class(
    "Snailfish",
    active = list(
        position = function(value) {
            if (missing(value)) {
                private$.pos  
            } else {
                private$.pos <- value
            }
        },
        parent = function(value) {
            if (missing(value)) {
                private$.parent
            } else {
                stopifnot(inherits(value, "Snailfish") || is.null(value))
                private$.parent <- value
            }
        }
    ),
    private = list(
        .left     = NULL,
        .right    = NULL,
        .parent   = NULL,
        .depth    = 0L,
        .pos      = 0L
    )
)

Snailfish$set(
    "public",
    "is_regular",
    function(dir = allowed_dirs) {
        allowed_dirs <- c("left", "right", "both")
        dir <- match.arg(dir, allowed_dirs)
        if (dir == "both") {
            dir <- allowed_dirs[1:2]
        }
        dir <- glue(".{dir}")
        res <- !map_lgl(mget(dir, private), inherits, "Snailfish")
        names(res) <- str_remove(names(res), "^\\.")
        res
    }
)

Snailfish$set(
    "public",
    "set_depth",
    function(start = 0L) {
        private$.depth <- start
        left <- self$left()
        right <- self$right()
        if (!self$is_regular("left")) {
            left$set_depth(start + 1L)
        }
        if (!self$is_regular("right")) {
            right$set_depth(start + 1L)
        }
        invisible(self)
    }
)

Snailfish$set(
    "public",
    "set_value",
    function(value, dir = c("left", "right")) {
        dir <- match.arg(dir)
        private[[glue(".{dir}")]] <- value
        invisible(self)
    }
)

Snailfish$set(
    "public",
    "get_value",
    function(dir = c("left", "right")) {
        dir <- match.arg(dir)
        stopifnot(self$is_regular(dir))
        private[[glue(".{dir}")]]
    }
)

Snailfish$set(
    "public",
    "child",
    function(dir = c("left", "right")) {
        dir <- match.arg(dir)
        switch(dir,
                 left  = if (!self$is_regular("left")) private$.left else NULL,
                 right = if (!self$is_regular("right")) private$.right else NULL)
    }
)

Snailfish$set(
    "public",
    "left",
    function() {
        self$child("left")
    }
)

Snailfish$set(
    "public",
    "right",
    function() {
        self$child("right")
    }
)

Snailfish$set(
    "public",
    "depth",
    function() {
        private$.depth
    }
)


Snailfish$set(
    "public",
    "neighbor",
    function(dir = c("left", "right")) {
        dir <- match.arg(dir)
        el <- self
        pa <- self$parent
        while (!is.null(pa) && el$position == dir) {
            el <- pa
            pa <- pa$parent  
        }
        if (!is.null(pa)) {
            new_dir <- dir
            while (!pa$is_regular(new_dir)) {
                pa <- pa$child(new_dir)
                new_dir <- switch(dir,
                                        left = "right",
                                        right = "left")
            }
            pa <- list(node = pa, dir = new_dir)
        }
        pa
    }
)

Snailfish$set(
    "public",
    "find_next_node",
    function() {
        find_next_node <- function(node) {
            res <- NULL
            if (!is.null(node)) {
                if (node$depth() == 4L) {
                    ## explosion
                    res <- list(node = node, event = "explode")
                } else {
                    ## check if split should happen at current stage
                    if (node$is_regular("left") && node$get_value("left") >= 10) {
                        res <- list(node = node, event = "split", dir = "left")
                    }
                    ## ... however there could be some explosions somewhere else
                    new_res <- Recall(node$left())
                    if (!is.null(new_res)) {
                        if (is.null(res) || 
                             (res$event != "explode" && 
                              new_res$event == "explode")) {
                            res <- new_res
                        } 
                    }
                    if (is.null(res) && node$is_regular("right") && 
                         node$get_value("right") >= 10) {
                        res <- list(node = node, event = "split", dir = "right")
                    }
                    new_res <- Recall(node$right())
                    if (!is.null(new_res)) {
                        if (is.null(res) || 
                             (res$event != "explode" && 
                              new_res$event == "explode")) {
                            res <- new_res
                        }
                    }
                }
            }
            res
        }
        find_next_node(self$root())
    }
)

Snailfish$set(
    "public",
    "root",
    function() {
        pa <- self
        while (pa$position != "root") {
            pa <- pa$parent
        }
        pa
    }
)
Snailfish$set(
    "public",
    "addr",
    function() {
        root <- self$root()
        addr <- Node$new("Snailfish")   
        create_tree <- function(node, parent) {
            if (!is.null(node)) {
                me <- parent$AddChild(obj_addr(node))
                if (!node$is_regular("left")) {
                    Recall(node$left(), me)
                } else {
                    me$AddChild(paste("L:", as.character(node$get_value("left"))))
                }
                if (!node$is_regular("right")) {
                    Recall(node$right(), me)
                } else {
                    me$AddChild(paste("R:", as.character(node$get_value("right"))))
                }
            }
        }
        create_tree(root, addr)
        print(addr)
    }
)

Snailfish$set(
    "public",
    "explode",
    function() {
        root <- self$root()
        add_value <- function(dir) {
            nb <- self$neighbor(dir)
            if (!is.null(nb)) {
                new_val <- self$get_value(dir)
                old_val <- nb$node$get_value(nb$dir)
                nb$node$set_value(old_val + new_val, nb$dir)
            }
        }
        add_value("left")
        add_value("right")
        self$parent$set_value(0L, self$position)
        self$parent <- NULL
        invisible(root)
    }
)

Snailfish$set(
    "public",
    "split",
    function(dir) {
        val <- self$get_value(dir) / 2L
        new_pair <- Snailfish$new(list(floor(val), ceiling(val)),
                                          self,
                                          self$depth() + 1L,
                                          pos = dir)
        self$set_value(new_pair, dir)
        invisible(self$root())
    }
)

Snailfish$set(
    "public",
    "reduce",
    function(verbose = FALSE, ...) {
        root <- self$root()
        next_node <- root$find_next_node()
        while(!is.null(next_node)) {
            if (next_node$event == "explode") {
                next_node$node$explode()
                if (verbose) {
                    wh <- capture.output(next_node$node)
                    cat("after exploding @", wh, ":\t\t", sep = "")
                    print(root, ...)
                }
            } else if (next_node$event == "split") {
                wh <- next_node$node$get_value(next_node$dir)
                next_node$node$split(next_node$dir)
                if (verbose) {
                    cat("after splitting @", wh, ":\t\t", sep = "")
                    print(root, ...)
                }
            }
            next_node <- root$find_next_node()
        }
        invisible(root)
    }
)

Snailfish$set(
    "public",
    "to_list",
    function() {
        to_list <- function(node) {
            res <- NULL
            if (node$is_regular("left")) {
                res <- node$get_value("left")
            } else {
                res <- Recall(node$left())
            }
            if (node$is_regular("right")) {
                res <- list(res, node$get_value("right"))
            } else {
                res <- list(res, Recall(node$right()))
            }
            res
        }
        to_list(self)
    }
)

Snailfish$set(
    "public",
    "magnitude",
    function() {
        sum <- function(node) {
            res <- 0
            if (!is.null(node)) {
                if (node$is_regular("left")) {
                    res <- 3 * node$get_value("left")
                }
                if (node$is_regular("right")) {
                    res <- res + 2 * node$get_value("right")
                }
                res <- res + 3 * Recall(node$left()) + 2 * Recall(node$right())
            }
            res
        }
        sum(self)
    }
)

Snailfish$set(
    "public",
    "initialize",
    function(lst, parent = NULL, depth = 0L, pos = "root", str = NULL) {
        stopifnot(is.null(str) || length(str) == 1L)
        if (!xor(missing(lst), is.null(str))) {
            warning("both 'lst' and 'str' are given - ",
                      "'lst' will be overridden by 'str'")
        }
        if (!is.null(str)) {
            lst <- str %>% 
                str_replace_all("\\[", "list(") %>% 
                str_replace_all("\\]", ")") %>% 
                parse(text = .) %>% 
                eval()
        }
        stopifnot(is.list(lst) && length(lst) == 2L)
        self$parent <- parent
        private$.depth  <- depth
        private$.pos    <- pos
        left <- lst[[1L]]
        right <- lst[[2L]]
        if (is.list(left)) {
            private$.left <- Snailfish$new(left, self, depth + 1L, "left")
        } else {
            private$.left <- left
        }
        if (is.list(right)) {
            private$.right <- Snailfish$new(right, self, depth + 1L, "right")
        } else {
            private$.right <- right
        }
    }
)

Snailfish$set(
    "public",
    "print",
    function(show_depth = FALSE, show_pos = FALSE, ...) {
        left <- if (self$is_regular("left")) 
            private$.left else
                capture.output(print(private$.left, show_depth, show_pos, ...))
        right <- if (self$is_regular("right")) 
            private$.right else
                capture.output(print(private$.right, show_depth, show_pos, ...))
        depth <- if (show_depth) glue("{private$.depth}") else ""
        pos <- if (show_pos) switch(private$.pos,
                                             left = "L",
                                             right = "R",
                                             root = "~") else ""
        sep <- if (show_depth | show_pos) ": " else ""
        mod <- glue("{depth}{pos}{sep}")
        cat("[", mod, left, ",", right, "]", "\n", sep = "")
        invisible(self)
    }
)

`%+%` <- function(e1, e2) {
    new_sf <- list(e1$to_list(),
                        e2$to_list())
    Snailfish$new(new_sf)
}
cache_file <- here::here("2021", "Task-18", "summation.rds")
force <- FALSE
if (!file.exists(cache_file) || force) {
    sf0 <- Snailfish$new(str = puzzle_data[[1L]])
    res <- reduce(puzzle_data[-1L], function(.x, .y) {
        sf <- Snailfish$new(str = .y)
        message(glue("Adding Snailfish {capture.output(sf)}"))
        sum <- .x %+% sf
        sum$reduce()
    }, .init = sf0)
    saveRDS(res, cache_file)
} else {
    res <- readRDS(cache_file)  
}

res$magnitude()
## [1] 3216

2.3.2 Solution - Part 2

To solve this puzzle we simply calculate all magnitudes by brute force.

cache_file <- here::here("2021", "Task-18", "pairwise_distance.rds")
force <- FALSE
if (!file.exists(cache_file) || force) {
    idx <- seq_along(puzzle_data)
    res <- matrix(NA, length(idx), length(idx))
    
    for (i in idx) {
        for (j in idx) {
            .x <- Snailfish$new(str = puzzle_data[[i]])
            .y <- Snailfish$new(str = puzzle_data[[j]])
            message(glue("Adding Snailfishs {i} and {j}: ",
                             "{capture.output(.x)} and {capture.output(.y)}"))
            sum <- .x %+% .y
            res[i, j] <- sum$reduce()$magnitude()
        }
    }
    
    saveRDS(res, cache_file)
} else {
    res <- readRDS(cache_file)
}
max(res[-seq(1, prod(dim(res)), ncol(res) + 1)])
## [1] 4643