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
1 point
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.
1 point
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];
1 point
*
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()
1 point
*
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()))