Solving a math problem with planner programming

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

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.