Weekly Challenge: The Hamiltonian Question

Weekly Challenge 382

Each week Mohammad S. Anwar sends out The Weekly Challenge, a chance for all of us to come up with solutions to two weekly tasks. Unless otherwise stated, Copilot (and other AI tools) have NOT been used to generate the solution. It's a great way for us all to practice some coding.

Challenge, My solutions

Sorry, no Perl solutions this week.

Task 1: Hamiltonian Cycle

Task

You are given a target number.

Write a script to arrange all the whole numbers from 1 up to the given target number into a circle so that every pair of side-by-side numbers adds up to a perfect square. Please make sure, the last number and the first must also add up to a square.

My solution

This was a fun challenge. After a few days of thought, I went to my trusty friend, a recursive function.

When the function is called for the first time, it populates the SQUARE set with the squares from 1 to n². In reality, I only need the squares up to n * 2 - 1, but that would be harder to write.

I also set the results list to a single 1 to seed the list in the first iteration. I then create a list called remaining_numbers which are the numbers from 2 to n (inclusive) that are not in the results list.

SQUARES = None

def hamiltonian_cycle(n: int, results=None) -> list[int]:
    global SQUARES

    if SQUARES is None:
        SQUARES = {n * n for n in range(1, n + 1)}

    if results is None:
        results = [1]

    remaining_numbers = [n for n in range(2, n + 1) if n not in results]

If the remaining_numbers list is empty, I have used all the numbers and need to check if the sum of the first and last number is also a square. If it is, I return the list to the calling function. If it isn't, I return an empty list to find another solution.

    if not remaining_numbers:
        if results[0] + results[-1] in SQUARES:
            return results
        return []

The rest of the function is an loop called i using each value from the remaining_numbers list. For each iteration, if the sum of the last number in the results list and i is a square, I call the recursive function again. If the loop is exhausted, I return an empty string.

    for i in remaining_numbers:
        if i + results[-1] in SQUARES:
            new_results = hamiltonian_cycle(n, results + [i])
            if new_results:
                return new_results

    return []

Examples

For the third example, the list differs from the one on the website. Unless I missed something, it is still valid.

$ ./ch-1.py 32
[1, 8, 28, 21, 4, 32, 17, 19, 30, 6, 3, 13, 12, 24, 25, 11, 5, 31, 18, 7, 29, 20, 16, 9, 27, 22, 14, 2, 23, 26, 10, 15]

$ ./ch-1.py 15
[]

$ ./ch-1.py 34
[1, 3, 13, 12, 4, 32, 17, 8, 28, 21, 15, 34, 30, 19, 6, 10, 26, 23, 2, 14, 22, 27, 9, 16, 33, 31, 18, 7, 29, 20, 5, 11, 25, 24]

Task 2: Replace Question Mark

Task

You are given a string that contains only 0, 1 and ? characters.

Write a script to generate all possible combinations when replacing the question marks with a zero or one.

My first solution

This was a question I was asked in a closed-book hand-written interview I had a few months ago. I didn't get the job, but I thought it would be suitable for a task for Team PWC members.

When I wrote this solution on paper, I mentioned that while I'm sure the code would work (spoiler: it does) it was probably not the most efficient one, and in the real world I'd just ask Copilot to do the job.

This solution is the script ch-2-alternate.py. I start by checking the input is made up of 0, 1 and ? characters. If there are no question marks, I return the original input as a single-item list. I also seed the result list with a single empty string.

import re

def replace_question_mark(input_string: str) -> list[str]:
    if not re.match(r"^[01?]+$", input_string):
        raise ValueError("input_string must contain only '0', '1', and '?' characters")

    if "?" not in input_string:
        return [input_string]

    result = [""]

I then iterate over each character. If the character is a question mark, I duplicate the array, appending 0 to the first half and 1 to the second half. If the character is 0 or 1, I append that character to each item in the list.

    for c in input_string:
        if c == "?":
            new_result = [row + "0" for row in result]
            new_result += [row + "1" for row in result]
            result = new_result
        else:
            result = [row + c for row in result]

    return result

The AI (and better) solution

So when I got home, I asked Copilot to write a solution for me. It took no time to produce the output in the script ch-2.py. This is slightly modified, but the logic came from Copilot.

After performing the same checks as the previous example, it finds the position of all the question marks and stores this in a list called question_positions.

from itertools import product
import re

def replace_question_mark(input_string: str) -> list[str]:
    if not re.match(r"^[01?]+$", input_string):
        raise ValueError("input_string must contain only '0', '1', and '?' characters")

    if "?" not in input_string:
        return [input_string]

    question_positions = [i for i, char in enumerate(input_string) if char == "?"]

It then uses the product function from the itertools package to generate all combinations of zeros and ones and substitutes them in the correct position.

    results = []
    for combination in product("01", repeat=len(question_positions)):
        chars = list(input_string)
        for pos, value in zip(question_positions, combination):
            chars[pos] = value
        results.append("".join(chars))

    return results

Examples

The order in the alternate script differs from the below. The solutions are still valid.

$ ./ch-2.py 01??0
['01000', '01010', '01100', '01110']

$ ./ch-2.py 101
['101']

$ ./ch-2.py ???
['000', '001', '010', '011', '100', '101', '110', '111']

$ ./ch-2.py 1?10
['1010', '1110']

$ ./ch-2.py 1?1?0
['10100', '10110', '11100', '11110']