Solving a math problem with planner programming | Hacker News Reader

Solving a math problem with planner programming

buttondown.email

70 pointstodsacerdoti10 comments

> Because Picat is a research language it's a little weird with putting expressions inside structures. If we did $state(1 + 1) it would store it as literally $state(1 + 1), not state(2).

> Also you have to use dollar signs for definitions but no dollar signs for pattern matching inside a function definition. I have no idea why.

I've heard of Picat before but haven't played with it. But from contrasting to Prolog I think I can guess what's going on.

In Prolog, everything is an uninterpreted term. If you want arithmetic "expressions" to be "evaluated", you must explicitly ask for that with the is/2 predicate. Also, there are no "functions" to be "applied". So in Prolog you would write:

    action(state(A, Clipboard), To, Action, Cost) :-
        NewA is A + Clipboard,        % I want the number 2, not the term 1 + 1
        To = state(NewA, Clipboard),  % I want a data structure called state, not to apply a hypothetical "state" function
        Action = ("P", To),
        Cost = 1.

Picat turns these things around. There are expressions, there are functions, and the = operator does evaluate its right-hand side. So now if you write state(NewA, Clipboard) on the RHS of an = operator, the default would be to interpret this as a function call to the "state" function. There is no such function, and if there were, you wouldn't want to call it here. You want a structure called "state". So you mark it as a structure construction rather than a function call.

This has nothing to do with being "a research language", just having to do with having to be explicit about interpreting things as data vs. code. It's the same as quote in Lisp: sometimes you want (f a b) to be a function application, and sometimes you want to build a list containing f, a, and b. In Picat as in Lisp, you need to use a quoting mechanism in the latter case.

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.

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.

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/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.

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.

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

Okay, I can see that now, thanks.

About the C++ implementation, instead of BFS, you most likely want to use Uniform search.

In general; search algorithms like BFS, DFS, Uniform, A* and variants have the following structure:

    do
      current_state, cost <- container.pop()
      container <- container.update(expand(current_state))
    while current_state != goal

where container is a datastructure, and this is the key difference. DFS simply prepends all nodes, so every expansion just goes deeper, we use a stack. BFS simply appends, it's a queue (an expensive one too!), uniform uses a priority queue based on the cost. This allows you to blend actions of variable cost, and still reach minimal cost nodes. A* simply augments this with a heuristic when sorting.

Planning is a really interesting way of solving problems; I used in in a data generation kind of software; the idea is that you provide a struct / type definition — can be recursive or otherwise, and the planner figures out a path to this. It can be further extended with adding conditions on the input, or generalizing this to accept schemas.

To reach the exact number, I would think that:

- if the number n is prime, it would be an SC + (n-1)*P, making the total number of actions n + 1 (as SC counts as 2 actions)

- if the number n is composite, you'd need to factor it, find the smallest and largest prime factors (pf1 and pf2), which would necessarily multiply into n again, and the total number of actions is (pf1 + 1) + (pf2 + 1)

If my reasoning is correct, reaching 100007, which is prime, would require 100008 actions. And reaching 100001, which factors to 11x9091, would require 9104 actions.

To reach at least n, I reason:

- 1 or 2 action sequences do nothing, as an SC is necessary followed by at least 1 P to have any effect on the output

- 3 actions (SCP) allow you to at most double the size

- 4 actions (SCPP) is more efficient, allowing you to triple the size

- 5 actions (SCPPP) is yet more efficient, allowing you to quadruple the size

- 6 actions of (SCPPPP) would allow you to quintuple the size (still more efficient than SCPSCP)

- 7 actions gets interesting as SCPSCPP, SCPPSCP and SCPPPPP would all sextuple the size

- 8 actions is the tipping point, where SCPPPPPP would hextuple the size, but you can achieve a better result by combining the previous steps - only SCP+SCPPP [identical to SCPPP+SCP, as multiplication is commutative] would make 8 actions, leading to octuple, or SCPP+SCPP leading to nonuple

That means that SCPPPPPP is no longer a viable choice and that more than 7 actions always means it's more effective to combine shorter sequences to muliply things out. The order of them does not matter. As x^y gets bigger faster with increases in y than with increases in x, and we can see from the list above that, whenever we starting combining sequences, multiplying the size by 9 is the most efficient we can do, for any significant large number n, we'd just wants as many repetitions of SCPP as possible in there, only switching to something else down the list when reaching the end goal can be done in fewer steps than multiplying by 3 repeatedly (and there's only a finite number of combinations there, when the number of actions is not evenly divisible by 4, not allowing you to use the SCPP sequence).

Disregarding any further occurrences of SCPP, you can do a combination of 1 sequence:

SCP (x2), SCPPP (x4), SCPPPP (x5), SCPPPPP (x6)

or a combination of 2 sequences, once again disregarding SCPP and more efficient shorter combinations: SCPPPSCPPP (x16), SCPPPSCPPPP (x20)

Even SCPPPPSCPPPP (x25) is already less efficient than the SCPPSCPPSCPP (x27) sequence of the same length.

So I figure that to reach at least n, you would always end up with as many repetitions of SCPP as possible, followed by one of the 6 above combinations (of one or two sequences, at most 11 actions). Any sequence of 12 actions or more could be more efficiently reduced to ones containing SCPP again.

Reply on news.ycombinator.com