Back to Basics Series I: The Origin

Prelude

If you have read some of my posts, you have realized that I love AI, but am also aware of the power it steals from us. I used to feel joy in programming, but since the arrival of "vibe coding", this seems not to be anymore true.

Furthermore, I have come to realize that I need to keep my programming skills sharp, so I am starting this series to teach myself the basics again. I have had some technical interviews and I want to improve my programming skills to be better prepared for them and to provide my clients with better support and better results.

The origin of this series

Let's imagine for one moment that you are asked during a job interview to solve a very simple problem:

Provide a function (in Python) that will take a string as argument and will return True or False.

Sounds very straightforward, right?

With this you don't know yet what the function should do, but you know what the input and output should be.

The input string would contain potentially some brackets, and the function should return True if the brackets are balanced, and False otherwise. The "allowed" brackets are (), [], and {}, and the function should ignore any other characters (although this wasn't stated but I will add it here for clarity and to provide some additional food for thought).

Finally, some "test cases" were provided and the expected outcomes for each. In this way, I could check that the function was working as expected. I will provide here some, although these were not the cases provided during the interview.

is_balanced("()") should return True
is_balanced("([{}])") should return True
is_balanced("(]") should return False
is_balanced("([)]") should return False
is_balanced("{[()]}") should return True

Solution

DISCLAIMER: This solution is not the only possible solution, and there are many other ways to solve this problem. My approach was to provide a solution that works, refactoring later.

After the problem statement, the first thing was to think out loud the solution. I started by writing down the input and output specifications, and then I thought about the possible cases. I then wrote down the solution in pseudocode, and finally I wrote the actual code.

Let's start with a naive solution: we start reading and we will keep track of the brackets we encounter. If we encounter an opening bracket, we will push it onto a stack. If we encounter a closing bracket, we will pop the top element from the stack and check if it matches the closing bracket. If it doesn't match, we will return False. If we reach the end of the string and the stack is empty, we will return True. Otherwise, we will return False.

A possible (and naive/brute) solution in Python would go like this:

VALID_SEQUENCES = ["()", "{}", "[]"]
VALID_OPEN = "[{("
VALID_CLOSE = ")}]"

def is_balanced(s: str) -> bool:
    stack = []

    for char in s:
        if char in VALID_OPEN:
            stack.append(char)
        elif char in VALID_CLOSE:
            if not stack:
                return False
            top = stack.pop()
            if not matches(top, char):
                return False
        # Ignore any other characters

    return len(stack) == 0

def matches(open: str, close: str) -> bool:
    return open + close in VALID_SEQUENCES

def main() -> None:
    TESTING_EXAMPLES = [
        "({[]})", "", "(]", "1", "11", "()", "{}", "[]", "}])([{"
    ]
    for example in TESTING_EXAMPLES:
        print(is_balanced(example))


if __name__ == "__main__":
    main()

And after running it, we get the following output:

True
True
False
True
True
True
True
True
False

What to take out of this

You may have noticed that the solution is...let's admit it, pretty straightforward (and ugly). But, it works! And, it's a good starting point. Remember: no AI to this point, just basic stack manipulation and trying to mimic what a human would do. Probably you would arrive at a more elegant solution using recursion or a different data structure, but you get the point: first pass, it works: you get to understand the problem and the solution.

Now, let's make a switch and use AI. I like to use a prompt structure that goes something like this:

CONTEXT: You are an expert at solving programming problems. You use the Socratic method to guide the user towards the solution.

REQUEST: You will be given a problem and you will need to provide a solution, with detailed instructions. Don't provide code, just help the user understand the problem and use the Socratic method to guide them towards the solution.

LANGUAGE: Clean and concise, professional-grade and easy to understand.

STRUCTURE: Use a step-by-step approach, breaking down the problem into smaller, manageable pieces. Provide clear and concise instructions for each step.

**IMPORTANT**: Always provide clear and concise instructions, even if the solution is straightforward. And don't provide code, just help the user understand the problem and use the Socratic method to guide them towards the solution.

Here's the problem:

Your task is to provide a Python function that will return True or False. The rules for the function are as follow:

The function will take an input string that may contain potentially some brackets, and the function should return True if the brackets are balanced, and False otherwise. The "allowed" brackets are `()`, `[]`, and `{}`, and the function should ignore any other characters (although this wasn't stated but I will add it here for clarity and to provide some additional food for thought).

Finally, some "test cases" to check them (minimum set, you may come up with some more and even with weird or edge cases):

- `is_balanced("()")` should return `True`
- `is_balanced("([{}])")` should return `True`
- `is_balanced("(]")` should return `False`
- `is_balanced("([)]")` should return `False`
- `is_balanced("{[()]}")` should return `True`

This could be a good starting point. Let's try it with your favourite LLM (ChatGPT, Claude, Gemini, Ollama...)

What do you think the LLM will do with this problem?

Hope you like this type of content. Stay tuned for more!