Author: scott-sic

A few months ago I wrote about my simple test to see how both Bard and ChatGPT 3.5 did with a simple programmer interview question (summary: neither one passed) and since Bard has had its innards recently replaced (with Google Gemini LLM) which is supposedly an improvement over its original PaLM LLM AI, I thought I’d rerun the test for Bard to see if it did any better.

The prompt I submitted back in September was:

create java 8 code/class that provides a macro replacement capability. specifically a string can contain zero or more macro references where a reference is something like “$name” (the $ char introduces the alphanumeric macro name), and the processing of the string requires a map and each $name is replaced with the corresponding value in the map. one special case is that if the $ char is encountered within a single-quote string, then it’s not taken as a macro

and so I submitted it exactly as above to the improved Bard. This is what is produced (though I did add the import java.util.* and the main() method):

import java.util.*;

public class MacroReplacer {

    private final Map<String, String> macros;

    public MacroReplacer(Map<String, String> macros) {
        this.macros = macros;
    }

    public String replaceMacros(String text) {
        StringBuilder builder = new StringBuilder();
        int pointer = 0;
        while (pointer < text.length()) {
            int dollarIndex = text.indexOf('$', pointer);
            if (dollarIndex == -1) {
                builder.append(text.substring(pointer));
                break;
            }

            // Check if dollar is inside a single-quote string
            int prevQuoteIndex = -1;
            int quoteIndex = text.indexOf('\'', pointer);
            while (quoteIndex != -1 && quoteIndex < dollarIndex) {
                prevQuoteIndex = quoteIndex;
                quoteIndex = text.indexOf('\'', quoteIndex + 1);
            }
            if (prevQuoteIndex != -1 && prevQuoteIndex % 2 == 1) {
                // Dollar inside single-quote string, append as-is
                builder.append(text.substring(pointer, dollarIndex + 1));
                pointer = dollarIndex + 1;
                continue;
            }

            // Extract macro name
            int nextSpaceIndex = text.indexOf(' ', dollarIndex + 1);
            int macroNameLength = nextSpaceIndex != -1 ? nextSpaceIndex - dollarIndex - 1 : text.length() - dollarIndex - 1;
            String macroName = text.substring(dollarIndex + 1, dollarIndex + 1 + macroNameLength);

            // Replace macro with value from map
            String macroValue = macros.get(macroName);
            if (macroValue != null) {
                builder.append(macroValue);
            } else {
                builder.append('$');
                builder.append(macroName);
            }

            pointer = dollarIndex + 1 + macroNameLength;
        }
        return builder.toString();
    }

    /**
     * had to add (copied from ChatGPT's code)
     */
    public static void main(String... args)
    {
        Map<String, String> macroMap = Map.of(
                "name", "John",
                "age", "30"
        );
        MacroReplacer bard = new MacroReplacer(macroMap);

        String input = "Hello $name! You are $age years old. Do not replace '   $age' in single quotes.";
        String output = bard.replaceMacros(input);

        System.out.println(output);
    }
}

and when I ran it I got

$name!30$age' in single quotes.

which, sadly, is much worse than original Bard.

Maybe GPT4 is better (I don’t want to pay to test that) but, then again, maybe I’m justified in still not worrying about them taking my job.

Late last year (2022) it seemed like the programming world freaked out about the capability of ChatGPT and, a bit later, Google’s Bard–it seemed like there were messages of doom everywhere about how programmers would be out of a job soon. There were many headlines about how people could create apps in just a few minutes.

After a while the hype settled down and the reality of what those two LLMs could be with respect to programming became more understood–it seemed that maybe after all, people like me wouldn’t be (yet) replaced by AI.

Testing them out

When I give interviews to candidate engineers, I have a standard set of questions/tasks that I ask them, somewhat to be able to normalize across engineers and somewhat because the questions I’ve asked seem to do a reasonable job of identifying what I view as strengths and weaknesses.

One of the questions I routinely ask candidates is a coding task that asks them to write Java code that does macro replacement. (For those readers who don’t know what this means, think of form emails/letters that start with something like “Dear Scott”, where the “Scott” part is taken from some database of people–behind this is something that has some template like “Dear firstname” — that replacement of firstname with “Scott” is basically a macro replacement).

I happened to interview a candidate recently for one of my contracts and was intrigued by the approach the candidate took to this task–he focused on optimization and ended up using what’s called a stack to try to make it as fast as possible (I don’t know that his approach would have been all that optimized…). That got me to thinking about whether or not my own answer to that interview question was faster (more optimized) than the usual approach that I’ve seen interview candidates respond with. (Yes, prior to asking candidates this question, I created a solution–in fact it was the solution that prompted me to include the problem as an interview question.)

For whatever reason I decided to test out ChatGPT and Bard to see how they both would do with solving this pretty trivial programming problem, mostly to compare the efficiency of my approach (which is to use a Finite State Machine–see https://en.wikipedia.org/wiki/Finite-state_machine).

The Prompt

I know there’s somewhat of an art to submitting the optimal “prompt” to these LLM AIs, but I’m not the sort to try to figure out how to make a supposedly smart AI be really smart, so I submitted the following prompt to both ChatGPT (3.5–the public version) and Bard (still public, but continually updated based on the alerts I see when I use it):

create java 8 code/class that provides a macro replacement capability. specifically a string can contain zero or more macro references where a reference is something like “$name” (the $ char introduces the alphanumeric macro name), and the processing of the string requires a map and each $name is replaced with the corresponding value in the map. one special case is that if the $ char is encountered within a single-quote string, then it’s not taken as a macro

From each of them I got Java code that compiled successfully. I didn’t trust the code at all to work so I started reviewing each result and realized that each one had bugs. For those of you who are programmers you might want to review the following code to see if you can spot the errors

ChatGPT code

This is what ChatGPT came back with given the above prompt

import java.util.Map;
import java.util.regex.Matcher;
import java.util.regex.Pattern;

public class Chatgpt {
    public static String process(String input, Map<String, String> macroMap) {
        String pattern = "\\$(\\w+)";
        Pattern r = Pattern.compile(pattern);

        StringBuilder result = new StringBuilder();
        boolean inSingleQuotes = false;

        for (int i = 0; i < input.length(); i++) {
            char c = input.charAt(i);

            if (c == '\'') {
                inSingleQuotes = !inSingleQuotes;
                result.append(c);
            } else if (!inSingleQuotes && c == '$') {
                Matcher matcher = r.matcher(input.substring(i));

                if (matcher.find()) {
                    String macroName = matcher.group(1);
                    String macroValue = macroMap.getOrDefault(macroName, "");
                    result.append(macroValue);
                    i += matcher.group(1).length() - 1;
                } else {
                    result.append(c);
                }
            } else {
                result.append(c);
            }
        }

        return result.toString();
    }

    public static void main(String[] args) {
        Map<String, String> macroMap = Map.of(
                "name", "John",
                "age", "30"
        );

        String input = "Hello $name! You are $age years old. Don't replace '  $age' in single quotes.";
        String output = process(input, macroMap);

        System.out.println(output);
    }
}

(Note: I modified the test input string based on what I believed would be a problem after reviewing both ChatGPT- and Bard-generated code; the specific modification I did was to add white space in between the ‘ and the $ characters).

And this is what running it produces:

Hello Johne! You are 30e years old. Don't replace '  30e' in single quotes.

which is clearly not what is intended as the last character of the macros (name and age) are incorrectly being included.

Bard code

This is what Google’s Bard came back with (with an edit of mine to include the main method with a string that I believed would cause it to fail):

import java.util.*;

public class Bard {

    private final Map<String, String> macros;

    public Bard(Map<String, String> macros) {
        this.macros = macros;
    }

    public String replaceMacros(String str) {
        StringBuilder sb = new StringBuilder();
        int i = 0;
        while (i < str.length()) {
            char c = str.charAt(i);
            if (c == '$') {
                // Check if the '$' character is within a single-quote string.
                if (i > 0 && str.charAt(i - 1) == '\'') {
                    sb.append(c);
                    i++;
                } else {
                    // Find the end of the macro name.
                    int end = i + 1;
                    while (end < str.length() && Character.isAlphabetic(str.charAt(end))) {
                        end++;
                    }
                    String macroName = str.substring(i + 1, end);
                    // Replace the macro name with the corresponding value in the map.
                    String macroValue = macros.get(macroName);
                    if (macroValue != null) {
                        sb.append(macroValue);
                    } else {
                        sb.append("$");
                        sb.append(macroName);
                    }
                    i = end;
                }
            } else {
                sb.append(c);
                i++;
            }
        }
        return sb.toString();
    }

    /**
     * had to add (copied from ChatGPT's code)
     */
    public static void main(String... args)
    {
        Map<String, String> macroMap = Map.of(
                "name", "John",
                "age", "30"
        );
        Bard bard = new Bard(macroMap);

        String input = "Hello $name! You are $age years old. Do not replace '   $age' in single quotes.";
        String output = bard.replaceMacros(input);

        System.out.println(output);
    }
}

and when it’s run it produces

Hello John! You are 30 years old. Do not replace '   30' in single quotes.

and that’s clearly wrong as it still replaces the macro even though it’s “protected” by single quotes.

Summary

I don’t want to draw this out by trying to figure out either why they both failed or how to make them produce correct code. I just want to show that a they both fail–miserably in my mind–to create correctly functioning code given a coding prompt. And I say “miserably” because the bugs that each solution has isn’t immediately obvious and shows up only with actual testing

My personal message on all this is if anyone thinks that the current versions of ChatGPT and Bard can do anything but produce some code that has to be reviewed, tested, and very likely modified, then they need to actually try out these LLMs. They just aren’t going to come close to replacing non-trivial programming at this time (and, my personal opinion is, after being in the industry for almost 45 years) is that it will be a very long time before we programmers have to worry about our jobs.

This is companion piece to “how to solve a maze”.

I’ve spent far too much time playing with mazes, both when I was young, and now later in life. I’ve wondered if this would fall under a “special interest” and I think there’s some argument that it could.

While I was playing with code for solving a maze, I had to have some maze for it to solve. Initially I just had the code take out walls at random, knowing that while this wasn’t the best approach by any means, it was probably good enough to test the solver code (assuming enough walls were taken out). I also resorted to hardcoding a set of walls to remove on a small maze.

But that wasn’t good enough, and I wanted to create good and fun mazes, though those attributes are hard to define.

Now, if a maze has a single path from start to finish, then a deterministic algorithm as described in the other post will find it. Unfortunately the creation of a good and fun maze isn’t so deterministic as the generation of it must incorporate some amount of randomness that ends up presenting a good number of long-ish wrong paths. Additionally maze creation has a few constraints that make it a bit less straightforward: all cells should be reachable from the start, and there should (ideally) be exactly one path through it.

False starts

Sometimes I rush into coding without thinking enough. I think this happens when I think the problem is easier than it really is, and because I’ve coding long enough that I think I don’t need to stop and think. In any case, that’s what I did at first–I didn’t think enough and ended up going down some blind alleys, which is totally apropos solving mazes.

My first attempt was to use recursion to create a path (I guess recursion was on my brain). My code notes describe the idea:

    /**
     * The real maze maker recursive algorithm.  Not sure if it will work
     * but the idea is that each invocation of this method the current
     * position is a newly entered square and we have to randomly decide
     * which direction to go (if we move at all), subject to the following
     * conditions:
     *
     *  * each cell must have at least 1 wall
     *  * we can't open up a wall to an adjacent cell that's already been visited
     *
     * We will rotate through the 4 directions and each time we have
     * a low probability of opening up a wall in that direction.  Once
     * we open up a wall, we recurse into this method.
     */

It kept track of the “ends” of the path and if the processing of the current “end” didn’t end up reaching the finish of the maze, it reprocessed it. I graded it as a failure because it left some cells isolated and it produced more than one path through the maze (at least that specific implementation did that–it might have been able to be modified to avoid one or both of those conditions, but I didn’t pursue that).

When it was clear that that approach didn’t work, I changed the code to choose cells at random, checking if they had at least one wall missing (meaning they were connected to the start cell through some path) and then opening up one of the remaining walls at random. The code would then, using my solver, check if there was a path from start to finish, and if there was, then the first phase of the construction was done. The second phase consisted of finding all the isolated cells (those that had 4 walls still), and opening up one of those walls at random, repeating until there were no isolated cells left.

Unfortunately that didn’t work all that well either for similar reasons.

A solution?

I don’t have enough notes in code left to reconstruct the different attempts between the recursive non-solution and the queue-based one that actually does a pretty good job so I’m just going to skip to describing this workable solution.

One of the issues noted above is how the recursive algorithm(s) left some cells isolated and one of the reasons for this happening is that there’s nothing that keeps track of what to try next other than the details in the stack of recursive calls and that information is lost bit by bit when a recursive call returns.

The way around this is to explicitly keep track of the cells that are still open to being extended, where this means specifically that it’s possible to open up another wall in the cell, where opening up a wall is allowed only if there’s a cell on the other side of the wall (i.e., not off the edge of the maze) and that cell has all four walls in place. This idea of keeping a cell “in play” if it’s possible to open up another wall is key to creating a maze that doesn’t leave any isolated cells.

Now, it’s possible to keep track of these in-play cells by examining each and every cell each time it’s time to try to open up another cell/wall, but there are some downsides to this:

1. it’s expensive in time to do this as cells will be needlessly evaluated multiple times once it’s not possible to open up any more of its walls
2. there’s no way to try to create a long path by continuing to try to extend from the just-opened cell. The control of this turns out to be an important parameter of how the final maze looks.

All queued up

The idea of the queue-based solution is to retain in the queue only those cells that might be able to have another wall opened up. We first push the start cell onto the queue, as it’s by definition it has all four walls intact, then we go into a loop that does the following:

1. terminate if the queue is empty
2. pop the first cell from the queue
3. check if the cell can have another wall opened up
4. if the cell can have one or more walls opened, then randomly choose one of the possibilities and open it up, putting the just-attached cell onto the queue, and put the original cell back onto the queue
5. if the cell doesn’t have any walls that can be opened, just drop the cell by not putting it back onto the queue.

That will produce a maze with a path from start to finish. And, interestingly, it doesn’t have to check if it’s solvable as it will always be solvable.

The details of step 4 determine if the maze is interesting or not, so it’s important to look at the possibilities in step 4. Given that there are two new items to push onto the queue (the just-examined cell–call this “current”–and the just-opened cell–call this “target”) and two ends to push them onto (which is possible using Java’s Queue class), the following enumerates the raw combinations:

1. “current” at the head of the queue, and “target” at head+1
2. “current” at the head of the queue, and “target” at the tail
3. “current” at the tail, and “target” at tail-1
4. “current” at the tail, and “target” at head
5. “target” at the head, and “current” at head+1
6. “target” at the head, and “current” at tail
7. “target” at the tail, and “current” at tail-1
8. “target” at the tail, and “current” at head

There are duplicates: (4) and (6), and (2) and (8), so there are six unique ways of pushing these two cells in step 3 (this ignores the strategy of inserting both at random positions in the queue).

Since the algorithm pulls the next cell to try to extend from the head of the queue, the maze created depends on what gets pushed onto the head (if anything). If we re-push to the head the cell just taken off, then the algorithm basically expands out the cell as much as possible before moving to the next one, which has a different effect than if the just-opened cells are expanded before reprocessing.

Interesting mazes

My code allows me to choose the extension strategy so I can evaluate the effects of them on the final maze. Given that each generated maze is different (due to the use of randomness) it’s not always easy to tell what’s good or not, but in general there are some patterns: (2) and (3) produce mazes that have fairly direct and straight paths from start to finish; (7) and (8) produce slightly more visually complicated mazes than (2) and (3) but whose solutions are equally simple; (1) produces mazes with long paths from start to finish that wind up and down, which look like they’d be hard to solve but really aren’t as there aren’t many deep branches along the way; (4) looks like it produces complicated mazes (more on this below); (5) is similar to (1); and (6) is similar to (1).

Here are a few simple character-based renderings of some of the various strategies (10×10 maze):

_________________________________________
|   |   |   |   |   |   |   |   |   |   |
| →   →   →   →   →   →   ↓     | →   F |
|_ _|___|___|_ _|_ _|_ _|_ _|___|_ _|___|
__ ___________ ___ ___ ___ _______ ______
|   |   |   |   |   |   |   |   |   |   |
| ↑ |   |   |   |   |   | ↓     | ↑ |   |
|_ _|_ _|_ _|___|___|___|_ _|___|_ _|_ _|
__ ___ ___ _______________ _______ ___ __
|   |   |   |   |   |   |   |   |   |   |
| ↑   ←   ← |   |     ↓   ←     | ↑   ← |
|_ _|___|_ _|_ _|___|_ _|_ _|___|___|_ _|
__ _______ ___ _______ ___ ___________ __
|   |   |   |   |   |   |   |   |   |   |
|   |     ↑   ←     | ↓ |   |       | ↑ |
|_ _|___|___|_ _|___|_ _|___|___|_ _|_ _|
__ ___________ _______ ___________ ___ __
|   |   |   |   |   |   |   |   |   |   |
|       |   | ↑     | ↓     |     →   ↑ |
|_ _|___|_ _|_ _|___|_ _|___|___|_ _|___|
__ _______ ___ _______ ___________ ______
|   |   |   |   |   |   |   |   |   |   |
|   |     →   ↑     | →   ↓     | ↑     |
|_ _|___|_ _|___|___|___|_ _|___|_ _|___|
__ _______ _______________ _______ ______
|   |   |   |   |   |   |   |   |   |   |
|   |     ↑ |   |   |   | →   →   ↑     |
|_ _|___|_ _|_ _|_ _|_ _|___|_ _|_ _|___|
__ _______ ___ ___ ___ _______ ___ ______
|   |   |   |   |   |   |   |   |   |   |
|   |     ↑   ←   ←   ← |   |   |       |
|_ _|___|_ _|_ _|___|_ _|_ _|___|_ _|_ _|
__ _______ ___ _______ ___ _______ ___ __
|   |   |   |   |   |   |   |   |   |   |
|       |   |   |     ↑   ←     |   |   |
|_ _|___|___|___|___|___|_ _|___|___|_ _|
__ _______________________ ___________ __
|   |   |   |   |   |   |   |   |   |   |
|                   |     S     |       |
|___|___|___|___|___|___|___|___|___|___|

and another

_________________________________________
|   |   |   |   |   |   |   |   |   |   |
| F         | ↓   ← |       |           |
|_ _|___|___|_ _|_ _|___|_ _|_ _|___|_ _|
__ ___________ ___ _______ ___ _______ __
|   |   |   |   |   |   |   |   |   |   |
| ↑   ←   ←   ← | ↑   ← |   |   |       |
|___|___|___|___|___|_ _|_ _|_ _|___|___|
______________________ ___ ___ __________
|   |   |   |   |   |   |   |   |   |   |
|                   | ↑ |   |       |   |
|_ _|___|___|___|_ _|_ _|_ _|___|_ _|_ _|
__ _______________ ___ ___ _______ ___ __
|   |   |   |   |   |   |   |   |   |   |
|   | →   →   ↓ |   | ↑   ← |       |   |
|_ _|_ _|___|_ _|___|___|_ _|_ _|___|_ _|
__ ___ _______ ___________ ___ _______ __
|   |   |   |   |   |   |   |   |   |   |
|   | ↑ |   | ↓ | →   ↓ | ↑ |   |       |
|_ _|_ _|_ _|_ _|_ _|_ _|_ _|_ _|_ _|___|
__ ___ ___ ___ ___ ___ ___ ___ ___ ______
|   |   |   |   |   |   |   |   |   |   |
|   | ↑ |   | →   ↑ | →   ↑ |   |       |
|_ _|_ _|_ _|___|___|_ _|___|_ _|___|_ _|
__ ___ ___ ___________ _______ _______ __
|   |   |   |   |   |   |   |   |   |   |
|   | ↑ |           |       |   |   |   |
|_ _|_ _|___|___|_ _|___|_ _|_ _|_ _|_ _|
__ ___ ___________ _______ ___ ___ ___ __
|   |   |   |   |   |   |   |   |   |   |
|     ↑   ←   ← |       |   |           |
|___|___|___|_ _|___|_ _|_ _|___|___|_ _|
______________ _______ ___ ___________ __
|   |   |   |   |   |   |   |   |   |   |
|       | →   ↑ |   |   |   |       |   |
|_ _|___|_ _|___|_ _|_ _|___|_ _|_ _|_ _|
__ _______ _______ ___ _______ ___ ___ __
|   |   |   |   |   |   |   |   |   |   |
|         ↑   ←   ←   ←   S     |       |
|___|___|___|___|___|___|___|___|___|___|

While both of the above mazes have a solution that looks interesting, only the second one is what I’d call a maze that’s not trivial to solve, as the first one doesn’t have many “deep” branches. The second one used strategy (4) while the first one used strategy (1).

This is where more (objective) analysis of the strategies is useful but I haven’t done much on that. I can say that there appears to be a balance between the branching factor (basically a normalized number of branches for each cell along the solution path), branch depth (the maximum path length of each incorrect branch), and branch volume (how many cells each incorrect branch occupies in total). I can only say that after eyeballing a number of mazes created by each strategy that strategy (4) creates satisfying mazes–ones that provide ample opportunities to take a wrong turn.