this post was submitted on 09 Nov 2025
6 points (80.0% liked)

Advent Of Code

1217 readers
1 users here now

An unofficial home for the advent of code community on programming.dev! Other challenges are also welcome!

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.

Everybody Codes is another collection of programming puzzles with seasonal events.

EC 2025

AoC 2025

Solution Threads

M T W T F S S
1 2 3 4 5 6 7
8 9 10 11 12

Visualisations Megathread

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 2 years ago
MODERATORS
 

Quest 3: The Deepest Fit

  • 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)
  • You can send code in code blocks by using three backticks, the code, and then three backticks or use something such as https://topaz.github.io/paste/ if you prefer sending it through a URL

Link to participate: https://everybody.codes/

Also, don't wait for me to make these posts, feel free to post yourself :)

top 10 comments
sorted by: hot top controversial new old
[–] mykl@lemmy.world 3 points 3 months ago

Very simple task for Uiua.

[10 5 1 10 3 8 5 2 2]
/+β—΄
[4 51 13 64 57 51 82 57 16 88 89 48 32 49 49 2 84 65 49 43 9 13 2 3 75 72 63 48 61 14 40 77]
/+↙20β†βŠΈβ—΄
/β†₯βŠœβ§»βŠΈβˆ˜β†

-> 29, 781, 3

[–] vole@lemmy.world 3 points 3 months ago* (last edited 3 months ago) (1 children)

Scheme/Guile

Guile doesn't seem to come with a bag implementation :(. Not a big deal, a linear scan works about as well.

(use-modules (ice-9 rdelim))
(use-modules (srfi srfi-1))

(define (parse-file file-name)
  (let* ((p (open-input-file file-name))
        (comma-split (string-split (read-line p) #\,))
        (number-list (map string->number comma-split)))
    number-list))

(let* ((crates (parse-file "notes/everybody_codes_e2025_q03_p1.txt"))
       (dedup-crates (delete-duplicates crates)))
  (format #t "P1 Answer: ~a\n\n" (apply + dedup-crates)))


(let* ((crates (parse-file "notes/everybody_codes_e2025_q03_p2.txt"))
       (dedup-crates (delete-duplicates crates))
       (sorted-crates (sort dedup-crates <)))
  (format #t "P2 Answer: ~a\n\n" (apply + (take sorted-crates 20))))


(let* ((crates (parse-file "notes/everybody_codes_e2025_q03_p3.txt"))
       (sorted-crates (sort crates <))
       (largest-set-size (let loop ((count 0) (l sorted-crates) (c #f) (max-count 0))
         (if (nil? l)
             max-count
             (let* ((new-c (car l))
                    (new-count (if (equal? new-c c) (+ count 1) 1)))
               (loop new-count (cdr l) new-c (max new-count max-count)))))))
  (format #t "P3 Answer: ~a\n\n" largest-set-size))
[–] ragingHungryPanda@piefed.keyboardvagabond.com 1 points 2 months ago (1 children)

I'm so far behind on these, but it's rare that I see a lanugage I've never heard before. I've heard of scheme. How did you come to using this language for the challenges?

[–] vole@lemmy.world 1 points 2 months ago

I wanted to learn scheme and perhaps work through SICP. Guille seemed like a reasonable scheme to choose because I've also been considering learning Guix. Guix is a package manager similar to Nix, and it uses Guille as its configuration language.

[–] VegOwOtenks@lemmy.world 2 points 3 months ago

I was scared of a hard combinatorial puzzle day, but this was a breeze.

{-# LANGUAGE TupleSections #-}
module Main (main) where
import Control.Monad ((<$!>))
import qualified Data.Text.IO as TextIO
import Data.Text (Text)
import qualified Data.Text as Text
import qualified Data.IntSet as IntSet
import Control.Arrow ((>>>))
import qualified Data.List as List
import qualified Data.IntMap as IntMap

part1 :: [IntSet.Key] -> IntSet.Key
part1 = IntSet.fromList
  >>> IntSet.foldl (+) 0

part2 :: [IntSet.Key] -> IntSet.Key
part2 = IntSet.fromList
  >>> IntSet.toAscList
  >>> take 20
  >>> sum

part3 :: [IntMap.Key] -> Int
part3 = List.map (, 1)
  >>> IntMap.fromListWith (+)
  >>> IntMap.toList
  >>> List.map snd
  >>> maximum

main :: IO ()
main = do
  sizes <- map (read . Text.unpack) . Text.split (== ',') <$!> TextIO.getLine
  print $ part1 sizes
  print $ part2 sizes
  print $ part3 sizes
[–] lwhjp@piefed.blahaj.zone 2 points 3 months ago

I thought this was going to be the knapsack problem, but no.

import Control.Monad  
import Data.List.Split  
import qualified Data.Set as Set  
import qualified Data.Multiset as MSet  

part1, part2, part3 :: [Int] -> Int  
part1 = sum . Set.fromList  
part2 = sum . Set.take 20 . Set.fromList  
part3 = maximum . MSet.toCountMap . MSet.fromList  

main =  
  forM_  
    [ ("everybody_codes_e2025_q03_p1.txt", part1),  
      ("everybody_codes_e2025_q03_p2.txt", part2),  
      ("everybody_codes_e2025_q03_p3.txt", part3)  
    ]  
    $ \(input, solve) ->  
      readFile input >>= print . solve . map read . splitOn ","  
[–] ystael@beehaw.org 2 points 3 months ago

Common Lisp doesn't have a built in set datatype, so you have to do uniqueness checking sort of by hand unless you want to pull in an external package.

(ql:quickload :str)

(defun read-inputs (filename)
  (let ((input-lines (uiop:read-file-lines filename)))
    (mapcar #'parse-integer (str:split "," (car input-lines)))))

(defun add-distinct (xs)
  (loop for x in (remove-duplicates (sort (copy-seq xs) #'>))
        sum x))

(defun main-1 (filename)
  (add-distinct (read-inputs filename)))

(defun main-2 (filename)
  (let* ((sizes (read-inputs filename))
         (first-20 (subseq (remove-duplicates (sort (copy-seq sizes) #'<)) 0 20)))
    (loop for x in first-20
          sum x)))

(defun count-max-copies (xs)
  (labels ((iter (xs cur-x cur-count max-count)
             (cond ((null xs)
                    max-count)
                   ((equal (car xs) cur-x)
                    (iter (cdr xs) cur-x (1+ cur-count) (max max-count (1+ cur-count))))
                   (t
                    (iter (cdr xs) (car xs) 1 max-count)))))
    (iter (cdr xs) (car xs) 1 1)))

(defun main-3 (filename)
  (count-max-copies (sort (read-inputs filename) #'<)))
[–] hades@programming.dev 2 points 3 months ago

Rust

pub fn solve_part_1(input: &str) -> String {
    let mut crates: Vec<i64> = input.split(",").map(|s| s.parse().unwrap()).collect();
    crates.sort();
    let mut monotonic_subsequence = vec![crates[0]];
    for size in crates.into_iter().skip(1) {
        if size == *monotonic_subsequence.last().unwrap() {
            continue;
        }
        monotonic_subsequence.push(size);
    }
    monotonic_subsequence.iter().sum::<i64>().to_string()
}

pub fn solve_part_2(input: &str) -> String {
    let mut crates: Vec<i64> = input.split(",").map(|s| s.parse().unwrap()).collect();
    crates.sort();
    let mut monotonic_subsequence = vec![crates[0]];
    for size in crates.into_iter().skip(1) {
        if size == *monotonic_subsequence.last().unwrap() {
            continue;
        }
        monotonic_subsequence.push(size);
        if monotonic_subsequence.len() >= 20 {
            break;
        }
    }
    monotonic_subsequence.iter().sum::<i64>().to_string()
}

pub fn solve_part_3(input: &str) -> String {
    let mut crates: Vec<i64> = input.split(",").map(|s| s.parse().unwrap()).collect();
    crates.sort();
    let mut monotonic_subsequences = vec![vec![crates[0]]];
    for size in crates.into_iter().skip(1) {
        let updateable_sequence = monotonic_subsequences
            .iter_mut()
            .find(|v| *v.last().unwrap() < size);
        match updateable_sequence {
            Some(v) => {
                v.push(size);
            }
            None => {
                monotonic_subsequences.push(vec![size]);
            }
        }
    }
    monotonic_subsequences.len().to_string()
}
[–] janAkali@lemmy.sdf.org 2 points 3 months ago* (last edited 3 months ago)

Nim

Reading this day's quest I was at first a bit confused what it asks me to calculate. Took me about a minute to realize that most of descriptions are not important and actual calculations for each part are very simple:

part 1 wants sum of each unique crate size
part 2 is same but only 20 smallest
part 3 is max count, because you can always put most crates in one large set and you only need 1 extra set per duplicate crate

proc solve_part1*(input: string): Solution =
  var seen: set[int16]
  for num in input.split(','):
    let num = parseInt(num).int16
    if num in seen: continue
    else:
      seen.incl num
      result.intVal += num

proc solve_part2*(input: string): Solution =
  var set = input.split(',').mapIt(parseInt(it).uint16)
  set.sort()
  result := set.deduplicate(isSorted=true)[0..<20].sum()

proc solve_part3*(input: string): Solution =
  var cnt = input.split(',').toCountTable()
  result := cnt.largest.val

Full solution at Codeberg: solution.nim

FSharp

I'm a month late, but eh. Compared to everyone else, it looks like my approach of preserving duplicates was unnecessary. I chose to use SortedSets (redundant since I sort the inputs) and cascade to the next best fit. The sorted sets also let me grab the Max/Min values and I thought that it was more in line with the intention than having a list that happens to be sorted.

I also sorted part 1 based on what I thought was the best fit, which was the same solution for part 3.
For part 2 I duplicated part 1's logic but reversed the order to asc instead of desc, but I don't know that that made a difference and excluded it here. The only difference is the "add if count < 20".

type Crate = int  
 // sorted set because only one item can be in at a time. The SortedSet is unnecessary here since the inputs are already sorted  
type CrateSet = SortedSet<Crate>  
let inline newCrateSet crate =  
    let cs = CrateSet()  
    cs.Add(crate) |> ignore  
    cs  
type Extensions() =  
    [<Extension>]  
    static member inline SmallestCrate (crates:CrateSet) : Crate option = match crates.Min with | 0 -> None | x -> Some x  
    [<Extension>]  
    static member inline LargestCrate (crates:CrateSet) : Crate option = match crates.Max with | 0 -> None | x -> Some x  

/// take a sorted input (not verified) and prioritize insertion into the first found list.  
/// This results in cascading to the "next best fit", but this approach relies on sorted inputs.  
let packEfficiently allCrates =  
    allCrates  
    |> Seq.fold (fun sortedCrates next ->  
            // find the first crate set that can hold the next item and put it in there  
            match sortedCrates with  
            | [] -> [newCrateSet next]  
            | items ->  
                match List.tryFind (fun (i:CrateSet) ->  
                    match i.SmallestCrate() with  
                    | Some c when c > next -> true  
                    | _ -> false) items with  
                | None ->  
                    let cs = newCrateSet next  
                    items@[cs] // appending to the end is less efficient for linked lists, but ensures that the first one gets the best goodies  
                | Some crates ->  
                    if not (crates.Add(next)) then failwith "failed to add" // really wrong if this happens  
                    items  

        ) []  

let part1 () =  
    parseInput "Inputs/Quest03/Q03_P01.txt"  
    |> Enumerable.OrderDescending  
    |> packEfficiently  
    |> _.Max(_.Sum())  

let part2() =  
    parseInput "Inputs/Quest03/Q03_P02.txt"  
    |> Enumerable.Order  
    |> part2Impl  
    |> List.filter (fun x -> x.Count = 20)  
    |> _.Min(_.Sum())  
    
let part3() =  
    parseInput "Inputs/Quest03/Q03_P03.txt"  
    |> Enumerable.OrderDescending  
    |> packEfficiently  
    |> _.Count()