Android unlock patterns

[Gh]

How many Android unlock patterns are possible in the 3x3 grid? There should be 389,112 possible patterns that comply with the rules. I asked ChatGPT whether it can provide a FreeBASIC program that calculates or counts this number.
As expected, this program does not run straight away. I did not succeed in debugging the program. I am also not a talented programmer. Does anyone have an idea how to get the program to run? It would be nice if it would also work for 4x4 grids and higher.
Thanks in advance, Hans

Code: Select all

' FreeBASIC program to count all possible unlock patterns in a 3x3 grid
' ChatGPT, 30.10.2024

Dim As Integer used(3, 3) = {0, 0, 0, 0, 0, 0, 0, 0, 0} ' Grid to store visited points
'     Dim As Integer used(3, 3) = {{0, 0, 0}, {0, 0, 0}, {0, 0, 0}}   ! Gh
Dim As Integer totalPatterns = 0 ' Counter for the total number of patterns

' Function to check if a point is within the grid and not yet used
Function IsValidPoint(x As Integer, y As Integer) As Integer
    Return (x >= 0 And x < 3 And y >= 0 And y < 3 And used(x, y) = 0)
End Function

' Function to add a point to the current pattern
Sub AddPoint(x As Integer, y As Integer, step As Integer)
    used(x, y) = 1
End Sub

' Function to remove a point from the current pattern
Sub RemovePoint(x As Integer, y As Integer)
    used(x, y) = 0
End Sub

' Recursive function to generate all patterns
Sub GenerateAllPatterns(startX As Integer, startY As Integer, step As Integer)
    ' If the pattern contains at least 4 points, we count it
    If step >= 3 Then
        totalPatterns += 1
    End If

    ' Generate all possible continuations of the current pattern
    For dirX As Integer = -1 To 1
        For dirY As Integer = -1 To 1
            If dirX = 0 And dirY = 0 Then Continue For ' No movement
            Dim As Integer nx = startX + dirX
            Dim As Integer ny = startY + dirY

            ' Check if the next point is valid and not yet visited
            If IsValidPoint(nx, ny) Then
                ' If a point is skipped, check if the intermediate point is visited
                Dim As Integer midX = (startX + nx) \ 2
                Dim As Integer midY = (startY + ny) \ 2
                If Abs(nx - startX) = 2 Or Abs(ny - startY) = 2 Then
                    If used(midX, midY) = 0 Then Continue For
                End If

                ' Add the point to the pattern and continue the recursion
                AddPoint(nx, ny, step + 1)
                GenerateAllPatterns(nx, ny, step + 1)
                RemovePoint(nx, ny) ' Remove the point after returning
            End If
        Next
    Next
End Sub

' Main program to generate and count the patterns
Sub GenerateAndCountAllPatterns()
    For x As Integer = 0 To 2
        For y As Integer = 0 To 2
            AddPoint(x, y, 0) ' Start with each possible starting point
            GenerateAllPatterns(x, y, 0)
            RemovePoint(x, y)
        Next
    Next
    Print "Total number of patterns: "; totalPatterns
End Sub

' Start the program
GenerateAndCountAllPatterns()

[paul doe]

Code: Select all

' FreeBASIC program to count all possible unlock patterns in a 3x3 grid
' ChatGPT, 30.10.2024

Dim As Integer used(3, 3) = {{0, 0, 0}, {0, 0, 0}, {0, 0, 0}} ' Grid to store visited points
'     Dim As Integer used(3, 3) = {{0, 0, 0}, {0, 0, 0}, {0, 0, 0}}   ! Gh
Dim shared As Integer totalPatterns = 0 ' Counter for the total number of patterns

' Function to check if a point is within the grid and not yet used
Function IsValidPoint(a() as integer, x As Integer, y As Integer) As Integer
    Return (x >= 0 AndAlso x < 3 AndAlso y >= 0 AndAlso y < 3 AndAlso a(x, y) = 0)
End Function

' Function to add a point to the current pattern
Sub AddPoint(a() as integer, x As Integer, y As Integer, step_ As Integer)
  a( x, y ) += step_
End Sub

' Function to remove a point from the current pattern
Sub RemovePoint( a() as integer, x As Integer, y As Integer)
  a( x, y ) = 0
End Sub

' Recursive function to generate all patterns
Sub GenerateAllPatterns( a() as integer, startX As Integer, startY As Integer, steps As Integer)
    ' If the pattern contains at least 4 points, we count it
    If steps >= 3 Then
        totalPatterns += 1
    End If

    ' Generate all possible continuations of the current pattern
    For dirX As Integer = -1 To 1
        For dirY As Integer = -1 To 1
            If dirX = 0 AndAlso dirY = 0 Then Continue For ' No movement
            Dim As Integer nx = startX + dirX
            Dim As Integer ny = startY + dirY

            ' Check if the next point is valid and not yet visited
            If IsValidPoint( a(), nx, ny ) Then
                ' If a point is skipped, check if the intermediate point is visited
                Dim As Integer midX = (startX + nx) \ 2
                Dim As Integer midY = (startY + ny) \ 2
                If Abs(nx - startX) = 2 OrElse Abs(ny - startY) = 2 Then
                    If a( midX, midY ) = 0 Then Continue For
                End If

                ' Add the point to the pattern and continue the recursion
                AddPoint(a(), nx, ny, steps + 1)
                GenerateAllPatterns( a(), nx, ny, steps + 1)
                RemovePoint( a(), nx, ny) ' Remove the point after returning
            End If
        Next
    Next
End Sub

' Main program to generate and count the patterns
Sub GenerateAndCountAllPatterns( a() as integer )
    For x As Integer = 0 To 2
        For y As Integer = 0 To 2
            AddPoint( a(), x, y, 0 ) ' Start with each possible starting point
            GenerateAllPatterns( a(), x, y, 0 )
            RemovePoint( a(), x, y )
        Next
    Next
    Print "Total number of patterns: "; totalPatterns
End Sub

' Start the program
GenerateAndCountAllPatterns( used() )

sleep()

Now it compiles, but the code is trash. I didn't bothered to check it for 'correctness', since this is a problem that doesn't have a fixed solution: the number of possible patterns depends heavily on the length of it, the starting point (ie where do you set the first point), and subsequent points.