Advent of Code 2024 in Picat?

[Hakan Kjellerstrand]

Anyone more that will participate in this year's Advent of Code (https://adventofcode.com/ ) with Picat? It starts this Sunday (December 1st at midnight EST (UTC-5)).

I have a private leaderboard that you are welcome to join. The code is 1004011-3a3a3aea .(enter this at the Private Leaderboard page).

If you are on another Picat related Leaderboard feel free to share the code.

This year I'll probably use my regex library for parsing the input files: https://github.com/hakank/picat_regex .

Hakan

[Neng-Fa Zhou]

Thanks, Hakan, for taking the initiative. I did the day-1 problems. Here are my programs:

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

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

It's fun to do programming in Picat!

Cheers,

NF

--
You received this message because you are subscribed to the Google Groups "Picat" group.
To unsubscribe from this group and stop receiving emails from it, send an email to picat-lang+...@googlegroups.com.
To view this discussion visit https://groups.google.com/d/msgid/picat-lang/b6dbdc84-8e21-41db-9c65-cc4516298044n%40googlegroups.com.

[Hakan Kjellerstrand]

That's great, Neng-Fa!

My solutions in Picat are here: 

- http://hakank.org/advent-of-code-2024/ .(primary)

- GitHub: https://github.com/hakank/hakank/tree/master/advent-of-code-2024 (might take some time until I update this)

/Hakan

[Claudio Cesar de Sá]

Hi everyone

I will try to do as possible as I can
Here are my codes:
https://github.com/claudiosa/CCS/tree/master/picat/2024_Advent

The readings from the file are coming from Neng-Fa's code.
At the end, the solution of  A  seems "a step-by-step" of Neng-Fa version, the B is  different.

claudio

PS sorry if this post is duplicated

[Claudio Cesar de Sá]

Hi

I finished Part A of Day 2 using CP.  Part B ... unfortunately... probably a wrong approach.
The readings input come from Hakan:  Lines = [Line.map(to_int): Line in read_file_lines(File).map(split)],
the length of "Lines" were variable ...
Day 3 ... only using a regex or something similar. I’ll stop here and wait for a problem with an easier input.
my best cheers for all

Claudio

[lassenza73]

Hi,

this is my code for day 1

import util.

main([Input]) =>
    Lines=read_file_lines(Input),
    N=length(Lines),
    S=[split(L) : L in Lines],
    S1=sort([S[T,1].to_int : T in 1 .. N]),
    S2=sort([S[T,2].to_int : T in 1 .. N]),

    D=sum([abs(S1[T] - S2[T]) : T in 1 .. N]),
    println(D),

    R=new_list(N),
    R=[sum([1  :  T2 in S2, T2==T1]) : T1 in S1],
    G=sum([R[T]*S1[T] : T in 1..N]),
    println(G).

Luca

[Neng-Fa Zhou]

I am wondering why using CP gives you an edge for the Day-2 problem. Take a look at my programs for Day-2 and Day-3.

https://github.com/nfzhou/aoc

I don't think using Hakan's regex library has any advantage for this problem either.

Cheers,

Neng-Fa

To view this discussion visit https://groups.google.com/d/msgid/picat-lang/a9032cd0-72ad-4bcf-bc21-9143e605d7dcn%40googlegroups.com.

[Neng-Fa Zhou]

Hi,

Your program uses the index operator on lists, such as S[T,1].to_int. You know that lists in Picat are singly-linked lists, and the operator L[I] takes linear time. It already takes O(n^2) time for your program to get the values ready for sorting.

Cheers,

NF

To view this discussion visit https://groups.google.com/d/msgid/picat-lang/737c1ee9-15ed-47f9-b9c5-c11a88d919afn%40googlegroups.com.

[Hakan Kjellerstrand]

Hi Claudio.

Glad that you joined! Good luck.

Yes, for today (Day 3) regexes certainly helped (though I know that some Prolog guys did it using DCGs).

For part1, I got the fastest solution submission time ever using regex (4min29s, and I'm not a fast typer), but then did a major newbie mistake for part 2 so it took hours to get the correct solution.

After Oisin (DestyNova at GitHub) did a non-regex approach, he added a very neat regex approach for part 2: https://github.com/DestyNova/advent_of_code_2024/tree/main/3 .I also recommend reading his notes about the problems since he mentions thing he struggles with in Picat.

/Hakan

[Claudio Cesar de Sá]

Hi everyone, answering...

1. Day 2 without CP:
   Indeed, Neng-Fa, CP wasn’t necessary to solve Day 2. I rewrote a version that avoids CP entirely. For checking order, I initially used the 'increasing' and 'decreasing' constraints from CP library. However, with 'sorting' and using 'reverse' predicates/functions achieve the same result. Hakan’s approach demonstrated this effectively.

2. Part B – Borrowed Logic:
   For Part B of Day 2, I borrowed this line: I borrowed   this line   "elseif (select(_A,Line,Line2) && safe(Line2)==1) then"  from Hakan. The use of 'select' is indeed very fitting here, and I hadn’t considered it before.

3. Neng-Fa’s Solutions:
   Neng-Fa, I reviewed your solutions for Day 2—they’re truly impressive. The use of the @ operator in predicates like safe(L@[X,Y|_]) and inc([X|L@[Y|_]]) left me speechless. I’ve seen the @ operator in your codes before but never fully understood its usage. Could you point me to some examples or resources to learn more? Your solutions are incredibly concise—congratulations!
   I also enjoy of this reading:  'Rs = [R : Line in read_file_lines(File), R = [to_int(T) : T in split(Line)]]',   a list comprehension inside another list  comprehension, cool and hard to think.  So interesting of a map applying a split like Hakan's version.

4. Day 3 – On Hold:
   I’ll skip Day 3 for now and come back to it later.

Let’s see what the next challenges bring!

Best regards,


Claudio

[Neng-Fa Zhou]

Hi Claudio,

The operator V@T, which originated in Haskell, is called an as-pattern. It uses a variable to reference a term that occurs in both a pattern in the head and the body. It avoids creating a term that already exists. For example,

inc([X|L@[Y|_]]), X < Y, Y-X =< 3 => inc(L).

is equivalent to

inc([X,Y|L]), X < Y, Y-X =< 3 => inc([Y|L]).

However, the later is less efficient that the former because the term [Y|L] is duplicated. Currently, the Picat compiler is not smart enough to reuse shared terms.

Cheers,

NF

To view this discussion visit https://groups.google.com/d/msgid/picat-lang/874c4a4d-33ed-4140-aba8-928561a489f3n%40googlegroups.com.

[lassenza73]

Hi all,

my code for day 2

import util.

f(L) = R =>
    A = [ L[T] - L[T+1]  : T in 1 ..length(L) - 1],
    B=map(abs,A),
    if max(B)<4 && min(B)>0 && (sum(B)==abs(sum(A))) then
        R=1
    else
        R=0
    end.

 safe([L,I]) = R =>
    H=f([L[T] : T in 1 .. length(L), T !=I ]),
    if H==0 && I<length(L) then  R=safe([L,I + 1]) else R=H end.

main([Input]) =>
    Lines=read_file_lines(Input),

    M=[map(to_int, X) : L in Lines, X=split(L) ],
    DF1=[ safe([Ml,length(Ml)+1]) : Ml in M ],  % part1
    println(sum(DF1)),
    DF2=[ safe([Ml,0]) : Ml in M ], % part2
    println(sum(DF2)).

[C. G.]

Hi everyone,

I participate as well, using picat only, as I intend to learn it better. Detected quite quickly that Hakan does it as well, I study afterwards his solutions to learn from them. I really liked the one where he combined regular code with constraints. His code uses 'map' as well frequently, quite elegant code. Maybe he could post his elegant and compact solutions on the reddit Advent of Code https://old.reddit.com/r/adventofcode/ daily solution megathread such that many people hear of picat, get curious and see and enjoy its advantages?

For 6th day, part 2, my brute force approach reached a very unexpected issue - continuously increasing memory usage, that I can't explain.

I came across of certain other things:
- I couldn't write J:=[J:J in 1..N, L[I,J]='^'][1] and had to write instead J:=[J:J in 1..N, L[I,J]='^'],J:=J[1] : why is that?

- I couldn't write R:=-1, I had to write R:=0-1; why is that?

and across many cases where the compiler reported the syntax errors in a not so helpful way.

The most worrisome is for me the continuously increasing memory footprint of my Advent of Code day 6 part 2. I've tried to isolate it and produce a smaller demonstrator, failed, so I post here the entire code in the hope someone can explain why the memory usage keeps increasing. It went up to 476 GB (!) but it solved the problem correctly. Can anyone say why the memory usage keeps increasing? I suspected maybe ":=" keeps adding new copies of the array, but a quick test failed to reproduce the behavior, so the question remains.

%in.txt contains the text from https://adventofcode.com/2024/day/6/input

import util.
%import regex.

cyclic(L,M,N,I,J):-
    %println(L),
    R:=0-1,C:=0,
    S:=0,
    while (member(I,1..M), member(J,1..N), S<N*M)
        %println([I,J,R,C]),
        I2:=I+R,J2:=J+C,
        if (member(I2,1..M) , member(J2,1..N)) then
            if L[I2,J2]!='#' then
                I:=I2,J:=J2,S:=S+1
            else
                AX:=C,C:=0-R,R:=AX
            end
        else
            I:=I2,J:=J2
        end        
    end,
    if (member(I,1..M), member(J,1..N)) then
        true
    else
        false
    end.




main=>
    L=read_file_lines("in.txt"),
    %println(L),
    M:=L.length,N:=L[1].length,
    println([M,N]),
    I:=[I:I in 1..M, member('^',L[I])], I:=I[1],
    println(I),
    J:=[J:J in 1..N, L[I,J]='^'],J:=J[1],
    println(J),
    S:=0,
    foreach (A in 1..M,B in 1..N)
    print([A,B]),
    if (L[A,B]='.') then
    L[A,B]:='#',
    if cyclic(L,M,N,I,J) then
        println("*"),
        S:=S+1,
    end,
    L[A,B]:='.'
    end
    end,
    println(S).
   

best regards,

Cristian

[Claudio Cesar de Sá]

Hi everyone,

Problem 04 is not difficult because the predicates find(...) and find_ignore_case(...) are very helpful when the input line is a string.
However, I spend a lot of time reading and transforming inputs into the correct data type and not understand well yet.

Following the  Usability  of Picat, a topic that Neng-Fa shared some time ago, I would say that is  my biggest challenge: reading data
from a file in the correct format and adjusted to the problem's requirements.

For example,  Problem 04, I used the following sequence to read the data:

.......
InputLines = read_file_lines(File),
NumRows = length(InputLines),
NumCols = length(first(InputLines)),
.......
It seems a list of list or an Array 2D?
But after that, using the predicates find(...) and find_ignore_case(...) didn’t work for me. I plan to study this further later.

I haven’t started reading Problem 05 yet.

That’s my update for today.

Best regards,

Claudio

[Claudio Cesar de Sá]

Hi

Today I can resume the  code of  Day 4, part A passed in the sample.  But the input test the number is low. Someone could give me some tip?
This problem is very interesting and my code is clear to understand. It is attached

thanks

Claudio

On Wednesday, December 4, 2024 at 6:57:12 PM UTC-3 lassenza73 wrote:

[Neng-Fa Zhou]

Hi,

Thank you for your feedback. 

You certainly don't want to use Picat as an imperative language. I am scared to see so many uses of :=. 

Lists in Picat are singly-lined, and it is very inefficient, in terms of both space and time, to use lists to represent matrices.

Here is my solution to the Day-6 problem:

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

I hope it's helpful for your to learn Picat.

Cheers,

Neng-Fa

[C. G.]

Hi,

I also solved this, so I will answer.

The (main direction) diagonals as you explore them in your code are the same in the transposed matrix as in the original one. You seem to miss on the other hand the secondary direction diagonals (bottom left to top right), that would be detected by the same code, after you reversed each line, instead of transposing the matrix (also read_file_lines gives you something that is a list of strings, that you can already use like a matrix). Same code used again and again for counting just on a different matrix calls for a modularization - extract it to a function and just call it, if I may suggest. It leads to reduced verbosity.

best regards,

Cristian

[C. G.]

Many thanks, yes, very interesting indeed - I didn't know that the prolog cut is available in picat as well, nor that an "if test" with a false condition is true (although this should have been expected).

best regards,

Cristian

[Neng-Fa Zhou]

Hi C.G.,

I realize that I need to write more in response to your feedback.

> I couldn't write J:=[J:J in 1..N, L[I,J]='^'][1]

This should be allowed. In the current version of Picat, the index operator can only be used with a variable, as in X[I,J]. It should be allowed to be used with any construct as long as the construct indicates a compound value, just like in Python and Julia.

> I couldn't write R:=-1

This is inherited from Prolog. The tokenizer treats :=- as one token.  You need to put a space to separate := and -, as in R := -1. The coding style suggests that every binary operator should be preceded and followed by a space.

> I suspected maybe ":=" keeps adding new copies of the array

No, it doesn't copy the array. Your program consumes so much memory, mainly due to 

member(I,1..M), member(J,1..N). In Picat, the range 1..N is converted to a list (unlike in Python and Julia). Instead of using member, you should use between instead, as in between(1,M,I).

> I didn't know that the prolog cut is available in picat

Picat supports Horn clauses (since version 3.0), so you can use Picat like Prolog, except that you need to distinguish between term constructors and function calls.

Thanks again for your feedback!

Cheers,

NF

[jf]

Hello,

Day 7:

I found my silly solution and turned to studying masters.

http://hakank.org/advent-of-code-2024/7.pi

However:

Your previous approach as well as the newer one

% eq([],S,S).
% eq([A|L],S0,S) :-
%  S0 <= S,
%  (S1 = S0*A ; S1 = S0+A),
%  eq(L,S1,S).

eq([],S,S).
eq([A|L],S0,S) :-
 S0 <= S,
 (S1 = S0*A ; S1 = S0+A),
 eq(L,S1,S).

failed on my data, probably because of eq(Ns,0,N), which may eat some  input because of the zero

when multiplied.

After  putting the first number into the accumulator it works:

...eq(Numbers, Sum)...

eq([N|Ns],S) =>
   eq(Ns, N, S).

etc.

Best regards

Josef

Dne neděle 1. prosince 2024 v 18:47:01 UTC+1 uživatel Hakan Kjellerstrand napsal:

[Hakan Kjellerstrand]

Hi Josef.

Thanks for the bug report on Day 7.

Would you mind test the updated program with your input: http://hakank.org/advent-of-code-2024/7.pi

I decided to fix it in the list comprehension instead:

For part1:

println([N : [N,M|Ns] in Lines, eq(Ns,M,N)].sum).

For part2:

println([N : [N,M|Ns] in Lines, (eq(Ns,M,N); eq2(Ns,M,N))].sum).

Interestingly - but not really surprisingly - the time for part 2 went down from 2.3s to 0.95s. Thanks for that as well!

Best,

Hakan

To view this discussion visit https://groups.google.com/d/msgid/picat-lang/f9cca5ca-9230-439b-b0be-fc5fb6ec3dean%40googlegroups.com.

--

Hakan Kjellerstrand
http://www.hakank.org/
http://www.hakank.org/webblogg/
http://www.hakank.org/constraint_programming_blog/
http://twitter.com/hakankj
https://www.facebook.com/hakankj

[Hakan Kjellerstrand]

Hi Josef.

Thanks for the bug report on Day 7.

Would you mind test the updated program with your input: http://hakank.org/advent-of-code-2024/7.pi

Here's the fix in the list comprehension:

For part1:

"""

println([N : [N,M|Ns] in Lines, eq(Ns,M,N)].sum).

"""

For part2:

"""

println([N : [N,M|Ns] in Lines, (eq(Ns,M,N); eq2(Ns,M,N))].sum).

"""

And the time for part 2 went down from 2.3s to 0.95s (part 1 is some millis faster). Thanks for that as well!

Best,

Hakan

[jf]

Yes, on my dataset it works OK (after removing that tiny s in the last line)

Best,

Josef

Dne neděle 8. prosince 2024 v 15:24:45 UTC+1 uživatel Hakan Kjellerstrand napsal:

[Hakan Kjellerstrand]

Thanks for testing. Glad it works. 

Sorry for the "s" (fixed) and any other inconveniences.

/Hakan

To view this discussion visit https://groups.google.com/d/msgid/picat-lang/fc941d71-f361-4af7-a1d9-2dfe73df7507n%40googlegroups.com.

[C. G.]

I've published my solutions for AOC2024:  https://github.com/cgrozea/AdventOfCode2024

All are written in Picat.

[Neng-Fa Zhou]

Today's (Day 16) challenge is a pathfinding problem. Part 1 can be straightforwardly modeled as a planning problem and solved efficiently using Picat's planner.

Part 2, however, is more challenging because it involves determining whether each square lies on an optimal path. Here is my solution:

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

The solution checks each square by:

1. Finding an optimal path from the start to the square.
2. Finding an optimal path from that square to the end.
3. Verifying if the combined cost equals the global optimum.

While this approach works on smaller sample instances, it struggles with larger ones. The program has been running for over an hour on the large instance without completing.

Do you have any suggestions for optimizing the solution?

Cheers,

NF

[Neng-Fa Zhou]

Sorry the solution is here:

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

To view this discussion visit https://groups.google.com/d/msgid/picat-lang/70154026-1d9e-4869-9346-a01ff36fb440n%40googlegroups.com.

[C. G.]

Hi,

I did the same and it worked for me quick enough.

Here my solution https://github.com/cgrozea/AdventOfCode2024/blob/main/16/part2.pi

Time 01:16:08 rank 2224

I debugged a long time, "thanks" to too much copy/paste - the traces of that are still in.

best regards,

Cristian

[Oisín Mac Fhearaí]

I also used the planner for part 1, and tried best_plan_nondet on part 2. It worked for the examples but was not making progress on the full input, even with a tip from Hakan to table the "action" predicate (this made a huge speedup for part 1).

Knowing the optimal cost from part 1, I had hoped to use the "Limit" parameter to best_plan_nondet to force exploration of paths with a cost of *exactly* Limit, but that's not how it works, so it instead still explores from cost=0. This probably isn't the main problem though.

Anyway after going out for the day, I came back and my part 2 program was still running after more than 12 hours. Then I tried doing Floyd-Warshall and Bellman-Ford implementations but it was too slow.

Finally I implemented Dijkstra search: once forwards from the start node to all reachable nodes, then backwards four times from the end node in each orientation. That program got the correct solution in 1.3 seconds.

Program: https://github.com/DestyNova/advent_of_code_2024/blob/main/16/part2_dijkstra.pi

Writeup: https://github.com/DestyNova/advent_of_code_2024/blob/main/16/README.md

I also ran into some weird behaviour, possibly trying to store too much information in the backtracking history (I was passing a "visited" ordset to the action predicate to avoid re-exploring the same states, although "table" would probably have sufficed). I left the broken program in the same directory (part2_setarg_error.pi).

Overall a good puzzle -- part 1 was comfortably solved by the planner, and part 2 was just a bit too much. It would be nice to have a best_plan_nondet variant that takes a Min_cost parameter, or even a plan_nondet that takes Limit.

[C. G.]

I think I understand the difference. For part 2 I just solved in total two planning problems, without the planner module, as I don't know it well enough to use it that flexibly. I used tabling instead.

The two planning problems are:

a) best cost from every point (and direction) of a path to E, if reachable from that point - this comes from free when computing explicitly with tabling what the planner did compute for me in part 1.

b) best cost of a path with reversed moves from every point+direction to (S,west) - to compensate for the movement direction reversal.

best regards,

Cristian

[Hakan Kjellerstrand]

I only manage to solve part 1 (http://hakank.org/advent-of-code-2024/16_part1.pi), using the planner module. The variant I did for part 2 works for the examples but is way too slow for the real data.

/Hakan

[Neng-Fa Zhou]

Thanks to all of you who shared your anecdotes. Cristian's experience showed that tabling works in this case provided that you are patient enough to wait. I am truly impressed by Oisin's clever solutions. Dijkstra's algorithm is the best choice in this case.

Here is my improved solution, which is tailored to part-2. It took 2 hours to find the answer on my computer. A state carries a via-point that must be passed through in a shortest path. The solution is slow because it basically mirrors the Floyd-Warshall algorithm. The same state representation could be used in Dijkstra's algorithm to eliminate the need to compute shortest paths backward.

Cheers,

NF

To view this discussion visit https://groups.google.com/d/msgid/picat-lang/3b6f590d-9bb2-433e-a3aa-2737e2b86b1en%40googlegroups.com.

[Neng-Fa Zhou]

The predicate best_plan_nondet is only good for small search problems. It first uses best_plan to find an optimal plan, and then uses the optimum cost as the bound to do depth-bounded search. It never tries to avoid redundancies during depth-bounded search.

It's not permitted to use := to update tabled data, as they are copied to the table area. For the same reason, it's not good to pass maps to tabled predicates because the built-in 'put' does the same thing as :=.

Cheers,

NF

To view this discussion visit https://groups.google.com/d/msgid/picat-lang/bcaa92ec-dc48-4b3f-b480-2c8731cd2c32n%40googlegroups.com.

[C. G.]

NF's solution to day 17 is quite nice ( https://github.com/nfzhou/aoc/blob/main/aoc_24_17_part2.pi ), but I don't understand one thing:

At https://adventofcode.com/2024/day/17/input I see

Register A: 30899381 Register B: 0 Register C: 0

Program:     2,4,1,1,7,5,4,0,0,3,1,6,5,5,3,0

but he used 2,4,1,5,7,5,0,3,4,0,1,6,5,5,3,0

which is not exactly the same.

Where is the discrepancy coming from?

[Neng-Fa Zhou]

I got the following when clicking on the link.

Cheers,

NF

Puzzle inputs differ by user.  Please log in to get your puzzle input.

To view this discussion visit https://groups.google.com/d/msgid/picat-lang/948c6d17-b697-45fc-843c-45c861ea82f5n%40googlegroups.com.

[jf]

Hello,

in aoc18 I have tried the code bellow.

It works, however there are three best plan versions, which give different results.

For experimental (small) data from the intro I got:

best_plan: 22
best_plan_bin: 24
best_plan_bb: 22

the bin is wrong:
...[(7,5),(7,6)],[(7,6),(7,7)]]
...[(7,5),(7,6)],[(7,6),(6,6)],[(6,6),(6,7)],[(6,7),(7,7)]]
...[(7,5),(7,6)],[(7,6),(7,7)]]

On my sharp data I got
316
316
318

and wrong is best_plan_bb

Why is that?

Thank you,

Josef

/*
advcode24-18.pi
*/

import planner, util.

main(L) =>
   L = [N, File],
   m(N.to_int(), File).

m(Faze, File) =>
   Reader = open(File),
   if ( File == "work/adv2024/ad18e.txt" ) then
      Rowcount = 7,
      Colcount = 7,
      Bytes = 12
   else
      Rowcount = 71,
      Colcount = 71,
      Bytes = 1024
   end,
   I = 1,
   Bytesmap = new_map(),
   while (not at_end_of_stream(Reader), I =< Bytes)
      [X,Y] = Reader.read_line().split(",").map(to_int),
              Bytesmap.put((Y+1,X+1)),   % forbidden
      I := I+1
   end,
   close(Reader),

   foreach ( Row in 1..Rowcount, Col in 1..Colcount, not Bytesmap.has_key( (Row,Col) ) )
      Neibs = [ (R,C) : (R,C) in neibs(Rowcount, Colcount, Row, Col),
            not Bytesmap.has_key( (R,C) ) ],
      get_global_map(n).put( (Row,Col), Neibs )
   end,

   Start = (1,1),
   End = (Rowcount,Colcount),
   get_global_map(e).put(end, End),

   best_plan(Start, Plan, Cost),
   % best_plan_bin(Start, Plan, Cost),
   % best_plan_bb(Start, Plan, Cost),

   nl,println(plan=Plan),
   nl,println(cost=Cost).

final((Row,Col)) =>
   (Row,Col) = get_global_map(e).get(end).

action( (Row,Col), S1, Action, Actioncost ) =>
   Neibs = get_global_map(n).get( (Row,Col) ),
   member(S1, Neibs),
   Action =  [(Row,Col),S1],
   Actioncost = 1.

neibs(Rowcount, Colcount, R, C) = [(R1,C1) : (R1,C1) in [(R-1,C), (R+1,C), (R,C-1), (R,C+1)],
   R1 >= 1, R1 =< Rowcount, C1 >= 1, C1 =< Colcount].

Dne středa 18. prosince 2024 v 15:51:55 UTC+1 uživatel Neng-Fa Zhou napsal:

[Neng-Fa Zhou]

It's a nice catch. I can confirm the strange behavior of best_plan_bb. It will be fixed by the next release.

Thank you for reporting. Several AOC participants are using Picat. It'd be great to hear comments and suggestions from them. Together we can make Picat even better.

Cheers,

NF

To view this discussion visit https://groups.google.com/d/msgid/picat-lang/618f04c8-db6f-4259-9374-2978edef062cn%40googlegroups.com.

[Oisín Mac Fhearaí]

The last few days have been fun -- day 17 was really tough and my CP/SAT model didn't terminate after many hours (I think due to making it overly general and "heavy"), so I started over with a manual analysis that was pretty painful. Days 18 and 19 were fairly easy, and day 20 part 1 was fine, but my solution for part 2 needed to run for 90 minutes! I'm not really sure how it could be faster, so I look forward to learning from other people's solutions later.

After using the same Dijkstra implementation several times, I extracted it into a separate module and wrapped it with a "best_plan_star/3" predicate that follows the planner API: https://github.com/DestyNova/advent_of_code_2024/blob/main/lib/planner_star.pi

After more testing I'll move it into a separate Git repo.

I tested it on one or two problems and it made a small improvement in runtime. When I have more time I'll test it on some of my solutions to 2023 and 2015 puzzles where I used the depth-based planner (especially the heuristic capability I just added, so it's really A* now and not Dijkstra). There will probably be many problems where A* uses way too much memory, in which case planner will be a safer choice. In future I might try the memory-bounded A* variants like PEA*. Any comments / testing would be welcome!

[C. G.]

I still try to use cp for the second part of the problem from day 17, the only one I didn't solve yet. As usual, I struggle a lot with the error reporting in picat - I already collect samples for NF.

But this one that I've found right now is really difficult to understand even after I've identified what code line that produced it, and therefore worrying:

============

import cp.
bits(A,V,N)=>V=new_array(N),V::0..1,
    A#=sum([2**(I-1)*V[I]:I in 1..N]). %this works
    %A#=[2**(I-1)*V[I]:I in 1..N].sum. %this does not!  *** error(instantiation_error,* /2)    
main=> A::0..15,A#=9
    ,bits(A,B,4)
    ,solve([A,B]),println([A,B]).

============

Basically List.sum doesn't work and raises an error, but sum(List) does work, on the same list. Aren't those guaranteed to be equivalent?

best regards,

Cristian

[Neng-Fa Zhou]

Here is my solution for the Day 20 part-2 problem:

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

It returns an answer in 2 seconds.

I wasted a lot of time due to my misunderstanding of the definition of cheat paths. Originally, I thought that  a cheat path was only made of walls, and a path was needed to be found from each origin to each viable destination. Later after spending time testing, I realized that a cheat path can be made of any type of cells and the Manhattan distance is the shortest distance. I have to say that the problem description could be made more clear to avoid misunderstandings.

I agree that a good library of graph algorithms, including the Dijkestra's algorithm, is very useful. Tabling is nice, but it can be very memory demanding.

Cheers,

NF

To view this discussion visit https://groups.google.com/d/msgid/picat-lang/b6fd91c0-89c7-487c-b263-1dd56b885915n%40googlegroups.com.

[Neng-Fa Zhou]

I agree that Picat's error messages need to be made more user friendly. This is something we need to work on next. Please send me your feedback after AoC is done. 

Personally I need a command line option, like "-trace", which enables that tracer from the beginning. In this way I can start tracing execution without entering the REPL. I also think that a backtrace of the runtime stack would be helpful whenever a run-time error occurs.

In a constraint context, the OOP notation cannot be used for function calls. I know it's inconsistent, but in a constraint context, we never need to chain function calls.

Cheers,

NF

To view this discussion visit https://groups.google.com/d/msgid/picat-lang/8b6e4d8d-f8b9-4582-b853-e4a5e8e64a14n%40googlegroups.com.

[Oisín Mac Fhearaí]

While solving today's puzzle with CP/SAT I noticed an issue where the predicates "count" and "exactly" seem unable to figure out the domain of the count variable: https://github.com/DestyNova/advent_of_code_2024/blob/main/23/part2.pi#L20-L21

A smaller example:

import sat. % cp is the same
main =>
  Xs = [0,1,1],
  Xs :: 0..1,
  %N :: 0..Xs.len,
  exactly(N,Xs,0),
  solve([],[Xs,N]),
  println(N).

If I don't uncomment the line defining N's domain, the program seems to hang forever as soon as it encounters the "exactly" predicate (and the same if I swap it for a count constraint). But it should figure out that the domain must be from 0 to the size of the list or array.

[Neng-Fa Zhou]

Thanks for reporting the issue. It's interesting. Picat converts the exactly constraint to #=, which should maintain interval consistency on N. I'll fix it in the next version.

I notice that your program becomes 40%  faster if the exactly constraint is changed to:

  sum(Clique) #= L-N,

Cheers,

NF

To view this discussion visit https://groups.google.com/d/msgid/picat-lang/2c34e017-a07a-4f8d-8110-c301dff2874en%40googlegroups.com.

[Oisín Mac Fhearaí]

Very cool! Although strangely, if we swap "L-N" for "N" and try to maximise that, it seems to be about 100% slower for SAT and 40% slower for CP. I would have expected no difference in performance, but I guess it generates different clauses behind the scenes.

[C. G.]

I also found something today, while trying to understand the relation between the constraints and backtracking, loops and so on: this program gives me different (and wrong) results when using sat instead of cp. I cannot explain why this happens.

import cp.
%import sat.

main=>
foreach(I in 1..2)
X::1..100,
Y::0..100,
if I=1 then
    X mod 2 #=0
else
    X mod 3 #=0
end
,solve([$min(X)],[]),println({I,X})
end
.

best regards,

Cristian

[C. G.]

Day 24, part 2, my take:

After failing to model it with Picat (the problem I generate is unsatisfiable)  - see https://github.com/cgrozea/AdventOfCode2024/blob/main/24/part2_picat_wrong.pi - I wrote a Picat Minizinc model builder and solved that model with Google OR Tools. My code, the huge but easily solvable MiniZinc model, as well as a Picat generator for problems of various sizes are all here: https://github.com/cgrozea/AdventOfCode2024/tree/main/24

best regards,

Cristian

[Neng-Fa Zhou]

I can confirm the bug in the SAT encoding of the mod constraint.

Picat> import sat

Picat> X :: 1..100, X mod 2 #= 0, solve($[min(X)],X)

X = 4

Thanks for reporting the bug. It'll be fixed by the next release.

BTW, it's generally not good to have nested calls to solve. Your program should be written as follows:

import sat.
main=>
    between(1,2,I),
    X::1..100,

    if I=1 then
        X mod 2 #=0
    else
        X mod 3 #=0
    end,

    solve([$min(X)],[]),println({I,X}),
    fail.

Cheers,

NF

To view this discussion visit https://groups.google.com/d/msgid/picat-lang/8ef01fbb-c026-4cde-ba16-c60f63a14168n%40googlegroups.com.

[Neng-Fa Zhou]

I'll look into it. What value should be given to K0?

BTW, It's weird to see many lines of your program beginning with a comma. Do you think Picat, like Julia,  should insert a comma if a line needs a comma but misses one?

Cheers,

NF

To view this discussion visit https://groups.google.com/d/msgid/picat-lang/f49cf8e8-df31-433f-a2a9-5f1a9c1cea6fn%40googlegroups.com.

[C. G.]

The value for K0 depends on the input (how many gates are involved in swaps). For the input in part 2 of day 24, the correct value is 8. For smaller inputs, that can be generated with my generator, one should use the same value as used when generating (e.g. 2 for a single pair of swapped gates).

Thank you for the offer to look into it, I just managed to repair it, there was a test for AND left there instead of testing for addition.

Now I can proudly present a pure Picat solution to solve automatically day 24 part 2 task using constraints : https://github.com/cgrozea/AdventOfCode2024/blob/main/24/part2.pi

The SAT solver is single core, but it was fairly fast in this case, it required 25 seconds on my machine.

On the today machines with 100 cores and more (we use one with 192 cores), a parallel SAT solver might make sense. Using just 1% or less of the machine cannot be the optimal way.

Concerning the commas, yes, please! This in my view absolutely needed, it makes much easier to comment out single lines no matter whether the previous line has or not a comma, or whether the line to be commented our is the last before an "end".

 I considered attempting this myself as a preprocessor, I managed so far to write a script (in Picat)  that tokenizes Picat programs, using read_picat_token. I am afraid that I would need to reimplement the grammar parsing, as I couldn't really find the parser in the sources. Also the other way around as well, if someone finds it more natural to put commas like this (especially in one-liners), why not?
foreach(X in L),do_that,and_this,end

Other ways I think Picat can be improved, please tell me your opinion:
- the above: whitespace(incl. newline) is equivalent to a comma, if needed

- function (pointers?) as regular objects that can be passed around, composition produces a new function, specialization; to make this clearer, how can one map split(":") to the strings in a list?

x.f.g=g(f(x))
call(f.g,x)

- this one is conflicting with the constraints notation, but I kept commenting out lines with #, I wonder whether it would be a good idea to accept # as a comment when it is at the beginning of the line, or the very least when this happens in the very first line - see below.

- connected to the previous one, executable scripts in Picat for linux, bsd and other unix/posix environments, with the shebang (slash-bang) notation.

If the following script is in a file a.pi, and the file a.pi is marked as executable

#!/bin/env picat
main=>println("hi").

executing it produces a syntax error, as Picat doesn't see the first line as a comment:
*** SYNTAX ERROR *** (1-3) wrong rule.
#!/b <<HERE>>  
   in/env picat

- more/full orthogonality, e.g. why shouldn't List.sum work in the context of constraints, when it works everywhere else in Picat, and the rest of the program is written like this?

- a simple/clear way to interface with external solvers (be it CP solvers, SAT solvers or others). I like the way Minizinc achieves this by plain configuration

- regex (of Hakan, or one of yours) should be included

- [nice to have] related to the previous one, it would be nice if this sort of functionality extension could be done with a plugin system (not requiring to recompile Picat). Compiling picat is not difficult, but imagine 16 such packages or 100, using one subset of those should not require fixing (or deciding upon) it at Picat compile time.

I hope you find something useful in my suggestions.

best regards,

Cristian

[Neng-Fa Zhou]

Hi CG,

Congratulations on your success in solving the Day 24 part-2 problem! It's really a tough problem.

Here is what I started with:

https://picat-lang.org/tmp/gen.pi

It tries to identify faulty gates by using many random inputs and removing a smallest set of gates from the circuit (meaning that the constraints are not enforced for these gates). Once the potential faulty gates are identified, I use another program to select four pairs from the set to be swapped. The circuit, after swappings, is good if it is unsatisfiable when X+Y = Z is changed to X+Y != Y. After spending many hours along the path, I couldn't come up with a solution. So I gave up. 

I am done with this year's AOC. Although I couldn't earn all the stars, it was really fun to participate. Could you please explain your solution? I will rewrite your code into something that is more readable once I understand your approach.

Thank you very much for your suggestions. Hakan has proposed a zoom meeting for interested developers and users to discuss the future of Picat. We'll definitely invite you to participate.

Cheers,

NF

To view this discussion visit https://groups.google.com/d/msgid/picat-lang/35bfe2e0-9ecb-4e26-8052-0010e5239150n%40googlegroups.com.

[C. G.]

Hi NF,

The idea of my program is fairly simple:

Use constraints solving and ask that on a number of random  (x,y) pairs x+y=z holds (predicate madd). The number of pairs is given by the argument Steps, I used 30 and 40, after finding out on smaller problems that this suffices (if both produce the same solution, then probably there are enough constraints to avoid ambiguity and that solution is the true one).

The modelling of the swaps:

K(=8) swaps are to be there, I count those from 1 to 8, and have a block of 8 slots, Swappers, that contain the values to be swapped, and assume 1 will swap with 2, 3 with 4 and so on. This helps keeping the number of variables describing the swapping scheme linear and not quadratic.

Each gate has two version of the output, the straight one, V,  that computes what the gate should compute (predicate op), and a value after a potential swap, Vafter. In any gates that use the outcome of this one, Vafter is used.

The constraints for this mechanism are given in the predicate add_gate_constr.

There are 8 decision variables for each gate that control whether that gate is involved in a swap, and precisely how:

Vswap[1..8] . Only one can be set. When Vswap are all 0, it means the gate is not involved in a swap and then Vafter#=V.

If Vswap[I]=1 then the gate is involved in the swap as input to the Swappers slot I.

E.g. if I=3, it means it swaps with the slot 4, that is Vafter is whatever value another gate involved in swaps feeds the slot 4 with.

Vswap for each gate are the only variables that are _not_ new/do not change their value from one (x,y) pair to the next one.

My initial mistake was to reuse also Swappers from one pair to the next one, this led to the model being inconsistent from 2 pairs on.

In my experience the sat solver was the fastest on this type of model (I've done comparisons on smaller prgrams, as my generator can generate such problems of arbitrary sizes). I found somehow the comparison with MiniZinc interesting. MiniZinc is very elegant and expressive, but not really a universal programming language - e.g. I couldn't even sort an array of strings after I've got them, it simply doesn't sort strings. On the other hand (maybe because of that) when I look at a minizinc program I see directly the model. When I look at my Picat program here I see a program that somehow builds the CSP model, but I don't see the model itself, even when I want to debug it. It would be nice if the constraints store could be dumped in a way that enables inspection of the rules stored so far. Also minimal unsatisfiable subset would be nice to have. I could have tried to solve it on the way to understand what constraints I've just added are incompatible with the previous ones, just didn't think of this.

Thank you for inviting me to the call about developing Picat.

best regards,

Cristian

[Oisín Mac Fhearaí]

I solved day 24 manually by treating the gates as sequential instructions and reordering them in vim until there were no dependency hazards (i.e. all "instructions" depend only on the results of previous instructions), then breaking them into repeated blocks of 5 instructions that handle each digit and carry (except the first 2 instructions since no carry applies to bit 0). After reordering and grouping the instructions, it became obvious which instructions violated the pattern, and how to fix it.

But I also wanted to solve it automatically. My intention was to do a proof by refutation (i.e. find a solution to the gate swaps such that the problem of finding some X,Y such that that network fails to output X+Y in the Z registers). But I couldn't figure out how to express that sort of nested "satisfy proposition P1 such that proposition P2 is UNSAT" proof in Picat. Eventually, I got it to work similar to Cristian's solution -- search for a set of swaps such that some hardcoded iterations of random X+Y values sum correctly. This takes about 32 seconds on my computer: https://github.com/DestyNova/advent_of_code_2024/blob/main/24/part2_sat.pi (note that it uses Hakan's regex build to parse the input).

I also tried an incremental nondet solver, which tries to proceed one swap at a time, minimising the total number of errors for another set of random sums. It took something like 2 hours to find one swap, so I didn't bother finishing it for all swaps: https://github.com/DestyNova/advent_of_code_2024/blob/main/24/part2_incr_nondet.pi

Finally I made a genetic algorithm version that tries to minimise the count of errors over a distribution of sums on numbers of different sizes (in bits). That's been running for nearly 14 hours and discovered 2 correct swaps so far: https://github.com/DestyNova/advent_of_code_2024/blob/main/24/part2_genetic_algorithm.pi

That was definitely the problem whose automatic solution was the least obvious to me... I'll have to check out people's approaches in other programming languages.

[C. G.]

I have now all stars, all my solutions are in Picat and are available here: https://github.com/cgrozea/AdventOfCode2024

I find some of them compact and elegant, thanks to the expressiveness of Picat, some others are unintelligible thanks to me using 1 letter variable names, and some are so ugly that debugging was a nightmare - see part 2 of day 21, that took me several days to fix. What I learned from completing AOC 2024 in Picat is that debugging in a multi-paradigm language is very complicated and time consuming.

Not having breakpoints and similar debugging helpers means you are left with print as the only debugging tool.

My favorite Picat aspects:

- tabling with min/max optimization - I could avoid the planing module and customize as needed shortest path algorithms just using tabling.

This bit me in the end at problem 21, where only stuffing my code in addition with minof led to the behavior I expected without it. The predicate minof is also not fully explained in the user guide, I had to chase old presentations to understand how to use it.

- list/array interpolation

- functional composition (dot-chain notation .call1.call2) and aspects (map).

I am still not always sure how various constructs and paradigms interact with each other: does the backtracking inside if-then-else work, such  that the construct is able to generate more solutions when asked? Is it possible to use backtracking to generate constraints ? This is what I expected, and it would have been useful, but my tests seem to indicate that during the backtracking phase the constraints added on the branch that is rolled back are also eliminated.

best regards,

Cristian

[Neng-Fa Zhou]

Congratulations to both Cristian and Oisin on earning all 50 stars!

Cristian, where is the file "m1" required by your program for Day 21? I played with Oisin's program, and tried to improve its efficiency by turning the plan generation problem into a counting problem and reducing nondeterminism (for example, consider only paths that have fewest turns). I believe that for given two directional-pad keys, there must be a best path, so it's unnecessary to try all possible paths using minof.

I am always appreciative to hear your feedback and happy to take your questions. The if-then-else construct

if C then G1 else G2 end

has the same semantics as (C -> G1; G2) in Prolog. While G1 and G2 are backtrackable, C is not. You can assume that C behaves like once(C).

It's generally not a good idea to leave choice points during constraint generation. If you have multiple disjuncts, then use #\/ to connect them rather than ";".

Cheers,

NF

To view this discussion visit https://groups.google.com/d/msgid/picat-lang/19c294f0-8760-4d96-879a-5279617c2c6dn%40googlegroups.com.

[C. G.]

I've added the missing file to my repo, it is here https://github.com/cgrozea/AdventOfCode2024/blob/main/21/m1

My possibly naive idea about using backtracking to collect constraints was this:

say I want to constrain the swapped gates problem for every pair of X and Y of a certain length. Those can be generated dynamically with backtracking, and for every generated pair I would have added the constraint that X+Y=Z, and I would have not expected the constraints store to be rolled back when I move to the next pair. In other words I would have expected the constraints storage to be in the global map (in a way) not on the heap, thus not be affected by backtracking. I can see advantages in both ways, but best would be to give control to the users.

best regards,

Cristian

[Neng-Fa Zhou]

Thanks to C.G. for his help—I’ve rewritten his model for the Day 24 Part-2 problem into a more readable program:

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

It’s truly a brilliant CSP model! CP has been used to train networks, and this is yet another excellent example.

Additionally, I’ve developed a new Picat solution for the Day 21 Part-2 problem:

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

As I suspected, this problem doesn’t require non-deterministic search. An optimal path is always the one that is shortest, has the fewest turns, and follows the direction ordering of <^v> (a handy insight I found on Reddit). This program uses a nice feature of Picat's tabling that allows multiple objectives to be optimized.

With these updates, my repository now includes solutions for all the 2024 Advent of Code problems! It’s been incredibly rewarding to participate, and I’m grateful to everyone who joined the discussions, offered help, and provided feedback.

Now let me collect all the stars for Picat and the Picat community!

Cheers,
NF

[Claudio Cesar de Sá]

Hi everyone,

Congratulations to Christian, Neng-Fa, Hakan, and Oisín! Perhaps you four could be called "The Four Heralds of Renewal."
This is truly a significant achievement for the PICAT community. Competing in a contest that attracts the best programmers
from around the world and earning recognition across industries is no small feat.

Personally, I managed to earn only 7 stars, but I closely followed the discussions here and reviewed some of your impressive code.
 For reference, I’ve shared my tiny contributions here:
https://github.com/claudiosa/CCS/tree/master/picat/2024_Advent

Neng-Fa, I believe it would be fantastic to see a LinkedIn post highlighting PICAT's participation in the AOC.
It’s a great opportunity to showcase the capabilities of the language and the brilliance of its community.

Once again, congratulations to all four of you on this remarkable accomplishment!

Best regards,

Claudio


"PS: I feel a healthy sense of jealousy"

[Neng-Fa Zhou]

I had time to redo the Day 16 problem. My original solution is too slow, and it needs hours to produce the answer. Inspired by Oisin's solution, I use, in the new solution, two separate tabled calls for each free cell, one for computing the lowest cost to the start, and the other for computing the lowest cost to the end. 

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

This solution only needs seconds to find the answer. 

I learned a lesson through this problem. We not only need to design a good state representation that facilitates sharing, but also need to formulate recurrences to facilitate sharing.

Cheers,

NF