Haskell

I was late to the part on this one and forgot to post my solution :3

import Data.List  

readInput = map readMove . lines  
  where  
    readMove (d : ds) =  
      let n = read ds :: Int  
       in case d of  
            'L' -> -n  
            'R' -> n  

part1 = length . filter ((== 0) . (`mod` 100)) . scanl' (+) 50  

part2 = fst . foldl' count (0, 50)  
  where  
    count (z, p) d =  
      let (q, r) = (p + d) `divMod` 100  
          a = if p == 0 && d < 0 then -1 else 0  
          b = if r == 0 && d < 0 then 1 else 0  
       in (z + abs q + a + b, r)  

main = do  
  input <- readInput <$> readFile "input01"  
  print $ part1 input  
  print $ part2 input  

I think we basically did the same bug, but I did it in rust.

160ms is respectable, I am at 300ms. Probably should remove my sqrt.

Thank you! ☺️

Haskell

import Control.Arrow
import Control.Monad
import Data.Char
import Data.List
import Data.Maybe
import Data.Ord
import Text.ParserCombinators.ReadP

import Data.Array.Unboxed qualified as A
import Data.Map.Strict qualified as M

parse = fst . last . readP_to_S (endBy (sepBy (read <$> munch1 isDigit) (char ',')) (char '\n'))

sortedPairs l = sortOn dist [(x, y) | (x : ys) <- tails l, y <- ys]
  where
    dist = uncurry $ (sum .) . zipWith (\a b -> (b - a) ^ 2)

merge l = scanl' f (initialAssocs, initialSizes)
  where
    f s@(assocs, sizes) (a, b) = case compare ia ib of
        GT -> f s (b, a)
        LT ->
            ( M.map (\x -> if x == ib then ia else x) assocs
            , sizes A.// [(ib, 0), (ia, (sizes A.! ia) + (sizes A.! ib))]
            )
        EQ -> s
      where
        (ia, ib) = (assocs M.! a, assocs M.! b)

    initialAssocs = M.fromList $ zip l [1 ..]
    initialSizes = A.listArray (1, length l) $ repeat 1 :: A.UArray Int Int

main = do
    contents <- parse <$> getContents
    let pairs = sortedPairs contents
        merged = merge contents pairs
        n = findIndex ((== length contents) . (A.! 1) . snd) merged

    print $ product . take 3 . sortBy (comparing Down) . A.elems . snd <$> merged !? 1000
    print $ uncurry (*) . (head *** head) . (pairs !!) . pred <$> n

Yeah, that's one thing the gurus keep hammering home: anything you can move out of loop constructs (inc rows, partition, etc as well as the obvious do, repeat) and handle pervasively is a big win.

Go

Now I'm behind by 1 day, will try to catch up.

For part 2 I spent a good while thinking about it, then when I convinced myself my plan could work, struggled a bit with the implementation. But it worked in the end. Basically grid[i][j] is how many different ways you can reach a cell. Start at 1 on the S cell, then propagate the values down and keep adding up the nums when you reach cells through different paths. The answer is the sum of the nums in the last row.

func part2() {
	// file, _ := os.Open("sample.txt")
	file, _ := os.Open("input.txt")
	defer file.Close()
	scanner := bufio.NewScanner(file)

	input := [][]rune{}

	for scanner.Scan() {
		line := []rune(scanner.Text())
		input = append(input, line)
	}

	m := len(input)
	n := len(input[0])
	grid := make([][]int, m)
	for i := range m {
		grid[i] = make([]int, n)
	}

	for i := range m {
		for j := range n {
			c := input[i][j]
			if i == 0 {
				if c == 'S' {
					grid[i][j] = 1
				}
				continue
			}
			if c == '^' {
				grid[i][j-1] += grid[i-1][j]
				grid[i][j+1] += grid[i-1][j]
			} else {
				grid[i][j] = grid[i][j] + grid[i-1][j]
			}
		}
	}

	paths := 0
	for j := range n {
		paths += grid[m-1][j]
	}

	fmt.Println(paths)
}

It can be confusing, for sure. But I really like Pairs and Triples.

answer = distance.first.first.first * distance.first.second.first is not very elegant, lol.

Oh wow, I see you went the Kotlin way of hacking together an object with Pairs and Triples. I used to do that too but then it got too confusing lol

For part one and likely part 2 you don't need to do all 499500 comparisons, you could split the grid into boxes and only search adjacent ones. E.g. z / 10 = which decile and look at z, z-1, z+1 (and the same for x and y). Less work for the processor, more work for you, and of course, sqrt (which you can also probably skip) is so efficient on modern chips that the overhead of this eats a chunk of the benefits (depending on how low-level your language is).

Fixed, thanks!

Rust

Part 1 took a decent while, partly life getting in the way, partly as I was struggling with some Rust things like floats not being sortable without mucking around, plus some weird bugs trying to get collect to do everything that I eventually just rewrote to avoid.

I found the noisy_float crate which let me wrap f64 as a "real" r64 which meant no NaN which meant Ord which meant sort_by_cached_key() and the rest worked.

I'd planned how to partition the closest neighbour search, but the whole thing runs in 24ms so I didn't bother.

type Id = usize;
type Connection = (Id, Id);
type Circuit = HashSet<Id>;

#[derive(PartialEq)]
struct Point {
    x: usize,
    y: usize,
    z: usize,
}

impl FromStr for Point {
    type Err = Report;

    fn from_str(s: &str) -> Result<Self> {
        let mut parts = s.split(',');
        Ok(Point {
            x: parts.next().ok_or_eyre("missing x")?.parse()?,
            y: parts.next().ok_or_eyre("missing y")?.parse()?,
            z: parts.next().ok_or_eyre("missing z")?.parse()?,
        })
    }
}

impl Point {
    fn distance(&self, other: &Point) -> R64 {
        let dist = ((
            self.x.abs_diff(other.x).pow(2) +
            self.y.abs_diff(other.y).pow(2) +
            self.z.abs_diff(other.z).pow(2)) as f64)
            .sqrt();
        r64(dist)
    }
}

struct Boxes(Vec<Point>);

impl Boxes {
    fn closest(&self) -> Vec<Connection> {
        let mut closest = (0..self.0.len())
            .flat_map(|a| ((a + 1)..self.0.len()).map(move |b| (a, b)))
            .collect::<Vec<_>>();

        closest.sort_by_cached_key(|&(a, b)| self.0[a].distance(&self.0[b]));
        closest
    }

    fn connect_all(&self, p1_threshold: usize) -> Result<(usize, usize)> {
        let mut circuits: Vec<Circuit> = (0..self.0.len())
            .map(|id| HashSet::from_iter(iter::once(id)))
            .collect();

        let mut closest = self.closest().into_iter();
        let mut p1 = 0;
        let mut n = 0;
        loop {
            n += 1;
            let (a, b) = closest.next().ok_or_eyre("All connected already")?;
            let a_circ = circuits.iter().position(|c| c.contains(&a));
            let b_circ = circuits.iter().position(|c| c.contains(&b));
            match (a_circ, b_circ) {
                (None, None) => {
                    circuits.push(vec![a, b].into_iter().collect());
                }
                (None, Some(idx)) => {
                    circuits[idx].insert(a);
                }
                (Some(idx), None) => {
                    circuits[idx].insert(b);
                }
                (Some(a_idx), Some(b_idx)) if a_idx != b_idx => {
                    let keep_idx = a_idx.min(b_idx);
                    let rem_idx = a_idx.max(b_idx);

                    let drained = circuits.swap_remove(rem_idx);
                    // this position is still valid since we removed the later set
                    circuits[keep_idx].extend(drained);
                }
                _ => { /* already connected to same circuit */ }
            };

            if n == p1_threshold {
                circuits.sort_by_key(|set| set.len());
                circuits.reverse();
                p1 = circuits.iter().take(3).map(|set| set.len()).product();
            }
            if circuits.len() == 1 {
                let p2 = self.0[a].x * self.0[b].x;
                return Ok((p1, p2));
            }
        }
    }
}

Another factor of 10 in problem size would have required more efficient data structures and the "correct" algorithm. But as it is, we can get by with sets-as-lists and just updating a hash table, if we're willing to wait a few seconds for the answer.

(ql:quickload :str)

(defun parse-line (line)
  (coerce (mapcar #'parse-integer (str:split "," line)) 'vector))

(defun read-inputs (filename)
  (let ((input-lines (uiop:read-file-lines filename)))
    (make-array (list (length input-lines) 3)
                :initial-contents (mapcar #'parse-line input-lines))))

(defun distance (points p q)
  (flet ((square (x) (* x x)))
    (sqrt (+ (square (- (aref points p 0) (aref points q 0)))
             (square (- (aref points p 1) (aref points q 1)))
             (square (- (aref points p 2) (aref points q 2)))))))

(defun all-labeled-edges (points)
  (loop for j from 0 to (1- (car (array-dimensions points)))
        nconcing (loop for i from 0 to (1- j)
                       collect (list (distance points i j) i j))))

(defun short-labeled-edges (points nedges)
  (subseq (sort (all-labeled-edges points) #'< :key #'first) 0 nedges))

(defun adjacency-map (labeled-edges)
  (let ((result (make-hash-table)))
    (loop for (nil v w) in labeled-edges
          do (setf (gethash v result) (cons w (gethash v result)))
             (setf (gethash w result) (cons v (gethash w result))))
    result))

(defun components (n adjacency-map)
  (let ((remaining (loop for i from 0 to (1- n) collect i))
        (result nil))
    (loop for v = (car remaining)
          until (null v)
          do (let ((this-component nil)
                   (next-component (list v)))
               (loop until (subsetp next-component this-component)
                     do (progn
                          (setf this-component next-component)
                          (setf next-component
                                (reduce #'union
                                        (cons this-component
                                              (mapcar #'(lambda (w) (gethash w adjacency-map))
                                                      this-component))))))
               (setf result (cons this-component result))
               (loop for w in this-component
                     do (setf remaining (delete w remaining)))))
    result))

(defun main-1 (filename)
  (let* ((points (read-inputs filename))
         (adjacency (adjacency-map (short-labeled-edges points 1000)))
         (components (components (car (array-dimensions points)) adjacency))
         (lengths (sort (mapcar #'length components) #'>)))
    (* (car lengths) (cadr lengths) (caddr lengths))))

(defun fusing-edge (n labeled-edges)
  (let ((sorted-edges (sort labeled-edges #'< :key #'first))
        (components (make-hash-table)))
    (loop for i from 0 to (1- n)
          do (setf (gethash i components) (list i)))
    (loop for (nil v w) in sorted-edges
          do (let ((new-component (union (gethash v components) (gethash w components))))
               (cond ((= (length new-component) n)
                      (return (list v w)))
                     ((not (subsetp new-component (gethash v components)))
                      (loop for x in new-component
                            do (setf (gethash x components) new-component))))))))

(defun main-2 (filename)
  (let* ((points (read-inputs filename))
         (n (car (array-dimensions points))))
    (destructuring-bind (v w) (fusing-edge n (all-labeled-edges points))
      (* (aref points v 0) (aref points w 0)))))

Christmas, I guess :) (I just pick a random colour each time a roll is removed)

Yeah, max of 256 paths, and if there were no holes in the splitter layout, it would be the full 256. Also why i had to limit the depth to 16 layers, more than that and the brute forcing gets a bit silly.

Day 8: https://youtu.be/QiezRG4jiUM

Getting pretty close to having written my own game renderer, only slower and worse :D

That's interesting. I found part 1 to be the hard part and part 2 was just simplifying part 1. They ran in about the same time for me, too.

Part 1 run time:

Input IO: 0m 0s 10ms
Input Parse: 0m 0s 21ms
Algorithm: 0m 0s 250ms
Total: 0m 0s 281ms

Part 2 run time:

Input IO: 0m 0s 11ms
Input Parse: 0m 0s 22ms
Algorithm: 0m 0s 255ms
Total: 0m 0s 288ms

Code:

const val connectionsLimit = 1000
const val circuitsLimit = 3

fun part1() {
    val input = getInput(8)
    val circuits: MutableList<MutableSet<Triple<Int, Int, Int>>> = parseInput1(input)
    val distances: MutableList<Pair<Pair<Triple<Int, Int, Int>, Triple<Int, Int, Int>>, Double>> = mutableListOf()
    val tempList = circuits.toList()
    for (i in tempList.indices) {
        val left = tempList[i].first()
        for (j in i + 1..<tempList.size) {
            val right = tempList[j].first()
            val distance = calculateDistance(left, right)
            val coordinates = left to right
            distances.add(coordinates to distance)
        }
    }
    distances.sortBy { it.second }
    // Parts 1 and 2 are the same until here
    for (i in 0..<connectionsLimit) {
        val distance = distances[i]
        val leftCircuit = circuits.first { it.contains(distance.first.first) }
        val rightCircuit = circuits.first { it.contains(distance.first.second) }
        if (leftCircuit != rightCircuit) {
            leftCircuit.addAll(rightCircuit)
            circuits.remove(rightCircuit)
        }
    }
    val sizes = circuits.map { it.size.toLong() }.sortedDescending().slice(0..<circuitsLimit)
    val total = sizes.reduce { acc, i -> acc * i }
    println(total)
}

fun part2() {
    val input = getInput(8)
    val circuits: MutableList<MutableSet<Triple<Int, Int, Int>>> = parseInput1(input)
    val distances: MutableList<Pair<Pair<Triple<Int, Int, Int>, Triple<Int, Int, Int>>, Double>> = mutableListOf()
    val tempList = circuits.toList()
    for (i in tempList.indices) {
        val left = tempList[i].first()
        for (j in i + 1..<tempList.size) {
            val right = tempList[j].first()
            val distance = calculateDistance(left, right)
            val coordinates = left to right
            distances.add(coordinates to distance)
        }
    }
    distances.sortBy { it.second }
    // Part 2 differs starting here
    var answer = 0
    for (distance in distances) {
        val leftCircuit = circuits.first { it.contains(distance.first.first) }
        val rightCircuit = circuits.first { it.contains(distance.first.second) }
        if (leftCircuit != rightCircuit) {
            leftCircuit.addAll(rightCircuit)
            circuits.remove(rightCircuit)
            if (circuits.size == 1) {
                answer = distance.first.first.first * distance.first.second.first
                break
            }
        }
    }
    println(answer)
}

fun parseInput1(input: String): MutableList<MutableSet<Triple<Int, Int, Int>>> {
    return input.lines()
        .filter { it.isNotBlank() }
        .map {
            val split = it.split(",")
            mutableSetOf(Triple(split[0].toInt(), split[1].toInt(), split[2].toInt()))
        }
        .toMutableList()
}

fun calculateDistance(left: Triple<Int, Int, Int>, right: Triple<Int, Int, Int>): Double {
    val dx = (left.first - right.first).toDouble()
    val dy = (left.second - right.second).toDouble()
    val dz = (left.third - right.third).toDouble()
    val distanceSquared = dx.pow(2) + dy.pow(2) + dz.pow(2)
    return sqrt(distanceSquared)
}

You're right, iterating through the pairs does seem to be the way. After doing some analyzing of what takes how long, it seems my issue is with (quickly) figuring out whether I've already connected all nodes or not.

C++

Both parts in 40 ms. As always, the real AoC with C++ is parsing the input, although having a number that changes in the puzzle messes up my test/ solution runners.

Uses Boost's implementations of sets, since they're just plain faster than the STL ones.

#include <boost/log/trivial.hpp>
#include <boost/unordered/unordered_flat_set.hpp>
#include <filesystem>
#include <fstream>
#include <stdexcept>

namespace {

struct Point {
  int x, y, z;
};

auto distance(const Point &a, const Point &b) {
  auto &[ax, ay, az] = a;
  auto &[bx, by, bz] = b;
  ssize_t dx = ax - bx;
  ssize_t dy = ay - by;
  ssize_t dz = az - bz;
  return size_t(dx * dx + dy * dy + dz * dz);
}

using PList = std::vector<Point>;
using DMap = std::vector<std::pair<std::pair<size_t, size_t>, size_t>>;
using DSet = boost::unordered::unordered_flat_set<size_t>;

auto read() {
  auto rval = PList{};
  auto ih = std::ifstream{"08.txt"};
  auto line = std::string{};
  while (std::getline(ih, line)) {
    auto c1 = line.find(',');
    auto c2 = line.find(',', c1 + 1);
    rval.emplace_back(
        std::stoi(line.substr(0, c1)),
        std::stoi(line.substr(c1 + 1, c2 - c1 - 1)),
        std::stoi(line.substr(c2 + 1))
    );
  }
  return rval;
}

auto dmap(const PList &t) {
  auto rval = DMap{};
  for (auto a = size_t{}; a < t.size() - 1; ++a)
    for (auto b = a + 1; b < t.size(); ++b)
      rval.emplace_back(std::make_pair(a, b), distance(t.at(a), t.at(b)));
  return rval;
}

auto find(size_t c, std::vector<DSet> &sets) {
  for (auto i = sets.begin(); i != sets.end(); ++i)
    if (i->contains(c))
      return i;
  throw std::runtime_error{"can't find"};
}

auto part1(const PList &t, size_t count, const DMap &d) {
  auto circuits = std::vector<DSet>{};
  for (auto i = size_t{}; i < t.size(); ++i) {
    auto c = DSet{t.size()};
    c.insert(i);
    circuits.push_back(std::move(c));
  }

  for (auto i = size_t{}; i < count; ++i) {
    auto a = d.at(i).first.first;
    auto b = d.at(i).first.second;
    auto ac = find(a, circuits);
    auto bc = find(b, circuits);
    if (ac == bc)
      continue;
    ac->insert(bc->begin(), bc->end());
    circuits.erase(bc);
  }

  std::sort(circuits.begin(), circuits.end(), [](auto &a, auto &b) {
    return a.size() > b.size();
  });
  auto total = size_t{1};
  for (auto i = size_t{}; i < 3; ++i)
    total *= circuits.at(i).size();

  return total;
}

auto part2(const PList &t, const DMap &d) {
  auto circuits = std::vector<DSet>{};
  for (auto i = size_t{}; i < t.size(); ++i) {
    auto c = DSet{t.size()};
    c.insert(i);
    circuits.push_back(std::move(c));
  }

  for (auto i = size_t{}; i < d.size(); ++i) {
    auto a = d.at(i).first.first;
    auto b = d.at(i).first.second;
    auto ac = find(a, circuits);
    auto bc = find(b, circuits);
    if (ac == bc)
      continue;
    ac->insert(bc->begin(), bc->end());
    circuits.erase(bc);
    if (circuits.size() == 1) {
      return ssize_t(t.at(a).x) * ssize_t(t.at(b).x);
    }
  }
  throw std::runtime_error{"never joins?"};
}

} // namespace

auto main() -> int {
  auto t = read();
  BOOST_LOG_TRIVIAL(info) << "Day 8: read " << t.size();
  auto test = std::filesystem::current_path().filename().string() ==
              std::string{"test"};

  auto d = dmap(t);
  std::sort(d.begin(), d.end(), [](auto &a, auto &b) {
    return a.second < b.second;
  });

  BOOST_LOG_TRIVIAL(info) << "1: " << part1(t, test ? 10 : 1000, d);
  BOOST_LOG_TRIVIAL(info) << "2: " << part2(t, d);
}

What are we calling brute force here? Continuing to go through the pair list and merging groups? Is there any other way?

When I compare it to some other Uiua solutions on the Discord I feel like I'm still just banging rocks together.

That certainly doesn't reflect my mood today.

Thanks, 'Tis the season.

the trap

Re. what connections to process or not? That seems to be like one of those that's either completely obvious when you implement your solution one way, and a nasty pitfall when you do it another. In this case, pre-computing the list of pairs to process vs. finding the next one when you need it.

This is crazy concise and fast! Impressive.