1. 18
    Solving a math problem with planner programming compsci plt buttondown.com/hillelwayne
    hwayne avatar authored by hwayne 8 months ago |
    Archive.org Archive.today Ghostarchive
    | 5 comments
    1. 7
      wizeman avatar wizeman edited 8 months ago

      We should be able to fuse the select and copy steps together, meaning instead of having three actions (select, copy, paste) we only need two (selectcopy, paste), where selectcopy takes twice as many steps as pasting.

      I think you can optimize even further than that: since it makes no sense to have two selectcopy actions in a row, nor to have a single selectcopy as the final action, you can merge selectcopy with paste, thus ending up with two possible actions:

      1. selectcopypaste with 3 steps
      2. paste with 1 step
      1. 3
        hyperpape avatar hyperpape 8 months ago

        But we can’t make that optimization because it breaks monotonicity. We’re now pushing a mix of n+1 and n+2 steps onto the queue, and there’s no way to order things to guarantee all of the n+1 steps are searched before any n+2 step.

        Not to try and discourage using fun languages, but I think you could use multiple queues or a priority queue for this.

        1. 1
          MoonlitKnight avatar MoonlitKnight 8 months ago

          This seems to be a typo:

          I’ve written about it in-depth [here] and also a comparison of planning to model checking [here].

          Both [here]s link to the same post.

          I must confess I’m somewhat mystified by the C++ program. Specifically:

                  case PASTE:
            q.push({n.noOfAs, n.steps, n.noOfAsCopied, SELECT});
            q.push({n.noOfAs + n.noOfAsCopied, n.steps + 1, n.noOfAsCopied, PASTE});
            break;

          Two new states are added in the PASTE case because there are two possibilities for what to do next, SELECT or PASTE. But why is neither the number of steps nor the number of A’s increased in the first case? The first 4 states we encounter are {1, 0, 0, SELECT}, {1, 1, 0, COPY}, {1, 2, 1, PASTE}, {1, 2, 1, SELECT}`. What does the last of these represent?

          Also,

          Since we’ll be fusing selects and copies, we don’t need to also track the number of characters selected (unlike the C++).

          As far as I can tell the C++ program doesn’t track selected characters. Am I missing something obvious?

          1. 2
            hwayne avatar hwayne 8 months ago

            Both [here]s link to the same post.

            Fix’d

            Two new states are added in the PASTE case because there are two possibilities for what to do next, SELECT or PASTE. But why is neither the number of steps nor the number of A’s increased in the first case? The first 4 states we encounter are {1, 0, 0, SELECT}, {1, 1, 0, COPY}, {1, 2, 1, PASTE}, {1, 2, 1, SELECT}`.

            Read the state not as what’s done but what the state machine is thinking of doing next. So {1, 2, 1, PASTE} means the program is thinking of doing a paste, and it can either decide to paste ({2, 3, 1, PASTE}) or switch to deciding to SELECT ({1, 2, 1, SELECT}).

            What does the last of these represent?As far as I can tell the C++ program doesn’t track selected characters. Am I missing something obvious?

            No, I just misread “steps” as “number selected”.

            1. 2
              MoonlitKnight avatar MoonlitKnight 8 months ago

              Read the state not as what’s done but what the state machine is thinking of doing next. So {1, 2, 1, PASTE} means the program is thinking of doing a paste, and it can either decide to paste ({2, 3, 1, PASTE}) or switch to deciding to SELECT ({1, 2, 1, SELECT}).

              But that means that you could go SELECT -> COPY -> SELECT, no? The COPY leads to a PASTE but then we decide not to do the PASTE after all and do another SELECT instead. I don’t think there’s a point in generating such branches, even if they don’t impact the program’s correctness.

              If we replace the line

              q.push({n.noOfAs, n.steps, n.noOfAsCopied, SELECT});

              by

              q.push({n.noOfAs + n.noOfAsCopied, n.steps + 1, n.noOfAsCopied, SELECT});

              we may still do a SELECT or a PASTE after a PASTE, but at least the PASTE always goes through. In my test, this reduces the number of states that need to be considered to find the result from 242_185_169 to 14_649_247.