#Day 7

1 messages · Page 1 of 1 (latest)

fair herald
# 
Ran 2025 day 7:
  Part 1: ✅ (in 1.763 ms)
  Part 2: ✅ (in 1.609 ms)
#

I think this is the first day so far where ive been happy with my original solution and wont need to rewrite it

noble fiber
#

I LOVED today

# 
Ran 2025 day 7:
  Part 1: _ (in 958 µs)
  Part 2: _ (in 1.234 ms)
#

was going to keep track of all the timelines, but remembered that I should never do more work than needed, and that all I need is the count of timelines

#

did some working out by hand to figure out the pattern (really helped simplify it in my head) and modified my part 1 solution just a little bit

fair herald
#

seems like your solution is pretty similar to mine

noble fiber
#

pretty much

#

I like how you've used set operations to update the beam positions

#

seems smarter than my nested fold

#

did you write your solution for the general case with n initial beams?

fair herald
#

kinda by accident just cause it ended up being easier yeah lol

noble fiber
#

yeah, it also does seem like a possible part 2 when you're on part 1

#

why do you sized_chunk on line 13? just to ignore the last line? is that because you saw the last line is empty (unlikely) or because your utils.lines adds an extra empty line or something like that?

fair herald
#

its because every second line is empty

#

so this

list.sized_chunk(2)
|> list.map(fn(lines) {
  let assert [first, _] = lines
  ...
})

only processes every even line

noble fiber
#

OH it's not window

fair herald
#

yeah

versed aurora
#

It took me sooo long

fair herald
#

its not strictly necessary, since both parts will work with empty sets

#

but it just avoids unnecessary operations

noble fiber
#

but i did some working out by hand

fair herald
#

i came up with the idea for my solution on a whim and just hoped that it would work

#

im glad i was right

#

overall enjoying the problems this year much more than i usually do

#

if we can get through all of them without any maze solving i would be happy

noble fiber
fair herald
#

yeah theyre definitely a bit easier, but I like the more moderate difficulty

#

it means i dont have to dedicate 2+ hours each day to aoc

noble fiber
#

that could be either because

  1. eric is still calibrating for a 12-day AoC
  2. the last time I did AoC was 2 years ago and (I hope) I'm a much better programmer now
versed aurora
#

I really like the solution I came up with though I'll have to clean it up later

#

I've picked keysmash names in a rush

fn asd(rows, start, splitters) { ... }
fn a(rays, splitters) { ... }
#

What's asd and a? I hope the me that wakes up in two hours will remember

noble fiber
#

good point

#

i should go back to sleep

fair herald
#

thankfully aoc starts at 4pm here in aus

open lodge
#

ouch, this was painful. I was being "clever" when I wrote one of my dict.upserts and it took a long time to find out. -_-

dusk cobalt
#

i should stop using u32

#

just use u64 or u128 i can do it

#

decided to use rust for this one when i was still trying to bruteforce it

#

and i had the right answer but u32

versed aurora
#

I had a dream where you came up with a gleam solution that took 5ns

noble fiber
versed aurora
#

Doing a jak was fun, wasn’t it??

noble fiber
noble fiber
versed aurora
noble fiber
noble fiber
chilly badge
#

Blessed be Set and Dict

#

Me at problem 2:

4x.png
#

"Surely I can just brute force computing individual beams, right?"

#

In the end I used a Dict(Int, Int) to track how many beams each location had at any given time, which I believe is almost identical to what i did in problem 1 which was to use a Set(Int) since I believe that's just a Dict(Int, Nil)

#

And then the final amount of beams is how many times a beam was split

noble fiber
versed aurora
#

I made it stupid fast

part 1: 0.107ms ±0.2      
part 2: 0.110ms ±0.2
#

I feel so smug about this

noble fiber
#

daaamn

versed aurora
#

The cool thing is this doesn't have to parse anything, it just goes over the entire string once and it's done

#

I'm a parse denier now, fuck parsing

noble fiber
#

yeah, i realised that a bit, I think. I was doing a fold within a fold with the same acc, and I thought that looked like the same as just folding over the string

versed aurora
#

I think this is my favourite day so far

noble fiber
#

what I really found surprising was the huge difference in orders of magnitude between the answers

#

almost 10 billion times

nocturne surge
#

hashmaps go brrrr

thick leaf
#

I have a very nice and clean recursive solution for part 2, made a lot more ugly by the fact that I need to do all sorts of weird actor-message-sending stuff to get a mutable memoization cache 😐

solemn bluff
#

today was p fun

#

at first for part 2 I tried replacing a set by a list, but that would have needed a list of 25 trillion elements so that wasn't feasible

so I just made it into a dict that kept the count

noble fiber
#

yeah, it's always best to avoid doing work you don't strictly need to do

solemn bluff
# 
type Splitters =
  Set(Int)


fn part1(input: #(Int, List(Splitters))) -> Nil {
  let #(start, splitters) = input

  let #(result, _) = {
    use #(count, beams), row <- list.fold(splitters, #(
      0,
      set.from_list([start]),
    ))
    let #(splits, beams) = splitter_pass(row, beams)
    #(count + splits, beams)
  }

  result
  |> int.to_string()
  |> string.append("Part 1: ", _)
  |> io.println()
}

fn part2(input: #(Int, List(Splitters))) -> Nil {
  let #(start, splitters) = input

  let result =
    {
      use beams, row <- list.fold(splitters, dict.from_list([#(start, 1)]))
      splitter_quantum_pass(row, beams)
    }
    |> dict.fold(0, fn(acc, _, n) { acc + n })

  result
  |> int.to_string()
  |> string.append("Part 2: ", _)
  |> io.println()
}

fn splitter_pass(s: Splitters, beams: Set(Int)) -> #(Int, Set(Int)) {
  use #(count, next), beam <- set.fold(beams, #(0, set.new()))
  case set.contains(s, beam) {
    True -> #(count + 1, next |> set.insert(beam - 1) |> set.insert(beam + 1))
    False -> #(count, set.insert(next, beam))
  }
}

fn splitter_quantum_pass(s: Splitters, beams: Dict(Int, Int)) -> Dict(Int, Int) {
  use next, beam, beam_count <- dict.fold(beams, dict.new())
  let inc = fn(x) {
    case x {
      Some(x) -> x + beam_count
      None -> beam_count
    }
  }

  case set.contains(s, beam) {
    True -> next |> dict.upsert(beam - 1, inc) |> dict.upsert(beam + 1, inc)
    False -> next |> dict.upsert(beam, inc)
  }
}
merry epoch
#

Can someone explain to me what part1 is actually asking for?

#

like

#

am i counting every time i encounter a splitter?

solemn bluff
#

yes

#

and also two beams can't appear on the same spot

merry epoch
#

ehh ok

#

timelines?!

#

wtf

earnest vault
#

Part 2 is not as complicated as it first appears

sand lava
#

today was fun!

pub fn pt_1(input: #(Int, List(List(Int)))) {
  let #(starting_pos, splitters) = input

  let acc = #(set.new() |> set.insert(starting_pos), 0)
  let acc =
    list.fold(splitters, acc, fn(acc, row) {
      list.fold(row, acc, fn(acc, position) {
        let #(beams, count) = acc

        case set.contains(acc.0, position) {
          True -> {
            let beams =
              beams
              |> set.delete(position)
              |> set.insert(position - 1)
              |> set.insert(position + 1)
            let count = count + 1

            #(beams, count)
          }
          False -> acc
        }
      })
    })

  acc.1
}

pub fn pt_2(input: #(Int, List(List(Int)))) {
  let #(starting_pos, splitters) = input

  let acc = dict.new() |> dict.insert(starting_pos, 1)
  let acc =
    list.fold(splitters, acc, fn(acc, row) {
      list.fold(row, acc, fn(acc, position) {
        let prev = acc |> dict.get(position) |> result.unwrap(0)

        acc
        |> dict.delete(position)
        |> dict.upsert(position - 1, fn(value) {
          value |> option.unwrap(0) |> int.add(prev)
        })
        |> dict.upsert(position + 1, fn(value) {
          value |> option.unwrap(0) |> int.add(prev)
        })
      })
    })

  acc |> dict.values |> int.sum
}

Ran 2025 day 7:
  Part 1: ✅ met expected value: 1537 (in 645 µs)
  Part 2: ✅ met expected value: 18818811755665 (in 516 µs)
thick leaf
#

Oh that's better:

fn count_timelines(
  remaining_layers: List(set.Set(Int)),
  location: Int,
  cache_handle,
) -> Int {
  let cache_key = #(list.length(remaining_layers), location)
  use <- memoize(cache_handle, cache_key)
  case remaining_layers {
    [] -> 1
    [current_layer, ..rest] -> {
      let split_this_layer = set.contains(current_layer, location)
      let answer = case split_this_layer {
        False -> count_timelines(rest, location, cache_handle)
        True ->
          count_timelines(rest, location - 1, cache_handle)
          + count_timelines(rest, location + 1, cache_handle)
      }
      actor.send(cache_handle, Set(cache_key, answer))
      answer
    }
  }
}

Using a self-written memoize function that uses an actor to keep the memo table

merry epoch
#

this is going to run for ages...

#

mine :P

thick leaf
#

Sorry

#

Yes, part 2 needs some trickery because the answer is Really Quite Large ™

merry epoch
#

:P

candid chasm
merry epoch
#

my clever solution for part2 is still not fast enough

#

nvm i just forgot to add to the dict

wicked yacht
#

Ended up with same iteration logic than p1 but with a dict to store the timelines counts

earnest vault
#

Yeah that's pretty much what I did

cyan snow
#

same, part 2 to part 1 was just going from set to dict

solemn bluff
#

same

#

I first tried going from a set to a list :>

cyan snow
thick leaf
#

Switching my cache to an ETS table dropped the timing to 5 ms from ~25

toxic rover
# 
Ran 2025 day 7:
  Part 1: _ (in 9.523 ms)
  Part 2: _ (in 6.144 ms)

way more timelines than I expected

scenic frigate
#

Numberphile recently released a video which is relevant ||https://www.youtube.com/watch?v=JXUOMsFBDXQ||

YouTube
Computerphile
Code Optimisation via Memoization - Computerphile

Learn this caching trick for faster code from Dr Mike Pound -- Check out Brilliant's courses and start for free at https://brilliant.org/computerphile/ (episode sponsor) -- More links in full description below ↓↓↓
Computerphile is supported by Jane Street. Learn more about them (and exciting career opportunities) at: https://jane-st.co/com...

▶ Play video
fair herald
#

Tbh the search+cache/memoization solutions seem like way more work to implement than the linear solution

noble fiber
#

yeah, i saw a bunch of people doing the memoization + tree search on the subreddit and it seemed much less intuitive than counting beam overlaps

earnest vault
#

Yep. I considered memoisation but set -> dict was a much easier transition than rewriting the entire solution

fair herald
#

Someone I know made this super clean version of the dict/hashmap solution in ruby

splits = 0
counters = Hash.new 0

ARGF.each_line(chomp: true) do |line|
  line.chars.each_with_index do |char, col|
    if char == ?^
      splits += 1 if counters[col] > 0
      counters[col - 1] += counters[col]
      counters[col + 1] += counters[col]
      counters[col] = 0
    elsif char == ?S
      counters[col] = 1
    end
  end
end

puts splits
puts counters.values.sum

In tempted to convert it to gleam to simplify my solution even further

versed aurora
#

I just used a list and went over the whole string

versed aurora
noble fiber
fair herald
#

Yeah it's the same general algorithm, just stripped down to the bare minimum

#

I also like the way it incorporates the pt 1 solution into the logic for pt 2

scenic frigate
faint tinsel
lilac hatch
#

I don't like how I had to separate part 1 and 2 tho

earnest vault
#

You can do it without memoisation

lilac hatch
#

:o

#

I was readng Jak's solution and my brain broke

merry epoch
#

i basically slapped memoization around the naive solution

#

I overcomplicated it a bit before i got to that solution, tough :P

lilac hatch
#

That's pretty cool. A bit too clever for me. Grug brain over here

#

Oh wait, because the splitter collision can't count for anything

lilac hatch
#

Oh good, I managed to clean up my solution without changing approach. Much easier now

scenic frigate
fair herald
#

You take the dict elements where it hits splitters, and duplicate those elements to the left (-1 to index) and right (+1 to index) of the splitter

#

Then just merge those left and right shifted dicts with the dict of elements that didn't hit anything, adding together anything on the same index

runic iron
# 
  Part 1:_ (in 79.839 ms)
  Part 2: _ (in 59.271 ms)

Went with a naive solution that had a cache slapped on it using ETS 🤡 (updated: tiny bit faster)

lilac hatch
rain roost
#

I also like watching @versed aurora on twitch, but never get to see it live because I don’t want spoilers until I’ve done the problem.

soft walrus
dire radish
#

I'm finding this one very tough, my solutions keeps rounding back to arrays, and there are no arrays...

fair herald
dire radish
soft walrus