this post was submitted on 15 Dec 2023
14 points (93.8% liked)

Advent Of Code

770 readers
1 users here now

An unofficial home for the advent of code community on programming.dev!

Advent of Code is an annual Advent calendar of small programming puzzles for a variety of skill sets and skill levels that can be solved in any programming language you like.

AoC 2023

Solution Threads

M T W T F S S
1 2 3
4 5 6 7 8 9 10
11 12 13 14 15 16 17
18 19 20 21 22 23 24
25

Rules/Guidelines

Relevant Communities

Relevant Links

Credits

Icon base by Lorc under CC BY 3.0 with modifications to add a gradient

console.log('Hello World')

founded 1 year ago
MODERATORS
14
submitted 11 months ago* (last edited 11 months ago) by Ategon to c/advent_of_code
 

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


πŸ”’ Thread is locked until there's at least 100 2 star entries on the global leaderboard

Edit: πŸ”“ Unlocked

top 18 comments
sorted by: hot top controversial new old
[–] [email protected] 5 points 11 months ago (1 children)

Rust

Part 1 was super simple with wrapping_add and wrapping_mul on a u8. Building an actual hash map in Part 2 was nice.

[–] [email protected] 2 points 11 months ago (1 children)

That array initialisation is pure poetry! πŸ˜„

[–] [email protected] 2 points 11 months ago (1 children)

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)

[–] [email protected] 1 points 11 months ago (1 children)

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.

[–] [email protected] 1 points 11 months ago

Ah, I see! Thank you.

[–] [email protected] 4 points 11 months ago* (last edited 11 months ago)

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!

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

[–] [email protected] 4 points 11 months ago

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];

https://github.com/sjmulder/aoc/blob/master/2023/c/day15.c

[–] cvttsd2si 4 points 11 months ago

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)
[–] [email protected] 3 points 11 months ago* (last edited 3 months ago)

Python

0.248 line-seconds (sixth simplest so far after days 6, 2, 1, 4 and 9).

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()))
[–] capitalpb 3 points 11 months ago

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()
    }
}
[–] [email protected] 3 points 11 months ago* (last edited 11 months ago) (1 children)

Dart

Just written as specced. If there's any underlying trick, I missed it totally.

9ms * 35 LOC ~= 0.35, so it'll do.

int decode(String s) => s.codeUnits.fold(0, (s, t) => ((s + t) * 17) % 256);

part1(List lines) => lines.first.split(',').map(decode).sum;

part2(List lines) {
  var rules = lines.first.split(',').map((e) {
    if (e.contains('-')) return ('-', e.skipLast(1), 0);
    var parts = e.split('=');
    return ('=', parts.first, int.parse(parts.last));
  });
  var boxes = Map.fromEntries(List.generate(256, (ix) => MapEntry(ix, [])));
  for (var r in rules) {
    if (r.$1 == '-') {
      boxes[decode(r.$2)]!.removeWhere((l) => l.$1 == r.$2);
    } else {
      var box = boxes[decode(r.$2)]!;
      var lens = box.indexed().firstWhereOrNull((e) => e.value.$1 == r.$2);
      var newlens = (r.$2, r.$3);
      (lens == null) ? box.add(newlens) : box[lens.index] = newlens;
    }
  }
  return boxes.entries
      .map((b) =>
          (b.key + 1) *
          b.value.indexed().map((e) => (e.index + 1) * e.value.$2).sum)
      .sum;
}
[–] [email protected] 2 points 11 months ago (1 children)

9ms * 35 LOC is ~0.350 tho

[–] [email protected] 2 points 11 months ago

That’s why I normally let computers do my sums for me. Corrected now.

[–] purplemonkeymad 3 points 11 months ago* (last edited 11 months ago)

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.

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

[–] [email protected] 2 points 11 months ago (1 children)

Haskell

import Data.Array
import qualified Data.ByteString.Char8 as BS
import Data.Char (isAlpha, isDigit)
import Relude
import qualified Relude.Unsafe as Unsafe
import Text.ParserCombinators.ReadP hiding (get)

hash :: String -> Int
hash = foldl' (\a x -> (a + x) * 17 `mod` 256) 0 . fmap ord

part1 :: ByteString -> Int
part1 = sum . fmap (hash . BS.unpack) . BS.split ',' . BS.dropEnd 1

-- Part 2

type Problem = [Operation]

type S = Array Int [(String, Int)]

data Operation = Set String Int | Remove String deriving (Show)

parse :: BS.ByteString -> Maybe Problem
parse = fmap fst . viaNonEmpty last . readP_to_S parse' . BS.unpack
  where
    parse' = sepBy parseOperation (char ',') <* char '\n' <* eof
    parseOperation =
      munch1 isAlpha
        >>= \label -> (Remove label <$ char '-') +++ (Set label . Unsafe.read <$> (char '=' *> munch1 isDigit))

liftOp :: Operation -> Endo S
liftOp (Set label v) = Endo $ \s ->
  let (b, a) = second (drop 1) $ span ((/= label) . fst) (s ! hash label)
   in s // [(hash label, b <> [(label, v)] <> a)]
liftOp (Remove l) = Endo $ \s -> s // [(hash l, filter ((/= l) . fst) (s ! hash l))]

score :: S -> Int
score m = sum $ join [(* (i + 1)) <$> zipWith (*) [1 ..] (snd <$> (m ! i)) | i <- [0 .. 255]]

part2 :: ByteString -> Maybe Int
part2 input = do
  ops <- appEndo . foldMap liftOp . reverse <$> parse input
  pure . score . ops . listArray (0, 255) $ repeat []
[–] [email protected] 2 points 11 months ago

Nice use of foldMap!

[–] [email protected] 2 points 11 months ago

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.

[–] [email protected] 2 points 11 months ago* (last edited 11 months ago)

Nim

My whole solution can be expressed in just two words: Ordered HashTable

Total runtime: 0.068 line-seconds (40 LOC * 1.7 ms)
Puzzle rating: exceptionally confusing description 4/10
Code: cleaned up solution with types
Snippet:

proc getHash(s: string): int =
  for c in s:
    result = ((result + c.ord) * 17) mod 256

proc solve(lines: seq[string]): AOCSolution[int] =
  var boxes: array[256, OrderedTable[string, int]]
  for line in lines:
    block p1:
      result.part1 += line.getHash()

    block p2:
      if line.endsWith('-'):
        var name = line.strip(leading=false, chars={'-'})
        boxes[getHash(name)].del(name)
      else:
        let (name, _, value) = line.partition("=")
        boxes[getHash(name)][name] = value[0].ord - '0'.ord

  for bi, box in boxes:
    if box.len < 1: continue
    for vi, val in enumerate(box.values):
      result.part2 += (bi+1) * (vi+1) * val