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 :)

  • ystael@beehaw.org
    link
    fedilink
    arrow-up
    2
    ·
    3 days 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) #'<)))
    
  • mykl@lemmy.world
    link
    fedilink
    arrow-up
    2
    ·
    3 days 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
    link
    fedilink
    English
    arrow-up
    3
    ·
    edit-2
    6 days ago

    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))
    
  • Amy@piefed.blahaj.zone
    link
    fedilink
    English
    arrow-up
    2
    ·
    8 days 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 ","  
    
  • VegOwOtenks@lemmy.world
    link
    fedilink
    arrow-up
    2
    ·
    8 days 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
    
  • hades@programming.devOPM
    link
    fedilink
    arrow-up
    2
    ·
    8 days 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
    link
    fedilink
    arrow-up
    2
    ·
    edit-2
    8 days 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