Prompt Engineering and LeetCode

With AI it becomes super interesting to try to "guide" it to solve a coding (LeetCode) problem. An example would be this one here: The Knight’s Tour - LeetCode

2664. The Knight’s Tour

Medium

Given two positive integers m and n which are the height and width of a 0-indexed 2D-array board, a pair of positive integers (r, c) which is the starting position of the knight on the board.

Your task is to find an order of movements for the knight, in a manner that every cell of the board gets visited exactly once (the starting cell is considered visited and you shouldn't visit it again).

Return the array board in which the cells' values show the order of visiting the cell starting from 0 (the initial place of the knight).

Note that a knight can move from cell (r1, c1) to cell (r2, c2) if 0 <= r2 <= m - 1 and 0 <= c2 <= n - 1 and min(abs(r1 - r2), abs(c1 - c2)) = 1 and max(abs(r1 - r2), abs(c1 - c2)) = 2.

 

 

Example 1:

Input: m = 1, n = 1, r = 0, c = 0
Output: [[0]]
Explanation: There is only 1 cell and the knight is initially on it so there is only a 0 inside the 1x1 grid.

Example 2:

Input: m = 3, n = 4, r = 0, c = 0
Output: [[0,3,6,9],[11,8,1,4],[2,5,10,7]]
Explanation: By the following order of movements we can visit the entire board.
(0,0)->(1,2)->(2,0)->(0,1)->(1,3)->(2,1)->(0,2)->(2,3)->(1,1)->(0,3)->(2,2)->(1,0)

 

Constraints:

• 1 <= m, n <= 5
• 0 <= r <= m - 1
• 0 <= c <= n - 1
• The inputs will be generated such that there exists at least one possible order of movements with the given condition

The solution is a backtracking DFS, and my implementation is down below:

public int[][] TourOfKnight(int m, int n, int r, int c)
{
    int[][] retVal = new int[m][];
    for (int ri = 0; ri < m; ri++)
    {
        retVal[ri] = new int[n];
        for (int ci = 0; ci < n; ci++) retVal[ri][ci] = -1;
    } 

    retVal[r][c] = 0;
    KnightDFS(retVal, 1, r, c);
    return retVal;
}

private bool KnightDFS(int[][] retVal,
                        int countSteps,
                        int r,
                        int c)
{
    if (countSteps >= retVal.Length * retVal[0].Length) return true;

    int[] rowDelta = { 2, 2, -2, -2, 1, 1, -1, -1 };
    int[] colDelta = { 1, -1, 1, -1, 2, -2, 2, -2 };

    for (int i = 0; i < rowDelta.Length; i++)
    {
        int nextR = r + rowDelta[i];
        int nextC = c + colDelta[i];

        if (nextR >= 0 &&
            nextR < retVal.Length &&
            nextC >= 0 &&
            nextC < retVal[nextR].Length &&
            retVal[nextR][nextC] == -1)
        {
            retVal[nextR][nextC] = countSteps;
            if (KnightDFS(retVal, countSteps + 1, nextR, nextC)) return true;
            retVal[nextR][nextC] = -1;
        }
    }

    return false;
}

Using Bing AI, which is powered by GPT4, we can use prompt engineering to guide it to solving the problem, but it does require some steps. It took me 3 iterations to guide it to find the right solution. Here are the different prompts that I used:

1/ Solve this problem https://leetcode.com/problems/the-knights-tour/ in C# and explain to me step by step

It didn't really work. The AI simply looked at the "Forum" for that question, copied and pasted one solution that did not even compile. So I used tags in my prompt to better guide it:

2/ Please write me a solution by replacing the "#DATA#" tag in the following code: public class Solution { public int[][] TourOfKnight(int m, int n, int r, int c) { #DATA# } }

It was better. At least it did compile and run, but still it was not working for one case. I explicitly told the AI which case wasn't working, what the AI was returning as the answer, and what the expected answer was:

3/The solution didn't work for the input 3 4 0 0. The output should have been [[0,3,6,9],[11,8,1,4],[2,5,10,7]]. The actual output was [[0,-1,-1,-1],[-1,-1,-1,-1],[-1,-1,-1,-1]]. Please try again.

It finally did the trick (see below). The bot apologized and gave me a correct answer the compiled, ran and passed, even performing better than mine (mine down below is the blue circle whereas the Bing AI is the red circle). 

Do you think that Large Language Models and Generative AI will change how we carry out interviews? It certainly will. There are several school of thoughts going on right now:

A/ No change, and we just require the candidates to not use AI

B/ Partially embrace it, still requiring the candidates to write their own solutions, but potential to use AI as for consulting things like language/syntax (supporting role)

C/ Fully embrace it, where questions are expected to be solved as a combination of own expertise in addition to strong prompt engineering skills

To be determined! Cheers, ACC.