Advent of Code 2023

Like last year (>>33531), let us post about the Advent of Code (https://adventofcode.com/2023) and flex our various programming muscles. First day is incredibly cheeky this year, but don't loose hope Anon! Part 2 protip: sevenine parses as 7 9 Here's my part 1 and 2 in Common Lisp (using alexandria, arrow-macros, iterate, cl-ppcre, trivia and my homegrown library): (defun line->num (line) (let* ((digits (cl-ppcre:all-matches-as-strings "[1-9]" line)) (first (first digits)) (last (last-elt digits))) (parse-integer (concat-strings first last)))) (format t "~A~%" (iter (for line in-file (car uiop:*command-line-arguments*) using #'read-line) (sum (line->num line)))) (defparameter *digit-map* (make-hash-table :test 'equal)) (defparameter *digit-scanner* nil) (iter (for i from 1 to 9) (for digit = (format nil "~R" i)) (setf (gethash digit *digit-map*) (format nil "~S" i)) (collect digit into digit-list) (finally (setf *digit-scanner* (cl-ppcre:create-scanner (concat-strings "(?=(" (apply #'join-strings #\| "[1-9]" digit-list) "))"))))) (defun line->num (line) (flet ((match->digit (m) (if (= (length m) 1) m (gethash m *digit-map*)))) (let* ((digits (let (acc) (cl-ppcre:do-register-groups (m) (*digit-scanner* line (nreverse acc)) (push m acc)))) (first (first digits)) (last (last-elt digits))) (parse-integer (concat-strings (match->digit first) (match->digit last)))))) (format t "~A~%" (iter (for line in-file (car uiop:*command-line-arguments*) using #'read-line) (sum (line->num line)))) PS: don't forget to replace your tabs with spaces before posting code in here

I was worried that Lainchan forgot about Advent of Code, so I'm very glad to see this thread! I'm mainly using Common Lisp this year, which I'm relatively new to, so I'm writing utilities as I go, to sharpen my skills. I wonder if I'll hit a wall where I can't avoid the usage of regular expressions. >>37777 I see you used ~R. Neat! I completely forgot about it and spelled out the numbers myself. Here are my solutions for day 2: (defparameter constraints '((red . 12) (green . 13) (blue . 14))) (defun possible-set-p (set) (every (lambda (n&c) (<= (car n&c) (cdr (assoc (cadr n&c) constraints)))) set)) (defun read-sets (line) (mapcar (lambda (str) (group-n 2 (with-input-from-string (s str) (read-list s)))) (split-on #\; (nsubstitute #\Space #\, (subseq-after #\: line))))) (defsolver 2 1 (file) (let ((id 1) (sum 0)) (dolines (ln file) (let ((sets (read-sets ln))) (if (every #'possible-set-p sets) (and (incf sum id) (print sets)))) (incf id)) sum)) (defsolver 2 2 (file) (let ((sum 0)) (dolines (ln file) (let ((cubes (apply #'append (read-sets ln)))) (loop for (n color) in cubes if (eq 'red color) maximize n into red else if (eq 'green color) maximize n into green else maximize n into blue finally (incf sum (* red green blue))))) sum))

In case anyone will find this helpful: The description of Part 1 of Day 2 is ambiguous. It says: > In game 1, three sets of cubes are revealed from the bag (and then put back again). What is meant is that *each set* is revealed and then put back, so during each game you put back right after you reveal a set. But I initially incorrectly interpreted it as "all sets are revealed and then put back all at once".

>>37784 Oh, lucky I didn't fall into that. Guess I intuited the game logic properly. Only posting part 2, since it's almost the same as 1: (defstruct (cubes (:conc-name "")) (red 0 :type (integer 0)) (green 0 :type (integer 0)) (blue 0 :type (integer 0))) (defun parse-game-log (line) (iter (for handful in (split-string "; " line :start (+ (position #\: line) 2))) (collect (let ((cubes (make-cubes))) (cl-ppcre:do-register-groups (count color) ("([0-9]+) ([^,]+)(?=, )?" handful cubes) (assert (and count color)) ;; silence warnings (setf (slot-value cubes (case (aref color 0) (#\r 'red) (#\g 'green) (#\b 'blue))) (parse-integer count))))))) (defun minimum-bag (game-data) (iter (for handful in game-data) (maximize (red handful) into red) (maximize (green handful) into green) (maximize (blue handful) into blue) (finally (return (make-cubes :red red :green green :blue blue))))) (format t "Power sum: ~A~%" (iter (for line in-file (car uiop:*command-line-arguments*) using #'read-line) (for game-id from 1) (for game-data = (parse-game-log line)) (for min-bag = (minimum-bag game-data)) (sum (* (red min-bag) (green min-bag) (blue min-bag))))) Nobody else?

Day 2 in Haskell hs {-# LANGUAGE OverloadedStrings #-} import qualified Data.Text as T import Data.Map unpackInt :: T.Text -> Int unpackInt = read . T.unpack parseLine = fmap (fmap (readLinePair . reverse . T.words) . T.splitOn ",") . T.splitOn ";" . T.drop 1 . T.dropWhile (/= ':') where readLinePair [a,b] = (a, unpackInt b) checkLineOne = any (any checkOne) . parseLine where checkOne ("red", b) = b > 12 checkOne ("green", b) = b > 13 checkOne ("blue", b) = b > 14 partTwo = sum . fmap (product . unionsWith max . fmap fromList . parseLine) . T.lines partOne dat = sum [if ls !! (x - 1) then 0 else x | x <- [1..(length ls)] ] where ls = (fmap checkLineOne . T.lines) dat main = do dat <- readFile "input.txt" print $ "Part 1: " ++ (show . partOne . T.pack) dat print $ "Part 2: " ++ (show . partTwo . T.pack) dat

>>37783 Nice. Started with an alist with keywords too but went for a struct after that. You should try iterate, I've completely stopped using loop since I did! >>37787 Damn, you make me painfully aware of how painful text processing is in CL.

>>37777 Is it worth trying Haskell to do advent of code? I /am/ unemployed right now, but probably not for much longer.

>>37792 Can't decide for you, but I can help you think about it. Potential reasons to learn such a niche language here: 1) It's fun. For me, using CL is just quite fun, even with all its warts; I think Haskell can be fun for people who like ML type systems. 2) It's useful. Doubtful, unless you want a career in academics. 3) It's mind expanding. Especially when you've never used more than enterprise drone tier stuff like C/C++, C#, Java, Go or Rust.

>>37792 Oh, and some people start with an alien PL and switch to something more familiar once the going gets too rough.

Day 3 in CL. Could have used a multidimensional char array (would have needed displaced strings to do my parse-integer, though), could have surrounded the original map with dots to avoid bound checking, could have... But whatever, it works. At least, I only parse numbers I need. (defparameter *map* (list->vector (uiop:read-file-lines (car uiop:*command-line-arguments*)))) (defparameter *map-height* (length *map*)) (defparameter *map-width* (length (aref *map* 0))) (defun find-numbers () (iter (for line in-vector *map*) (for x from 0) (cl-ppcre:do-matches (start end "[0-9]+" line) (collect `(,x ,start . ,end))))) (defun number-value (numpos) (destructuring-bind (x yfrom . yto) numpos (parse-integer (aref *map* x) :start yfrom :end yto))) (defun part-p (numpos) (iter (with (nx nyfrom . nyto) = numpos) (for x from (max 0 (- nx 1)) to (min (- *map-height* 1) (+ nx 1))) (if (find-if (lambda (c) (and (not (alphanumericp c)) (char/= c #\.))) (aref *map* x) :start (max 0 (- nyfrom 1)) :end (min (- *map-width* 1) (+ nyto 1))) (return t)))) (defun find-parts (number-map) (remove-if-not #'part-p number-map)) (defun sum-parts (part-map) (-<>> part-map (mapcar #'number-value) (reduce #'+))) (defun mark-stars (numpos star-map) (iter (with (nx nyfrom . nyto) = numpos) (for x from (max 0 (- nx 1)) to (min (- *map-height* 1) (+ nx 1))) (dolist (y (position-all #\* (aref *map* x) :start (max 0 (- nyfrom 1)) :end (min (- *map-width* 1) (+ nyto 1)))) (push numpos (gethash (cons x y) star-map))))) (defun find-gears (number-map) (iter (with star-map = (make-hash-table :test 'equal)) ;; star pos -> nearby part count (for numpos in number-map) (mark-stars numpos star-map) (finally (return (iter (for (key val) in-hashtable star-map) (when (= (length val) 2) (collect val))))))) (defun sum-gear-ratios (gear-map) (iter (for (part1 part2) in gear-map) (sum (* (number-value part1) (number-value part2))))) (let ((number-map (find-numbers))) (format t "Engine part sum: ~A~%" (sum-parts (find-parts number-map))) (format t "Gear ratio sum: ~A~%" (sum-gear-ratios (find-gears number-map))))

Day 3 in Haskell import Data.Char (isDigit) import Text.Read (readMaybe) import Data.Array import Data.Maybe (catMaybes, mapMaybe) import Data.List (nub) type Index2D = (Int, Int) cartProduct :: [a] -> [b] -> [(a,b)] cartProduct xs ys = [(x, y) | x <- xs, y <- ys] numberLen :: String -> Int numberLen s = numberLenIter s 0 where numberLenIter "" i = i numberLenIter s i = if (isDigit . head) s then numberLenIter (tail s) (i + 1) else i isPrefixNumber :: String -> Bool isPrefixNumber x = numberLen x > 0 lineToInts :: String -> [Maybe Int] lineToInts "" = [] lineToInts s = let nl = numberLen s in if nl > 0 then (replicate nl . (readMaybe :: String -> Maybe Int) . take nl) s ++ lineToInts (drop nl s) else Nothing:(lineToInts . tail) s maybeIntsToArray :: [[Maybe Int]] -> Array Index2D (Maybe Int) maybeIntsToArray is = listArray ((1,1), (w, h)) $ concat is where w = (length . head) is h = length is neighbourhood :: Index2D -> Index2D -> [Index2D] neighbourhood (x, y) (boundsX, boundsY) = filter ((`elem` [1..boundsY]) . snd) . filter ((`elem` [1..boundsX]) . fst) $ cartProduct [x - 1 .. x + 1] [y - 1 .. y + 1] isSymbol :: Char -> Bool isSymbol x = not $ isDigit x || x == '.' findValidNums :: [String] -> [Maybe Int] findValidNums rawSymbols = concatMap (nub . fmap (ints !) . (`neighbourhood` (w,h)) . fst) . filter (isSymbol . snd) $ assocs syms where w = (length . head) rawSymbols h = length rawSymbols ints = (maybeIntsToArray . fmap lineToInts) rawSymbols syms = listArray ((1,1), (w, h)) $ concat rawSymbols partTwo :: [String] -> Int partTwo rawSymbols = sum . fmap product . filter (\x -> length x == 2) . fmap (nub . mapMaybe (ints !) . (`neighbourhood` (w,h)) . fst) . filter ((=='*') . snd) $ assocs syms where w = (length . head) rawSymbols h = length rawSymbols ints = (maybeIntsToArray . fmap lineToInts) rawSymbols syms = listArray ((1,1), (w, h)) $ concat rawSymbols main = do dat <- readFile "input.txt" print $ "Part 1: " ++ (show . sum . catMaybes . findValidNums . lines) dat print $ "Part 2: " ++ (show . partTwo . lines) dat

>>37801 Those are some serious line lengths...

>>37777 I was kicked off /g/'s private leaderboard for being too slow. Maybe aoc is too hard for a beginner like myself. I just want to get gud. It took me like 4 years to get good at guitar, but it's been like a year and I really thought I'd be able to tackle this stuff by now

>>37804 That leaderboard is a joke anyway, since it relies on you being in the US timezone. But why don't you post (or are you the Haskell guy)?

My first year giving it a go I am using python, here is my code for all the days so far: 1.1) from typing import Tuple def search_first(line: str) -> int: return int(line[0]) if line[0].isnumeric() else search_first(line[1:]) def search_last(line: str) -> int: return int(line[-1]) if line[-1].isnumeric() else search_last(line[:-1]) def search_first_last_v1(line: str) -> Tuple[int, int]: return search_first(line), search_last(line) FILE = 'puzzle_data' # FILE = 'puzzle_data_test' file_contents = [] with open(FILE, 'r') as file: file_contents = file.readlines() acc = 0 for line in file_contents: first, last = search_first_last_v1(line) acc += first * 10 + last print(acc) 1.2) from typing import Tuple map_str_number = { 'one': 1, 'two': 2, 'three': 3, 'four': 4, 'five': 5, 'six': 6, 'seven': 7, 'eight': 8, 'nine': 9, 'zero': 0, } def search_first(line: str) -> int: for key in map_str_number.keys(): if line.startswith(key): return map_str_number[key] return int(line[0]) if line[0].isnumeric() else search_first(line[1:]) def search_last(line: str) -> int: for key in map_str_number.keys(): if line.endswith(key): return map_str_number[key] return int(line[-1]) if line[-1].isnumeric() else search_last(line[:-1]) def search_first_last_v1(line: str) -> Tuple[int, int]: return search_first(line), search_last(line) FILE = 'puzzle_data' # FILE = 'puzzle_data_test_2' file_contents = [] with open(FILE, 'r') as file: file_contents = file.readlines() acc = 0 for line in file_contents: first, last = search_first_last_v1(line) acc += first * 10 + last print(acc)

>>37777 day 4 code (both parts, Python 3) f = open("input").read().strip().split('\n') p1 = 0 dp = [1] * len(f) for i, x in enumerate(f): win, num = x.split(':')[1].strip().split('|') win = { s for s in win.split() } num = [ s for s in num.split() ] matches = len([ s for s in num if s in win ]) # part 1 if matches: p1 += 2 ** (matches - 1) # part 2 (simple dp) for j in range(matches): dp[i + j + 1] += dp[i] print(p1) print(sum(dp)) -------Part 1-------- -------Part 2-------- Day Time Rank Score Time Rank Score 4 00:05:40 976 0 00:19:08 2005 0 3 00:13:12 608 0 00:31:43 1599 0 2 00:12:13 1951 0 00:18:44 2485 0 1 00:04:36 1787 0 00:19:44 1708 0 first time posting here, i hope the code tags work

Is there really no cool way to do pt 2? All the ways I've seen feel icky.

>>37811 tabular dp: dp = [1] * n for i in range(n): for j in range(matches[i]): dp[i + j + 1] += dp[i] p2 = sum(dp)

Day 4. Took me far less time than previous days. Probably because I had already written all utilities that I used to read cards. Although, I had to add SUBMAPCAR and NLENGTHEN. (defstruct card my-nums win-nums) (defun read-card (line) (destructuring-bind (left right) (split-on #\| (subseq-after #\: line)) (make-card :my-nums (read-list-from-string right) :win-nums (read-list-from-string left)))) (defun count-matches (card) (with-slots (my-nums win-nums) card (length (intersection my-nums win-nums)))) ;;; Part 1 (defun card-score (card) (let ((n (count-matches card))) (if (> n 0) (expt 2 (1- n)) 0))) (defsolver 4 1 (file) (let ((total 0)) (dolines (ln file) (incf total (card-score (read-card ln)))) total)) ;;; Part 2 (defsolver 4 2 (file) (let ((total 0) ; maintain a list of card copy counts following the current card (copies (list))) (dolines (ln file) (let ((nmatches (count-matches (read-card ln))) (ncards (1+ (or (pop copies) 0)))) (incf total ncards) ; SUBMAPCAR will map only the first NMATCHES copy counts (setf copies (submapcar (lambda (n) (+ n ncards)) (nlengthen copies nmatches :initial-element 0) :end nmatches)))) total))

Not my prettiest code, but who cares, eh. fuarrrking tired from work. (defun parse-card (line) (let* ((start-pos (+ (position #\: line) 1)) (split-pos (position #\| line))) (cons (read-all-from-string line :start start-pos :end (- split-pos 1)) (read-all-from-string line :start (+ split-pos 1))))) (defun card-win-count (card) (length (intersection (car card) (cdr card)))) (defun card-score (win-count) (if (zerop win-count) 0 (expt 2 (- win-count 1)))) (iter (for line in-file (car uiop:*command-line-arguments*) using #'read-line) (collect (card-win-count (parse-card line)) into card-win-counts result-type vector) (finally (format t "Score sum: ~A~%" (reduce #'+ (map 'list #'card-score card-win-counts))) (format t "Number of cards: ~A~%" (iter outer (with card-tally = (make-array (length card-win-counts) :initial-element 1)) (for cur-tally in-vector card-tally with-index i) (sum cur-tally) (iter (for j from i to (+ i (aref card-win-counts i))) (in outer (incf (aref card-tally j) cur-tally))))))) >>37811 Indeed, if someone has the formula, I'm taking. >>37813 Feels a little overkill to make a struct when you only need to track the count of winning numbers? But well, you don't know what part 2 has in store for you, when starting... I'll probably borrow your subseq-after, looks useful.

>>37812 Yeah, that's basically what I have… I thought there might be a cool trick.

>>37815 that is the trick, i don't think it can be done faster $ time python3 code.py 33950 14814534 real 0m0.010s user 0m0.010s sys 0m0.000s what's icky about dp? tabular dp is pure

>>37815 I dont know. Just feels kinda ugly to me for such a simple problem

day 5 part 2 is tough, nocoders are finished

day 5 part 2 (efficient) f = open("HxnN.txt").read().strip().split('\n') def merge(arr: list) -> list: ret = [] arr.sort() a, b = arr[0] for p in arr: if p[0] <= b: b = max(b, p[1]) continue ret.append((a, b)) a, b = p ret.append((a, b)) return ret def translate(arr: list, translations: list) -> list: ret = [] for translation in translations: tmp = [] a, b, offset = translation for p in arr: if p[0] >= b or p[1] < a: tmp.append(p) continue if a <= p[0] <= p[1] <= b: ret.append((p[0] + offset, p[1] + offset)) continue if p[0] <= a <= b <= p[1]: ret.append((a + offset, b + offset)) tmp.append((p[0], a)) tmp.append((b, p[1])) continue if p[0] <= a <= p[1] <= b: ret.append((a + offset, p[1] + offset)) tmp.append((p[0], a)) continue if a <= p[0] <= b <= p[1]: ret.append((p[0] + offset, b + offset)) tmp.append((b, p[1])) arr = tmp arr.sort() for p in arr: ret.append(p) return merge(ret) s2s, s2f, f2w, w2l, l2t, t2h, h2l = [], [], [], [], [], [], [] i = 2 while i < len(f): line = f[i] i += 1 while i < len(f): translation = f[i] i += 1 if not translation: break d, s, r = map(int, translation.split()) translation = ( s, s + r, d - s ) match line.split('-')[2].split()[0]: case "soil": s2s.append(translation) case "fertilizer": s2f.append(translation) case "water": f2w.append(translation) case "light": w2l.append(translation) case "temperature": l2t.append(translation) case "humidity": t2h.append(translation) case "location": h2l.append(translation) seeds = list(map(int, f[0][len("seeds: "):].split())) solution = [] for i in range(0, len(seeds), 2): solution.append((seeds[i], seeds[i] + seeds[i + 1])) solution = translate(solution, s2s) solution = translate(solution, s2f) solution = translate(solution, f2w) solution = translate(solution, w2l) solution = translate(solution, l2t) solution = translate(solution, t2h) solution = translate(solution, h2l) print("gold:", solution[0][0]) bigboy #5 url: https://0x0.st/HxnN.txt size: 424K silver: 11056616 gold: 101900923 $ time python3 code.py gold: 100062714 real0m2.531s user0m2.527s sys0m0.004s

>>37826 RIP indentation, here's a Carbon render instead todays experience should remind me to do more range problems

Why bother when you have SBCL at hand? Didn't even try to look at the incredibly detailed compiler output, just peppered some feelgood declarations here and there. (declaim (optimize (speed 3) (debug 0) (safety 0))) ;; Vroom vroom! (deftype fixnum>=0 () `(integer 0 ,most-positive-fixnum)) (defstruct (range (:conc-name nil)) (src-start 0 :type fixnum>=0) (dst-start 0 :type fixnum>=0) (width 0 :type fixnum>=0)) ;; cl:length conflict (defun parse-range (line) (let ((nums (read-all-from-string line))) (make-range :src-start (second nums) :dst-start (first nums) :width (third nums)))) (defun parse-map (lines) (-<>> (cdr lines) (mapcar #'parse-range) (sort <> #'< :key #'src-start))) (defun parse-almanac (lines) (let ((map-lines (split-on "" lines :test #'string= :start 2)) (seeds (read-all-from-string (car lines) :start (position #\Space (car lines))))) (cons seeds (mapcar #'parse-map map-lines)))) (declaim (inline translate-id) (ftype (function (fixnum>=0 list) fixnum>=0) translate-id)) (defun translate-id (id map) (iter (for (the range r) in map) (for (the fixnum d) = (- id (src-start r))) (cond ((< d 0) (return id)) ((< d (width r)) (return (+ d (dst-start r))))) (finally (return id)))) (declaim (ftype (function (fixnum>=0 list) fixnum>=0) find-location)) (defun find-location (id maps) (if maps (find-location (translate-id id (car maps)) (cdr maps)) id)) (let* ((lines (uiop:read-file-lines (car uiop:*command-line-arguments*))) (almanac (parse-almanac lines))) (destructuring-bind (seeds . maps) almanac (format t "Lowest location number (pt1): ~A~%" (iter (for s in seeds) (minimize (find-location s maps)))) (format t "Lowest location number (pt2): ~A~%" (iter outer (for (sstart srange) on seeds by #'cddr) (iter (for s from sstart to (+ sstart srange)) (in outer (minimize (find-location s maps)))))))) $ time sbcl --load prog.lisp --eval '(quit)' input Lowest location number (pt1): 173706076 Lowest location number (pt2): 11611182 sbcl --noinform --load prog.lisp --eval '(quit)' input 213.95s user 0.05s system 99% cpu 3:34.02 total I'm not dumb, but way too tired for this soykaf. By the way, am I delusional or this is getting hard way faster than last year?

I quickly made some bad python code for 5.2 and left for work with it running. It worked, but I feel like I cheated this. I think I have several ideas for optimized algorithm, might try it later.

I reused my 5.1 solution for 5.2 and it worked, but took almost 30 minutes. Needless to say, it didn't feel good. So I made an attemp at compiling the maps into a single one - seed-to-location, but ran out of waking time. Going to try again while keeping up with new problems.

Is it me or is day 6 actually the easiest thus far? I might have not made the most optimized code for 6.2, but it took only about 9 seconds for my potato to solve it.

>>37834 easiest *recent* day, 2 was easier imho

I'm trying to solve Day 6 by solving a quadratic inequality, but for some reason the solution for Part 2 is off by 3 and I can't understand why. Time: 54817088 Distance: 446129210351007 Correct Answer: 34934171 Incorrect Answer: 34934174 ;; solve x^2 - tx + d < 0 (defun win-ways/math (time distance) (let* ((a 1) (b (- time)) (c distance) (discrim (- (expt b 2) (* 4 a c)))) (cond ((plusp discrim) (let ((x1 (/ (- (- b) (sqrt discrim)) (* 2 a))) (x2 (/ (+ (- b) (sqrt discrim)) (* 2 a)))) (values (1+ (- (ceiling (1- x2)) (floor (1+ x1)))) (list x1 x2)))) ; this branch is never taken ((zerop discrim) (let ((x (- (/ b (* 2 a))))) (if (> (* x (- time x)) distance) x nil))) (t nil))))

>>37830 >>37833 I did the same and I don't think it's cheating. I anticipated some fuarrrkery when I was solving 5.1 so I sorted the mappings and used binary search. In total both solutions ended up taking under 6 minutes, which is way less time than it would have taken me to think up a better solution and to implement it. >>37834 Yeah I agree, it was a nice relief. >>37838 If x1<x2 are your bounds, then if you set x=x1 or x=x2, your boat will tie exactly with the winner. The problem didn't have any rules on tying, so I assumed it wouldn't be a problem, and that x1 and x2 are not whole. So I set X1=ceil(x1), X2=floor(x2). Then, any integer x satisfying X1<=x<=X2 is a solution. Think about it and realise that there are X2-X1+1 such possible integer values of x. Here is my code: ```go criticalMinus := (-time - math.Sqrt(math.Pow(time, 2)-4*distance)) / -2 criticalPlus := (-time + math.Sqrt(math.Pow(time, 2)-4*distance)) / -2 // inspected manually to see which is the lower bound and which is the upper bound criticalPlus = math.Ceil(criticalPlus) criticalMinus = math.Floor(criticalMinus) fmt.Println(int(criticalMinus) - int(criticalPlus) + 1) ```

>>37839 I translated your Go code into Common Lisp and the answer is off by 4. There must be something about arithmetic in Common Lisp that I don't know about. (defun solve (time distance) (let* ((q (sqrt (- (expt time 2) (* 4 distance)))) (crit-minus (/ (- (- time) q) (- 2))) (crit-plus (/ (+ (- time) q) (- 2)))) (1+ (- (truncate (floor crit-minus)) (truncate (ceiling crit-plus))))))

(defun parse-race-logs (lines) (mapcar #'cons (read-all-from-string (first lines) :after #\:) (read-all-from-string (second lines) :after #\:))) (defun winning-range (race-data) (destructuring-bind (tm . rc) race-data (let ((√Δ (sqrt (- (* tm tm) (* 4 (+ rc 1)))))) (cons (ceiling (+ (- tm) √Δ) -2) (floor (- (- tm) √Δ) -2))))) (defun incl-range-length (range) (+ (- (cdr range) (car range)) 1)) (defun concat-integers (&rest numbers) (parse-integer (format nil "~{~D~}" numbers))) (let* ((lines (uiop:read-file-lines (car uiop:*command-line-arguments*))) (races-data (parse-race-logs lines))) (format t "Part 1: ~A~%" (-<>> races-data (mapcar #'winning-range) (mapcar #'incl-range-length) (reduce #'*))) (format t "Part 2: ~A~%" (-<>> (cons (apply #'concat-integers (mapcar #'car races-data)) (apply #'concat-integers (mapcar #'cdr races-data))) (winning-range) (incl-range-length)))) Made me add :after/:before to my read-all-from-string that can take characters or strings. I feel it's gonna help clean my AoC code substantially. >>37838 At first, I made "excluding" versions of ceiling/floor like you, but then I realized that solving "dist > x" and fiddling with the roots didn't give the same result as "dist >= x + 1", which I used henceforth.

>>37805 not the haskell guy but i'll post a solution at some point. i tried doing them in rust while learning rust at the same time, maybe i should switch to something easier for now

>>37839 By the way, do you think Go is convenient for this type of tasks? I'm mostly wondering about the parsing and string processing stuff.

>>37845 I am doing them in go. Can someone here give an example of how to parse these correctly in golang, I am doing novice trash https://github.com/nanabonobo7000/advent

>>37845 I think Go is nice, I like doing algorithm type tasks in Go because I can follow the execution easily. I did the course https://www.manning.com/liveprojectseries/six-small-algorithm-projects-with-go (was a beta tester, got it for free) and implementing these tasks was pretty comfy. But one thing that I hate about Go is the idea of zero values. They are useful sometimes, for example you can use a map with value type bool as a set, but nevertheless I would prefer to have nullable/nillable types instead. >>37846 I suggest that you write some helper functions and re-use them from one challenge to another. For example you could write assert(condition bool, message string), check(err error) and fetchInput(day int) string , for the following reasons: - it's nice to be able to assert the state of your code and panic if the assertion fails, saves you some debugging time later and makes it less hassle to write these assertions if you are unsure about edge conditions while writing your function - dropping errors is not a great idea (like you are doing with strconv.Atoi() ), and panicking on error is dead simple when you have this re-usable check(err) to drop into your code. because Go has no nullable/nillable types, you pretty much *have* to check the error returned by a function like strconv.Atoi, othewise you cannot POSSIBLY know if you are reading valid data or garbage data or the zero value of a type - do you really want to copy-paste the same stdin processing block 25 times this month? it's much nicer to have a function that caches your input, that way you can even experiment with different inputs by temporarily replacing day-07.txt and then putting the original back. Why not make this function return different useful ways of expressing the data? You can return the string itself, the slice of lines, the slice of integers that appear in the input (all nicely parsed). And then you can just pick and choose which representation(s) are suitable for today's challenge, and drop the rest. You can also use the regexp package for string processing, but note that it does not have support for backreferences BUT all regular expressions run in linear time which I think is VERY nice: > The regexp implementation provided by this package is guaranteed to run in time linear in the size of the input. (This is a property not guaranteed by most open source implementations of regular expressions.) For more information about this property, see https://swtch.com/~rsc/regexp/regexp1.html or any book about automata theory. As an example, here is some code from my day 6, where I don't follow all my advice from above: ``` lines := strings.Split(input, "\n") // drop the last empty line lines = lines[0 : len(lines)-1] if len(lines) != 2 { panic("assertion failed: wrong number of lines") } rNum := regexp.MustCompile("[0-9]+") timeDistanceTuples := make([][2]int, 0) times := rNum.FindAllString(lines[0], -1) distances := rNum.FindAllString(lines[1], -1) for i := range times { time, err := strconv.Atoi(times[i]) check(err) distance, err := strconv.Atoi(distances[i]) check(err) timeDistanceTuples = append(timeDistanceTuples, [2]int{time, distance}) } ```

Day 7 was fun. My idea was to change AKQJT to edcba (edcd1 for second part) and also add prefix number 7-1 based on the hand combination value so that I can just use string sort in the end.

>>37849 Impressive, very nice. I calculated a base-13 (was it 13?) key manually using all the given information and sorted by this key.

For day 8 part 2 is the correct way to do this something to do with LCM of the the individual full circle Z hits of the unique starts? I am just iterating through like a monkey

>>37868 if you read Erics mind you would know: 1, start -> Z == Z -> Z 2, there is only 1 Z in each cycle

>>37869 Thank you so much, that saved me the time. It should have been stated in the task in my opinion.

>>37870 np and yes, fuarrrk Eric

>>37869 Thank you brother that helps avoid overthinking >>37870 Filtering the monkeys sir, to be honest he should have made the LR directions string much shorter and then did the unsimplified case, would take more logic The lore is sus, you would think a ghost would take a faster direct route not go like 1000000x more steps in schrodinger ghost superpositioning

>>37869 > 2, there is only 1 Z in each cycle okay maybe this is a reasonable way to make the input 'nice' > 1, start -> Z == Z -> Z Is there any reason why this should be true in general? I feel like this should be in the question because this makes your life significantly easier. If this does not hold, then the path traversed, starting from each **A element, is characterised by two numbers: the number of steps until you reach the cycle; the length of the cycle. Also notice that the period of each cycle is 0 mod [the length of the left/right instructions on the first line] which is also an odd unstated assumption.

>>37876 >Is there any reason why this should be true in general? no, its a special case yes, it should have been stated in the problem description offsets (start -> Z) are 0 so LCM is viable (required since the answer is ~13,000,000,000,000) i also noticed Z nodes are reached from the same instruction index (280) in my input but not the sample the number of instructions is also prime - this is probably significant but im too tired --------Part 1-------- --------Part 2-------- Day Time Rank Score Time Rank Score 8 00:05:02 402 0 04:40:52 16055 0 today was rough

golfed day 9 both parts python 3 f = open("input").read().strip().split('\n') def solve(seq: list) -> int: i = 0 while any(seq[-1]): seq.append([seq[i][j + 1] - seq[i][j] for j in range(len(seq[i]) - 1)]) i += 1 for i in range(len(seq) - 2, -1, -1): seq[i].append(seq[i][-1] + seq[i + 1][-1]) return seq[0][-1] p1 = p2 = 0 for line in f: line = list(map(int, line.split())) p1 += solve([line]) p2 += solve([line[::-1]]) print(p1, p2)

Day 10 part 2, first try, linear time, feels good.

Another one in the club fuarrrk 8p2. 7p2 was "hard" for me because trivia really isn't well documented and the joker thing was a bit painful (used match on the card tally to get the hand type). >>37885 Eh, a bit cute considering this is the easiest day yet (or almost). Would probably have something similar if I merged both loop, but meh. (defun Δ (seq) (iter (for cur in seq) (for prev previous cur) (if prev (collect (- cur prev))))) (defun next-value (seq) (iter (for s initially seq then (Δ s)) (until (every #'zerop s)) (sum (last-elt s)))) (defun prev-value (seq) (iter (for s initially seq then (Δ s)) (for sign initially 1 then (- sign)) (until (every #'zerop s)) (sum (* sign (first s))))) (let* ((lines (uiop:read-file-lines (car uiop:*command-line-arguments*))) (seqs (mapcar #'read-all-from-string lines))) (format t "Next value sum: ~A~%" (reduce #'+ (mapcar #'next-value seqs))) (format t "Prev valum sum: ~A~%" (reduce #'+ (mapcar #'prev-value seqs)))) I'm liking the decent number of ideas I'm getting for my bag of tools.

Quick headcount, who's still in? Anyway, finished 10p2 tonight and I'm mentally flattened (I mean, already tired from deadlines at work). Definitely harder than 2022.

>>37895 Something something about weekend problems being harder and that you were supposed to do day 10 yesterday...

>>37895 I am on 10-2, im a bit retarded I have 99% of the code I am just struggling to order my condtions. Also I am drunk Started onto 11-1, as a nonprogrammer this is a fun event. I feel like this is what computer science clucks do all day in uni as homework problems so they are all smug about knowing some generic way of doing it.

>>37892 Cooler Δ: (defun Δ (seq) (mapcar #'- (cdr seq) seq))

>>37895 I had to skip a day, but I'm back on track. But doing both 10 and 11 in one day was taxing.

>>37895 planning on making it through day 25 tabular dp today, tricky to derive the recurrence relations for bottom-up but worked eventually

>>37909 Is it bad that I don't know the names for the techniques I am implementing? I just saw that there seemed to be a way to solve this recursively, so I implemented a base case and an recursive case. Then it was still taking forever to run so I added a cache (my solution function is pure so this is OK). Should I try to get an overview of what these methods are called?

Attempted to come up with my own solution for Day 10 Part 2, but wasn't successful. I initially tried to solve it by flooding the rectangle surrounding the loop but then realised that I don't account for those tiles that squeeze in-between the pipes, so that didn't work. I thought about _expanding_ the loop to create gaps where tiles originally squeeze in-between and then flooding it again. But that seemed like too much work. So in the end I skipped part 2. Maybe will attempt it again. Day 11 was ok but I still managed to spend a lot of time debugging it - turned out I carelessly used SORT and discarded its result. So yesterday I really learned the risk of using destructive operations. Day 12 was also ok. I employed memoization to solve part 2. ;;;; Advent of Code 2023, Day 12 ;;;; This snippet is stripped to essentials (defstruct (row (:constructor make-row (springs sizes))) springs sizes) (defun group-position (size springs) "Returns the position in a list of springs where a sized group of damaged springs begins, or NIL." (assert (> size 0)) (labels ((rec (i rest) (cond ((= i size) (when (or (null rest) (not (damaged-p (car rest)))) i)) ((null rest) nil) ((not (operational-p (car rest))) (rec (1+ i) (cdr rest)))))) ; skip all operational springs (multiple-value-bind (tail offset) (member-if2 (complement #'operational-p) springs) (when tail (if (rec 0 tail) offset ; if match failed but the first spring is unknown, ; then assume unknown is operational and try again without it (when (unknown-p (car tail)) (awhen (group-position size (cdr tail)) (+ 1 offset it)))))))) (defun count-arrangements (row) (with-slots (springs sizes) row (cond ((null sizes) (if (every (complement #'damaged-p) springs) 1 0)) ((null springs) 0) (t (let ((pos (group-position (car sizes) springs))) (if (null pos) 0 (let ((springs-from-group (nthcdr pos springs))) (+ (count-arrangements (make-row (nthcdr (1+ (car sizes)) springs-from-group) (cdr sizes))) (if (unknown-p (car springs-from-group)) (count-arrangements (make-row (cdr springs-from-group) sizes)) 0))))))))) (defsolver 12 1 (file) (let ((rows (read-input file))) (apply #'+ (mapcar #'count-arrangements rows)))) (defun read-row-2 (line) (destructuring-bind (springs sizes) (split-on #\Space line) (make-row (map-identity 'list (multiply-sequence 'string 5 springs "?")) (multiply-sequence 'list 5 (read-list-from-string (substitute #\Space #\, sizes)))))) ;; enable local (separately for each row) memoization of count-arrangements (defsolver 12 2 (file) (dflet ((read-row #'read-row-2)) (let ((rows (read-input file))) (apply #'+ (mapcar (lambda (row) (with-memoized count-arrangements (count-arrangements row))) rows)))))

>>37910 if you think that would be useful (e.g. to find similar problems to practice) what you did is called top-down dynamic programming using memoization

Pretty proud of my day 11. The data structure is pretty clever (if I may say so myself), I felt a tad smart with that 2pass expansion using a macro to avoid repetition and it's my first time using mapcon, which made my peepee very hard. Though I now realize I could have just sorted a single list twice, eh. (defun find-stars (map) (let ((stars (array-position-all #\# map))) (cons ;; Lists of shared star coordinates sorted by x and y (sort (copy-list stars) #'< :key #'car) (sort stars #'< :key #'cadr)))) (defmacro expand/impl (stars axis rate) (let ((key (if (eq axis :y) 'car 'cadr))) `(iter (for s in ,stars) (for cur = (,key s)) (for prev previous cur initially -1) (if (/= prev cur) (sum (* (- cur prev 1) (- ,rate 1)) into shift)) (incf (,key s) shift)))) (defun expand (stars &key rate) (expand/impl (car stars) :y rate) (expand/impl (cdr stars) :x rate)) (defun dist (star1 star2) (reduce #'+ (mapcar (lambda (a b) (abs (- a b))) star1 star2))) (let ((map (-<>> (car uiop:*command-line-arguments*) (uiop:read-file-lines) (apply #'aops:stack-rows)))) (iter (for exprate in '(2 1000000)) (for stars = (find-stars map)) ;; Too lazy to copy the subsharing (expand stars :rate exprate) (format t "Sum of shortest paths: ~A~%" (-<>> (car stars) (mapcon (lambda (l) (mapcar (lambda (s) (dist (car l) s)) (cdr l)))) (reduce #'+))))) A nice bench to rest on after day 10.

Looks like I'm filtered on 12. I don't have any decent ideas. I tried making the permutations of possible question mark substitutions and select the suitable ones, but it took too long and I'm too tired to try optimize it. A bit sad, I thought I could make it past the half mark at least.

>>37914 Just skip it. From what I vaguely remember the scoring in advent of code is so heavily skewed to fastest finish that there's no point in even bothering after the first few hours.

>>37911 SBCL warns when you don't use sort's return value, though.

Can a programmer chud explain to me how novice programmers are supposed to tackle part-2s? Clearly most of them are to scale solutions to filter out trash iteration. Are there tips on how to repeatedly apply this, and are tips going to language specific or just a general practice?

>>37921 By having a brain and using it, most of the time. The remaining fews are about being educated in CS and discrete maths.

>>37923 Well that is why I asked for tips from people in the know because its not about just being logical you need to use your chosen language to be efficient. My soykaf solves it but it will just take 10 years to iterate and I don't know the tricks. Not everyone is a codemonkey chud who spent their uni years doing reindeer puzzles that AI can solve in: *checks the AOC scoreboard* yup looks like about 90 seconds including compile, runtime and submission ping

GOlain checking in, got there in the end for today's challenge

>>37777 i hate chinese remainder theorem so fuarrrking much

>>37923 >>37925 based. you asked for a chud and a chud answer is what you got. dont like it? next time dont ask for it

I managed to get 40 stars. What I learned: 1. My skill of solving algorithmic problems is underdeveloped, as is my understanding of algorithmic complexity. 2. Writing Common Lisp in Vim is painful sometimes. I have been using SLIMV, which works better for me than Vlime. Paredit obstructs some other plugins from working correctly, such as visual-multi. I am considering Emacs. 3. I heavily underestimated the amount of time I would require for each problem. My initial plan included the usage of more than just Common Lisp: I also wanted to try concatenative programming and Haskell. 4. The previous year felt more wholesome - that's what I concluded from my observations of 4chan AoC threads. I don't remember seeing that many people expressing their dislike for AoC, which primarily boils down to their being bored and uninterested in given problems. Nevertheless, the first 2 weeks felt awesome to me.