[HN Gopher] Solving a math problem with planner programming
       ___________________________________________________________________
        
       Solving a math problem with planner programming
        
       Author : todsacerdoti
       Score  : 19 points
       Date   : 2024-07-02 16:20 UTC (6 hours ago)
        
 (HTM) web link (buttondown.email)
 (TXT) w3m dump (buttondown.email)
        
       | PartiallyTyped wrote:
       | 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.
        
       | Jtsummers wrote:
       | 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.
        
       ___________________________________________________________________
       (page generated 2024-07-02 23:01 UTC)