Advent of Code

[Mark Engelberg]

Is anyone here doing the Advent of Code problems in Picat?

The problems start off quite easy, but I thought it would be a good way for me to get more comfortable with the basics of Picat i/o handling, concision, style and development techniques by comparing my efforts against others. 

[Mark Engelberg]

My thoughts and code from Day 1:

https://github.com/Engelberg/aoc22/tree/main/picat/day1

[Hakan Kjellerstrand]

Hi Mark.

I'm not sure how many days I will do AoC in Picat as long as it's fun (this year I will not do it the first thing in the morning since that was  good for my blood pressure. :-)).

As you mention in the GitHub port, there is no built-in function for splitting a line on "\n\n" (i.e. more than one character); the built-in split function (in the util module) only splits on a single char.  In last year's AoC I did some variants of this, for example using DCG. But this year I will play as much as possible with my regex module (https://github.com/hakank/picat_regex ), for example for splitting on "\n\n".

   split_string(Str,Sep) = regex_replace(Sep,"|",Str).split("|").

The full program is

"""

   import util.
   import regex.

   main => go.
   go =>
      File = "1.txt",
      Total = [split(Line,"\n").map(to_int).sum : Line in split_string(read_file_chars(File),"\n\n")],
       println(Total.max),
       println(Total.sort_down.take(3).sum),

       nl.

    split_string(Str,Sep) = regex_replace(Sep,"|",Str).split("|").

"""

As you see, I tend to use chaining for these kinds of problems, for example using map/1 and take/2.

/Hakan

--
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 on the web visit https://groups.google.com/d/msgid/picat-lang/ef3ca6bb-ea23-4f9f-a1c5-6845db4e2dabn%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

[Neng-Fa Zhou]

When doing scripting, I often use the built-in append to search for a substring in a string. Here is a script for splitting a string into tokens separated by "\n\n":

main =>
    S = "\n\nab\n\ncd\n\nef\n\n",
    split2(S,Tokens),
    foreach (Token in Tokens)
        println(Token)
    end.

split2("\n\n",Tokens) => Tokens = [].
split2(S,Tokens), append(Token,"\n\n",Rest,S) =>
    Tokens = [Token|TokensR],
    split2(Rest,TokensR).
split2(S,Tokens) =>
    Tokens = [S].

Cheers,

NF

On Thu, Dec 1, 2022 at 2:40 AM Mark Engelberg <mark.en...@gmail.com> wrote:

Is anyone here doing the Advent of Code problems in Picat?

The problems start off quite easy, but I thought it would be a good way for me to get more comfortable with the basics of Picat i/o handling, concision, style and development techniques by comparing my efforts against others. 

--

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 on the web visit https://groups.google.com/d/msgid/picat-lang/d0e7f04a-842c-4fc6-9a1d-9f0edd4af5b9n%40googlegroups.com.

[Hakan Kjellerstrand]

Thanks for your variant of splitting strings, Neng-Fa.

My collection of AoC 2022 is here: https://github.com/hakank/hakank/tree/master/advent-of-code-2022

which includes a Picat solution for Day 2 (today). I'll start with a Picat solution - since it's the language I think in when solving problems - and then perhaps add solutions in some other language.

To view this discussion on the web visit https://groups.google.com/d/msgid/picat-lang/CAFOC6HRMP8XOxrPQzfH8-MAEnEKTxY%2BuRX0pjdU1%3D07GkzU0FQ%40mail.gmail.com.

[Mark Engelberg]

Picat doesn't have global variables, correct?

I couldn't figure out an elegant way to define the relevant maps for reuse across functions. I ended up putting them in the main predicate and passing them as arguments to any function that needed them, but that seemed rather unwieldy. Please show me a better way.

I see in your code you just did the entire thing inside of main, but I'd like to understand how to do this in a more composable way.

https://github.com/Engelberg/aoc22/blob/main/picat/day2/part1.pi

I like the way you turned beats into a predicate so you can find the argument that produces the desired result so elegantly. I did not think of that.

[Hakan Kjellerstrand]

Picat does not support global variables as in traditional imperative languages. There are (at least) three ways for doing something similar:

* add the variables in the calls to the functions/predicates, for example using a single "master map" that contains all maps

* add the data as facts in the global database (cf my beats/2 as you mentioned ).

   A simple example (not relevant to today's problem) is to set a single value as global accessible :

      number_of_players(4).

    Here is a more relevant example:

     map_other("A","Rock").
     map_other("B","Paper").
     map_other("C","Scissors").

     map_me1("X","Rock").
     map_me1("Y","Paper").
     map_me1("Z","Scissors").

     map_me2("X","Loose").
     map_me2("Y","Draw").
     map_me2("Z","Win").

     map_points("Rock",1).
     map_points("Paper",2).
     map_points("Scissors",3).
  

   This is a nice (Prolog) approach, especially if one want to access the facts in both directions .e.g

         map_me2(A,"Loose")  -> A="X"

         map_me2("Z",B)         -> B ="Win"

   To simplify this, one can add these facts "programmatically" to the database using cl_facts/1:

      cl_facts($[map_other("A","Rock"),map_other("B","Paper"),map_other("C","Scissors"),
             map_me1("X","Rock"), map_me1("Y","Paper"), map_me1("Z","Scissors"),
             map_me2("X","Loose"), map_me2("Y","Draw"), map_me2("Z","Win"),
             map_points("Rock",1), map_points("Paper",2), map_points("Scissors",3)
             ]),

    Note that cl_facts/1 only works for simple facts, not predicates or functions. Also see cl_facts/2 and cl_facts_table/1-2.

* use get_global_map(). Here's a simple example:

   """

   main =>

      Map = get_global_map(), 

      Map.put(a,1),Map.put(b,2),Map.put(c,3),

      test().

    test =>

       Map = get_global_map(),

       println(Map.get(a).

   """

    The drawback of this approach is that one has to access the global map using get_global_map/0 in each predicate.

    There are variants of global maps which have some different behaviours regarding backtracking etc: see get_table_map/0 and get_heap_map/0.

A small style comment in your code: I note that you tend to use ":=" for simple assignments (unification in Prolog parlance). It's better style to use "=" for these unifications and only use ":=" when/if you are re-assigning a variable.

[Hakan Kjellerstrand]

I've added a variant (go2/0) using facts (via cl_facts/1) instead of the maps: https://github.com/hakank/hakank/blob/master/advent-of-code-2022/2.pi 

Also, the lookup for part2 slightly different: using call/3 to get the proper action. However, it uses the same general approach as go/0, i.e. keeping everything in a single predicate.

[Mark Engelberg]

OK, reworked it both with global map and with predicates replacing the maps. The predicate version is probably the cleanest: https://github.com/Engelberg/aoc22/blob/main/picat/day2/v3.pi

What is the efficiency of storing facts in predicates as opposed to hash maps, when you are only going to do one-direction key->value lookups?

[Neng-Fa Zhou]

Normally you don't want to represent a map as a set of facts, because it takes time to have the facts compiled. If the number of key->value pairs is small and the map is static, meaning that it is never updated, then it makes sense to represent a map as facts.

If you don't want to have a map passed around as an argument, you can use a heap map, and retrieve it whenever you need it using the built-in

M = get_heap_map(your_map_id).

A heap map is just like a map created using new_map(). It is backtrackable. However, if you want to use the same map among different execution paths, even with backtracking, then you should use a global map and retrieve it whenever you need it using the built-in

M = get_global_map(your_map_id).

Here you can see the difference between a heap map and a global map:

Picat> M = get_heap_map(m1), M.put(1,1)
M = (map)[1 = 1]
yes

Picat> M = get_heap_map(m1), M.put(2,2)
M = (map)[2 = 2]
yes

After backtracking, the map created before is lost.

 
Picat> M = get_global_map(m1), M.put(1,1)
M = (gmap)[1 = 1]
yes

Picat> M = get_global_map(m1), M.put(2,2)
M = (gmap)[2 = 2,1 = 1]

A global map is similar to a dynamic predicate created using assert in Prolog.

Cheers,

NF

[Mark Engelberg]

Day 15 part 2 has a very elegant solution in Picat, but it only seemed to work efficiently with SMT as the backend solver. SAT ran out of memory, CP never seemed to finish, MIP generated an error when reading the solution from the temp file. (The error I got was `Writing MIP solution to '__tmp.sol'... ERROR:: invalid value for an integer variable:3068580.0`  and additionally, that floating point value given in the error message is off by one from the correct integer answer for my input).

I'd be interested in understanding why the SMT solver is the best tool for this problem.

https://github.com/Engelberg/aoc22/blob/main/picat/day15/v1.pi (I preprocessed the input file to just contain the numbers so I wouldn't have to worry about the parsing aspect of the problem).

[Hakan Kjellerstrand]

Nice model!

What version of Picat are you using? I'm running v 3.3#3 (under Linux Ubuntu 20.05) and get the following results.

* smt: z3:0,152s  cvc4: 1.381s

* sat: 2.598s

* mip: cbc: 1.188s glpk: the same error as you reported

* cp: too slow (I've tested a couple of different search heuristics but all are very slow)

All (except mip/glpk and cp) give the same solution.

In my experience it's quite rare that SMT is faster than both SAT and CP.

By the way, I've just started with Part 1 and there's the DCG to parse the input file:

"""
digits([C|Rest]) --> [C], { (ascii_digit(C) ; C == '-')}, digits(Rest).
digits([]) --> [].

% "Sensor at x=2, y=18: closest beacon is at x=-2, y=15"
parse_line(Line) --> "Sensor at x=", digits(SX1), ", y=", digits(SY1),
                      ": closest beacon is at x=", digits(BX1), ", y=", digits(BY1),
                      {
                        Line = [SX1,SY1,BX1,BY1].map(to_int)
                      }.
% parse_line([]) --> [].

parse_lines([Line|Lines]) --> parse_line(Line), "\n",  parse_lines(Lines).
% parse_lines([Line]) --> parse_line(Line).
parse_lines([]) --> [].
"""

--

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 on the web visit https://groups.google.com/d/msgid/picat-lang/f8d8188d-eb95-4472-b2f0-f9ff6843ffaen%40googlegroups.com.

[Hakan Kjellerstrand]

Forgot this: When I run the model, the value of 3068580.0 that you commented is the value of Dx (-1), not the answer that is printed: i.e. tuningFrequency(3068581,3017867) = 1227432701786. Is 3068581 the correct solution?

[Mark Engelberg]

You're right, I'm now getting the solution on the SAT solver in a reasonable amount of time, although noticeably slower than SMT. I must not have tested it on SAT again after changing my model (in a previous iteration, I hadn't thought to implement absolute value as a max, I was implementing it as a logical conditional constraint based on whether the value was positive or negative, so it wasn't producing a result on SAT).

On Mip, my point was that the model calls to solve for [Dx,Dy] and it's printing out one less than the correct value of Dx, so even if it didn't produce an error message, I'm not sure tuning frequency would produce the correct result, since possibly the Mip solver would be returning a Dx that is off by one.

[Mark Engelberg]

I'm not familiar with this DCG syntax, so I'm unclear on how this parsing code works. Where I can read more about that?

[Hakan Kjellerstrand]

The Cbc solver (https://github.com/coin-or/Cbc ) works for this example.  I get the same error for the GLPK solver but I'm not sure if the error is from GLPK or Picat. The __tmp.sol file contains these lines which seems to be relevant:

   613 r.616            -3.06858e+06        -4e+06              
   614 r.617             3.06858e+06             0              
   342 X136         *    3.06858e+06             0         4e+06

Perhaps Neng-Fa can make some sense of this?

The DCG (Definite Clause Grammar) that is supported by Picat is the "standard" Prolog syntax. See for example:

- https://en.wikipedia.org/wiki/Definite_clause_grammar
- https://www.amzi.com/manuals/amzi/pro/ref_dcg.htm

Most of these examples work in Picat.

Beware that the Web contains a lot of examples of "extended" DCGs, such as those in SWI Prolog, which might not work (directly) in Picat. SWI Prolog supports helper DCG such as "number" (identifying a number), "white" (identifying whitespace), etc.  I tried to mimic this in http://www.hakank.org/picat/dcg_utils.pi (tested in http://www.hakank.org/picat/dcg_utils_test.pi) but this is not as neat as the one defined in SWI Prolog.

Some better examples are the perhaps one I did the other day for parsing the input files for some of the days in AoC 22.See the *_dcg.pi file in https://github.com/hakank/hakank/tree/master/advent-of-code-2022. E.g. for day 5 (https://github.com/hakank/hakank/blob/master/advent-of-code-2022/5_dcg.pi)  amd day 7 (https://github.com/hakank/hakank/blob/master/advent-of-code-2022/7_dcg2.pi).

You can find more examples at http://www.hakank.org/picat/ , search for "DCG".

On Fri, Dec 16, 2022 at 12:47 AM Mark Engelberg <mark.en...@gmail.com> wrote:

I'm not familiar with this DCG syntax, so I'm unclear on how this parsing code works. Where I can read more about that?

[Neng-Fa Zhou]

The problem is caused by the ignorance of integer declarations by GLPK. The variable is declared integer. However, GLPK outputs the value 3068580.0. I don't think this is a bug of GLPK. I once experienced a similar problem with Gurobi. I reported it as a bug to Gurobi, and was told that it is acceptable for a MIP solver to return a float for a variable even if the variable is declared integer:-(.

For special cases where a float can be rounded equivalently to an integer, Picat should convert the float to integer. I have made this change. You'll be able to see this in the next release.

It's interesting that my version of Picat (an internal version) solves the problem much faster than the released version using sat.

$ time /cygdrive/c/Picat/emu/picat aoc15_sat.pi
12274327017867

CPU time 0.422 seconds.

There is still big room for optimizations in SAT encodings.

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 on the web visit https://groups.google.com/d/msgid/picat-lang/CAAfCYyz2sty3RpPdfCGgD2u0G0kNB1feVYgzuFFRJFkQPX4FDg%40mail.gmail.com.

[Mark Engelberg]

Day 19 works reasonably well with a simple model that is a fairly straightforward translation of the problem statement.

https://github.com/Engelberg/aoc22/tree/main/picat/day19

I feel like there's a better model that leverages the fact that one can compute the resources at a given time step directly from the previous bot-building decisions, without explicitly tracking the number of bots, but my attempts to build such a model didn't quite work and I was unsuccessful debugging that model.

I'm very curious to see if there's a Picat constraint model or one using the planner module that can solve Day 16, as I couldn't come up with one.

[Neng-Fa Zhou]

Yes, the Day-16 problem could be better solved using a planner.

https://adventofcode.com/2022/day/16

Do you have a draft program that we can start with?

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 on the web visit https://groups.google.com/d/msgid/picat-lang/49a6a38e-e050-4347-8ce1-743c985689f3n%40googlegroups.com.

[Claudio Cesar de Sa]

Mark

Congratulations for your performance/dedication in AoC, I stopped on Day 05.  My major difficulty: the input file and dealing with this raw data.
My plan was to read these files in another language such as V or Python, in the sequence generate a file with the data formatted in facts and rules,
to call this file  from Picat and solve it
here some of my codes

https://github.com/claudiosa/CCS/tree/master/v_programming_language/AoC_2022
but the inputs take some time to deal with.
For instance, Day05 is a cool and easy problem, but the input ... is weird/boring

Surely, the hard problems enrolling searches, DP, planning etc, will be solve more efficiently with Picat

Your initial question on Regular Expression, answered by Hakan, really is like "key-master" to solve all these problems of AoC.

As Neng-Fa mentioned... if you have read the input file ... with the Picat planner is nice to solve the problem of Day16

Have you ever solved the other days?


claudio

To view this discussion on the web visit https://groups.google.com/d/msgid/picat-lang/CAFOC6HSVg6D-d-pT0gParZG4-4dqKvXj1F%2BTteezAQ1a97%2B6cg%40mail.gmail.com.

--

claudio

**********************************************************************

Whatsapp: +55 47 992451825
Telegram: @ccs1664
https://claudiocesar.wordpress.com/about/

https://github.com/claudiosa  (start in CCS)

***********************************************************************

[Hakan Kjellerstrand]

Hi Claudio.

As mentioned to Mark earlier, I've used DCG for reading the input files for some of the solutions. It can take a while to get the DCG correct but I think it's worth it to know more about DCGs.

Here are some examples of this year's problems when using DCG was quite nice (or at least possible):

* Day 1: https://github.com/hakank/hakank/blob/master/advent-of-code-2022/1_dcg.pi

* Day 2: https://github.com/hakank/hakank/blob/master/advent-of-code-2022/2_dcg.pi

* Day 4: https://github.com/hakank/hakank/blob/master/advent-of-code-2022/4_dcg.pi

* Day 5: https://github.com/hakank/hakank/blob/master/advent-of-code-2022/5_dcg.pi

* Day 7: https://github.com/hakank/hakank/blob/master/advent-of-code-2022/7_dcg2.pi

* Day 11: https://github.com/hakank/hakank/blob/master/advent-of-code-2022/11.pi

In some cases, regexes are easier, for example for Day 1 and 4:

* Day 1: https://github.com/hakank/hakank/blob/master/advent-of-code-2022/1.pi

* Day 4: https://github.com/hakank/hakank/blob/master/advent-of-code-2022/4b.pi

but then one have to use my regex module (https://github.com/hakank/picat_regex) but this means that PCRE2 must be installed and Picat must be recompiled.

For Day 16 (which I haven't finished), here's a DCG to parse the input file:

"""
seq([])     --> [].
seq([E|Es]) --> [E], {E != ' ', E != '\n'}, seq(Es).

digits([C|Rest]) --> [C], {ascii_digit(C)}, digits(Rest).
digits([]) --> [].

seq_list([S|Ss]) --> seq(S), (", " ; " "), seq_list(Ss).
seq_list([S]) --> seq(S).
seq_list([]).

% Valve AA has flow rate=0; tunnels lead to valves DD, II, BB
% Valve HH has flow rate=22; tunnel leads to valve GG
parse_line([valve(Valve),flow_rate(Valve,FlowRate),lead_to(Valve,LeadTo)]) --> "Valve ", seq(Valve),
                                       " has flow rate=", digits(FlowRate1), {FlowRate1 != "", FlowRate = FlowRate1.to_int},
                                       "; ", ("tunnels lead to valves" ; "tunnel leads to valve"),
                                       " ", seq_list(LeadTo).

parse_lines([Line|Lines]) --> parse_line(Line), "\n", parse_lines(Lines).

parse_lines([Line]) --> parse_line(Line).
parse_lines([]) --> [].

"""

It's then used like this:

"""

go =>

  File = "16_test.txt",
  % File = "16.txt",
  Chars = read_file_chars(File),
  once(parse_lines(Lines,Chars,[])),

  % ...

"""

DCGs are quite powerful: In addition to parsing files, DCGs can also be used to generate all possible strings that are valid according to the DCG. For example, here's an example of using DCGs to generate all 48 misspelling of my last name (kjellerstrand):

"""

go =>
  % Check a string
  if kjellerstrand("kjellerstrand",[]) then
    println(correct)
  else
    println(not_correct)
  end,
  % Generate all strings
  All = findall(S,kjellerstrand(S,[])),
  println(All.len),
  nl.

kjellerstrand -->
        "k", ("je" ; "ä"), "ll", ("" ; "er" ; "ar"), ("st" ; "b"), ("" ; "r"), "a", (""; "n"), "d".

"""

The output is

"""

[kjellstad,kjellstand,kjellstrad,kjellstrand,kjellbad,kjellband,kjellbrad,kjellbrand,kjellerstad,kjellerstand,kjellerstrad,kjellerstrand,kjellerbad,kjellerband,kjellerbrad,kjellerbrand,kjellarstad,kjellarstand,kjellarstrad,kjellarstrand,kjellarbad,kjellarband,kjellarbrad,kjellarbrand,källstad,källstand,källstrad,källstrand,källbad,källband,källbrad,källbrand,källerstad,källerstand,källerstrad,källerstrand,källerbad,källerband,källerbrad,källerbrand,källarstad,källarstand,källarstrad,källarstrand,källarbad,källarband,källarbrad,källarbrand]
48

"""

Other examples of using DCGs can be seen at my Picat page (http://hakank.org/picat/ ,  search for "DCG"):. For example_

* Wordle solver: http://hakank.org/picat/wordle_dcg.pi

* Generate DCG from a list of words: http://hakank.org/picat/make_dcg.pi (cf my make_regex: http://hakank.org/picat/make_regex.pi)

* Generating possible accepted string from (simple) regexes: http://hakank.org/picat/regex_generating_strings_v3.pi

* Solving Regex Crossword (https://regexcrossword.com): http://hakank.org/picat/regex_crossword.pi

* Some DCG "utils"/general constructs: http://hakank.org/picat/dcg_utils.pi which is tested by http://hakank.org/picat/dcg_utilstest.pi

Hope this helps.

/Hakan

To view this discussion on the web visit https://groups.google.com/d/msgid/picat-lang/CAHQhj4pWmGiRA%2B-%3DWXnMDmWGm_1NVXPPBjAu-R7F7p5634Yd-g%40mail.gmail.com.

[Neng-Fa Zhou]

Hi Claudio,

Picat is not ASP, and you really don't want to use another scripting language to do I/O, especially in a competition. I have implemented many DSLs in Picat, and I believe that Picat is as good as Python for scripting, if not better.

Here is my solution to the Day-5 problem:

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

With the append, split, and pattern-matching, Picat is good for dealing with various data formats.

Cheers,

NF

To view this discussion on the web visit https://groups.google.com/d/msgid/picat-lang/CAHQhj4pWmGiRA%2B-%3DWXnMDmWGm_1NVXPPBjAu-R7F7p5634Yd-g%40mail.gmail.com.

[Mark Engelberg]

My plan initially was to code the problems first in Clojure (since I'm most comfortable with that, make sure I understand the problem well) and then try it in Picat. After the first several days, I decided to only do the "interesting" problems in Picat.

Day 16 seems like potentially a planner problem, but I couldn't figure out any sensible model that would work. As far as I can tell, everything in the planner module is oriented around finding lowest-cost paths, not finding the paths that maximize some value within a certain bounded use of resources. To further complicate matters, in the Advent of Code Day 16 problem, the value of visiting a location is dependent on how early you get there. I couldn't think of any way to represent that for the planner.

Today's problem (Day 21) also seems like a really good fit for Picat as it's essentially a very simple constraint solving problem. However, the numbers involved are quite large, and it doesn't appear that Picat can handle integers this large. When I try to run it in Picat, I get *** error(small_integer_expected(268435508),overflow_check).

On the couple problems where I was able to leverage Picat's capabilities, I was very impressed. My Clojure code required a lot of insight into the nature of the problem statement to figure out how to cleverly prune the search tree to run efficiently. Picat basically just worked on a straightforward translation of the problem statement.

[Hakan Kjellerstrand]

I did the Day 21 problem with Picat, see at https://github.com/hakank/hakank/blob/master/advent-of-code-2022/21b.pi .

One thing that might be troublesome is the divisions, so I converted them to multiplications instead (within the parsing DCG).

Actually, the CP solver is smart enough to solve both parts2 without solve/1 (though I've kept solve/1 in the program.)

Part 2 was a little messier to handle and in my first solution (21.pi) I hard coded the relevant variables, but in 21b.pi this was done in the program as well.

--
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 on the web visit https://groups.google.com/d/msgid/picat-lang/CAORbMONTdVGxVeedc7EvjXaEgMoSenW29TgOZSwFSHmW0%2BZ6uA%40mail.gmail.com.

[Hakan Kjellerstrand]

Oisín (DestyNova) wrote Picat versions for Day 21 as well, and especially part 1 is neat (it does not use a constraint solver): https://github.com/DestyNova/advent_of_code_2022/tree/main/21 

His Part 2 uses CP, however.

/Hakan

[Mark Engelberg]

I gather that Picat doesn't have "eval", so you're writing out a Picat file with all the constraints. I did something similar, here's the file that was produced:

https://github.com/Engelberg/aoc22/blob/main/picat/day21/v1.pi

I got rid of the divisions, but I'm still getting an error in all the various solvers. What am I doing wrong?

Thanks.

[Neng-Fa Zhou]

Here is my solution to the Day-16 problem. As the objective is to maximize a quantity, the planner module is useless for this problem. The solution uses tabling (a.k.a. dynamic programming) instead.

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

It produces an answer 1751 in 1s. I am curious about how the solution compares with ones in other languages in terms of conciseness and efficiency.

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 on the web visit https://groups.google.com/d/msgid/picat-lang/CAORbMONTdVGxVeedc7EvjXaEgMoSenW29TgOZSwFSHmW0%2BZ6uA%40mail.gmail.com.

[Hakan Kjellerstrand]

Mark, when I run v1.pi (using cp solver in Picat v3.3#3), I don't get any errors. What error do you get using cp solver?

Using SAT, I get free_var_not_allowed, which is probably because no decision variable has any domains.

[Mark Engelberg]

I see:

Compiling:: v1.pi
v1.pi compiled in 39 milliseconds
loading...
*** error(failed,main/0)

I'm also on Picat v3.3#3, on Windows.

I tried on the SAT solver adding a (really large) domain [since the numbers get quite large, it wasn't clear how to set a useful domain], and that seemed to hang the program.

[Hakan Kjellerstrand]

Mark, that is strange.

I don't have a Windows machine to test this on.

What happens if you comment out the line with solve/1 (using cp)?

When using very large domains, then the SAT solver might have to try a lot of values and that can take a while...

[Mark Engelberg]

Same error even when I comment out the solve line.

[Mark Engelberg]

Thank you so much for showing this solution to Day 16's problem. There's a lot I can learn from this example.

I had forgotten that tabling could be combined with min/max. I'm a little confused about the use of $rate and $edge. I thought that notation created a data structure, like a record, but did not actually create a "fact" in the database. But later, you access rate and edge like facts. Where can I find a good explanation of that, to clear up my misconceptions.

As you asked for a comparison, here's my Clojure code for Day 16:

https://github.com/Engelberg/aoc22/blob/main/clojure/aoc22/src/aoc22/day16/core.clj

On my machine, it solves part 1 in 70ms; part 2 in prints the solution right away but takes about 4s to prove optimality, and the code is comparably concise.

However:

1) I'm utilizing a couple of libraries I previously wrote, a parsing library and a graph data structure library with some graph search algorithms. The parsing library makes it so that I pretty much only need to specify a context-free grammar for the input file format, helping with the concision. I use the graph library to compute the shortest-path distances between every pair of caves and store that in a map. Without having that algorithm already at my disposal, the code would have been much longer.

2) A key part of my approach for part 1 is that before branching on a state, I do a heuristic that provides an upper-bound on how much flow could possibly be released within the time remaining from this state, and if that's not better than the best I've seen, I don't bother searching that state. My heuristic is that I sum together the benefit I would get from turning on all the valves reachable in the time remaining, computed independently of one another. So, for example if I can reach valve A in 2 minutes from my current location and turning it on would net a certain benefit (its flow * the remaining time after I reach it), and I can reach valve B in 4 minutes from my current location and gain a net benefit, I simply add together those independently computed values. Even though this is too high (in reality going for valve A will reduce the benefit of going for valve B and vice versa), it's a useful upper-bound estimate that can be computed quickly. Without that heuristic, my code is considerably slower. And surely the Picat version could be sped up by such a heuristic as well. 

So the Picat version impresses because it accomplishes so much with a fairly direct translation of the problem. You effectively got shortest-path "for free" with tabling, whereas I used a library algorithm. You got good performance just from the natural branch/bound behavior of the built-in backtracking and tabling, whereas I had to think about the problem structure to come up with an upper-bound heuristic.

[Neng-Fa Zhou]

I realized that the executable for Windows available on picat-lang.org is 32-bit, although it also runs on 64-bit Windows. You can use the function maxint_small() to check if your executable is for 32-bit or 64-bit.

Picat> maxint_small()=X
X = 268435455

So your program doesn't work because of overflow. You need to download the executable for 64-bit windows available on Domingo's GitHub at:

https://github.com/mingodad/picat/actions/runs/3211218427#artifacts

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 on the web visit https://groups.google.com/d/msgid/picat-lang/CAORbMOM1x8NnKPFgxfbAvLS4DD0kZ279gRqFcV2DLaHd2B%2BZiQ%40mail.gmail.com.

[Alfredo Beaumont]

Hi,

Here's my solution to Day 16 problem:
https://gist.github.com/abeaumont/06f0dcf8f3f43e7254b9855ff36c4d25
It also uses tabling, so it may be similar to Neng-Fa's solution, I
haven't looked into it yet.
It's a direct translation of the problem into DP without heuristics
and thus it requires a lot of resources, especially for part 2 (I made
some state model optimizations there, still no heuristics). I haven't
been able to run part 2 locally with the problem input, I estimate
it'd require something like half an hour and 120GB to run. I'd be
happy to learn any further optimizations in the state model that could
make tabling more resource efficient.

Cheers,
Alfredo.

Hau idatzi du Neng-Fa Zhou (neng...@gmail.com) erabiltzaileak (2022
abe. 22, og. (04:44)):

> To view this discussion on the web visit https://groups.google.com/d/msgid/picat-lang/CAFOC6HSRYk8g-%2BcD9sOrH9_9FN8LERMWD3ZaZ2Yr0x-9wQVwog%40mail.gmail.com.

[Peter Bernschneider]

Here is my Picat cp solution of day 21/ part 2: https://github.com/bernschneider/adventofcode2022/blob/main/advent202221_2.pi

Using constraint programming coding was straight forward, the program is short and also very fast!

Cheers, Peter

[Peter Bernschneider]

Marc, 

You must remove the HUMN #= .. line, but define HUMN as a variable. You also must replace the ROOT #= ... line with an equality constrain as requested in the problem description: In the given example the new line is PPPW #= SJMN (see my code at https://github.com/bernschneider/adventofcode2022/blob/main/advent202221_2e.pi). 

The code for your instance of the problem could be https://github.com/bernschneider/adventofcode2022/blob/main/advent202221_2p.pi.

Cheers, Peter