Crespyl's recent activity

  1. Comment on Day 2: Rock Paper Scissors in ~comp.advent_of_code

    Crespyl
    Link
    I'm confident that there's a tighter solution, but this is a simple puzzle and I'm in a lazy mood: Parts 1 & 2, Clojure (defn line-result [line] (case (first line) \A (case (last line) \X (+ 1 3)...

    I'm confident that there's a tighter solution, but this is a simple puzzle and I'm in a lazy mood:

    Parts 1 & 2, Clojure
    (defn line-result [line]
      (case (first line)
        \A (case (last line)
             \X (+ 1 3)
             \Y (+ 2 6)
             \Z (+ 3 0))
        \B (case (last line)
             \X (+ 1 0)
             \Y (+ 2 3)
             \Z (+ 3 6))
        \C (case (last line)
             \X (+ 1 6)
             \Y (+ 2 0)
             \Z (+ 3 3))))
    
    (defn part-1 [input]
      (reduce + (map line-result input)))
    
    (defn line-result-2 [line]
      (case (first line)
        \A (case (last line)
             \X (+ 3 0)
             \Y (+ 1 3)
             \Z (+ 2 6))
        \B (case (last line)
             \X (+ 1 0)
             \Y (+ 2 3)
             \Z (+ 3 6))
        \C (case (last line)
             \X (+ 2 0)
             \Y (+ 3 3)
             \Z (+ 1 6))))
    
    (defn part-2 [input]
      (reduce + (map line-result-2 input)))
    
    2 votes
  2. Comment on Day 1: Calorie Counting in ~comp.advent_of_code

    Crespyl
    Link
    Working in Clojure this time around, also probably not going to try and stay up all night so much this year. Parts 1 & 2 (defn parse-elves [input] (->> (str/split input #"\n\n") (map...

    Working in Clojure this time around, also probably not going to try and stay up all night so much this year.

    Parts 1 & 2
    (defn parse-elves [input]
      (->> (str/split input #"\n\n")
          (map #(str/split-lines %))
          (map #(map parse-long %))
          (map vec)))
    
    (defn sort-elves [elves]
      (->> elves
           (sort-by #(reduce + %))
           (reverse)))
    
    (defn part-1 [input]
      (->> input
           parse-elves
           sort-elves
           first
           (reduce +)))
    
    (defn part-2 [input]
      (let [elves (sort-elves (parse-elves input))
            first (nth elves 0)
            second (nth elves 1)
            third (nth elves 2)]
        (reduce + (concat first second third))))
    
    2 votes
  3. Comment on What games have you been playing, and what's your opinion on them? in ~games

    Crespyl
    Link
    I've just recently finished Stray, which was a little on the short side, but the length is enough to get my fill and not wear out its welcome. I'd only seen a couple teaser trailers, so I went in...

    I've just recently finished Stray, which was a little on the short side, but the length is enough to get my fill and not wear out its welcome.

    I'd only seen a couple teaser trailers, so I went in not knowing about a couple of core elements, and those pieces were a nice surprise when the game unlocked them for me.

    I really liked the design of the explorable areas, though it's held back a little by being a bit inconsistent with which things you can jump to or how high you can go with each jump.

    I've also started another attempt at Disco Elysium, but that's the sort of game I feel like I have to chew on quite a bit in between sessions. Lovely art though.

    5 votes
  4. Comment on CGP Grey on zebra vs horse domestication in ~life

    Crespyl
    Link Parent
    I do fear Poe's Law in these situations. I'm pretty sure I've met enough people who have genuinely joked about that very line ("Cows are machines..."), not finding it absurd at all (just funny),...

    I do fear Poe's Law in these situations. I'm pretty sure I've met enough people who have genuinely joked about that very line ("Cows are machines..."), not finding it absurd at all (just funny), while being explicity opposed to animal rights discussion.

    4 votes
  5. Comment on BMW makes heated seats a monthly subscription in ~tech

    Crespyl
    Link Parent
    I've had cause to do this with my Android on a number of occasions, usually for p2p local file transfers in areas with no or limited service. It's often easier to make my phone into a hotspot with...

    I've had cause to do this with my Android on a number of occasions, usually for p2p local file transfers in areas with no or limited service. It's often easier to make my phone into a hotspot with a short-lived web server than to rummage around trying to find the right combination of cables/sd cards/readers/adapters/system settings.

    Services like AirDrop or whatever Google calls their "people nearby" sharing are getting better, but often still seem to need internet access or have other UX issues; everyone can connect to a hotspot and open their browser.

    5 votes
  6. Comment on Does anybody have any experience with switching to pipewire? in ~comp

    Crespyl
    Link
    I switched my KDE Neon desktop over, maybe a year or two back, and it was pretty straightforward; I haven't had any issues with it since. In my case it was just a matter of installing the...

    I switched my KDE Neon desktop over, maybe a year or two back, and it was pretty straightforward; I haven't had any issues with it since.

    In my case it was just a matter of installing the appropriate pipewire packages and swapping out the systemd services.

    If you need any help with the specifics I can go run down the notes I took, but if you're on Arch already it should be pretty manageable. As long as you have the pipewire-pulse adapter, it should be totally transparent to all your PA-using applications.

    3 votes
  7. Comment on Happy 4th Birthday, Tildes! in ~tildes

    Crespyl
    Link
    Wow, it feels like such a short time ago, but so much has happened since then! Props to Deimos and all the tilders for maintaining this little corner of sanity on the internet, and here's to many...

    Wow, it feels like such a short time ago, but so much has happened since then!

    Props to Deimos and all the tilders for maintaining this little corner of sanity on the internet, and here's to many more years!

    13 votes
  8. Comment on Slow Social, a social network built for friends, not influencers in ~tech

    Crespyl
    Link Parent
    Your link lost the h from https, which has the interesting result (in at least my browser) of rendering as a normal link, but it does nothing when clicked. I'm pretty sure I've usually seen...

    Your link lost the h from https, which has the interesting result (in at least my browser) of rendering as a normal link, but it does nothing when clicked. I'm pretty sure I've usually seen browsers prompt the user when they encounter an unknown protocol (like ttps://... ought to be), but that doesn't seem to happen in this case. I'm not sure why that is.

    3 votes
  9. Comment on Is it a good time to upgrade to Windows 11? in ~tech

    Crespyl
    Link Parent
    Anecdotally, I can say that running WSL2 (mind the 2 there, there's a big architectural shift going from WSL1 to 2) on Win10 with a third-party X server (I've used Xming and most recently GWSL)...

    Anecdotally, I can say that running WSL2 (mind the 2 there, there's a big architectural shift going from WSL1 to 2) on Win10 with a third-party X server (I've used Xming and most recently GWSL) has worked fine for me in the past.

    Under the hood, WSL2 is actually just creating and managing a VM for you, so there's still that resource commitment in a chunk of ram and disk space, but the overall experience is quite good.

    The new stuff with native graphical support is based on Wayland instead of X, and may or may not have some teething issues, but I'm not using Wayland yet even on my desktop which runs KDE Neon full time. That said, the initial demos for the Win11 graphical WSL work do look really promising, and there's a chance that I end up getting value from Wayland on Windows before I do much with it on Linux.

    4 votes
  10. Comment on Gaming on Linux - LTT Daily Driver Challenge Finale in ~games

    Crespyl
    Link Parent
    This has been my experience as well, but, like you, I also have a pretty long history with Linux and know how to dig around and find information efficiently, as well as how to keep an eye out for...

    This has been my experience as well, but, like you, I also have a pretty long history with Linux and know how to dig around and find information efficiently, as well as how to keep an eye out for compatibility issues when buying hardware. My taste in games also tends to lean towards older/indie games, open source stuff, or things with native ports, so Proton is usually really smooth for me. The tricky ones (as always) are the occasional multiplayer games my friends want me in on, some stuff from non-Steam stores (usually manageable once it's set up, but always a pain getting there), and of course anything with invasive anti-cheat.

    If I can find a report of anyone getting a game working with Proton, then I can usually feel confident enough picking it up and getting it running myself even outside of Steam; but I couldn't recommend it to someone who isn't at least a "power user" on Windows and used to doing things like, for example, downgrading a graphics driver version because of a regression in some game, or jumping through hoops to get some third party controller working properly (both things I've had to do in Windows in the past).

    It's definitely still a tinkerer's experience now, but it's constantly getting better, and if you're of the tinkering mindset and don't mind getting your hands dirty every now and again there's a lot to enjoy about the whole process, and (IMO) enough other benefits to Linux to make it a daily driver.

    Definitely can recommend the dual-boot route, just getting that set up for the first time is a good learning experience on its own, and once you get a taste of the workflow (and aesthetic) customization options you may find it hard to go back.

    7 votes
  11. Comment on Day 21: Dirac Dice in ~comp.advent_of_code

    Crespyl
    Link
    Well part one is easy enough, part two looks like the modular arithmetic problem from Day 22 of 2019, and is probably beyond my abilities (certainly beyond my abilities for tonight!). I'll...

    Well part one is easy enough, part two looks like the modular arithmetic problem from Day 22 of 2019, and is probably beyond my abilities (certainly beyond my abilities for tonight!). I'll probably do some reading over the next few days and see if I can make some headway, but I'm also heading up to visit the family for the rest of the holidays, so this will probably mark the end of my day-by-day solving.

    Happy Christmas and a merry New Year to everyone, it's been fun solving with y'all!

    Part 1 Ruby

    I went with a somewhat overly verbose object oriented approach, thinking that maybe part two would involve rolling lots of separate dice, deterministic or otherwise. I was sort of right, but not in a way that made this particular DDice class useful.

    class DDice
      def initialize()
        @max = 100
        @next_roll = 1
        @total_rolls = 0
      end
    
      def total_rolls
        @total_rolls
      end
    
      def roll
        @total_rolls += 1
        result = @next_roll
    
        @next_roll = @next_roll + 1
        @next_roll = 1 if @next_roll > @max
    
        return result
      end
    
      def roll_n(n)
        (0...n).map { roll }
      end
    end
    
    def wrap(n)
      n -= 10 until n <= 10
      n
    end
    
    def compute_p1(input)
      p1_pos = input.lines[0].chomp.chars.last.to_i
      p2_pos = input.lines[1].chomp.chars.last.to_i
    
      p1_score = 0
      p2_score = 0
    
      die = DDice.new
    
      loop do
        p1_rolls = die.roll_n(3)
        p1_step = p1_rolls.sum
        p1_pos = wrap(p1_pos + p1_step)
        p1_score += p1_pos
        # puts "Player 1 rolls #{p1_rolls.join('+')} and moves to space #{p1_pos} for a total score of #{p1_score}"
        break if p1_score >= 1000
    
        p2_rolls = die.roll_n(3)
        p2_step = p2_rolls.sum
        p2_pos = wrap(p2_pos + p2_step)
        p2_score += p2_pos
        # puts "Player 2 rolls #{p2_rolls.join('+')} and moves to space #{p2_pos} for a total score of #{p2_score}"
        break if p2_score >= 1000
      end
    
      winner = p1_score >= 1000 ? 'p1' : 'p2'
      loser  = p1_score >= 1000 ? 'p2' : 'p1'
      puts "#{winner} wins with #{[p1_score, p2_score].max} points, after #{die.total_rolls} rolls"
      puts "#{loser} loses with #{[p1_score, p2_score].min} points, after #{die.total_rolls} rolls"
    
      (([p1_score, p2_score].min) * die.total_rolls)
    end
    
    2 votes
  12. Comment on Day 20: Trench Map in ~comp.advent_of_code

    Crespyl
    Link Parent
    This is pretty much the root of the puzzle. I think every input enhancement string starts with a "#" character. Without getting too far into spoilers: the edge case that's catching you out is when...

    This is pretty much the root of the puzzle. I think every input enhancement string starts with a "#" character.

    Without getting too far into spoilers: the edge case that's catching you out is when nine "."s become a "#", but what happens in the infinite expanse of "#"s on the next step?

    2 votes
  13. Comment on Day 20: Trench Map in ~comp.advent_of_code

    Crespyl
    Link
    This was refreshingly easy after that last one! Part 1 Ruby The only tricky thing here is to keep a close eye on your puzzle input, especially the "enhancement string". if your test case passes,...

    This was refreshingly easy after that last one!

    Part 1 Ruby

    The only tricky thing here is to keep a close eye on your puzzle input, especially the "enhancement string".

    if your test case passes, but doesn't work on the real inputPay attention to what's happening in the infinite expanse outside the main area, what happens to a pixel when every value is a `1`, and what happens when every value is a `0`?
    def enhancement_index(map, x, y)
      [
        [-1, -1], [0, -1], [+1, -1],
        [-1,  0], [0,  0], [+1,  0],
        [-1, +1], [0, +1], [+1, +1]
      ].map { |dx, dy| [x + dx, y + dy] }
       .map { |nx, ny| map[[nx,ny]] }
       .join
       .tr('.#', '01')
       .to_i(2)
    end
    
    def enhance_map(map, enhancement)
      min_x = map.keys.map { |k| k[0] }.min
      max_x = map.keys.map { |k| k[0] }.max
      min_y = map.keys.map { |k| k[1] }.min
      max_y = map.keys.map { |k| k[1] }.max
    
      output = Hash.new('.')
      output.default = enhancement[enhancement_index(map, 999999999, 999999999)]
    
      ((min_x-1)..(max_x+1)).each do |x|
        ((min_y-1)..(max_y+1)).each do |y|
          output[[x,y]] = enhancement[enhancement_index(map, x, y)]
        end
      end
    
      return output
    end
    
    def print_map(map)
      min_x = map.keys.map { |k| k[0] }.min
      max_x = map.keys.map { |k| k[0] }.max
      min_y = map.keys.map { |k| k[1] }.min
      max_y = map.keys.map { |k| k[1] }.max
    
      output = Hash.new('.')
    
      ((min_y-2)..(max_y+2)).each do |y|
        ((min_x-2)..(max_x+2)).each do |x|
          print map[[x,y]]
        end
        print "\n"
      end
    end
    
    def compute_p1(input)
      enhancement = input.lines.first.chomp
    
      map = Hash.new('.')
      row, col = 0, 0
    
      input.lines[2..].each do |line|
        line.chomp.chars.each do |c|
          map[[col, row]] = c
          col += 1
        end
        row += 1; col = 0
      end
    
      step_one = enhance_map(map, enhancement)
      step_two = enhance_map(step_one, enhancement)
    
      step_two.values.tally['#']
    end
    
    Part 2 Ruby

    A little slow on the runtime here, there's certainly room to optimize, but 15s isn't bad.

    def compute_p2(input)
      enhancement = input.lines.first.chomp
    
      map = Hash.new('.')
      row, col = 0, 0
    
      input.lines[2..].each do |line|
        line.chomp.chars.each do |c|
          map[[col, row]] = c
          col += 1
        end
        row += 1; col = 0
      end
    
      50.times do
        map = enhance_map(map, enhancement)
      end
    
      map.values.tally['#']
    end
    
    3 votes
  14. Comment on Day 19: Beacon Scanner in ~comp.advent_of_code

    Crespyl
    (edited )
    Link
    PHEW! With less than an hour before todays puzzle! I liked day 19 a lot more than day 18; with 18 I felt like I understood what was supposed to be happening, but the difficulty came from a...

    PHEW! With less than an hour before todays puzzle!

    I liked day 19 a lot more than day 18; with 18 I felt like I understood what was supposed to be happening, but the difficulty came from a slightly awkward implementation and difficulty understanding what the puzzle actually wanted.

    Today (/yesterday), I really understood what I was supposed to be doing, and could properly enjoy working out the mechanism to get there. Took me ages, but I did manage it!

    Part 1 Ruby

    This code is all still a mess, with leavings from various dead-ends still hanging around. I may come back around later and try to clean it up and describe it better, but for now I'll just dump what I've got and try to give a general overview.

    Edit: Oh, I should add; the one big thing that got me going again was basically to give up on trying to figure 3D/matrix math and rotations properly, and just look at the ways that a given star at [x,y,z] might be transformed. The axes might get shuffled around (ie [y,z,x]), and the signs might get flipped eg ([-x,-y,-z]). Instead of working out proper rotations and trying those, I just generate every possible combination of axis-shuffling (which I call rotations in my code) and sign-flipping (inversion). This means more things to check, but I know the right combination has to be in there somewhere, and since I'm only looking at three stars at a time, it doesn't add too many options.

    def dist3d(a, b)
      Math.sqrt((b[0] - a[0])**2 + (b[1] - a[1])**2 + (b[2] - a[2])**2)
    end
    
    def beacon_triangles(beacons)
      beacons.combination(3).map do |a, b, c|
        ab = dist3d(a, b)
        bc = dist3d(b, c)
        ca = dist3d(c, a)
        [[ab, bc, ca].sort, Set.new([a, b, c])]
      end.to_h
    end
    
    def beacon_transformations(beacon)
      transforms = [] # list of [beacon, ['rotation', inversion]] pairs
    
      rotations  = [0,1,2].permutation(3).to_a
      inversions = [[1,1,1], [1,1,-1], [1,-1,1], [-1,1,1], [1,-1,-1], [-1,1,-1], [-1,-1,1], [-1,-1,-1]]
    
      rotations.each do |r|
        inversions.each do |i|
          transformed = [beacon[r[0]] * i[0], beacon[r[1]] * i[1], beacon[r[2]] * i[2]]
          transforms << [transformed, [r, i]]
        end
      end
    
      transforms
    end
    
    def relative_scanner_position(triangles_a, triangles_b)
      intersection = triangles_a.keys.to_set.intersection(triangles_b.keys.to_set).to_a
      return nil if intersection.empty?
    
      candidates = Hash.new(0)
    
      until intersection.empty?
        t = intersection.shift
    
        ta = triangles_a[t].to_a
        tb = triangles_b[t].to_a
    
        # for each beacon in triangle_b, try every transform and check the computed difference to each beacon in triangle_a
        tb.each_with_index do |tb_beacon, i|
          transforms = beacon_transformations(tb_beacon)
          transforms.each do |pos, ri| # transformed beacon pos, [rotation, inversion]
            c = [ta[i][0] - pos[0], ta[i][1] - pos[1], ta[i][2] - pos[2]]
            candidates[[c, ri]] += 1
          end
        end
      end
    
      # returns [scanner_position, [rotation, inversion]]
      candidates.invert[candidates.values.max]
    end
    
    def transform_scan(transform, scan)
      rotation, inversion = transform
      scan.map do |beacon|
        [beacon[rotation[0]] * inversion[0],
         beacon[rotation[1]] * inversion[1],
         beacon[rotation[2]] * inversion[2]]
      end
    end
    
    def offset_scan(offset, scan)
      scan.map do |beacon|
        [beacon[0] + offset[0],
         beacon[1] + offset[1],
         beacon[2] + offset[2]]
      end
    end
    
    # [offset, [rotation, inversion]]
    def apply_relative_position(relative_position, scan)
      offset_scan(relative_position[0], transform_scan(relative_position[1], scan))
    end
    
    def triangles_overlap?(triangles_a, triangles_b)
      intersection = triangles_a.keys.to_set.intersection(triangles_b.keys.to_set)
      intersection.size >= 220
    end
    
    # takes position+transform pairs eg a=[pos, [rotation, inversion]]
    def resolve_relative_positions(a, b)
      pos_a = a[0]
      inv_a = a[1][1]
    
      pos_b = b[0]
      inv_b = b[1][1]
    
      [pos_a[0] + pos_b[0] * inv_a[0],
       pos_a[1] + pos_b[1] * inv_a[1],
       pos_a[2] + pos_b[2] * inv_a[2]]
    end
    
    def find_path_to_0(relative_positions, origin, tgt=origin)
      return [0] if origin == 0
    
      graph = relative_positions.keys.reduce(Hash.new { Set.new }) { |g,k| g[k[0]] += [k[1]]; g }
      find_path(graph, origin, 0)
    end
    
    def find_path(graph, from, to)
      explored = Set.new([from])
      open = [from]
      path = {}
      until open.empty?
        current = open.shift
        break if current == to
    
        neighbors = graph[current].reject { explored.include?(_1) }
        neighbors.each do |n|
          explored += [n]
          path[n] = current
          open << n
        end
      end
    
      ret = [to]
    
      until to == from
        to = path[to]
        ret << to
      end
    
      ret.reverse
    end
    
    def compute_p1(input)
      scans = input.split(/--- scanner (\d+) ---/)[1..].each_slice(2).map { |n, s|
        scanner_idx = n.to_i
        reports = s.lines.map(&:chomp).reject(&:empty?).map { _1.split(',').map(&:to_i) }
        [scanner_idx, reports]
      }.to_h
    
      known_beacons = scans[0].to_set
    
      triangulated_scans = scans.map { |id,scan| {id: id, triangles: beacon_triangles(scan)} }
    
      scanner_positions = { 0 => [0,0,0] }
      scanner_transforms = { 0 => [[0,1,2], [1,1,1]] }
    
      relative_positions_a = triangulated_scans.combination(2)
                             .filter { |a,b| triangles_overlap?(a[:triangles], b[:triangles]) }
                             .map { |a,b| [[a[:id], b[:id]], relative_scanner_position(a[:triangles], b[:triangles])] }
      relative_positions_b = triangulated_scans.combination(2)
                             .filter { |a,b| triangles_overlap?(a[:triangles], b[:triangles]) }
                             .map { |b,a| [[a[:id], b[:id]], relative_scanner_position(a[:triangles], b[:triangles])] }
      relative_positions = (relative_positions_a + relative_positions_b).to_h
    
    
      # resolve scans
      resolved_scans = {0 => scans[0].to_set}
      (1...scans.size).each do |i|
        location = i
        scan = scans[i]
        path = find_path_to_0(relative_positions, i)[1..]
    
        until path[0] == 0
          scan = apply_relative_position(relative_positions[[path[0],location]], scan)
          location = path.shift
        end
    
        resolved_scans[i] = apply_relative_position(relative_positions[[0,location]], scan)
      end
    
      resolved_scans.values.inject(&:+).size
    end
    

    This puzzle is kind of like a sci-fi astronavigation problem that gets referenced fairly often; given some set of points (stars) in 3D space, how can I figure out my position relative to a known origin? I may drift back and forth between referring to the beacons as "beacons" or "stars" interchangeably because that's how I was thinking of it the whole time, so that's what's going on there.

    To do this, we need to look at the relationships between the stars (beacons here) and find similarities between the unknown (results from any scanner other than 0) and the known (results from scanner 0, since we're treating that as the origin). Initially I was trying to get by with just looking at the distance to each pair of stars in a given scan, and then finding pairs with the same distances in other scans.

    This sort of worked, but was giving me trouble with the rotations and I doubt it would've worked in the full input; so I ended up going with triangles instead.

    The slowest part of my solution is to go through each scan, find every combination of three stars (A,B,C), compute the distance in three dimensional space between each of them (AB,BC,CA), and sort those distances into an array. Once I have this normalized triangle, I store that as the key to a hash, with the three stars as the value, something like { [1,2,3] => [[x1,y1,z1], [x2,y2,z2], [x3,y3,z3]] }

    I do this for every combination of three stars in every scan, which ends up being about 2,300 triangles per scan.

    Once I have this table of triangles (and the stars involved in each) for every scan, I can start looking for intersections. Any intersection will give me a set of at least three stars that I can work out a transformation for.

    If I were a better mathematician, I'd probably know the matrix math to work this out more directly, but since I'm only looking at three stars at a time, I can just try everything and it works out well enough.

    This is the relative_scanner_position function above, it takes a pair of triangle maps (A,B), finds the triangles that are present in both, and then tries every possible transformation on each star in each triangle from B. Each time a transformed star location lines up with one of the stars from A, we add one point to that transform.

    At the end, we find the highest scoring transform and return that as the relationship between scanner A and scanner B.

    So now we can take any given pair of scans, find out if they overlap at all, and if so what the relationship is between the two.

    We do this for all overlapping scans, and as we go we're building up two important pieces of information: 1) the graph of connected/overlapping scans, and 2) a table of transforms that let us move stars from one frame of reference to another.

    Initially I tried to directly flatten all the transforms to get everything down into the coordinate space of scanner 0, but that was giving me trouble so I ended up using BFS to pathfind my way to a list of transformations to apply to each scan. Fortunately the graph is small enough that this doesn't add a meaningful amount of time.

    Then it's just a matter of flattening all the stars into one coordinate space, throwing them in a set, and counting.

    Part 2 Ruby

    I actually had, at one point, tracked down all the scanner locations (relative to scanner 0) during the part 1 solve, but ended up throwing them out at some point by the time I actually finished part 1. So I had to re-solve for that, but that ends up being as easy as mapping [0,0,0] down through the transform path with all the other stars.

    I could improve the runtime by re-using all the work from part 1, but instead I just copy-pasted everything again ¯\_(ツ)_/¯

    I enjoyed this enough that I'd like to come back and clean up the code and description a bit, but I'm out of time before day 20 and I've got holiday travel coming up, so this is what we get for now!

    def compute_p2(input)
      scans = input.split(/--- scanner (\d+) ---/)[1..].each_slice(2).map { |n, s|
        scanner_idx = n.to_i
        reports = s.lines.map(&:chomp).reject(&:empty?).map { _1.split(',').map(&:to_i) }
        [scanner_idx, reports]
      }.to_h
    
      known_beacons = scans[0].to_set
    
      triangulated_scans = scans.map { |id,scan| {id: id, triangles: beacon_triangles(scan)} }
    
      scanner_positions = { 0 => [0,0,0] }
      scanner_transforms = { 0 => [[0,1,2], [1,1,1]] }
    
      relative_positions_a = triangulated_scans.combination(2)
                               .filter { |a,b| triangles_overlap?(a[:triangles], b[:triangles]) }
                               .map { |a,b| [[a[:id], b[:id]], relative_scanner_position(a[:triangles], b[:triangles])] }
      relative_positions_b = triangulated_scans.combination(2)
                               .filter { |a,b| triangles_overlap?(a[:triangles], b[:triangles]) }
                               .map { |b,a| [[a[:id], b[:id]], relative_scanner_position(a[:triangles], b[:triangles])] }
      relative_positions = (relative_positions_a + relative_positions_b).to_h
    
      # resolve scans and positions
      resolved_scans = {0 => scans[0].to_set}
      (1...scans.size).each do |i|
        location = i
        scan = scans[i]
        pos = [[0,0,0]]
        path = find_path_to_0(relative_positions, i)[1..]
    
        until path[0] == 0
          scan = apply_relative_position(relative_positions[[path[0],location]], scan)
          pos =  apply_relative_position(relative_positions[[path[0],location]], pos)
          location = path.shift
        end
    
        resolved_scans[i] = apply_relative_position(relative_positions[[0,location]], scan)
        scanner_positions[i] = apply_relative_position(relative_positions[[0,location]], pos).first
      end
    
      def manhattan(a,b)
        a.zip(b).map { |i,j| (i-j).abs }.sum
      end
    
      scanner_positions.values.combination(2).map { |a,b| manhattan(a,b) }.max
    end
    
    ```
    
    </details>
    
    1 vote
  15. Comment on Day 18: Snailfish in ~comp.advent_of_code

    Crespyl
    Link
    Alright, here's my messy unoptimized solution: Core logic Split "Split" was the "easiest" part because it seemed like the most straight-forward. Unfortunately, it was "too easy" because I quickly...

    Alright, here's my messy unoptimized solution:

    Core logic

    Split

    "Split" was the "easiest" part because it seemed like the most straight-forward. Unfortunately, it was "too easy" because I quickly implemented a recursive split function that actually introduced a subtle bug that only became apparent when the solutions required snailfish numbers that had multiple "splittable" values at once.

    The specification requires that you only ever split one number at a time, and then check for "explodable" numbers before splitting the next number.

    So here's the (much less elegant) recursive "split-leftmost" piece (plus some supporting helpers):

    def split(n)
      split_once(n)[0]
    end
    
    def split_once(n, did_split=false)
      return [n, did_split] if did_split
    
      if (n.is_a? Fixnum) && n >= 10
        [[(n/2.0).floor, (n/2.0).ceil], true]
      elsif n.is_a? Fixnum
        [n, false]
      elsif n.is_a? Array
        split_nodes = n.map do |node|
          if did_split
            node
          else
            split_node, did_split = split_once(node, did_split)
            split_node
          end
        end
        [split_nodes, did_split]
      end
    end
    
    def can_split?(n)
      split(n) != n
    end
    

    This also introduces the theme of complex return values that include some information about the state of the recursive operation that influences the work further up the stack. This came more naturally after my horrific solution for "explode".

    Explode

    When reading the problem description, my first thought was "hey, this moving numbers left and right deal looks tricky to solve in a tree, maybe it'll be simpler if I just try to keep it as a flat string and work it that way?", and my second thought was "nahh, surely part 2 will be something fiddly that relies on tree traversal, I'll just do it as a tree, how hard could it be?". After banging my head on the wall for hours, solving it with a tree, and then going back and looking at the other string-based solutions, I definitely should've just gone with my first instinct.

    Anyway, here goes:

    def add_to_first(node, value)
      if node.is_a? Array
        [add_to_first(node[0], value), node[1]]
      else
        node + value
      end
    end
    
    def add_to_last(node, value)
      if node.is_a? Array
        [node[0], add_to_last(node[1], value)]
      else
        node + value
      end
    end
    
    def explode(n)
      apply_explode(n, 0)[:value]
    end
    
    def apply_explode(n, depth=0)
      n = n.clone
      return {explode: false, going_left: 0, going_right: 0, value: n} unless n.is_a? Array
    
      if depth >= 4
        raise "tried to explode complex pair #{n} at depth #{depth}" unless n.all? { _1.is_a? Fixnum }
    
        return {explode: true, going_left: n[0], going_right: n[1], value: 0}
      else
    
        try_left = apply_explode(n[0], depth+1)
    
        if try_left[:explode]
          n[1] = add_to_first(n[1], try_left[:going_right])
          return {explode: true, going_left: try_left[:going_left], going_right: 0, value: [try_left[:value], n[1]]}
        end
    
        try_right = apply_explode(n[1], depth+1)
        if try_right[:explode]
          n[0] = add_to_last(n[0], try_right[:going_left])
          return {explode: true, going_left: 0, going_right: try_right[:going_right], value: [n[0], try_right[:value]]}
        end
    
        return {explode: false, going_left: 0, going_right: 0, value: n}
      end
    end
    
    def can_explode?(n)
      explode(n) != n
    end
    

    This isn't really as bad as my first take, even with the overly complex return value hashes, but being super explicit about absolutely everything helped me think through it a bit. For a while I kept thinking/worrying that I was supposed to apply explode to both branches at once and somehow merge the "going_left" and "going_right" values back into the siblings, and it was tracking that down that finally helped me realize that each iteration of "explode" must only explode one pair. This ensures that it's fine to stop recursing as soon as I find one pair that does explode.

    For the longest time I kept trying to wrap my head around how best to find the next/previous simple number in the tree and propagate up and down the tree in some kind of clean recursive style. I think I might've ended up needing a structure with parent-pointers or something to do that properly. Instead, I went with this complex return value hash that indicates whether the node exploded and what values should be moved left or right, and that can propagate back up the call stack until the number lands somewhere.

    Reduce

    def reduce(n)
      loop do
        if can_explode?(n)
          n = explode(n)
        elsif can_split?(n)
          n = split(n)
        else
          return n
        end
      end
    end
    

    Magnitude

    Thankfully, this one is actually as straightforward as it looks

    def magnitude(n)
      return n unless n.is_a? Array
      3 * magnitude(n[0]) + 2 * magnitude(n[1])
    end
    
    Part 1 Ruby

    With all that in place, the actual solution is pretty easy (the input being valid list notation for use with eval is a nice plus).

    def add(a, b)
      [a, b]
    end
    
    def sum_list(list)
      list[1..].reduce(list[0]) { |sum, n| reduce(add(sum, n)) }
    end
    
    def compute_p1(input)
      numbers = input.lines.map(&:chomp).map { eval(_1) }
      sum = sum_list(numbers)
      magnitude(sum)
    end
    
    Part 2 Ruby

    And this is quite simple too, we just leverage the stdlib combination method and check each of (a+b), (b+a).

    def compute_p2(input)
      numbers = input.lines.map(&:chomp).map { eval(_1) }
    
      best = 0
      numbers.combination(2).each do |a, b|
        a_b = magnitude(reduce(add(a,b)))
        best = a_b if a_b > best
        b_a = magnitude(reduce(add(b,a)))
        best = b_a if b_a > best
      end
    
      best
    end
    
    2 votes
  16. Comment on Day 18: Snailfish in ~comp.advent_of_code

    Crespyl
    (edited )
    Link Parent
    Maybe spoilers JFC, I had the explode correct this whole time. /facepalm My problem was the order of operations for the "split" step; each iteration of split should only process one (the leftmost)...
    Maybe spoilers JFC, I had the explode correct this whole time. /facepalm

    My problem was the order of operations for the "split" step; each iteration of split should only process one (the leftmost) value. After that it should return to try an explode step before splitting any additional values.

    And with that out of the way, p2 is easy enough. I'll come back for the writeup tomorrow.

    For anyone else stuck on this one, make sure you've got your order of operations correct, don't get ahead of yourself or make any more changes for a given step than exactly what's specified.

    4 votes
  17. Comment on Day 18: Snailfish in ~comp.advent_of_code

    Crespyl
    Link Parent
    I'm glad I'm not the only one having trouble, hah. It seems like it's got to boil down to some kind of clever tree traversal/balance sort of deal, but I gotta admit I'm running out of steam on it....

    I'm glad I'm not the only one having trouble, hah.

    It seems like it's got to boil down to some kind of clever tree traversal/balance sort of deal, but I gotta admit I'm running out of steam on it.

    "Explode" really seems like the sticking point for me, and I've got a working implementation that covers all but the last big example, and it breaks for reasons I've not figured out yet.

    I suspect the biggest trick lies in how you move the "exploding" values back up and then down the tree to the correct place. I almost want to just flatten the tree back into a string or something and manipulate it that way.

    I think I'm going to have to concede this one for the night and come back to it tomorrow.

    4 votes
  18. Comment on Day 17: Trick Shot in ~comp.advent_of_code

    Crespyl
    Link Parent
    Aha, I figured there should be a closed form solution for part one, but brute-force was fast enough that I didn't bother pursuing it further. Good catch!

    Aha, I figured there should be a closed form solution for part one, but brute-force was fast enough that I didn't bother pursuing it further.

    Good catch!

    1 vote
  19. Comment on What's up with the NFT hate? in ~tech

    Crespyl
    Link Parent
    The only way I see NFTs actually being useful/relevant is if/when someone attaches them to some real service/product, not just links to jpegs. Imagine a ticketing system based on an NFT model; you...

    The only way I see NFTs actually being useful/relevant is if/when someone attaches them to some real service/product, not just links to jpegs.

    Imagine a ticketing system based on an NFT model; you have a genuinely scarce resource (seats at a specific showing of some movie/band/event), issued by some originating authority (the venue) that is obligated to provide access to the seats in exchange for the tokens. An NFT approach would let you construct a smart contract system that allows arbitrary reselling/trading of tickets in a way that guarantees the venue/band/whoever still gets some percentage cut of the secondary market, while still ensuring that the buyer knows they are getting a genuine ticket, all directly peer-to-peer with no TicketMaster/trusted-third-party in the way.

    The closest I've seen to this so far is just people talking about microtransactions for digital items/perks in online games, which is at least an improvement over jpg links, but still has most of the problems of existing microtransaction-oriented business models. If we end up in an open metaverse world where I can actually port NFT game objects from one platform to another, maybe this gets more interesting.

    Until then, I'm pretty down on any NFT scheme that doesn't connect back to some real-world service.

    5 votes
  20. Comment on Day 17: Trick Shot in ~comp.advent_of_code

    Crespyl
    Link
    Part 1 Ruby A simple brute-force approach works just fine here. def compute_p1(input) matches = input.chomp.match(/target area: x=(-?\d+)..(-?\d+), y=(-?\d+)..(-?\d+)/) x_min, x_max, y_min, y_max...
    Part 1 Ruby A simple brute-force approach works just fine here.
    def compute_p1(input)
      matches = input.chomp.match(/target area: x=(-?\d+)..(-?\d+), y=(-?\d+)..(-?\d+)/)
      x_min, x_max, y_min, y_max = matches[1..].map(&:to_i)
    
      x_range = x_min..x_max
      y_range = y_min..y_max
    
      best_x = 0
      best_y = 0
      best_max_y = 0
    
      x_range.max.times do |x|
        x_range.max.times do |y|
          hit, max_y = test_probe(x,y, x_range, y_range)
          if hit && max_y > best_max_y
            best_x = x
            best_y = y
            best_max_y = max_y
          end
        end
      end
    
      return best_max_y
    end
    
    def test_probe(vx, vy, x_range, y_range)
      x,y = 0,0
      max_y = 0
      loop do
        return [true, max_y] if x_range.include?(x) && y_range.include?(y)
        return [false, max_y] if x > x_range.max || y < y_range.min || (! x_range.include?(x) && vx == 0)
    
        x += vx
        y += vy
    
        max_y = y if y > max_y
    
        vx = (vx - (vx <=> 0)) # we use ruby's `<=>` all-in-one comparison operator, which returns one of -1, 0, or +1 depending on whether the left value is less, equal, or greater than the right value
        vy -= 1
      end
    end
    
    Part 2 Ruby My initial solution here was also just straight-forward brute force, which took about ~3min on my machine. While that was running I took a closer look at the problem and tried to work out how to narrow down the search space a bit.

    For the x-coordinate, we know that the upper bound can't be any higher than the right (/highest) side of the target box since the first step would put the probe beyond it. Next, we know that the x-velocity will eventually reach 0, and we need to make sure that it reaches the left (/lowest) side of the target area before that happens. Since the velocity decreases by one each step, we can work out the distance covered with the same series sum from an earlier puzzle (n * (n+1) / 2).

    At first, I just used this directly as a filter ( (0..x_max).filter { (_1 * (_1 + 1) / 2) >= x_min } ), but it turns out that sqrt(2n) actually gives us a quick approximation of the lower bound of that series anyway, so instead we can just search the range (Math.sqrt(x_min*2).floor..x_max).

    For the y-coordinate, the lower bound is like the x-coordinate upper bound; anything lower than the bottom edge of the target area will immediately fall past it. The upper bound turns out to be closely related, any positive velocity will reach 0 after n steps, and then by the time the probe returns to y=0, the y-velocity will be -n, and suddenly the situation looks the same as it does for the lower bound.

    All together, we have (Math.sqrt(x_min).floor >= x < x_max) and (y_min >= y < y_min.abs), which lets us narrow down the search enough to complete in under a second.

    def compute_p2(input)
      matches = input.chomp.match(/target area: x=(-?\d+)..(-?\d+), y=(-?\d+)..(-?\d+)/)
      x_min, x_max, y_min, y_max = matches[1..].map(&:to_i)
    
      ((Math.sqrt(x_min*2).floor)..x_max).to_a
        .product((y_min..(y_min.abs-1)).to_a)
        .reduce(0) do |sum, coords|
        hit, _max_y = test_probe(coords[0], coords[1], x_min..x_max, y_min..y_max)
        hit ? sum + 1 : sum
      end
    end
    
    3 votes