Crespyl's recent activity

  1. Comment on The erosion of deep literacy in ~misc

    Crespyl
    Link Parent
    I think that was the joke...

    the irony of a TL;DR

    I think that was the joke...

    6 votes
  2. Comment on In smart apartments, is tenants’ privacy for rent? in ~tech

    Crespyl
    Link Parent
    Yeah, I'm... less than thrilled at the prospect. I know there was a case a year or two back in NY where the tennants ended up suing the managers for the right to have a basic mechanical key,...

    Yeah, I'm... less than thrilled at the prospect.

    I know there was a case a year or two back in NY where the tennants ended up suing the managers for the right to have a basic mechanical key, though I don't recall the details. I'd rather not go that route if I can avoid it, but maybe I can at least get them to delay the installation for my unit until my lease is up.

    The lady at the leasing office I spoke to told me they wouldn't have most of the answers I wanted until after the scheduled Q&A event with the SmartRent reps next week, but I expect to be out of town that day so I've emailed my questions and asked that they get back to me when they can.

    3 votes
  3. Comment on In smart apartments, is tenants’ privacy for rent? in ~tech

    Crespyl
    Link
    While I've been interested in IoT/smart-home technology for a while now, I haven't invested in any devices yet, largely because most systems require some proprietary third party cloud application...

    While I've been interested in IoT/smart-home technology for a while now, I haven't invested in any devices yet, largely because most systems require some proprietary third party cloud application to function correctly, and partly because I live in a tiny apartment and nothing can ever be more than a few yards away from me, so the gains from putting all my widgets on the network are somewhat limited.

    There's a few open source projects that I've been toying with the idea of setting up, mostly just for the hell of it, but this week the managers for my building announced that they're partnering with SmartRent to install new locks, smart hubs, and presumably other devices in all the apartments. I've asked a few questions and haven't got a straight answer back yet, but it doesn't seem that we'll be allowed to opt out of the installation.

    7 votes
  4. Comment on What are you reading these days? in ~books

    Crespyl
    Link Parent
    I agree that Cibola Burn is definitely something of a change of pace from the other books, the next book does pick up again IMO. I actually kind of enjoyed the weird slow desperate disaster aspect...

    I agree that Cibola Burn is definitely something of a change of pace from the other books, the next book does pick up again IMO.

    I actually kind of enjoyed the weird slow desperate disaster aspect of CB and was really curious how the show would try to adapt it. I think they did a pretty good job of hitting the important bits without letting it get boring, and they traded a lot of the "downtime" from CB to introduce setup for Nemesis Games next season.

    One aspect of the whole arc of the series that I find interesting is just how old the main cast gets, even with future tech keeping them active and healthy for a long time, their age still starts to catch up to them. CB is where I first started to notice it and it becomes more of a factor later on. It's something that I think a lot of TV shows tend to avoid (for understandable practical reasons) and I'm curious to see the approach Amazon ends up taking.

    2 votes
  5. Comment on What are all the different ways in which we can appreciate games? in ~games

    Crespyl
    (edited )
    Link
    I tried to find a word other than "gameplay" (which feels too broad), but I'm not sure I can do much better without breaking the one-word theme. Aspect Description Examples System (?) We can...

    I tried to find a word other than "gameplay" (which feels too broad), but I'm not sure I can do much better without breaking the one-word theme.

    Aspect Description Examples
    System (?) We can appreciate a game that lets us explore a well crafted system of interacting logical parts. The player can learn the rules of the system by observation and experimentation, and apply critical thinking and problem-solving skills to achieve goals. Stephens Sausage Roll, Factorio, The Witness, Antichamber
    Competition We can appreciate a game for fostering a competitive spirit among peers, to test themselves against each other as teams or individuals Dota 2, Rocket League
    Cooperation We can appreciate a game that allows and encourages two or more people to work together towards a common goal A Way Out, ibb and obb, Portal 2
    5 votes
  6. Comment on Iowa Democratic caucus results delayed until Tuesday due to reporting inconsistencies and technical issues with app in ~news

    Crespyl
    Link
    The submission title caused me some concern until I went and confirmed that the article itself does not use the word "indefinitely" and, in fact, explicitly states: The title here should probably...

    The submission title caused me some concern until I went and confirmed that the article itself does not use the word "indefinitely" and, in fact, explicitly states:

    The party said the problem was not a result of a “hack or an intrusion” and promised that final results would be released Tuesday.

    The title here should probably be amended to clarify this.

    8 votes
  7. Comment on What's a widely criticized thing that you feel is worth defending? in ~talk

    Crespyl
    Link Parent
    I think it has more to do with being able to fit each individual story into part of a larger coherent whole. When a new story draws from an existing world it can add a lot of depth and context to...

    I think it has more to do with being able to fit each individual story into part of a larger coherent whole. When a new story draws from an existing world it can add a lot of depth and context to the characters (which works well in the SoM games for example), but when the team goes the extra mile to ensure that the new story doesn't conflict with the existing canon it can move beyond simply drawing from the original to feeding back into and further enriching the readers experience of the rest of the connected works.

    1 vote
  8. Comment on Something is broken in our science fiction in ~misc

    Crespyl
    Link Parent
    I suppose my point is that most of the things that are common across the *punk field are also quite common across storytelling generally. There are certainly some more-or-less particular elements...

    I suppose my point is that most of the things that are common across the *punk field are also quite common across storytelling generally.

    There are certainly some more-or-less particular elements to *punk writing (or else it wouldn't be a meaningful term), as the article mentions there's recurring themes of disenfranchised youth and capitalist-dystopia societies. I'd still argue that stories of disenfranchised youth will find an audience in any generation, and likewise any capitalist society will have an audience for stories of capitalism gone wrong.

    I think I may simply not be the target audience for this article. I love science fiction in general and have enjoyed my share of cyberpunk stories, but can't agree with the premise that the SF field is somehow broken or has failed to move past the themes and styles of cyberpunk. There's certainly a lot of *punk still being written (and I hope that remains the case), but there's also a wealth of fresh and creative new stories being told in other corners of the field.

    I think my response to the article really just boils down to "if you think we haven't moved past cyberpunk, perhaps it's time to read less *punk and start exploring the rest of the field."

    3 votes
  9. Comment on Something is broken in our science fiction in ~misc

    Crespyl
    Link Parent
    Since the dawn of civilization, has there really been a period of history where this template wasn't relevant? It's essentially a version of the classic Hero's Journey pattern, and I have a hard...

    this story template is still relevant

    Since the dawn of civilization, has there really been a period of history where this template wasn't relevant? It's essentially a version of the classic Hero's Journey pattern, and I have a hard time seeing a world populated by anything recognizably human in which this kind of story isn't still interesting.

    5 votes
  10. Comment on Which are your top five computer programs? in ~comp

    Crespyl
    Link
    Emacs: It's a Lisp Machine for building your ideal text editor tmux: Not just a terminal multiplexer, it's like a DE for your terminal, and it's scripting support allows for all sorts of...
    1. Emacs: It's a Lisp Machine for building your ideal text editor
    2. tmux: Not just a terminal multiplexer, it's like a DE for your terminal, and it's scripting support allows for all sorts of extensions (like integrating the system and tmux clipboards)
    3. KDE Connect: The best tool I've used for linking my phone and PC, remote input, file transfer, (whitelisted) shell commands, media player control, it all just works
    4. git: Essential for my work and personal projects, and despite the (mostly legitimate) UI gripes people have, I find it a pleasure to use. I suspect git played an important role in the modern push for decentralized content-addressed systems, which is a topic of great interest to me.
    5. sc-controller/Steam: My Steam Controller quickly became my preferred input device not just for couch-gaming, but any HTPC uses. It works great in Kodi or even general desktop usage, and the profile switching and virtual keyboard consistently just work the way I want them to.
    1 vote
  11. Comment on Which are your top five computer programs? in ~comp

    Crespyl
    Link Parent
    I'm another in the "own library" + mpd camp, although I usually use Cantata (KDE/Qt also has an MPRIS interface) or KDE Connect/M.A.L.P (Android) for clients. I do, however, use Google Music for...

    I'm another in the "own library" + mpd camp, although I usually use Cantata (KDE/Qt also has an MPRIS interface) or KDE Connect/M.A.L.P (Android) for clients.

    I do, however, use Google Music for its radio feature. In my experience it works better than Pandora used to for introducing me to new artists. I also really like that I can upload my own library and then easily stream it to my phone when I'm away from home, which is the killer feature that keeps me using Google over Spotify.

    So mpd for "serious" listening at home, and GPM for discovery and streaming on the go. There's some noise about Google switching to/replacing the service with YouTube Music in the future, but it's not clear to me what that means for the upload feature. If they drop that I'll probably just move to Spotify for streaming, or finally get around to setting up my own streaming server.

    3 votes
  12. Comment on What are the best movies mainly set in a single location? in ~movies

    Crespyl
    Link Parent
    I came to the thread to post Locke, glad to see someone else had the same thought. It's one of my favorite movies, and Hardy's performance is just so captivating. I can't begin to imagine what...

    I came to the thread to post Locke, glad to see someone else had the same thought.

    It's one of my favorite movies, and Hardy's performance is just so captivating. I can't begin to imagine what that kind of performance is like to give, working with almost no one else on set to directly interact with, and knowing that the entire film depends on you absolutely nailing your role.

    4 votes
  13. Comment on What games have you been playing, and what's your opinion on them? in ~games

    Crespyl
    Link
    I recently finished playing "Aporia: Beyond the Valley", an indie first-person puzzle game from a few years back. It got some buzz on release for its CryEngine-based visuals and storytelling, but...

    I recently finished playing "Aporia: Beyond the Valley", an indie first-person puzzle game from a few years back. It got some buzz on release for its CryEngine-based visuals and storytelling, but I never got around to playing it until this last week.

    These days it actually feels a little weird to be playing a puzzle game in this "walking-sim" style that also allows the player to jump and sprint as if it was an FPS. The extra mobility does come in handy later on, when the game brings in a bit of light stealth/horror gameplay in an unexpected change of pace.

    Some of the lighting effects and design seemed maybe a little over-done and distracting in some scenes, but overall the game was beautiful and it was really fun to explore the world and try to piece together the story from the little hints and slide-shows left behind.

    There were a couple of odd hiccups or possible bugs with one particular (essential) game mechanic near the end; I couldn't seem to pick up a certain type of item unless I had already used up all of the "oil" resource I was carrying, so it took me a while to first realize that picking up was intended to be an option, and then to collect the items and oil I needed to finish the section. There were a few other rough edges here and there, but overall the game was just a very pleasantly quiet and enjoyable experience.

    1 vote
  14. Comment on Day 20: Donut Maze in ~comp

    Crespyl
    Link
    Having done day 18 made this a good deal easier. Part 1 The trickiest bit was really just parsing the input and detecting the labels correctly. I ended up scanning over the map and looking for...

    Having done day 18 made this a good deal easier.

    Part 1

    The trickiest bit was really just parsing the input and detecting the labels correctly. I ended up scanning over the map and looking for uppercase letters, then checking all the neighbors to see if I could find both a second letter and an open/walkable '.' tile, which would be the portals actual location. Once I had all the labels, I could link up the pairs in a table and use that in my tile neighbors method.

    A simple BFS search worked well enough to find the solution.

    Part 2

    This was also pretty straightforward, but again managing the portals themselves was rather tricky, detecting whether a portal lead "in" or "out" kept failing and causing the pathfinder to get lost down infinite one-way holes. Eventually it turned out that I wasn't accounting for the whitespace in the margins of the input correctly, and my map thought its width was much less than it actually was.

    I updated the solver to work in three dimensions, and changed the neighbors method to return portal neighbors as either one step lower or higher.

    Once I fixed that, a simple BFS was still too slow, so I switched to A* and had a quick solution. My solver is still examining every tile individually, but it runs in about 1s on my input.

    Interestingly, on the second sample, my solver does get stuck with too many different paths, so I want to go back and fix it with a smarter approach.

    Similar to Day 18, it should be possible to build a map of which portals are directly connected to which other portals, and then do a graph search over that to determine the best order to traverse the portals in.

    Day 20 - Crystal
    #!/usr/bin/env crystal
    require "colorize"
    require "../lib/utils.cr"
    include Utils
    
    input = File.read(Utils.cli_param_or_default(0,"day20/sample.txt"))
    
    grid = input.lines.map { |l| l.chars.to_a }
    
    map = Map.new(grid)
    map.print_map
    
    path = bfs_path(->(loc : Vec2) { map.walkable_neighbors(loc) },
                    map.start,
                    map.goal)
    
    map.print_map_path(path)
    puts "Part 1: %i\n" % (path.size-1) # -1 to exclude the starting tile
    
    path = astar_path(->(loc : Vec3) { map.recursive_walkable_neighbors(loc) },
                      ->(loc : Vec3) { loc.dist(map.goal) },
                      Vec3.new(map.start),
                      Vec3.new(map.goal))
    
    map.print_map_path(path)
    puts "Part 2: %i" % (path.size-1)
    
    def bfs_path(neighbors : Proc(Vec2, Array(Vec2)), start : Vec2, goal : Vec2)
      open = Set(Tuple(Vec2, Array(Vec2))).new
      open.add({ start, [start] })
      visited = Set(Vec2).new
    
      iterations = 0
      while !open.empty?
        iterations += 1
        #puts "BFS Iterations: %i" % [iterations] if iterations % 100 == 0
    
        frontier = Set(Tuple(Vec2, Array(Vec2))).new
    
        open.each do |state|
          loc, path = state
          next if visited.includes? loc
          visited.add(loc)
    
          #map.print_map_path(path)
    
          return path if loc == goal
    
          neighbors.call(loc).each do |n|
            next if visited.includes? n
            frontier.add({n, path.clone << n})
          end
        end
    
        open = frontier
      end
    
      return [] of Vec2
    end
    
    def astar_path(get_neighbors : Proc(Vec3, Array(Vec3)), heuristic : Proc(Vec3, Int32), start : Vec3, goal : Vec3)
      open = Set(Vec3).new
      open.add(start)
    
      # map of the best known route to each node
      prev = Hash(Vec3, Vec3).new
    
      # distance from start to each node
      gscore = Hash(Vec3, Int32).new(Int32::MAX)
      gscore[start] = 0
    
      # heuristic scores for each node
      fscore = Hash(Vec3, Int32).new(Int32::MAX)
      fscore[start] = heuristic.call(start)
    
      # helper proc to produce an Array(Vec3) from the prev map
      reconstruct_path = ->(node : Vec3) {
        path = [node] of Vec3
        while (node = prev[node]?)
          path << node
        end
        return path
      }
    
      iterations = 0
      while !open.empty?
        iterations += 1
    
        # select the open node with the best heuristic score
        loc = open.min_by { |loc| fscore[loc] }
        open.delete(loc)
    
        # if iterations % 100000 == 0
        #   puts "A* Iterations: %i (%i)" % [iterations, open.size]
        #   map.print_map_path(reconstruct_path.call(loc))
        # end
    
        if loc == goal
          #puts "A* search ended: #{path}"
          return reconstruct_path.call(loc)
        end
    
        get_neighbors.call(loc).each do |n|
          # see if reaching n from this route is better than any previous route we
          # took to get here; if so, update the prev table and heuristic scores
          alt = gscore[loc] + loc.dist(n)
          if alt < gscore[n]
            prev[n] = loc
            gscore[n] = alt
            fscore[n] = gscore[n] + heuristic.call(n)
    
            open.add(n) unless open.includes? n
          end
        end
      end
    
      return [] of Vec3
    end
    
    # up, right, down, left
    DIRS = [Vec2.new(0,-1), Vec2.new(1,0), Vec2.new(0,1), Vec2.new(-1,0)]
    
    alias Tile = Char
    
    class Map
      property grid : Array(Array(Tile))
      property portals : Hash(Vec2, Vec2)
      property start : Vec2
      property goal : Vec2
      property width : Int32
      property height : Int32
    
      def initialize(grid)
        @depth = 0
        @grid = grid
        @portals = Hash(Vec2, Vec2).new
        @start = Vec2.new(0,0)
        @goal = Vec2.new(0,0)
    
        @height = @grid.size
        @width = @grid.map{ |row| row.size }.max # width calc is trickier since the
                                                 # padding whitespace gets in the
                                                 # way
    
        parse_portal_locs
    
        #puts "Map Ready (#{@width}x#{@height})"
      end
    
      def parse_portal_locs
        found_labels = Array(Tuple(String, Vec2)).new
    
        each_loc do |loc, tile|
          next unless tile.ascii_uppercase?
          # we found part of a portal, we need to find the upper-case neighbor,
          # and the attached actual grid point
    
          portal_loc = loc
          other_tile = tile
    
          normal_neighbors(loc).each do |neighbor|
            tile_neighbor = get(neighbor)
            #puts "   neighbor: #{tile_neighbor} (#{neighbor})"
    
            if tile_neighbor == '.'
              portal_loc = neighbor
            end
    
            next unless tile_neighbor.ascii_uppercase?
    
            other_tile = tile_neighbor
            #puts "   Tile Pair #{tile}, #{other_tile}; #{loc}"
          end
    
          if portal_loc != loc
            name = [tile, other_tile].sort.join
            found_labels << { name, portal_loc }
            #puts "Found Portal #{name} at #{portal_loc}"
          end
        end
    
        while !found_labels.empty?
          name, loc = found_labels.pop
    
          if name == "AA"
            @start = loc
            next
          elsif name == "ZZ"
            @goal = loc
            next
          end
    
          # find the other end
          other = found_labels.find { |pair| pair[0] == name }
          raise "Couldn't find other end of portal #{name}!" unless other
    
          # remove the other end from our set
          found_labels.reject!(other)
          _, other_loc = other
    
          @portals[loc] = other_loc
          @portals[other_loc] = loc
          #puts "Registered portal %s: %s -- %s" % [name, loc.to_s, other_loc.to_s]
        end
      end
    
      def each_loc(&block)
        @grid.each_with_index do |row, y|
          row.each_with_index do |tile, x|
            yield(Vec2.new(x,y),tile)
          end
        end
      end
    
      def walkable_neighbors(loc : Vec2) : Array(Vec2)
        portal_neighbors(loc).select { |l| get(l) == '.' }
      end
    
      def recursive_walkable_neighbors(loc : Vec3)
        recursive_portal_neighbors(loc).select { |l| get(l.xy) == '.' }
      end
    
      # n/e/s/w neighbors, but also check for portals
      def portal_neighbors(loc : Vec2)
        normal_neighbors(loc) + [@portals[loc]?].compact
      end
    
      # n/e/s/w neighbors and portals, but portals lead one layer in or out (z-axis)
      def recursive_portal_neighbors(loc : Vec3)
        neighbors = normal_neighbors(loc)
    
        if portal = @portals[loc.xy]?
          # inner or outer portal?
          if (loc.x > 2 && loc.y > 2 && loc.x < (@width-3) && loc.y < (@height-3))
            neighbors << Vec3.new(portal.x, portal.y, loc.z + 1)
          elsif loc.z > 0 && (loc.x <= 2 || loc.y <= 2 || loc.x >= @width-3 || loc.y >= @height-3)
            neighbors << Vec3.new(portal.x, portal.y, loc.z - 1)
          end
    
        end
        return neighbors
      end
    
      # n/e/s/w neighbors, ignoring portals
      def normal_neighbors(loc : Vec2)
        DIRS.map { |d| d + loc }
      end
    
      # "3d" neighbors, same z
      def normal_neighbors(loc : Vec3)
        DIRS.map { |d| Vec3.new(d.x+loc.x, d.y+loc.y, loc.z) }
      end
    
      def get(loc : Vec2)
        get_grid(loc.x, loc.y)
      end
    
      def get_grid(x, y) : Tile
        if @grid.size > y && y >= 0
          if @grid[y].size > x && x >= 0
            return @grid[y][x]
          end
        end
        return ' '
      end
    
      def print_map
        @grid.each_with_index do |row, y|
          row.each_with_index do |tile, x|
            if tile == '#'
              print tile.to_s.colorize(:red).mode(:dim)
            else
              print tile
            end
          end
          print "\n"
        end
      end
    
      def print_map_path(path : Array(Vec2))
        print_map_path(path.map { |l| Vec3.new(l) })
      end
    
      def print_map_path(path : Array(Vec3))
        @grid.each_with_index do |row, y|
          row.each_with_index do |tile, x|
            if l = path.find { |l| l.x == x && l.y == y }
              print ("%i" % (l.z % 10)).colorize(:green).mode(:bright)
            elsif tile == '#'
              print "#".colorize(:red).mode(:dim)
            else
              print tile
            end
          end
          print "\n"
        end
      end
    end
    
    2 votes
  15. Comment on Day 19: Tractor Beam in ~comp

    Crespyl
    Link
    I needed a breather after that last one, which I barely finished in time for Day 19. With a working Intcode VM this is pretty straightforward. Part 1 This works exactly the way you'd expect, just...

    I needed a breather after that last one, which I barely finished in time for Day 19. With a working Intcode VM this is pretty straightforward.

    Part 1

    This works exactly the way you'd expect, just run a loop over the 50x50 grid and test each point in turn, counting up the hits as we go. One important detail is that each "drone" is an independent unit, they only accept one target destination and you have to "send a new drone" (clone or reset) your device before testing the next point.

    #!/usr/bin/env crystal
    
    require "../lib/vm2.cr"
    require "../lib/utils.cr"
    
    
    prog = Utils.get_input_file(Utils.cli_param_or_default(0,"day19/input.txt"))
    vm = VM2.from_string(prog)
    
    hits = 0
    (0...50).each do |x|
      (0...50).each do |y|
        hit = check_point(x,y,vm.clone)
        hits += hit
    
        if hit > 0
          print '#'
        else
          print '.'
        end
      end
      print '\n'
    end
    
    puts "Part 1: %i" % hits
    
    def check_point(x,y,drone)
      drone.send_input(x)
      drone.send_input(y)
      drone.run
      return drone.read_output || 0
    end
    
    Part 2 I spent a few minutes trying to figure out if there was some way to use the drones to take enough measurements for a clever triangulation solution, but that was taking too long so I reverted to a simple iterative check.

    I start out with a 100x100 box that overlaps the start of the beam, then keep scooting it right and down until the whole thing just barely fits. The only difficulty here is making sure that the output is actually the north-west corner of the box, not the south-west corner that I was basing my tests off of.

    x,y = 0,50
    while true
      while check_point(x,y,vm.clone) == 0
        x += 1
      end
    
      if check_point(x+99,y-99,vm.clone) > 0 &&
         check_point(x+99,y,vm.clone) > 0 &&
         check_point(x,y-99,vm.clone) > 0 &&
         check_point(x,y,vm.clone) > 0
        # puts "hit at #{x},#{y}"
        break
      end
    
      y += 1
    end
    
    # adjust to nw corner
    puts "Part 2: %i" % [x*10000 + y-99]
    
    1 vote
  16. Comment on Day 18: Many-Worlds Interpretation in ~comp

    Crespyl
    (edited )
    Link
    Just doing part one took me long enough that I'm not sure I'll be able to finish p2 before the next puzzle. My first pass was based on just looking at the requirements for each key, identifying...

    Just doing part one took me long enough that I'm not sure I'll be able to finish p2 before the next puzzle.

    My first pass was based on just looking at the requirements for each key, identifying which key will be the last to pick up, and then working backwards from there. I was very quickly able to produce correct answers for any map except the fourth sample (with equidistant keys) and my actual input (I'd get a "valid" path, but not the shortest).

    Then I spent a lot of time trying to optimize it as if I was writing a single agent AI for a roguelike or something, it had a concepts of long and short term goals, where it was headed at any given time, and parameters for allowing it to notice and pick up keys that were a little ways off its path. This got me a little further, but not enough to reliably get the shortest path on the harder problems.

    Eventually I gave in and began re-writing for a generalized graph search and started running into the combinatorial explosion issues that everyone else did. This was long and difficult but informative. My approach started with a DFS and lots of heuristics to select the preferred node, including hard limits on step count (since I knew from the site that my initial solvers answer was too high, I could rule out any path that required more steps).

    Eventually I found myself on the wiki page for Dijkstra's algorithm, which still required me to figure out the optimal node representation during traversal so as not to blow up the space requirements with extra states, but I did get there in the end. My code is an absolute mess at this point, compared to previous days, but it does find the answer in ~2s.

    The code is too messy to really be worth showing, but it's on my github for the morbidly curious.

    If I come back and clean it up later I'll edit this comment with a more in-depth explanation of what it's actually doing.

    On to part two I suppose, but I need a break first.

    Edit: Part 2 is done, sort of. I took advantage of what looks like a (possibly intentional) quirk in the input that means the four quadrants can each be solved separately, using my algorithm from the first part. It's not pretty, but it works.


    I think the only kind of interesting things in my solution were the pre-computed requirements map for each key, and the flood-fill distance maps for each key.

    For each key, I ran a flood fill from its position out through the entire maze, storing the distance of each tile into a cache. This made finding the path distance from the robot or any other key a fast static lookup. I think this would've been more useful if I was still using my "wandering-agent" approach instead of the global dijkstra search that I ended up on. As it is, it's just used to help compute the scores/weights for each possible action.

    Additionally, at the start I used a bfs path-finding from each key to the robot, tracking (but passing) each locked door on the way. The list of doors passed through is the requirements for that key, which is essential information for deciding what keys are available at any given time.

    2 votes
  17. Comment on Day 17: Set and Forget in ~comp

    Crespyl
    (edited )
    Link
    This was a funny one in that I almost ended up writing no new code to solve it. I already had a debugger that could handle ASCII input and output, I just had to tweak it a bit to make feeding...

    This was a funny one in that I almost ended up writing no new code to solve it. I already had a debugger that could handle ASCII input and output, I just had to tweak it a bit to make feeding lines with the newline character easier.

    Since I didn't write much new code, I'll just share the bare-bones debugger I'm using:

    Intcode Debugger - Crystal
    #!/usr/bin/env crystal
    require "readline"
    require "colorize"
    require "../lib/vm2.cr"
    require "../lib/disasm.cr"
    
    class Debugger
      property vm : VM2::VM
    
      property watchlist : Hash(String, Int32)
      property breakpoints : Hash(Int32, String)
    
      property output_log : Array(Int64)
    
      property io_mode : Symbol
    
      def initialize()
        @vm = VM2::VM.new([0_i64])
        @watchlist = {} of String => Int32
        @breakpoints = {} of Int32 => String
        @output_log = [] of Int64
        @io_mode = :int
      end
    
      def print_vm_summary
        puts "%s:%s] PC: %s  BASE: %s" % [@vm.name, @vm.status, format_addr_val(@vm.pc), format_addr_val(@vm.rel_base)]
        puts "IN: #{@vm.input}" if @vm.input.size > 0
        puts "ERR: %s" % @vm.error if @vm.error
        print_watches
        print_disasm(@vm.pc, @vm.pc+25) if @vm.mem.size > 1
      end
    
      def print_watches
        puts @watchlist.map { |name, a| "%s (%05i) = %05i" % {name, a, @vm.read_mem(a)} }.join(", ")
      end
    
      def print_breaks
        puts "BREAKPOINTS:"
        puts @breakpoints.join("\n")
      end
    
      def print_disasm(start,stop)
        segment = @vm.mem[start..stop]
        log "showing #{start}..#{stop}"
    
        dis = Disasm.intcode_to_str(segment, start)
        log "\n%s\n" % dis
      end
    
      def prompt
        if @vm.mem.size > 1
          "%s:%s] " % [@vm.name, @vm.status, format_addr_val(@vm.pc), format_addr_val(@vm.rel_base)]
        else
          "> "
        end
      end
    
      def format_addr_val(addr)
        "%05i (%05i)" % [addr, @vm.read_mem(addr)]
      end
    
      def log(msg)
        puts msg
      end
    
      def run_vm
        log "running...\n"
        start = @vm.cycles
        while @vm.status == :ok && ! @breakpoints[@vm.pc]?
          @vm.exec
        end
        log "\nstopped after %s cycles" % [@vm.cycles - start]
        log " BREAKPOINT: %s" % @breakpoints[@vm.pc] if @breakpoints[@vm.pc]?
        print_vm_summary
      end
    
      def load_program(filename)
        @vm = VM2.from_file(filename)
        @vm.output_fn = ->(x: Int64) {
          @output_log << x;
          case @io_mode
          when :int then log "VM OUTPUT: %5i   (%s)" % [x,x.chr.ascii_control? ? ' ' : x.chr]
          when :text then print (x >= 0 ? x.chr : "{chr: %i}" % x)
          end
        }
        log "loaded VM (%i)" % @vm.mem.size
      end
    
      def step(n,verbose=false)
        c = @vm.cycles
        while n > 0 && @vm.status == :ok
          n -= 1
          @vm.exec
          print_vm_summary if verbose
        end
        log "stopped after #{@vm.cycles - c} cycles"
        print_vm_summary
      end
    
      def add_breakpoint(name, address)
        @breakpoints[address] = name
      end
    
      def rm_breakpoint(name)
        @breakpoints.each do |k,v|
          if v == name
            @breakpoints[k] = nil
          end
        end
      end
    
      def add_watch(name, address)
        @watchlist[name] = address
      end
    
      def rm_watch(name)
        @watchlist[name] = nil
      end
    
      def run
    
        log "Intcode Debugger Ready"
    
        if ARGV[0]?
          load_program ARGV[0]
          log "Loaded Program: %s" % ARGV[0]
        end
    
        while input = Readline.readline(prompt,true)
          line = input.strip
    
          if line == "" && @vm.mem.size > 1
            @vm.exec
            print_vm_summary
          end
    
          next unless line.match(/.+/)
    
          args = line.split(' ')
          command = args.shift
    
          case command
    
          when "load" # load program
            next if args.size < 1
            load_program(args[0])
            print_vm_summary
    
          when "run" # run the machine until it stops, or the pc hits a breakpoint
            run_vm
    
          when "step" # step foward n steps, ignoring breakpoints
            n = (args[0]? || "1").to_i
            puts "running #{n} steps"
            step(n)
    
          when "stepv" # step forward n steps, ignoring breakpoints, print state on each step
            n = (args[0]? || "1").to_i
            puts "running #{n} steps"
            step(n, true)
    
          when "breakpoint"
            if args.size > 0
              addrs = args.in_groups_of(2,"0").map { |a| {a[0], a[1].to_i} }
              addrs.each do |n,a|
                add_breakpoint(n,a)
              end
              log "added #{addrs.size} breakpoints"
            else
              print_breaks
            end
    
          when "watch" # add an address to the watchlist
            if args.size > 1
              addrs = args.in_groups_of(2,"0").map { |a| {a[0], a[1].to_i} }
              addrs.each do |n,a|
                add_watch(n,a)
              end
              log "added #{addrs.size} addresses to the watchlist"
            else
              print_watches
            end
    
          when "show" # show the state and watchlist, show n...: show a list of addresses
            if args.size > 0
              args.each do |a|
                puts "(%s) %05i" % [a, @vm.read_mem(a.to_i)]
              end
            else
              print_vm_summary
            end
    
          when "set"
            next if args.size < 2
    
            if args[0].match /\d+/
              a = args[0].to_i64
              v = args[1].to_i64
              @vm.write_mem(a,v)
            else case args[0].downcase
                 when "pc"
                   @vm.pc = args[1].to_i64
                 when "base"
                   @vm.rel_base = args[1].to_i64
                 when "status", "state"
                   case args[1]
                   when "ok"
                     @vm.status = :ok
                   when "halted"
                     @vm.status = :halted
                   when "needs_input"
                     @vm.status = :needs_input
                   else log "invalid status"
                   end
                 when "io"
                   case args[1]
                   when "int", "num"
                     @io_mode = :int
                   when "text", "ascii"
                     @io_mode = :text
                   else log "invalid io mode"
                   end
                 else log "can't set that"
                 end
            end
    
          when "disasm"
            start = args[0]? ? args[0].to_i : @vm.pc
            stop = args[1]? ? args[1].to_i : start+10
    
            print_disasm(start,stop)
    
          when "dump"
            File.write(args[0]? || "dump.txt", vm.mem.map{ |v| v.to_s }.join(","))
    
          when "input" # feed input to the machine
            next unless args.size > 0
            case @io_mode
            when :int
              args.each do |a|
                vm.send_input(a.to_i64)
              end
            when :text
              str = args.join(" ")
              str.chars.map { |c| c.ord.to_i64 }.each { |ascii| vm.send_input(ascii) }
            end
    
          when "line"
            str = "%s\n" % args.join(" ")
            str.chars.map { |c| c.ord.to_i64 }.each { |ascii| vm.send_input(ascii) }
    
          when "output" # show the machine's output
            log @output_log
    
          when "otext"
            log @output_log.map{ |v| v.unsafe_chr }.join
    
          when "exit"
            log "goodbye"
            break
          end
    
        end
    
      end
    
    end
    
    Debugger.new.run
    
    Part 1 As mentioned, this was quite simple: I just loaded the program into my debugger, enabled ASCII output, and ran the program to get the map.

    Once I had the map, it wasn't difficult to just look for the intersections and manually compute the answer from their positions.

    Part 2

    Part 2 is a kind of simple compression problem: you have a single long string (the full path the robot needs to traverse), and you must break it down into three different repeated chunks.

    Once again I was able to work out the path manually, and if you write out the steps it's not too difficult to find the repeating patterns. My editor helped a bit here since it was easy to try out substitutions by using the interactive search/replace feature.

    I did get stuck here for a while because of a transcription error that meant that the path I was working with didn't break down into chunks the way it should've; if you take the manual approach be sure to double check your work!

    Once I realized my error and could compress the path the way the robot wanted, I was able to just feed that back into the program in my debugger and get the answer.


    Edit:
    I still had an itch to write some more code, so I worked out an automated solution to P1 (edit-edit, also extracting the uncompressed path for p2):

    Part 1 - Crystal
    #!/usr/bin/env crystal
    
    require "../lib/vm2.cr"
    require "../lib/utils.cr"
    
    prog = Utils.get_input_file(Utils.cli_param_or_default(0,"day17/input.txt"))
    
    vm = VM2.from_string(prog)
    vm.run
    
    map = vm.output.map(&.chr).join.split('\n').map { |l| l.chars.to_a }
    def safe_get_xy(map,pos : Tuple(Int32,Int32))
      x,y = pos
      if map.size > y && y >= 0
        if map[y].size > x && x >= 0
          return map[y][x]
        end
      end
      return '.'
    end
    
    DIRS = [{0,-1},{1,0},{0,1},{-1,0}]
    def safe_get_dir_from_loc(map,loc,dir)
      safe_get_xy(map, {loc[0]+DIRS[dir][0],loc[1]+DIRS[dir][1]})
    end
    
    # find intersections and robot
    facings = ['^','>','v','<']
    robot = { {-1,-1}, 0}
    intersections = Hash(Tuple(Int32,Int32), Bool).new(false)
    map.each_with_index do |row,y|
      row.each_with_index do |tile,x|
        facings.index(tile).try { |f| robot = { {x,y}, f} }
    
        # check each direction to see if all 4 are #s
        up = safe_get_xy(map, {x, y-1})
        down = safe_get_xy(map, {x, y+1})
        left = safe_get_xy(map, {x-1, y})
        right = safe_get_xy(map, {x+1, y})
    
        if [tile, up,down,left,right].all?('#')
          intersections[{x,y}] = true
        end
    
      end
    end
    
    puts "Part 1: %i" % intersections.keys.map { |i| i[0] * i[1] }.sum
    
    path = [] of String
    dir_count = 0
    while true
      # from robot pos, find direction left or right
      forward = safe_get_dir_from_loc(map,robot[0], (robot[1]))
      right = safe_get_dir_from_loc(map,robot[0], ((robot[1] + 1) % DIRS.size))
      left = safe_get_dir_from_loc(map,robot[0], ((robot[1] - 1) % DIRS.size))
    
      if forward == '#'
        dir_count += 1
        robot = { {robot[0][0] + DIRS[robot[1]][0], robot[0][1] + DIRS[robot[1]][1]}, robot[1] }
      else
        path << dir_count.to_s if dir_count != 0
        dir_count = 0
        if left == '#'
          path << "L"
          robot = { robot[0], (robot[1] - 1) % DIRS.size }
        elsif right == '#'
          path << "R"
          robot = { robot[0], (robot[1] + 1) % DIRS.size }
        else
          break
        end
      end
    end
    puts "Path: %s" % path.join(',')
    
    1 vote
  18. Comment on Day 16: Flawed Frequency Transmission in ~comp

    Crespyl
    Link
    This, like the n-body problem, took a bit of doing and requires a few important insights. Part 1 can be solved more or less naively, in the way you'd expect. Part 2 on the other hand requires...

    This, like the n-body problem, took a bit of doing and requires a few important insights.

    Part 1 can be solved more or less naively, in the way you'd expect. Part 2 on the other hand requires substantial optimization.

    Part 1 Crystal

    My approach was straightforward: create a function fft_base_pattern that can expand the base pattern for the appropriate position, then loop through the input, multiply each digit by the matching value from the base pattern, sum all the results, take the abs (since some will be negative) then return the last digit of each.

    Already this is a little slow, but it gets the job done.

    #!/usr/bin/env crystal
    require "../lib/utils.cr"
    
    def split(str)
      str.chars.map { |c| c.to_i }
    end
    
    def fft_base_pattern(n) # return an interator
      base = [0,1,0,-1]
      base.map { |b| [b] * (n + 1) }.flatten.cycle.skip(1)
    end
    
    def fft_phases(list : Array(Int32), n)
      n.times do
        list = list.map_with_index { |v, idx|
          list.zip(fft_base_pattern(idx)).map { |pair|
            l, p = pair
            l * p
          }.sum.abs % 10
        }
      end
      list.join[0..7]
    end
    
    # p1
    input = split(Utils.get_input_file("day16/input.txt"))
    puts "Part 1: %i (input size %i)" % [fft_phases(input, 100), input.size]
    
    Part 2 - minor spoilers

    We're going to need to massively optimize the first part, and there's a few things that work in our favor, the first relates to how the base pattern expands for each index.

    In my case it helped to generate a table of patterns for each digit:

    # 10.times do |i|
    #   pattern = fft_base_pattern(i)
    #   puts pattern.first(10).map { |i| "%2i" % i }.join(", ")
    # end
    #
    # 1,  0, -1,  0,  1,  0, -1,  0,  1,  0 #  1
    # 0,  1,  1,  0,  0, -1, -1,  0,  0,  1 #  2
    # 0,  0,  1,  1,  1,  0,  0,  0, -1, -1 #  3
    # 0,  0,  0,  1,  1,  1,  1,  0,  0,  0 #  4
    # 0,  0,  0,  0,  1,  1,  1,  1,  1,  0 #  5
    # 0,  0,  0,  0,  0,  1,  1,  1,  1,  1 #  6 
    # 0,  0,  0,  0,  0,  0,  1,  1,  1,  1 #  7
    # 0,  0,  0,  0,  0,  0,  0,  1,  1,  1 #  8
    # 0,  0,  0,  0,  0,  0,  0,  0,  1,  1 #  9
    # 0,  0,  0,  0,  0,  0,  0,  0,  0,  1 # 10
    
    Part 2 - moderate spoilers Looking at the table, we can see that something important happens halfway through the list: the patterns from here out will always be n-1 0s, followed by nothing but 1s to the end of the list.

    Fortunately, my input (and I expect all of them) are constructed in such a way that the offset is more than halfway through the list. This means that 1) we can ignore the first part of the input (everything before the offset), and 2) everything after the offset is just going to be the sum of the following digits (mod 10).

    Part 2 - solution - Crystal

    Unfortunately, even with the realization that we "simply" have to sum the digits of the latter part of the input, my code was too slow, and I needed to improve it a bit more. The last change I needed to make was to pre-compute the "sum of following digits" for each value past the offset. The pre-compute step has to be fast too, and can be optimized by doing it in reverse, which allows us to easily re-use the sum of the previous position.

    # p2
    
    #input = split("03036732577212944063491565474664") * 10000
    input = split(Utils.get_input_file("day16/input.txt")) * 10000
    offset = input[0...7].join.to_i
    puts "Offset: %i" % offset
    
    # because of how the base pattern expands, beyond the halfway point the pattern
    # for every digit n will be n-1 0s followed by 1s for the rest of the list. This
    # means that the transformation for a digit n (n > size/2) is simply the sum of
    # the following digits.
    
    def p2_fast_fft_offset(numbers, offset)
    
      100.times do |phase|
        puts "> #{phase}" if phase % 10 == 0
    
        # the list of sums will the same for each digit, so we can save some time by
        # precomputing
        #
        # precomputed = numbers[offset...].map_with_index { |n,i| numbers[offset+i...].sum }
        #
        # however even precomputing like this is slow, we can do it faster in
        # reverse since that allows us to easily peek at the most recently computed value
        precomputed = [numbers.last]
        numbers[offset...numbers.size-1].reverse.each do |n|
          precomputed << precomputed.last + n
        end
        precomputed.reverse!
    
        next_phase = numbers[0...offset] + numbers[offset...].map_with_index { |n,i| precomputed[i] % 10 }
    
        numbers = next_phase
      end
    
      numbers[offset...offset+8].join
    end
    
    puts "Part 2: %i" % p2_fast_fft_offset(input, offset)
    
    2 votes
  19. Comment on Day 15: Oxygen System in ~comp

    Crespyl
    Link
    This was an interesting one, I kept having little issues where my robot would get lost and start plotting to the wrong places while mapping. Day 15 I spent a bunch of time on setting up mapping...

    This was an interesting one, I kept having little issues where my robot would get lost and start plotting to the wrong places while mapping.

    Day 15

    I spent a bunch of time on setting up mapping display and interactivity which ended up being kind of waste, if rather entertaining.

    Wandering around manually, I quickly noticed that the map was all single-tile corridors, so a naive "keep the wall on the left" approach would probably get me somewhere interesting eventually. It wasn't too difficult to write a function to have the robot check a direction and then return back to its original position if it actually succeeded in moving forward.

    Sticking to the left wall, my robot quickly found the goal, but its path was apparently sub-optimal, so I needed to explore more. I set the robot to just keep exploring in the same manner, building up a map as it goes. In my case I just had it stop after 3k steps, but I'm sure a more elegant solution is possible.

    Once you have the map, the actual solutions are quite straightforward graph problems: A* from the start to the station, then flood-fill from the station and count the steps.

    Day 15 Crystal
    #!/usr/bin/env crystal
    require "../lib/utils.cr"
    require "../lib/vm2.cr"
    
    class Droid
      property cpu : VM2::VM
    
      property x : Int32
      property y : Int32
      property facing : Int64
    
      property move_count : Int32
      property start_pos : Tuple(Int32,Int32)
      property station : Tuple(Int32, Int32)
    
      property map : Hash(Tuple(Int32, Int32), Int32)
    
      DIRS = {
        0 => { 0, 0},
        1 => { 0,-1},
        2 => { 0, 1},
        3 => {-1, 0},
        4 => { 1, 0}
      }
    
      def initialize(cpu, curses = false)
        @cpu = cpu
        @x, @y = 0, 0
        @last_move = 0
        @move_count = 0
        @state = :ok
        @facing = 4
        @station = {-1,-1}
        @map = Hash(Tuple(Int32, Int32), Int32).new { |h,k| h[k] = 9 }
        @start_pos = {@x,@y}
      end
    
      def coords_facing(dir)
        d = DIRS[dir]
        {@x+d[0],@y+d[1]}
      end
    
      def right_from(facing)
        case facing
        when 1 then 4_i64
        when 2 then 3_i64
        when 3 then 1_i64
        when 4 then 2_i64
        else raise "bad dir"
        end
      end
    
      def left_from(facing)
        case facing
        when 1 then 3_i64
        when 2 then 4_i64
        when 3 then 2_i64
        when 4 then 1_i64
        else raise "bad dir"
        end
      end
    
      def check_dir(d)
        @cpu.send_input(d)
        @cpu.run
        res = @cpu.read_output
        case res
        when 1 # space ok, move back to where we started
          reverse = right_from(right_from(d))
          @cpu.send_input(reverse)
          @cpu.run
          raise "COULDN'T BACKTRACK !" if @cpu.read_output != 1
          :ok
        when 0 # wall
          :wall
        when 2 # station
          :station
        else raise "got bad output from cpu"
        end
      end
    
      def try_forward
        nx,ny = coords_facing(@facing)
        @cpu.send_input(@facing)
        @cpu.run
        res = @cpu.read_output
        case res
        when 1
          @map[{@x,@y}] = 1
          @x, @y = nx, ny
          @move_count += 1
          :ok
        when 0
          @map[{nx,ny}] = 9
          :wall
        when 2
          @map[{nx,ny}] = 0
          @station = {nx,ny}
          @x, @y = nx, ny
          :station
        else raise "got bad output form cpu"
        end
      end
    
      def turn_left
        @facing = left_from(@facing)
      end
    
      def turn_right
        @facing = right_from(@facing)
      end
    
      def run
        state = :look
        while true
          case state
          when :move
            state = :look
            nx,ny = coords_facing(@facing)
            case try_forward
            when :ok
            when :wall
              turn_right
            when :station
              #break
            end
          when :look
            state = :move
            lx,ly = coords_facing(left_from(@facing))
            d = left_from(@facing)
            case check_dir(d)
            when :ok
              @map[{lx,ly}] = 1
              turn_left
            when :wall # go forward
              @map[{lx,ly}] = 9
            when :station # end
              @map[{lx,ly}] = 0
            end
          end
    
          # 3k should be enough to map anything
          break if @move_count > 3000
        end
      end
    end
    
    # Extract map
    prog = Utils.get_input_file(Utils.cli_param_or_default(0, "day15/input.txt"))
    droid = Droid.new(VM2.from_string(prog))
    droid.run
    
    map = droid.map
    
    # Use A* to map from droid.start_pos to droid.station
    
    alias Pos = Tuple(Int32, Int32)
    
    start = droid.start_pos
    station = droid.station
    solution = [] of Pos
    
    visited = Set(Pos).new
    open = [{start, [] of Pos, 1}]
    
    def dist(a,b)
      Math.sqrt( (a[0]-b[0])*(a[0]-b[0]) + ((a[1]-b[1])*(a[1]-b[1])) )
    end
    
    def neighbors(loc) : Array(Pos)
      x,y = loc
      [{x-1,y}, {x+1,y}, {x,y+1}, {x, y-1}]
    end
    
    #puts "Start search..."
    
    while !open.empty?
      loc, route, cost = open.pop
      next if visited.includes? loc
    
      new_route = [route, loc].flatten
      if loc == station
        solution = new_route.flatten
        break
      end
    
      visited.add(loc)
    
      neighbors(loc).each do |neighbor|
        next if map[neighbor]? == 9 || visited.includes? neighbor
        tile_cost = map[neighbor]? || 99
        new_cost = cost + tile_cost
        open << {neighbor, new_route, new_cost}
      end
    
      open = open.sort_by { |_,_,cost| cost }
    end
    
    puts "P1: %i" % (solution.size-1)
    
    # Flood fill from station, count the steps
    
    open = [station]
    visited = Set(Pos).new
    steps = 0
    
    while !open.empty?
      frontier = [] of Pos
      open.each do |loc|
        next if visited.includes? loc
        visited.add(loc)
        neighbors(loc).each do |neighbor|
          frontier << neighbor if map[neighbor] == 1
        end
      end
    
      open = frontier
      steps += 1
    end
    
    puts "P2: %i" % (steps-2) # account for initial expand and final check
    
    2 votes