Day 7: Bridge Repair

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

FAQ

  • RagingHungryPanda@lemm.ee
    link
    fedilink
    English
    arrow-up
    1
    ·
    3 days ago

    I’m way behind, but I’m trying to learn F#.

    I’m using the library Combinatorics in dotnet, which I’ve used in the past, generate in this case every duplicating possibility of the operations. I the only optimization that I did was to use a function to concatenate numbers without converting to strings, but that didn’t actually help much.

    I have parser helpers that use ReadOnlySpans over strings to prevent unnecessary allocations. However, here I’m adding to a C# mutable list and then converting to an FSharp (linked) list, which this language is more familiar with. Not optimal, but runtime was pretty good.

    I’m not terribly good with F#, but I think I did ok for this challenge.

    F#

    // in another file:
    let concatenateLong (a:Int64) (b:Int64) : Int64 =
        let rec countDigits (n:int64) =
            if n = 0 then 0
            else 1 + countDigits (n / (int64 10))   
    
        let bDigits = if b = 0 then 1 else countDigits b
        let multiplier = pown 10 bDigits |> int64
        a * multiplier + b
    
    // challenge file
    type Operation = {Total:Int64; Inputs:Int64 list }
    
    let parse (s:ReadOnlySpan<char>) : Operation =
        let sep = s.IndexOf(':')
        let total = Int64.Parse(s.Slice(0, sep))
        let inputs = System.Collections.Generic.List<Int64>()
        let right:ReadOnlySpan<char> = s.Slice(sep + 1).Trim()
    
       // because the Split function on a span returns a SpanSplitEnumerator, which is a ref-struct and can only live on the stack, 
       // I can't use the F# list syntax here
        for range in right.Split(" ") do
            inputs.Add(Int64.Parse(sliceRange right range))
            
        {Total = total; Inputs = List.ofSeq(inputs) }
    
    let part1Ops = [(+); (*)]
    
    let execute ops input =
        input
        |> PSeq.choose (fun op ->
            let total = op.Total
            let inputs = op.Inputs
            let variations = Variations(ops, inputs.Length - 1, GenerateOption.WithRepetition)
            variations
            |> Seq.tryFind (fun v ->
                let calcTotal = (inputs[0], inputs[1..], List.ofSeq(v)) |||> List.fold2 (fun acc n f -> f acc n) 
                calcTotal = total
                )
            |> Option.map(fun _ -> total)
            )
        |> PSeq.fold (fun acc n -> acc + n) 0L
    
    let part1 input =
        (read input parse)
        |> execute part1Ops
    
    let part2Ops = [(+); (*); concatenateLong]
    
    let part2 input = (read input parse) |> execute part2Ops
    

    The Gen0 garbage collection looks absurd, but Gen0 is generally considered “free”.

    Method Mean Error StdDev Gen0 Gen1 Allocated
    Part1 19.20 ms 0.372 ms 0.545 ms 17843.7500 156.2500 106.55 MB
    Part2 17.94 ms 0.355 ms 0.878 ms 17843.7500 156.2500 106.55 MB

    V2 - concatenate numbers did little for the runtime, but did help with Gen1 garbage, but not the overall allocation.

    Method Mean Error StdDev Gen0 Gen1 Allocated
    Part1 17.34 ms 0.342 ms 0.336 ms 17843.7500 125.0000 106.55 MB
    Part2 17.24 ms 0.323 ms 0.270 ms 17843.7500 93.7500 106.55 MB
  • mykl@lemmy.world
    link
    fedilink
    arrow-up
    7
    ·
    edit-2
    16 days ago

    Uiua

    This turned out to be reasonably easy in Uiua, though this solution relies on macros which maybe slow it down.

    (edit: removing one macro sped it up quite a bit)

    (edit2: Letting Uiua build up an n-dimensional array turned out to be the solution, though sadly my mind only works in 3 dimensions. Now runs against the live data in around 0.3 seconds.)

    Try it here

    Data    (□⊜⋕⊸(¬∈": "))⊸≠@\n "190: 10 19\n3267: 81 40 27\n83: 17 5\n156: 15 6\n7290: 6 8 6 15\n161011: 16 10 13\n192: 17 8 14\n21037: 9 7 18 13\n292: 11 6 16 20"
    Calib!  ≡◇⊢▽⊸≡◇(∈♭/[^0]:°⊂) # Calibration targets which can be constructed from their values.
    &p/+Calib!(+|×)Data
    &p/+Calib!(+|×|+×ⁿ:10+1ₙ₁₀,)Data
    
    • Quant@programming.dev
      link
      fedilink
      arrow-up
      3
      ·
      16 days ago

      Thanks to your solution I learned more about how to use reduce :D

      My solution did work for the example input but not for the actual one. When I went here and saw this tiny code block and you saying

      This turned out to be reasonably easy

      I was quite taken aback. And it’s so much better performance-wise too :D (well, until part 2 comes along in my case. Whatever this black magic is you used there is too high for my fried brain atm)

      • mykl@lemmy.world
        link
        fedilink
        arrow-up
        2
        ·
        16 days ago

        Haha, sorry about that, it does seem quite smug :-) I went into it expecting it to be a nightmare of boxes and dimensions, but finding it something I could deal with was a massive relief. Of course once I had a working solution I reversed it back into a multi-dimensional nightmare. That’s where the performance gains came from: about 10x speedup from letting Uiua build up as many dimensions as it needed before doing a final deshaping.

        I enjoyed reading a different approach to this, and thanks for reminding me that ⋕$"__" exists, that’s a great idiom to have up your sleeve.

        Let me know if there’s any bits of my solution that you’d like me to talk you through.

        • Quant@programming.dev
          link
          fedilink
          arrow-up
          2
          ·
          16 days ago

          No worries, it does seem a lot less difficult in hindsight now, my mind just blanked at what I expected to be a lot more code :))

          That performance improvement is amazing, I’ll definitely take a look at how that works in detail later. Just gotta recover from the mental stretch gymnastics trying to remember the state of the stack at different code positions

  • iAvicenna@lemmy.world
    link
    fedilink
    arrow-up
    4
    ·
    edit-2
    14 days ago

    Python

    It is a tree search

    def parse_input(path):
    
      with path.open("r") as fp:
        lines = fp.read().splitlines()
    
      roots = [int(line.split(':')[0]) for line in lines]
      node_lists = [[int(x)  for x in line.split(':')[1][1:].split(' ')] for line in lines]
    
      return roots, node_lists
    
    def construct_tree(root, nodes, include_concat):
    
      levels = [[] for _ in range(len(nodes)+1)]
      levels[0] = [(str(root), "")]
      # level nodes are tuples of the form (val, operation) where both are str
      # val can be numerical or empty string
      # operation can be *, +, || or empty string
    
      for indl, level in enumerate(levels[1:], start=1):
    
        node = nodes[indl-1]
    
        for elem in levels[indl-1]:
    
          if elem[0]=='':
            continue
    
          if elem[0][-len(str(node)):] == str(node) and include_concat:
            levels[indl].append((elem[0][:-len(str(node))], "||"))
          if (a:=int(elem[0]))%(b:=int(node))==0:
            levels[indl].append((str(int(a/b)), '*'))
          if (a:=int(elem[0])) - (b:=int(node))>0:
            levels[indl].append((str(a - b), "+"))
    
      return levels[-1]
    
    def solve_problem(file_name, include_concat):
    
      roots, node_lists = parse_input(Path(cwd, file_name))
      valid_roots = []
    
      for root, nodes in zip(roots, node_lists):
    
        top = construct_tree(root, nodes[::-1], include_concat)
    
        if any((x[0]=='1' and x[1]=='*') or (x[0]=='0' and x[1]=='+') or
               (x[0]=='' and x[1]=='||') for x in top):
    
          valid_roots.append(root)
    
      return sum(valid_roots)
    
    • Acters@lemmy.world
      link
      fedilink
      arrow-up
      1
      ·
      edit-2
      15 days ago

      I asked ChatGPT to explain your code and mentioned you said it was a binary search. idk why, but it output a matter of fact response that claims you were wrong. lmao, I still don’t understand how your code works

      This code doesn’t perform a classic binary search. Instead, it uses each input node to generate new possible states or “branches,” forming a tree of transformations. At each level, it tries up to three operations on the current value (remove digits, divide, subtract). These expansions create multiple paths, and the code checks which paths end in a successful condition. While the author may have described it as a “binary search,” it’s more accurately a state-space search over a tree of possible outcomes, not a binary search over a sorted data structure.

      I understand it now! I took your solution and made it faster. it is now like 36 milliseconds faster for me. which is interesting because if you look at the code. I dont process the entire list of integers. I sometimes stop prematurely before the next level, clear it, and add the root. I don’t know why but it just works for my input and the test input.

      code
      def main(input_data):
          input_data = input_data.replace('\r', '')
          parsed_data = {int(line[0]): [int(i) for i in line[1].split()[::-1]] for line in [l.split(': ') for l in input_data.splitlines()]}
          part1 = 0
          part2 = 0
          for item in parsed_data.items():
              root, num_array = item
              part_1_branches = [set() for _ in range(len(num_array)+1)]
              part_2_branches = [set() for _ in range(len(num_array)+1)]
              part_1_branches[0].add(root)
              part_2_branches[0].add(root)
              for level,i in enumerate(num_array):
                  if len(part_1_branches[level]) == 0 and len(part_2_branches[level]) == 0:
                      break
      
                  for branch in part_1_branches[level]:
                      if branch == i:
                          part_1_branches[level+1] = set() # clear next level to prevent adding root again
                          part1 += root
                          break
                      if branch % i == 0:
                          part_1_branches[level+1].add(branch//i)
                      if branch - i > 0:
                          part_1_branches[level+1].add(branch-i)
      
                  for branch in part_2_branches[level]:
                      if branch == i or str(branch) == str(i):
                          part_2_branches[level+1] = set() # clear next level to prevent adding root again
                          part2 += root
                          break
                      if branch % i == 0:
                          part_2_branches[level+1].add(branch//i)
                      if branch - i > 0:
                          part_2_branches[level+1].add(branch-i)
                      if str(i) == str(branch)[-len(str(i)):]:
                          part_2_branches[level+1].add(int(str(branch)[:-len(str(i))]))
          print("Part 1:", part1, "\nPart 2:", part2)
          return [part1, part2]
      
      if __name__ == "__main__":
          with open('input', 'r') as f:
              main(f.read())
      

      however what I notice is that the parse_input causes it to be the reason why it is slower by 20+ milliseconds. I find that even if I edited your solution like so to be slightly faster, it is still 10 milliseconds slower than mine:

      code
      def parse_input():
      
        with open('input',"r") as fp:
          lines = fp.read().splitlines()
      
        roots = [int(line.split(':')[0]) for line in lines]
        node_lists = [[int(x) for x in line.split(': ')[1].split(' ')] for line in lines]
      
        return roots, node_lists
      
      def construct_tree(root, nodes):
          levels = [[] for _ in range(len(nodes)+1)]
          levels[0] = [(root, "")]
          # level nodes are tuples of the form (val, operation) where both are str
          # val can be numerical or empty string
          # operation can be *, +, || or empty string
      
          for indl, level in enumerate(levels[1:], start=1):
      
              node = nodes[indl-1]
      
              for elem in levels[indl-1]:
                  if elem[0]=='':
                      continue
      
                  if (a:=elem[0])%(b:=node)==0:
                      levels[indl].append((a/b, '*'))
                  if (a:=elem[0]) - (b:=node)>0:
                      levels[indl].append((a - b, "+"))
      
          return levels[-1]
      
      
      def construct_tree_concat(root, nodes):
          levels = [[] for _ in range(len(nodes)+1)]
          levels[0] = [(str(root), "")]
          # level nodes are tuples of the form (val, operation) where both are str
          # val can be numerical or empty string
          # operation can be *, +, || or empty string
      
          for indl, level in enumerate(levels[1:], start=1):
      
              node = nodes[indl-1]
      
              for elem in levels[indl-1]:
                  if elem[0]=='':
                      continue
      
                  if elem[0][-len(str(node)):] == str(node):
                      levels[indl].append((elem[0][:-len(str(node))], "||"))
                  if (a:=int(elem[0]))%(b:=int(node))==0:
                      levels[indl].append((str(int(a/b)), '*'))
                  if (a:=int(elem[0])) - (b:=int(node))>0:
                      levels[indl].append((str(a - b), "+"))
      
          return levels[-1]
      
      def solve_problem():
      
        roots, node_lists = parse_input()
        valid_roots_part1 = []
        valid_roots_part2 = []
      
        for root, nodes in zip(roots, node_lists):
          
          top = construct_tree(root, nodes[::-1])
      
          if any((x[0]==1 and x[1]=='*') or (x[0]==0 and x[1]=='+') for x in top):
            valid_roots_part1.append(root)
            
          top = construct_tree_concat(root, nodes[::-1])
      
          if any((x[0]=='1' and x[1]=='*') or (x[0]=='0' and x[1]=='+') or (x[0]=='' and x[1]=='||') for x in top):
      
            valid_roots_part2.append(root)
      
        return sum(valid_roots_part1),sum(valid_roots_part2)
        
      if __name__ == "__main__":
          print(solve_problem())
      
      • iAvicenna@lemmy.world
        link
        fedilink
        arrow-up
        2
        ·
        edit-2
        14 days ago

        Wow I got thrashed by chatgpt. Strictly speaking that is correct, it is more akin to Tree Search. But even then not strictly because in tree search you are searching through a list of objects that is known, you build a tree out of it and based on some conditions eliminate half of the remaining tree each time. Here I have some state space (as chatgpt claims!) and again based on applying certain conditions, I eliminate some portion of the search space successively (so I dont have to evaluate that part of the tree anymore). To me both are very similar in spirit as both methods avoid evaluating some function on all the possible inputs and successively chops off a fraction of the search space. To be more correct I will atleast replace it with tree search though, thanks. And thanks for taking a close look at my solution and improving it.

        • Acters@lemmy.world
          link
          fedilink
          arrow-up
          1
          ·
          14 days ago

          idk why my gpt decided to be like that. I expected a long winded response with a little bit of ai hallucinations. I was flabbergasted, and just had to post it.

          I seemingly realized that working forward through the list of integers was inefficient for me to do, and I was using multiprocessing to do it too! which my old solution took less than 15 seconds for my input. your solution to reverse the operations and eliminate paths was brilliant and made it solve it in milliseconds without spinning up my fans, lol

  • lwhjp@lemmy.sdf.org
    link
    fedilink
    arrow-up
    4
    ·
    edit-2
    17 days ago

    Haskell

    A surprisingly gentle one for the weekend! Avoiding string operations for concatenate got the runtime down below one second on my machine.

    import Control.Arrow
    import Control.Monad
    import Data.List
    import Data.Maybe
    
    readInput :: String -> [(Int, [Int])]
    readInput = lines >>> map (break (== ':') >>> (read *** map read . words . tail))
    
    equatable :: [Int -> Int -> Int] -> (Int, [Int]) -> Bool
    equatable ops (x, y : ys) = elem x $ foldM apply y ys
      where
        apply a y = (\op -> a `op` y) <$> ops
    
    concatenate :: Int -> Int -> Int
    concatenate x y = x * mag y + y
      where
        mag z = fromJust $ find (> z) $ iterate (* 10) 10
    
    main = do
      input <- readInput <$> readFile "input07"
      mapM_
        (print . sum . map fst . (`filter` input) . equatable)
        [ [(+), (*)],
          [(+), (*), concatenate]
        ]
    
    • VegOwOtenks@lemmy.world
      link
      fedilink
      English
      arrow-up
      2
      ·
      17 days ago

      I wanted to this the way yo did, by repeatedly applying functions, but I didn’t dare to because I like to mess up and spend some minutes debugging signatures, may I ask what your IDE setup is for the LSP-Hints with Haskell?
      Setting up on my PC was a little bit of a pain because it needed matching ghc and ghcide versions, so I hadn’t bothered doing it on my Laptop yet.

      • LeixB@lemmy.world
        link
        fedilink
        arrow-up
        3
        ·
        16 days ago

        I use neovim with haskell-tools.nvim plugin. For ghc, haskell-language-server and others I use nix which, among other benefits makes my development environment reproducible and all haskellPackages are built on the same version so there are no missmatches.

        But, as much as I love nix, there are probably easier ways to setup your environment.

        • VegOwOtenks@lemmy.world
          link
          fedilink
          arrow-up
          2
          ·
          16 days ago

          I just checked and I have haskell-tools.nvim on my PC but it somehow crashes the default config of the autocompletion for me, which I am too inexperienced to debug. I’ll try it nonetheless, since I don’t have autocompletion on the laptop anyways, thank you for the suggestion!

      • lwhjp@lemmy.sdf.org
        link
        fedilink
        arrow-up
        2
        ·
        16 days ago

        Ah, well, I have a bit of a weird setup. GHC is 9.8.4, built from git. I’m using HLS version 2.9.0.1 (again built from git) under Emacs with the LSP and flycheck packages. There are probably much easier ways of getting it to work :)

        • VegOwOtenks@lemmy.world
          link
          fedilink
          arrow-up
          2
          ·
          16 days ago

          I envy emacs for all of its modes, but I don’t think I’m relearning the little I know about vi. Thank you for the answer on the versions and building!

    • lwhjp@lemmy.sdf.org
      link
      fedilink
      arrow-up
      2
      ·
      edit-2
      17 days ago

      Since all operations increase the accumulator, I tried putting a guard (a <= x) in apply, but it doesn’t actually help all that much (0.65s -> 0.43s).

      • VegOwOtenks@lemmy.world
        link
        fedilink
        arrow-up
        2
        ·
        edit-2
        16 days ago

        0.65 -> 0.43 sounds pretty strong, isn’t that a one-fourth speedup?

        Edit: I was able to achieve a 30% speed improvement using this on my solution

        • lwhjp@lemmy.sdf.org
          link
          fedilink
          arrow-up
          2
          ·
          16 days ago

          It’s not insignificant, sure, but I’d prefer 10x faster :D

          Plus I’m not sure it’s worth the loss of generality and readability. It is tempting to spend hours chasing this kind of optimization though!

  • LeixB@lemmy.world
    link
    fedilink
    arrow-up
    4
    ·
    17 days ago

    Haskell

    import Control.Arrow
    import Data.Char
    import Text.ParserCombinators.ReadP
    
    numP = read <$> munch1 isDigit
    parse = endBy ((,) <$> (numP <* string ": ") <*> sepBy numP (char ' ')) (char '\n')
    
    valid n [m] = m == n
    valid n (x : xs) = n > 0 && valid (n - x) xs || (n `mod` x) == 0 && valid (n `div` x) xs
    
    part1 = sum . fmap fst . filter (uncurry valid . second reverse)
    
    concatNum r = (+r) . (* 10 ^ digits r)
        where
            digits = succ . floor . logBase 10 . fromIntegral
    
    allPossible [n] = [n]
    allPossible (x:xs) = ((x+) <$> rest) ++ ((x*) <$> rest) ++ (concatNum x <$> rest)
        where
            rest = allPossible xs
    
    part2 = sum . fmap fst . filter (uncurry elem . second (allPossible . reverse))
    
    main = getContents >>= print . (part1 &&& part2) . fst . last . readP_to_S parse
    
  • VegOwOtenks@lemmy.world
    link
    fedilink
    English
    arrow-up
    3
    ·
    17 days ago

    Haskell

    I’m not very proud, I copied my code for part two.

    import Control.Arrow hiding (first, second)
    
    import qualified Data.List as List
    import qualified Data.Char as Char
    
    parseLine l = (n, os)
            where
                    n = read . takeWhile (Char.isDigit) $ l
                    os = map read . drop 1 . words $ l
    
    parse :: String -> [(Int, [Int])]
    parse s = map parseLine . takeWhile (/= "") . lines $ s
    
    insertOperators target (r:rs) = any (target ==) (insertOperators' r rs)
    insertOperators' :: Int -> [Int] -> [Int]
    insertOperators' acc []     = [acc]
    insertOperators' acc (r:rs) = insertOperators' (acc+r) rs ++ insertOperators' (acc*r) rs
    
    insertOperators2 target (r:rs) = any (target ==) (insertOperators2' r rs)
    insertOperators2' :: Int -> [Int] -> [Int]
    insertOperators2' acc []     = [acc]
    insertOperators2' acc (r:rs) = insertOperators2' (acc+r) rs ++ insertOperators2' (acc*r) rs ++ insertOperators2' concatN rs
            where
                    concatN = read (show acc ++ show r)
    
    part1 ls = filter (uncurry insertOperators)
            >>> map fst
            >>> sum
            $ ls
    part2 ls = filter (uncurry insertOperators2)
            >>> map fst
            >>> sum
            $ ls
    
    main = getContents >>= print . (part1 &&& part2) . parse
    
  • Andy@programming.dev
    link
    fedilink
    arrow-up
    3
    ·
    17 days ago

    Factor

    spoiler
    TUPLE: equation value numbers ;
    C: <equation> equation
    
    : get-input ( -- equations )
      "vocab:aoc-2024/07/input.txt" utf8 file-lines [
        split-words unclip but-last string>number
        swap [ string>number ] map <equation>
      ] map ;
    
    : possible-quotations ( funcs numbers -- quots )
      dup length 1 -
      swapd all-selections
      [ unclip swap ] dip
      [ zip concat ] with map
      swap '[ _ prefix >quotation ] map ;
    
    : possibly-true? ( funcs equation -- ? )
      [ numbers>> possible-quotations ] [ value>> ] bi
      '[ call( -- n ) _ = ] any? ;
    
    : solve ( funcs -- n )
      get-input
      [ possibly-true? ] with filter
      [ value>> ] map-sum ;
    
    : part1 ( -- n )
      { + * } solve ;
    
    : _|| ( m n -- mn )
      [ number>string ] bi@ append string>number ;
    
    : part2 ( -- n )
      { + * _|| } solve ;
    
  • Quant@programming.dev
    link
    fedilink
    arrow-up
    3
    ·
    16 days ago

    Uiua

    Credits to @mykl@lemmy.world for the approach of using reduce and also how to split the input by multiple characters.
    I can happily say that I learned quite a bit today, even though the first part made me frustrated enough that I went searching for other approaches ^^

    Part two just needed a simple modification. Changing how the input is parsed and passed to the adapted function took longer than changing the function itself actually.

    Run with example input here

    PartOne ← (
      &rs ∞ &fo "input-7.txt"
      ⊜□≠@\n.
      ≡◇(⊜□≠@:.)
      ≡⍜⊡⋕0
      ≡⍜(°□⊡1)(⊜⋕≠@ .)
      ⟜(⊡0⍉)
    
      # own attempt, produces a too low number
      # ≡(:∩°□°⊟
      #   ⍣(⍤.◡⍣(1⍤.(≤/×)⍤.(≥/+),,)0
      #     ⊙¤⋯⇡ⁿ:2-1⊸⧻
      #     ⊞(⍥(⟜⍜(⊙(↙2))(⨬+×⊙°⊟⊡0)
      #         ↘1
      #       )⧻.
      #       ⍤.=0⧻.
      #     )
      #     ∈♭◌
      #   )0)
    
      # reduce approach found on the programming.dev AoC community by mykl@lemmy.world
      ≡(◇(∈/(◴♭[⊃(+|×)]))⊡0:°⊂)
      °□/+▽
    )
    
    PartTwo ← (
      &rs ∞ &fo "input-7.txt"
      ⊜(□⊜⋕¬∈": ".)≠@\n.
      ⟜≡◇⊢
      ≡◇(∈/(◴♭[≡⊃⊃(+|×|⋕$"__")]):°⊂)
      °□/+▽
    )
    
    &p "Day 7:"
    &pf "Part 1: "
    &p PartOne
    &pf "Part 2: "
    &p PartTwo
    
  • sjmulder@lemmy.sdf.org
    link
    fedilink
    arrow-up
    3
    ·
    17 days ago

    C

    Big integers and overflow checking, what else is there to say 😅​

    Code
    #include "common.h"
    
    /* returns 1 on sucess, 0 on overflow */
    static int
    concat(uint64_t a, uint64_t b, uint64_t *out)
    {
    	uint64_t mul;
    
    	for (mul=1; mul<=b; mul*=10) ;
    
    	return 
    	    !__builtin_mul_overflow( mul, a, out) &&
    	    !__builtin_add_overflow(*out, b, out);
    }
    
    static int
    recur(uint64_t expect, uint64_t acc, uint64_t arr[], int n, int p2)
    {
    	uint64_t imm;
    
    	return
    	    n < 1 ? acc == expect :
    	    acc >= expect ? 0 :
    	    recur(expect, acc + arr[0], arr+1, n-1, p2) ||
    	    recur(expect, acc * arr[0], arr+1, n-1, p2) ||
    	    (p2 && concat(acc, arr[0], &imm)
    	        && recur(expect, imm, arr+1, n-1, p2));
    }
    
    int
    main(int argc, char **argv)
    {
    	char buf[128], *tok, *rest;
    	uint64_t p1=0, p2=0, arr[32], expect;
    	int n;
    
    	if (argc > 1)
    		DISCARD(freopen(argv[1], "r", stdin));
    	
    	while ((rest = fgets(buf, sizeof(buf), stdin))) {
    		assert(strchr(buf, '\n'));
    		expect = atoll(strsep(&rest, ":"));
    
    		for (n=0; (tok = strsep(&rest, " ")); n++) {
    			assert(n < (int)LEN(arr));
    			arr[n] = atoll(tok);
    		}
    
    		p1 += recur(expect, 0, arr, n, 0) * expect;
    		p2 += recur(expect, 0, arr, n, 1) * expect;
    	}
    
    	printf("07: %"PRIu64" %"PRIu64"\n", p1, p2);
    	return 0;
    }
    

    https://github.com/sjmulder/aoc/blob/master/2024/c/day07.c

  • hades@lemm.ee
    link
    fedilink
    arrow-up
    2
    ·
    17 days ago

    C#

    public class Day07 : Solver
    {
      private ImmutableList<(long, ImmutableList<long>)> equations;
    
      public void Presolve(string input) {
        equations = input.Trim().Split("\n")
          .Select(line => line.Split(": "))
          .Select(split => (long.Parse(split[0]), split[1].Split(" ").Select(long.Parse).ToImmutableList()))
          .ToImmutableList();
      }
    
      private bool TrySolveWithConcat(long lhs, long head, ImmutableList<long> tail) {
        var lhs_string = lhs.ToString();
        var head_string = head.ToString();
        return lhs_string.Length > head_string.Length &&
          lhs_string.EndsWith(head_string) &&
          SolveEquation(long.Parse(lhs_string.Substring(0, lhs_string.Length - head_string.Length)), tail, true);
      }
    
      private bool SolveEquation(long lhs, ImmutableList<long> rhs, bool with_concat = false) {
        if (rhs.Count == 1) return lhs == rhs[0];
        long head = rhs[rhs.Count - 1];
        var tail = rhs.GetRange(0, rhs.Count - 1);
        return (SolveEquation(lhs - head, tail, with_concat))
          || (lhs % head == 0) && SolveEquation(lhs / head, tail, with_concat)
          || with_concat && TrySolveWithConcat(lhs, head, tail);
      }
    
      public string SolveFirst() => equations
        .Where(eq => SolveEquation(eq.Item1, eq.Item2))
        .Select(eq => eq.Item1)
        .Sum().ToString();
      public string SolveSecond() => equations
        .Where(eq => SolveEquation(eq.Item1, eq.Item2, true))
        .Select(eq => eq.Item1)
        .Sum().ToString();
    }
    
  • Ananace@lemmy.ananace.dev
    link
    fedilink
    arrow-up
    2
    ·
    edit-2
    17 days ago

    Made a couple of attempts to munge the input data into some kind of binary search tree, lost some time to that, then threw my hands into the air and did a more naïve sort-of breadth-first search instead. Which turned out to be better for part 2 anyway.
    Also, maths. Runs in just over a hundred milliseconds when using AsParallel, around half a second without.

    C#
    List<(long, int[])> data = new List<(long, int[])>();
    
    public void Input(IEnumerable<string> lines)
    {
      foreach (var line in lines)
      {
        var parts = line.Split(':', StringSplitOptions.TrimEntries);
    
        data.Add((long.Parse(parts.First()), parts.Last().Split(' ').Select(int.Parse).ToArray()));
      }
    }
    
    public void Part1()
    {
      var correct = data.Where(kv => CalcPart(kv.Item1, kv.Item2)).Select(kv => kv.Item1).Sum();
    
      Console.WriteLine($"Correct: {correct}");
    }
    public void Part2()
    {
      var correct = data.AsParallel().Where(kv => CalcPart2(kv.Item1, kv.Item2)).Select(kv => kv.Item1).Sum();
    
      Console.WriteLine($"Correct: {correct}");
    }
    
    public bool CalcPart(long res, Span<int> num, long carried = 0)
    {
      var next = num[0];
      if (num.Length == 1)
        return res == carried + next || res == carried * next;
      return CalcPart(res, num.Slice(1), carried + next) || CalcPart(res, num.Slice(1), carried * next);
    }
    
    public bool CalcPart2(long res, Span<int> num, long carried = 0)
    {
      var next = num[0];
      // Get the 10 logarithm for the next number, expand the carried value by 10^<next 10log + 1>, add the two together
      // For 123 || 45
      // 45 ⇒ 10log(45) + 1 == 2
      // 123 * 10^2 + 45 == 12345
      long combined = carried * (long)Math.Pow(10, Math.Floor(Math.Log10(next) + 1)) + next;
      if (num.Length == 1)
        return res == carried + next || res == carried * next || res == combined;
      return CalcPart2(res, num.Slice(1), carried + next) || CalcPart2(res, num.Slice(1), carried * next) || CalcPart2(res, num.Slice(1), combined);
    }
    
  • TunaCowboy@lemmy.world
    link
    fedilink
    arrow-up
    2
    ·
    edit-2
    17 days ago

    python

    45s on my machine for first shot, trying to break my will to brute force 😅. I’ll try improving on it in a bit after I smoke another bowl and grab another drink.

    solution
    import itertools
    import re
    import aoc
    
    def ltr(e):
        r = int(e[0])
        for i in range(1, len(e), 2):
            o = e[i]
            n = int(e[i + 1])
            if o == '+':
                r += n
            elif o == '*':
                r *= n
            elif o == '||':
                r = int(f"{r}{n}")
        return r
    
    def pl(l, os):
        d = [int(x) for x in re.findall(r'\d+', l)]
        t, ns = d[0], d[1:]
        ops = list(itertools.product(os, repeat=len(ns) - 1))
        for o in ops:
            e = str(ns[0])
            for i, op in enumerate(o):
                e += f" {op} {ns[i + 1]}"
            r = ltr(e.split())
            if r == t:
                return r
        return 0
    
    def one():
        lines = aoc.get_lines(7)
        acc = 0
        for l in lines:
            acc += pl(l, ['+', '*'])
        print(acc)
    
    def two():
        lines = aoc.get_lines(7)
        acc = 0
        for l in lines:
            acc += pl(l, ['+', '*', '||'])
        print(acc)
    
    one()
    two()
    
      • TunaCowboy@lemmy.world
        link
        fedilink
        arrow-up
        1
        ·
        edit-2
        16 days ago

        It’s not a long lived project, it’s a puzzle, and once solved never needs to run again. My objective here is to get the correct answer, not win a style contest.

        Can you provide a link to your solution? I’d like to check it out.

        • Katzenmann@feddit.org
          link
          fedilink
          English
          arrow-up
          1
          ·
          edit-2
          16 days ago

          My initial comment was a bit harsh, I’m sorry for that. It was meant to be a bit of a joke. Anyway here’s my code. Do note that I don’t do the challenges timed so I have a bit more time to name my variables accordingly. Takes 35 seconds to run on a pc with a AMD Ryzen 5 5600

          import sys
          from tqdm import tqdm
          
          
          input = sys.stdin.read()
          
          def all_operator_permutations(operator_count):
              if operator_count == 0:
                  return [[]]
          
              smaller_permutations = all_operator_permutations(operator_count-1)
              return [
                      *[['+', *ops] for ops in smaller_permutations],
                      *[['*', *ops] for ops in smaller_permutations],
                      *[['||', *ops] for ops in smaller_permutations],
                      ]
          
          def test_operators(ops, values):
              res = values.pop(0)
              for op in ops:
                  match op:
                      case '*':
                          res *= values.pop(0)
                      case '+':
                          res += values.pop(0)
                      case '||':
                          res = int(f"{res}{values.pop(0)}")
              return res
          
          
          total_calibration_result = 0
          
          for line in tqdm(input.splitlines()[:]):
              target, *tail = line.split(':')
              target = int(target)
              values = [int(val) for val in tail[0].split()]
          
              all_perms = all_operator_permutations(len(values) - 1)
              ops = all_perms.pop()
              while True:
                  res = test_operators(ops, values.copy())
                  if res == target:
                      total_calibration_result += target
                      break
                  if not all_perms:
                      break
                  ops = all_perms.pop()
          
          print(total_calibration_result)
          
  • janAkali@lemmy.one
    link
    fedilink
    English
    arrow-up
    2
    ·
    edit-2
    17 days ago

    Nim

    Bruteforce, my beloved.

    Wasted too much time on part 2 trying to make combinations iterator (it was very slow). In the end solved both parts with 3^n and toTernary.

    Runtime: 1.5s

    func digits(n: int): int =
      result = 1; var n = n
      while (n = n div 10; n) > 0: inc result
    
    func concat(a: var int, b: int) =
      a = a * (10 ^ b.digits) + b
    
    func toTernary(n: int, len: int): seq[int] =
      result = newSeq[int](len)
      if n == 0: return
      var n = n
      for i in 0..<len:
        result[i] = n mod 3
        n = n div 3
    
    proc solve(input: string): AOCSolution[int, int] =
      for line in input.splitLines():
        let parts = line.split({':',' '})
        let res = parts[0].parseInt
        var values: seq[int]
        for i in 2..parts.high:
          values.add parts[i].parseInt
    
        let opsCount = values.len - 1
        var solvable = (p1: false, p2: false)
        for s in 0 ..< 3^opsCount:
          var sum = values[0]
          let ternary = s.toTernary(opsCount)
          for i, c in ternary:
            case c
            of 0: sum *= values[i+1]
            of 1: sum += values[i+1]
            of 2: sum.concat values[i+1]
            else: raiseAssert"!!"
          if sum == res:
            if ternary.count(2) == 0:
              solvable.p1 = true
            solvable.p2 = true
            if solvable == (true, true): break
        if solvable.p1: result.part1 += res
        if solvable.p2: result.part2 += res
    

    Codeberg repo

  • JRaccoon@discuss.tchncs.de
    link
    fedilink
    English
    arrow-up
    2
    ·
    17 days ago

    Java

    Today was pretty easy one but for some reason I spent like 20 minutes overthinking part 2 when all it needed was one new else if. I initially through the concatenation operator would take precedence even tho it clearly says “All operators are still evaluated left-to-right” in the instructions…

    I’m sure there are optimizations to do but using parallelStreams it only takes around 300ms total on my machine so there’s no point really

    The code
    import java.io.IOException;
    import java.nio.charset.StandardCharsets;
    import java.nio.file.Files;
    import java.nio.file.Path;
    import java.util.Arrays;
    import java.util.List;
    
    public class Day7 {
        public static void main(final String[] _args) throws IOException {
            final List<Equation> equations = Files.readAllLines(Path.of("2024\\07\\input.txt"), StandardCharsets.UTF_8).stream()
                .map(line -> line.split(":\\s"))
                .map(line -> new Equation(
                        Long.parseLong(line[0]),
                        Arrays.stream(line[1].split("\\s"))
                            .map(Integer::parseInt)
                            .toArray(Integer[]::new)
                    )
                ).toList();
    
            final char[] part1Operators = {'+', '*'};
            System.out.println("Part 1: " + equations.parallelStream()
                .mapToLong(equation -> getResultIfPossible(equation, part1Operators))
                .sum()
            );
    
            final char[] part2Operators = {'+', '*', '|'};
            System.out.println("Part 2: " + equations.parallelStream()
                .mapToLong(equation -> getResultIfPossible(equation, part2Operators))
                .sum()
            );
        }
    
        private static Long getResultIfPossible(final Equation equation, final char[] operators) {
            final var permutations = Math.pow(operators.length, equation.values.length - 1);
            for (int i = 0; i < permutations; i++) {
                long result = equation.values[0];
                int count = i;
    
                for (int j = 0; j < equation.values.length - 1; j++) {
                    // If the result is already larger than the expected one, we can short circuit here to save some time
                    if (result > equation.result) {
                        break;
                    }
    
                    final char operator = operators[count % operators.length];
                    count /= operators.length;
    
                    if (operator == '+') { result += equation.values[j + 1]; }
                    else if (operator == '*') { result *= equation.values[j + 1]; }
                    else if (operator == '|') { result = Long.parseLong(String.valueOf(result) + String.valueOf(equation.values[j + 1])); }
                    else {
                        throw new RuntimeException("Unsupported operator " + operator);
                    }
                }
    
                if (result == equation.result) {
                    return result;
                }
            }
    
            return 0L;
        }
    
        private static record Equation(long result, Integer[] values) {}
    }
    
  • mykl@lemmy.world
    link
    fedilink
    arrow-up
    2
    ·
    edit-2
    17 days ago

    Dart

    Suspiciously easy, so let’s see how tomorrow goes… (edit: forgot to put the language! Dart for now, thinking about Uiua later)

    import 'package:more/more.dart';
    
    var ops = [(a, b) => a + b, (a, b) => a * b, (a, b) => int.parse('$a$b')];
    
    bool canMake(int target, List<int> ns, int sofar, dynamic ops) {
      if (ns.isEmpty) return target == sofar;
      for (var op in ops) {
        if (canMake(target, ns.sublist(1), op(sofar, ns.first), ops)) return true;
      }
      return false;
    }
    
    solve(List<String> lines, dynamic ops) {
      var sum = 0;
      for (var line in lines.map((e) => e.split(' '))) {
        var target = int.parse(line.first.skipLast(1));
        var ns = line.skip(1).map(int.parse).toList();
        sum += (canMake(target, ns.sublist(1), ns.first, ops)) ? target : 0;
      }
      return sum;
    }
    
    part1(List<String> lines) => solve(lines, ops.sublist(0, 2));
    part2(List<String> lines) => solve(lines, ops);