What I Wish I Knew When Learning Picat

[David Silverman]

I love Picat. I've spent the past several months learning the language and completing puzzles and Advent of Code problems.

Inspired by What I Wish I Knew When Learning Haskell, I've written up what I learned along the way in this document. Many thanks to Hakan for his tireless editing!

Here's my document and code. Feedback welcome. I hope it helps someone.

What I Wish I Knew When Learning Picat

link:  https://github.com/dsagman/picat

[Neng-Fa Zhou]

Thank you for your writing. While the User's Guide is terse and dry, your document—with examples—is a joy to read. I especially enjoyed your solution to the AoC 2016 Day 15 problem. I actually came to understand the problem description through your code!

Here are a few corrections:

* Arrays (O(n) access) => Arrays (O(1) access)

* It a standard BFS => It uses a standard BFS

*  solve($[degree,updown,min(L1), min(QE),

Picat doesn't support multiple objectives, so the second objective, min(QE), has no effect.

* N=3, println(my_n_is_set_to_N). % output my_n_is_set_to_3
 my_n_is_set_to_N is an atom, so the output should be my_n_is_set_to_N.

Cheers,

NF

[Claudio Cesar de Sá]

Hi David,

Congratulations on your text about the PICAT language. I’ve read some parts, and it’s truly a pleasure to read.
I believe you might soon be able to turn it into a full programming book using PICAT, once you are a native English speaker.
If you place it in a separate GitHub repository, everyone can contribute using pull requests to your text.
A collaborative effort to continue and enrich your work.
Congratulations once again, and count on my help if you ever need it.

Claudio

[David Silverman]

Thanks! I think it is already a separate github repository with just the text and example code. Do I need to change something for others to do pull requests?

[Neng-Fa Zhou]

David's program for the Day 24 problem of AOC16 takes too long to solve my input (https://github.com/nfzhou/aoc/blob/main/in16_24.txt).

 I wrote a program from scratch: 

https://github.com/nfzhou/aoc/blob/main/aoc_16_24_part2.pi

It uses the hcp constraint. For part-1, you need to add a dummy node to the graph. My program only takes 3s to solve the instance.

I am still looking into why David's program hangs with the beta version (It finishes with version 3.8#7).

Cheers,

NF

[Neng-Fa Zhou]

As David comments in the source code, the freeze is caused by multiple calls to best_plan. It's not a good idea to have multiple calls to best_plan in one program. After I changed the best_plan to path, where path is defined below, the program works well and is much faster (it takes less than 1s).

table (+,min)
path([End,_Neibs,End],Cost) => Cost = 0.
path([[Y,X],Neibs,End],Cost) =>
    member(MoveTo,Neibs[Y,X]),
    NextS = ([MoveTo,Neibs,End]),
    path(NextS,Cost1),
    Cost = Cost1+1.    

Cheers,

NF

[David Silverman]

Nice and very interesting!

I will put these in my readme when I get back from  vacation. One thought though: the planner presents a straightforward way of conceptualizing a stepwise optimization. That abstraction is what I love about Picat. 

A DFS or BFS also works, but requires more CS knowledge. Folks here are experts and that makes these algorithms “easier”. I have to always pause to think how graph search works and while I wrote BFS and DFS in Pascal in 1985, they are not as clear to me as planner. Moreover, DFS or BFS can also be done in any language. Only Picat has the planner. 😀

Perhaps there’s a way to abstract DFS and BFS with the clarity of planner’s interface? The “holy grail” is not to have the programmer think through the search algorithm.  

Or perhaps the lesson is for me that I do need to learn these techniques 

[David Silverman]

Thank you! I have thoroughly enjoyed learning and using Picat. 

I've made these edits below.

For this one though, "solve($[degree,updown,min(L1), min(QE)," I am seeing that the CP version gives the wrong result for part 2 versus the knapsack version. How can I modify the code to solve for minimum length and QE? Here's the current output:

Bin 1: [1,89,101,107,109,113]
Table Answer Part 1: 11846773891

CPU time 0.007 seconds.


Found 6, 11846773891 {0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,0,1,0,1,0,0,0}
Bin 1: [1,89,101,107,109,113]
CP Answer Part 1: 11846773891

CPU time 0.194 seconds.


Bin 1: [61,107,109,113]
Table Answer Part 2: 80393059

CPU time 0.0 seconds.


Found 4, 89809099 {1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,0,0,0,0,1,1,1}
Bin 1: [89,97,101,103]
CP Answer Part 2: 89809099

CPU time 0.011 seconds.

The code is here:

https://github.com/dsagman/picat/blob/main/example%20code/day24_2015.pi

--
You received this message because you are subscribed to a topic in the Google Groups "Picat" group.
To unsubscribe from this topic, visit https://groups.google.com/d/topic/picat-lang/NBR294O9tik/unsubscribe.
To unsubscribe from this group and all its topics, send an email to picat-lang+...@googlegroups.com.
To view this discussion visit

https://groups.google.com/d/msgid/picat-lang/ac068065-0363-4d3b-889e-0395d732d10dn%40googlegroups.com

.

[David Silverman]

I'll answer my own question, we only need to minimize QE. Here's my revised code. I made a bunch of simplifications in the cp version and ffd is much faster here than the default search method.

import cp.

main =>

% Weights = {1, 2, 3, 4, 5, 7, 8, 9, 10, 11},

Weights = {1,2,3,7,11,13,17,19,23,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97,101,103,107,109,113},

print("===========\n"),

time(go_kn(Weights,sum(Weights)//3, 1)),

printf("===========\n"),

time(go(Weights, sum(Weights)//3, 1)),

printf("===========\n"),

time(go_kn(Weights, sum(Weights)//4, 2)),

printf("===========\n"),

time(go(Weights, sum(Weights)//4, 2)),

printf("===========\n").

go(Weights,Target,Q) =>

printf("Constraint Solution Part %w\n",Q),

assign_bin1(Weights,Target,Bins,QE,L1),

solve($[ffd,min(QE),

report(printf("Found %w, %w %w\n", L1, QE, Bins))],

Bins),

Bin1Weights = [BW: I in 1..Weights.length, BW=Bins[I]*Weights[I],BW>0],

printf("Bin 1: %w ",Bin1Weights),

printf("CP Answer Part %d: %w\n",Q,prod(Bin1Weights)).

assign_bin1(Weights,Target,Bins,QE,L1) =>

N = length(Weights),

Bins = new_array(N),

Bins :: 0..1,

scalar_product(Weights, Bins, Target),

L1 #= sum(Bins), % for reporting bin1 size

QE #= prod([max(1,(Bins[I]*Weights[I])) : I in 1..N]). % Minimize QE = product of weights

go_kn(Weights,Target,Q) =>

printf("Knapsack Solution Part %w\n",Q),

knapsack(to_list(Weights),Target,Sack,Val),

printf("Bin 1: %w\n",Sack),

printf("Table Answer Part %d: %w\n",Q,second(Val)).

% knapsack modified from https://picat-lang.org/picatbook2015/constraint_solving_and_planning_with_picat.pdf

% Val = (Length of Sack, QE)

% Item is a list of weights

table(+,+,-,min)

knapsack(_,C,Sack,Val), C<=0 =>

Sack = [], Val = (1,1).

knapsack([_|L],C,Sack,Val), C > 0 ?=>

knapsack(L,C,Sack,Val).

knapsack([IWeight|L],C,Sack,Val), C >= IWeight =>

Sack = [IWeight|Sack1],

knapsack(L,C-IWeight,Sack1,Val1),

Val = (first(Val1)+1,second(Val1)*IWeight).

[Neng-Fa Zhou]

Your program doesn't look good. First, you cannot minimize QE only; you need to minimize the cardinality of group-1 first, and then minimize QE. Second, you have to make sure that the items that are not assigned to group-1 can be evenly distributed by weight to the remaining groups.

This problem is much harder than I thought. My model (https://github.com/nfzhou/aoc/blob/main/aoc_15_24.pi), which uses an integer-domain variable for each item to indicate the assigned group, takes too long to compute.

Cheers,

NF

[David Silverman]

I have always been terrible at number theory, but I think there's something about the way the puzzle uses odd weights that allows for just QE to be minimized and get the right answer. Or I just got lucky with my input.

Regardless, I got your code to compute the correct result for my dataset in .4 seconds for K=3 and .2 seconds for K=4. 

Here's the changes I made, and they make a big assumption.

I am going to make an assumption based the Reddit discussion.  https://www.reddit.com/r/adventofcode/comments/3y1s7f/day_24_solutions/ I assume there's a valid solution for the other groups if we divide the total weight by K and assign that to group 1. Solving for all groups makes the problem much harder.  

The puzzle instructions hint at this by saying "It doesn't matter how many packages are in either of the other two groups, so long as all of the groups weigh the same."  While not exactly a green light for my assumptions, it's strongly implying it.

If only solving for group 1, then the selection variable Vs can be 0..1 instead of 0..K-1 and use Vs[I] = 1 for group 1. Then we can get the number of elements in group one with sum(Vs) instead of sum(Vs #= 0).  And the prod with prod(max(1,Vs[I]*Ws[I])).

There's much more about K equal subset partitioning here: https://en.wikipedia.org/wiki/Partition_problem, but I don't immediately see anything here that validates the assumption from Reddit. 

Code is here: https://github.com/dsagman/picat/blob/main/example%20code/day24_2015_nfz.pi