Patreon stuff for the picat blog post

format_picat.raku

# This is a script for rendering the output of the picat paths in my blogpost:
# https://www.hillelwayne.com/post/picat
# Allows putting flags before positional args, and writing -bf instead of -b -f
my %*SUB-MAIN-OPTS = :named-anywhere, :bundling;

#`[
Grammars are collections of nested regexes for parsing stuff.
See https://docs.raku.org/language/grammar_tutorial
Note that Raku has its own regex syntax, it's not backwards-compatible with Perl5 regexes
See https://docs.raku.org/language/regexes

Example input:

Origin: {0,0}
Goal: {2,2}
Bounds: {10, 10}
Path: {1,0}, {2,0}, {2,1}, {2,2}

]#

grammar Pather { 
  rule TOP { <origin> <goals> <bounds>? <plan> } # TOP is first rule matching
  token origin { 'Origin: ' <(<coord>)> } # tokens ignore whitespace not in quotes, rules do not
  token goals { 'Goal''s'?': ' <(<coords>)> } 
  token bounds { 'Bounds: ' <(<coord>)> }
  token plan { 'Path: ' <(<coords>)> }

  token coords { '['? <coord> [',' <.ws> <coord>]* ']'?}
  token coord {'{' <number> ',' ' '? <number> '}'}
  token number { '-'?\d+ }
  
}

#| An action class takes a grammar output and postprocesses it,
#| ie turning strings into numbers, putting things in arrays, etc.
#| See https://docs.raku.org/language/grammars#Action_objects
class PatherActions {

  #| method named `X` is called on the results of rule `X`
  #| So this is called the result of TOP, coord is called on results of coord, etc
  method TOP($/) { 

    # make expr stores expr in `made`.
    # make in TOP stores it in the top-level output object, see $m in MAIN
    make {
        origin => $/<origin><coord>.made,
        goals => $/<goals><coords>.made,
        bounds => $/<bounds><coord>.made,
        plan => $/<plan><coords>.made,
        walls => $/<walls><coords>.made,
    }
  }
  method coord($/) { make (+$/<number>[0], +$/<number>[1]);}
  method coords($/) { 
    make $/<coord>>>.made; # >>.made is *basically* `.map({$_.made})`
  }
}


#| MAIN automatically generates a CLI from its parameters.
#| See https://buttondown.email/hillelwayne/archive/raku-is-surprisingly-good-for-clis/
sub MAIN($script, #= Picat filepath, eg planner1.pi
  Bool :b($border), #= adds a nice border around the output
  Bool :f($five-by-five) #= hard-fixes the bounds to 5x5 grid
) {
  my $run = run 'picat.exe', $script, :out; # Calls picat.exe, stores reults of STDOUT
  my $out = $run.out.slurp(:close); # copied from https://docs.raku.org/type/Proc
  my $m = Pather.parse($out, actions => PatherActions); # Parse with Pather grammar, applied PatherActions to parsed output
  my %data = $m.made; # $m.made is the output of `make expr` in PatherActions.TOP
  %data<bounds> = <5 5> if $five-by-five; #<5 a> = [5, "a"]

  #| If $x = 3, ^$x = (0, 1, 2), [' ' for ^$x] = [' ', ' ', ' ']
  my @grid = [[' ' for ^%data<bounds>[0]] for ^%data<bounds>[1]];


  #| Assign places symbols on the the grid. 
  #| If @grid = [[' ', ' ', ' ']], then assign(<1 0>, '!')
  #| makes it   [[' ', '!', ' ']]
  sub assign(@coord, $val) {
    # `with` assigns value of $_ in local scope, so I don't have to write @coord<>[1]
    with @coord<> { #Have to write @coord<> to "decontainerize it", see https://docs.raku.org/language/operators#postcircumfix_%3C%3E
      @grid[$_[1]; $_[0]] = $val;
    }
  }

  
  # Make all of the path steps look like •
  # Do this first so it doesn't overwrite any goals
  # more decontainerization
  for %data<plan><> -> $step {
    assign $step, '•';
  }

  # Make origin an O
  assign(%data<origin>, 'O');
  
  # Make every goal in Grid a G
  # Overwrites the • 
  for %data<goals><> -> $step {
    assign $step, 'G';
  }

  if $border {
    my $b = '+' ~ '-' x %data<bounds>[0] ~ '+'; # ~ is string concat, `-x4`=`----`
    say $b;
    for @grid.reverse { # Reversing grid makes puts O on the bottom instead of top
      say '|' ~ .join ~ '|'; # .join without left-hand-side equiv to $_.join
    } 
    say $b;
  }
  else {@grid.reverse>>.join.map(&say);}
}

partition_planner.pi

% Picat planning algorithm that finds the *most* numbers that
% Can be removed from a list before it has an equal partition
% Blogpost has converse (fewest numbers)

import planner.
import util.
import cp.

main =>
Numbers = [32, 122, 77, 86, 59, 47, 154, 141, 172, 49, 5, 62, 99, 109, 17, -30]  
  , if final($plan(Numbers)) then
      println("Input already has a partition!")
      , explain_solution(Numbers)
    else
        best_plan($setup(Numbers), Plan)
      , printf("Removed: %w%n",[R: $remove(R, _) in Plan])
      , $remove(Last, $plan(FinalState)) = Plan[Plan.length]
      , explain_solution(FinalState)
    end
  .

final(plan(Numbers)) => get_solutions(Numbers) != [].

get_solutions(Numbers) = S =>
  X = new_list(Numbers.length)
  , X :: 0..1
  , X[1] #= 0 % symmetry breaking
  , sum(Numbers) #= 2*sum([Numbers[I]*X[I]: I in 1..Numbers.length])
  , S = solve_all([$limit(1)], X) 
  .
  
action(plan(From), To, Action, Cost) ?=>
   member(Element, From)
   , To =.. [plan, delete(From, Element)]
   , Action = $remove(Element, To)
   , Cost = -abs(Element)
   .

% The hacky bit
action(setup(From), To, Action, Cost) ?=> 
   To = $plan(From)
   , Action = setup
   , Cost = 100 
   .

explain_solution(plan(Numbers)) =>
  [Sol] = get_solutions(Numbers)
  , Left =  [Numbers[I]: I in 1..Numbers.length, Sol[I] = 0]
  , Right = [Numbers[I]: I in 1..Numbers.length, Sol[I] = 1]
  , printf("%s=%d%n", join([to_string(N): N in Left], "+"), sum(Left))
  , printf("%s=%d%n", join([to_string(N): N in Right], "+"), sum(Right))
  .