Day 15: Lens Library
Megathread guidelines
- Keep top level comments as only solutions, if you want to say something other than a solution put it in a new post. (replies to comments can be whatever)
- Code block support is not fully rolled out yet but likely will be in the middle of the event. Try to share solutions as both code blocks and using something such as https://topaz.github.io/paste/ , pastebin, or github (code blocks to future proof it for when 0.19 comes out and since code blocks currently function in some apps and some instances as well if they are running a 0.19 beta)
FAQ
- What is this?: Here is a post with a large amount of details: https://programming.dev/post/6637268
- Where do I participate?: https://adventofcode.com/
- Is there a leaderboard for the community?: We have a programming.dev leaderboard with the info on how to join in this post: https://programming.dev/post/6631465
🔒 Thread is locked until there’s at least 100 2 star entries on the global leaderboard
Edit: 🔓 Unlocked
Haskell
Took a while to figure out what part 2 was all about. Didn’t have the energy to golf this one further today, so looking forward to seeing the other solutions!
Solution
0.3 line-seconds
import Data.Char import Data.List import Data.List.Split import qualified Data.Vector as V hash :: String -> Int hash = foldl' (\a c -> ((a + ord c) * 17) `rem` 256) 0 hashmap :: [String] -> Int hashmap = focus . V.toList . foldl' step (V.replicate 256 []) where focus = sum . zipWith focusBox [1 ..] focusBox i = sum . zipWith (\j (_, z) -> i * j * z) [1 ..] . reverse step boxes s = let (label, op) = span isLetter s i = hash label in case op of ['-'] -> V.accum (flip filter) boxes [(i, (/= label) . fst)] ('=' : z) -> V.accum replace boxes [(i, (label, read z))] replace ls (n, z) = case findIndex ((== n) . fst) ls of Just j -> let (a, _ : b) = splitAt j ls in a ++ (n, z) : b Nothing -> (n, z) : ls main = do input <- splitOn "," . head . lines <$> readFile "input15" print $ sum . map hash $ input print $ hashmap input
Nim
My whole solution is two words:
Ordered Table
Total runtime: 2 ms
Puzzle rating: exceptionally confusing description 4/10
Code:proc calcHash(s: string): int = for c in s: result = ((result + c.ord) * 17) mod 256 proc solve(lines: seq[string]): AOCSolution[int] = block p1: for line in lines: result.part1 += line.getHash() block p2: var boxes: array[256, OrderedTable[string, int]] for line in lines: if '=' in line: let (name, _, value) = line.partition("=") let boxInd = name.getHash() boxes[boxInd][name] = value.parseInt elif '-' in line: var name = line name.removeSuffix("-") let boxInd = name.getHash() boxes[boxInd].del(name) for bi, box in boxes: if box.len < 1: continue for li, val in enumerate(box.values): result.part2 += (bi+1) * (li+1) * val
Python
0.248 line-seconds (sixth simplest so far after days 6, 2, 1, 4 and 9).
Also on Github
import collections import re from .solver import Solver def _hash(string: str) -> int: result = 0 for c in string: result = (result + ord(c)) * 17 % 256 return result def _assert_full_match(pattern: str, string: str): m = re.fullmatch(pattern, string) if not m: raise RuntimeError(f'pattern {pattern} does not match {string}') return m class Day15(Solver): input: list[str] def __init__(self): super().__init__(15) def presolve(self, input: str): self.input = input.rstrip().split(',') def solve_first_star(self) -> int: return sum(_hash(string) for string in self.input) def solve_second_star(self) -> int: boxes = [collections.OrderedDict() for _ in range(256)] for instruction in self.input: label, op, value = _assert_full_match(r'([a-z]+)([=-])(\d*)', instruction).groups() box = boxes[_hash(label)] match op: case '-': if label in box: del box[label] case '=': box[label] = value return sum((1 + box_idx) * (1 + lens_idx) * int(value) for box_idx, box in enumerate(boxes) for lens_idx, (_, value) in enumerate(box.items()))
Scala3
def hash(s: String): Long = s.foldLeft(0)((h, c) => (h + c)*17 % 256) extension [A] (a: List[A]) def mapAtIndex(idx: Long, f: A => A): List[A] = a.zipWithIndex.map((e, i) => if i == idx then f(e) else e) def runProcedure(steps: List[String]): Long = @tailrec def go(boxes: List[List[(String, Int)]], steps: List[String]): List[List[(String, Int)]] = steps match case s"$label-" :: t => go(boxes.mapAtIndex(hash(label), _.filter(_._1 != label)), t) case s"$label=$f" :: t => go(boxes.mapAtIndex(hash(label), b => val slot = b.map(_._1).indexOf(label) if slot != -1 then b.mapAtIndex(slot, (l, _) => (l, f.toInt)) else (label, f.toInt) :: b ), t) case _ => boxes go(List.fill(256)(List()), steps).zipWithIndex.map((b, i) => b.zipWithIndex.map((lens, ilens) => (1 + i) * (b.size - ilens) * lens._2).sum ).sum def task1(a: List[String]): Long = a.head.split(",").map(hash).sum def task2(a: List[String]): Long = runProcedure(a.head.split(",").toList)
Had to take a couple days off, but this was a nice one to come back to. Will have to find some time today to go back and do one or two of the 3 that I missed. I don’t have much to say about this one - I had an idea almost immediately and it worked out without much struggle. There’s probably some cleaner ways to write parts of this, but I’m not too disappointed with how it turned out.
https://github.com/capitalpb/advent_of_code_2023/blob/main/src/solvers/day15.rs
use crate::Solver; use std::collections::HashMap; #[derive(Debug)] struct Lens { label: String, focal_length: u32, } fn hash_algorithm(input: &str) -> u32 { input .chars() .fold(0, |acc, ch| (acc + ch as u32) * 17 % 256) } pub struct Day15; impl Solver for Day15 { fn star_one(&self, input: &str) -> String { input .trim_end() .split(',') .map(hash_algorithm) .sum::() .to_string() } fn star_two(&self, input: &str) -> String { let mut boxes: HashMap> = HashMap::new(); for instruction in input.trim_end().split(',') { let (label, focal_length) = instruction .split_once(|ch| char::is_ascii_punctuation(&ch)) .unwrap(); let box_number = hash_algorithm(label); let lenses = boxes.entry(box_number).or_insert(vec![]); if focal_length == "" { lenses.retain(|lens| lens.label != label); continue; } let new_lens = Lens { label: label.to_string(), focal_length: focal_length.parse().unwrap(), }; if let Some(lens_index) = lenses.iter().position(|lens| lens.label == new_lens.label) { lenses[lens_index].focal_length = new_lens.focal_length; } else { lenses.push(new_lens); } } boxes .iter() .map(|(box_number, lenses)| { lenses .iter() .enumerate() .map(|(lens_index, lens)| { (box_number + 1) * (lens_index as u32 + 1) * lens.focal_length }) .sum::() }) .sum::() .to_string() } }
Rust
Part 1 was super simple with
wrapping_add
andwrapping_mul
on au8
. Building an actual hash map in Part 2 was nice.That array initialisation is pure poetry! 😄
I’m not fluent in Rust, but is this something like the C++ placement new? Presumably just declaring a table of Vecs won’t automatically call the default constructor? (Sorry for my total ignorance – pointers to appropriate reading material appreciated)
You can create an array filled with all the same values in Rust, but only if all values have the same memory representation because they will be copied. That just doesn’t work with Vec’s, because they must all have their own unique pointer. And to have uninitialized values at first (think NULL-pointers for every Vec) while creating each Vec, something like this is apparently needed.
The appropriate way would certainly have been to store the map as a
Vec>
instead of an array, but I just wanted to see if could.
C
Yes, it’s a hash table. Did I pick a language with built in hash tables? Of course I didn’t. Could I have used one of the many libraries implementing one? Sure. But the real question is, can we make do with stuffing things into a few static arrays at nearly zero memory and runtime cost? Yes!
In the spirit of Fred Brooks, it’ll suffice here to show my data structures:
struct slot { char label[8]; int lens; }; struct box { struct slot slots[8]; int nslots; }; static struct box boxes[256];
This felt … too simple. I think the hardest part of part two for me was reading comprehension. My errors were typically me not reading exactly was there.
Python
import re import math import argparse import itertools def int_hash(string:str) -> int: hash = 0 for c in [*string]: hash += ord(c) hash *= 17 hash = hash % 256 return hash class Instruction: def __init__(self,string:str) -> None: label,action,strength = re.split('([-=])',string) self.label = label self.action = action if not strength: strength = 0 self.strength = int(strength) def __repr__(self) -> str: return f"Instruction(l={self.label}, a={self.action}, s={self.strength})" def __str__(self) -> str: stren = str(self.strength if self.strength > 0 else '') return f"{self.label}{self.action}{stren}" class Lens: def __init__(self,label:str,focal_length:int) -> None: self.label:str = label self.focal_length:int = focal_length def __repr__(self) -> str: return f"Lens(label:{self.label},focal_length:{self.focal_length})" def __str__(self) -> str: return f"[{self.label} {self.focal_length}]" def main(line_list:str,part:int): init_sequence = line_list.splitlines(keepends=False)[0].split(',') sum = 0 focal_array = dict[int,list[Lens]]() for i in range(0,256): focal_array[i] = list[Lens]() for s in init_sequence: hash_value = int_hash(s) sum += hash_value # part 2 stuff action = Instruction(s) position = int_hash(action.label) current_list = focal_array[position] existing_lens = list(filter(lambda x:x.label == action.label,current_list)) if len(existing_lens) > 1: raise Exception("multiple of same lens in box, what do?") match action.action: case '-': if len(existing_lens) == 1: current_list.remove(existing_lens[0]) case '=': if len(existing_lens) == 0: current_list.append(Lens(action.label,action.strength)) if len(existing_lens) == 1: existing_lens[0].focal_length = action.strength case _: raise Exception("unknown action") print(f"Part1: {sum}") #print(focal_array) sum2 = 0 for i,focal_box in focal_array.items(): for l,lens in enumerate(focal_box): sum2 += ( (i+1) * (l+1) * lens.focal_length ) print(f"Part2: {sum2}") if __name__ == "__main__": parser = argparse.ArgumentParser(description="template for aoc solver") parser.add_argument("-input",type=str) parser.add_argument("-part",type=int) args = parser.parse_args() filename = args.input if filename == None: parser.print_help() exit(1) part = args.part file = open(filename,'r') main(file.read(),part) file.close()
Nim
Almost caught up. Not much to say about this one. Part 1 was a freebie. Part 2 had a convoluted description, but was still pretty easy.