3 ms·

An additional insight which can reduce the search space: SC following an SC is a no-op (it changes nothing about the state but the number of steps). The only tw

An additional insight which can reduce the search space: SC following an SC is a no-op (it changes nothing about the state but the number of steps). The only two productive action or action sequences are P and SCP where SCP doubles the size of the string in 3 steps. Switching the C++ code to use this insight [edit: and switching to a priority queue to allow for multiple simultaneous steps] cut the execution time by about 90% in my testing of it. That's not as fast as the picat solution on the same computer for me, but it's much closer than the original C++ code. Not properly benchmarked but my times are roughly: picat: 0.06 seconds C++ using SCP and a priority queue: 0.36 seconds C++ original: 3.8 seconds The times are consistent across runs but I don't have a benchmarking program on that computer to give better numbers.

hwayne 2y ago
I'm genuinely surprised that the Picat is so much faster than the C++. I assumed it would be easier to write, but also slower.
- Karliss 2y ago
  I have a feeling that it might be due to C++ solution not being proper BFS since it doesn't have anything preventing the visiting of same state multiple times. One thing that slightly tripped me is that full BFS state space without additional tricks is in theory N^2 (current length x copied length) . Also the memory usage for C++ solution is ~1.8GB and bumping N to 200K increased it to 6GB . I assume that Picat automatically detects and prevents duplicate computation on identical states. Got nerd sniped. If you think about the problem a bit harder (but not hard to go into math of prime factors) there is a dynamic programming solution. The code for obtaining only steps is a bit simpler, but it can be also extended to recover full answer https://gist.github.com/karliss/5ca978390791daca71a1d812c43a924c https://gist.github.com/karliss/5ca978390791daca71a1d812c43a... Had no issue obtaining full 9104 step solution for ==100001 . On my computer: C++ DP: <0.003s C++ from article: 3.032s Memory usage of DP solution is linear. The double nested loops look a bit scary, but it actually forms harmonic series sum: `sum (n/i) ~ n log n` so the speed isn't bad for non analytic solution. The main insight for fast DP solution is how to reduce the state space from NxN (lenght X copied length) to N. All solutions will be in form (SC(P)+)+. Once you know minimum step count for reaching some length, you don't care about what the currently copied length is. Assuming you reach some length L_2 = L_1 * i, any solutions L_1(i+j) would already be processed when handling L_1, means you only need to updated L_2 (i). Now that I have written it I get where the factorization related math talk in stack exchange comes from.
bgoated01 2y ago
Doesn't SCP just give you the same number of characters, since there is no select nothing action? The paste replaces whatever is currently selected. That's what it looks like the C++ code in the article is doing to me. That's also how a quick real world test works for me. That's why you don't see any SCP in their solution not followed by another P.
- Jtsummers 2y ago
  No, per the original asker on Math Exchange SCP doubles the number of As, there's no need in their problem description to deselect. It's not the same as the typical C-a, C-c, C-v shortcuts on a modern computer where you'd need a deselect option after C-c. The C++ program produces a trace that also results in SCP doubling the size, or the 42 action sequence wouldn't even work. If you look at the trace that Hillel shows (and is on Math Overflow) it would only work out to 2304 As if you had to do SCPP to double the size and SCPPP to triple it. Which is quite a bit short of the target of 100,000. > What I started thinking about was – If the steps of "select all", "copy" and "paste" are roughly counted as one step. Each step makes the number ×2, so it is a geometric progression with a common ratio of 2. It's clear from that that he was not thinking of a paste following a select-copy as replacing what was already there. EDIT: Typos
  - bgoated01 2y ago
    Okay, I can see that now, thanks.

hwayne 2y ago

I'm genuinely surprised that the Picat is so much faster than the C++. I assumed it would be easier to write, but also slower.

Karliss 2y ago
I have a feeling that it might be due to C++ solution not being proper BFS since it doesn't have anything preventing the visiting of same state multiple times. One thing that slightly tripped me is that full BFS state space without additional tricks is in theory N^2 (current length x copied length) . Also the memory usage for C++ solution is ~1.8GB and bumping N to 200K increased it to 6GB . I assume that Picat automatically detects and prevents duplicate computation on identical states. Got nerd sniped. If you think about the problem a bit harder (but not hard to go into math of prime factors) there is a dynamic programming solution. The code for obtaining only steps is a bit simpler, but it can be also extended to recover full answer https://gist.github.com/karliss/5ca978390791daca71a1d812c43a924c https://gist.github.com/karliss/5ca978390791daca71a1d812c43a... Had no issue obtaining full 9104 step solution for ==100001 . On my computer: C++ DP: <0.003s C++ from article: 3.032s Memory usage of DP solution is linear. The double nested loops look a bit scary, but it actually forms harmonic series sum: `sum (n/i) ~ n log n` so the speed isn't bad for non analytic solution. The main insight for fast DP solution is how to reduce the state space from NxN (lenght X copied length) to N. All solutions will be in form (SC(P)+)+. Once you know minimum step count for reaching some length, you don't care about what the currently copied length is. Assuming you reach some length L_2 = L_1 * i, any solutions L_1(i+j) would already be processed when handling L_1, means you only need to updated L_2 (i). Now that I have written it I get where the factorization related math talk in stack exchange comes from.

bgoated01 2y ago

Doesn't SCP just give you the same number of characters, since there is no select nothing action? The paste replaces whatever is currently selected. That's what it looks like the C++ code in the article is doing to me. That's also how a quick real world test works for me. That's why you don't see any SCP in their solution not followed by another P.

Jtsummers 2y ago
No, per the original asker on Math Exchange SCP doubles the number of As, there's no need in their problem description to deselect. It's not the same as the typical C-a, C-c, C-v shortcuts on a modern computer where you'd need a deselect option after C-c. The C++ program produces a trace that also results in SCP doubling the size, or the 42 action sequence wouldn't even work. If you look at the trace that Hillel shows (and is on Math Overflow) it would only work out to 2304 As if you had to do SCPP to double the size and SCPPP to triple it. Which is quite a bit short of the target of 100,000. > What I started thinking about was – If the steps of "select all", "copy" and "paste" are roughly counted as one step. Each step makes the number ×2, so it is a geometric progression with a common ratio of 2. It's clear from that that he was not thinking of a paste following a select-copy as replacing what was already there. EDIT: Typos
- bgoated01 2y ago
  Okay, I can see that now, thanks.