Day 16: Reindeer Maze

Megathread guidelines

  • Keep top level comments as only solutions, if you want to say something other than a solution put it in a new post. (replies to comments can be whatever)
  • You can send code in code blocks by using three backticks, the code, and then three backticks or use something such as https://topaz.github.io/paste/ if you prefer sending it through a URL

FAQ

  • @Acters@lemmy.world
    2•5 hours ago

    only improvement I can think of is to implement a dead end finder to block for the search algorithm to skip all dead ends that do not have the end tile (“E”). by block I mean artificially add a wall to the entrance of the dead end. this should help make it so that it doesn’t go down dead ends. It would be improbable but there might be an input with a ridiculously long dead end.

    • @Pyro@programming.dev
      1•2 hours ago

      Interesting, how would one write such a finder? I can only think of backtracking DFS, but that seems like it would outweigh the savings.

      • @Acters@lemmy.world
        1•4 minutes ago

        ah well, my idea is at high level view. Here is a naive approach that should accomplish this. Not sure how else I would accomplish this without more thought put in to make it faster:

        [ Paste ]

        edit: whoops, sorry had broke the regex string and had to check for E and S is not deleted lol

        This is how the first example would look like:

        ###############
#...#####....E#
#.#.#####.###.#
#.....###...#.#
#.###.#####.#.#
#.###.......#.#
#.#######.###.#
#...........#.#
###.#.#####.#.#
#...#.....#.#.#
#.#.#.###.#.#.#
#.....#...#.#.#
#.###.#.#.#.#.#
#S###.....#...#
###############

        This is how the second example would look like:

        #################
#...#...#...#..E#
#.#.#.#.#.#.#.#.#
#.#.#.#...#...#.#
#.#.#.#####.#.#.#
#...#.###.....#.#
#.#.#.###.#####.#
#.#...###.#.....#
#.#.#####.#.###.#
#.#.###.....#...#
#.#.###.#####.###
#.#.#...###...###
#.#.#.#####.#####
#.#.#.......#####
#.#.#.###########
#S#...###########
#################

        It has more noticeable improvement on larger maps, and especially effective if there are no loops! (i.e. one path) because it would just remove all paths that will lead to a dead end.