ChatGPT: There will be math

This is not a post about financial industry compliance. It is about math, and programming, and, yes, ChatGPT. It that's not for you, turn around now and click on something more exciting. Dogs swimming maybe? I will join you in a minute.

For those handful of you who remain (you know who you are), I saw this problem on the YouTube channel Numberphile: https://www.janestreet.com/bug-byte/. You are given a graph with nodes, edges, and some rules to follow. I tried for a minute by hand and gave up. Then I spent two days coding the solution.

This is a classic constraint optimization programming problem. There's a lot of constraint solvers and systems, including some Python libraries and the standalone MiniZinc, and um, others, and I'm willing to bet you haven't even heard of MiniZinc. But because I enjoy choosing the sharpest tool that I don't know how to use, and sticking it in my eye, I opted for the programming language Picat. Picat (picat-lang.org)

Picat is in the Prolog family of logic programming languages, but also has functional elements ala Lisp/Haskell, and, mercifully, loops, function return value assignment, and print statements. This means you can choose to work with recursion or with symbolic logic unification, or just write some for loops and print statements. And if you've ever tried debugging Haskell, you know what I mean by just wishing you could print the damn thing without having to reason about type theory.

Picat also has built in constraint programming solvers. Thus, a natural fit--you see what I did there--for this problem. However, Picat's syntax is challenging and there isn't a lot of documentation or help online. "Do I need a comma after this line or will the compiler throw-up?" Anyone's guess, and several hours spent on figuring out how to put commas in an if-then-else.

Let's ask ChatGPT! And yes, it helped. But it also made up a new_graph() function. Would've been great if it existed. Same with the "standard astar algorithm". It confused Picat syntax with Haskell, which is far more commonly used--and that's saying something! It also tried to smuggle in some Python.

In the end, ChatGPT helped me over the first hump by coming up with a workable core approach. But once it got me going, it became like a parent running behind a child learning to ride a bike and refusing to let go of the seat. It made me fall down a lot.

Why? Because LLMs are good where there's a lot of good data and weak where there isn't. It's just that simple. ChatGPT went in the drawers of Stack Overflow and Reddit and vacuumed up all the answers. Picat was not even lint at the bottom. For example, ChatGPT got close, but not exactly, the syntax for writing to a file. Then again, it's amazing that it even knew what Picat was and could produce anything useful.

In my coding process, I found it effective to extract intermediary results and feed them into Python for analysis. ChatGPT was great for doing that and had no problem helping me produce abstract symbol trees from strings parsed with regular expressions--something I had no idea you could do so easily.

Then I could go back to Picat and try to figure out how to do the same thing with constraints, unification and recursion. The final version runs pretty much instantaneously on a 6-year-old mid-range laptop.

Oh, and I was serious about there being a few of you who would care: Linda Lesniak Hakan Kjellerstrand Don Zirilli Tom Schroeder Anthony Doan Conor Hoekstra . This is for you. Anyone else still here, good for you!

If you want to solve the puzzle yourself, please go ahead now. Spoilers follow.

import cp.

main =>
    % Define the graph with nodes and edges
    Nodes = ['A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'J', 'K', 'L', 'M', 'N', 'O', 'P', 'Q', 'S'],
    Edges = [('A', 'B'), ('A', 'D'),
             ('B', 'S'),
             ('C', 'H'),
             ('D', 'S'), ('D', 'H'),
             ('S', 'I'),
             ('F', 'I'),
             ('G', 'J'),
             ('H', 'J'), ('H', 'K'),
             ('I', 'J'), ('I', 'L'),
             ('J', 'K'), ('J', 'L'),
             ('K', 'M'), ('K', 'P'), ('K', 'N'),
             ('L', 'O'),
             ('M', 'N'), ('M', 'O'),
             ('N', 'E'),
             ('O', 'E'),
             ('Q', 'L')],

    % Edges are tuples of nodes and weights in range 1..24
    EdgeVars = [(Edge, V) : Edge in Edges, V :: 1..24],
    
    % Unique edge weights
    % Reduce search space to 24! = 6,204,484,903,168,028,160
    all_distinct([V : (_, V) in EdgeVars]),

    % Constraint to enforce known edge weights 
    % Reduce search space to 19! = 121,645,100,408,832,000
    KnownWeights = [(('D','S'), 12),
                    (('J', 'K'), 24),
                    (('K', 'N'), 7),
                    (('I', 'L'), 20)],
    foreach((Edge, Weight) in KnownWeights),
        member((Edge, Weight), EdgeVars)
    end,
    
    % Constraint to enforce known sum of weights for nodes
    % Reduce search space to 48
    KnownSums = [('A', 17), 
                 ('B', 3),
                 ('H', 54),
                 ('I', 49),
                 ('J', 60),
                 ('K', 79),
                 ('L', 75),
                 ('M', 29),
                 ('N', 39),
                 ('O', 25)],
    foreach((Node, Sum) in KnownSums),
        NodeEdges = [(N1, N2) : (N1, N2) in Edges, (N1 = Node ; N2 = Node)],
        NodeVars = [V : (Edge, V) in EdgeVars, Edge in NodeEdges],
        sum(NodeVars) #= Sum
    end,

    % Constraint that sum of weight on an edge = KnownPathSum OR 
    % sum of weight plus min edge on neighbor is <= to KnownPathSums
    % only need C, G, and F to reduce search space to 2
    KnownPathSums = [
                    ('C', 31),
                    %  ('D', 19), 
                    %  ('D', 23),
                     ('G', 6), 
                    %  ('G', 9), 
                    %  ('G', 16),
                     ('F', 8)],
    foreach((Node, Sum) in KnownPathSums),
        NodeEdges = [(N1, N2) : (N1, N2) in Edges, N1 = Node],
        NodeVars = [V : (Edge, V) in EdgeVars, Edge in NodeEdges],
        Neighbors = [N2 : (N1, N2) in Edges, N1 = Node],
        NodeOneHopEdges = [(N1, N2) : (N1, N2) in Edges, N1 in Neighbors],
        NodeOneHopVars = [V : (Edge, V) in EdgeVars, Edge in NodeOneHopEdges],
        (sum(NodeVars) #= Sum) #^ (sum(NodeVars) + min(NodeOneHopVars) #=< Sum)
    end,

    Solutions = solve_all([ffc], EdgeVars),
    printf("Number of solutions: %d\n", length(Solutions)),
    foreach(Solution in Solutions)
        AllEdges = Solution ++ [((Y,X), Weight) : ((X,Y), Weight) in Solution],
        sp(AllEdges, 'S', 'E', Path, _),
        Message = [chr(W+64) : ((X,Y), W) in Path],
        println('====================='),
        println(Path),
        println("Message is: "++Message),
    end,
    save_solution(Solutions),
    println("Done!").

% shortest path adapted from Picat Manual
table (+,+,+,-,min)
sp(Graph,X,Y,Path,WL) ?=>
    Path = [((X,Y),Wxy)],
    WL = Wxy,
    member(((X,Y), Wxy), Graph).

sp(Graph,X,Y,Path,WL) =>
    Path = [((X,Z), Wxz)|Path1],
    member(((X,Z), Wxz), Graph),
    sp(Graph,Z,Y,Path1,WL1),
    WL1 = Wzy,
    WL = Wxz+Wzy.

% Save to file for use with Python
save_solution(Solutions) =>
    Out = open("solutions.txt", write),
    foreach(Solution in Solutions)
        println(Out, Solution)
    end,
    close(Out).