How to resolve the algorithm De Bruijn sequences step by step in the Go programming language

Published on 12 May 2024 09:40 PM
#Go

How to resolve the algorithm De Bruijn sequences step by step in the Go programming language

Table of Contents

Problem Statement

The sequences are named after the Dutch mathematician   Nicolaas Govert de Bruijn.

A note on Dutch capitalization:   Nicolaas' last name is   de Bruijn,   the   de   isn't normally capitalized unless it's the first word in a sentence.   Rosetta Code (more or less by default or by fiat) requires the first word in the task name to be capitalized.

In combinatorial mathematics,   a   de Bruijn sequence   of order   n   on a   size-k   alphabet (computer science)   A   is a cyclic sequence in which every possible   length-n   string (computer science, formal theory)   on   A   occurs exactly once as a contiguous substring. Such a sequence is denoted by   B(k, n)   and has length   kn,   which is also the number of distinct substrings of length   n   on   A;     de Bruijn sequences are therefore optimally short. There are: distinct de Bruijn sequences   B(k, n).

For this Rosetta Code task,   a   de Bruijn   sequence is to be generated that can be used to shorten a brute-force attack on a   PIN-like   code lock that does not have an "enter" key and accepts the last   n   digits entered.

Note:   automated teller machines (ATMs)   used to work like this,   but their software has been updated to not allow a brute-force attack.

A   digital door lock   with a 4-digit code would have B (10, 4) solutions,   with a length of   10,000   (digits). Therefore, only at most     10,000 + 3     (as the solutions are cyclic or wrap-around)   presses are needed to open the lock. Trying all 4-digit codes separately would require   4 × 10,000   or   40,000   presses.

(The last requirement is to ensure that the verification tests performs correctly.   The verification processes should list any and all missing PIN codes.) Show all output here, on this page.

Let's start with the solution:

Step by Step solution about How to resolve the algorithm De Bruijn sequences step by step in the Go programming language

The provided Go program demonstrates the generation and validation of a de Bruijn sequence, which is a combinatorial object with applications in various fields. Here's a detailed explanation of the source code:

  1. Constants and Variables:

    • digits: A constant string representing the digits 0 to 9.
    • a: A byte array of length k*n used to construct the de Bruijn sequence.

  2. deBruijn Function:

    • This function generates a de Bruijn sequence of order k and length n.
    • It initializes a with the k digits from digits and uses a recursive closure db to construct the sequence.
    • The recursive function db performs the following steps:
      • If the current position t is greater than n, it checks if n is divisible by p (the previous position). If so, it appends the digits from a at position p to t to the seq slice.
      • Otherwise, it copies the digit at position t-p to position t in a and calls db recursively with t+1 and p.
      • It iterates through the remaining digits in the range j = a[t-p] + 1 to k, assigns them to position t in a, and calls db recursively with t+1 and t.
    • Finally, the function returns the concatenated seq slice and the first n-1 digits of the sequence to form a cyclic pattern.

  3. allDigits Function:

    • This function checks if a string s contains only digits (0 to 9).

  4. validate Function:

    • This function validates a given de Bruijn sequence db.
    • It creates a slice found of length 10000 to track the occurrences of all 4-digit combinations within db.
    • It iterates through all 4-digit substrings in db, checks if they are valid digits, and increments the corresponding count in found.
    • It then checks for missing or duplicate 4-digit combinations and reports any errors found.

  5. reverse Function:

    • This function reverses the order of characters in a string.

  6. main Function:

    • It calls the deBruijn function to generate a de Bruijn sequence with 10 digits and length 4 (i.e., db).
    • It prints the length of the generated sequence, the first 130 digits, and the last 130 digits.
    • It validates the original de Bruijn sequence (db), the reversed de Bruijn sequence (dbr), and an overlaid de Bruijn sequence where one digit is replaced with a dot ('.').

Source code in the go programming language

package main

import (
    "bytes"
    "fmt"
    "strconv"
    "strings"
)

const digits = "0123456789"

func deBruijn(k, n int) string {
    alphabet := digits[0:k]
    a := make([]byte, k*n)
    var seq []byte
    var db func(int, int) // recursive closure
    db = func(t, p int) {
        if t > n {
            if n%p == 0 {
                seq = append(seq, a[1:p+1]...)
            }
        } else {
            a[t] = a[t-p]
            db(t+1, p)
            for j := int(a[t-p] + 1); j < k; j++ {
                a[t] = byte(j)
                db(t+1, t)
            }
        }
    }
    db(1, 1)
    var buf bytes.Buffer
    for _, i := range seq {
        buf.WriteByte(alphabet[i])
    }
    b := buf.String()
    return b + b[0:n-1] // as cyclic append first (n-1) digits
}

func allDigits(s string) bool {
    for _, b := range s {
        if b < '0' || b > '9' {
            return false
        }
    }
    return true
}

func validate(db string) {
    le := len(db)
    found := make([]int, 10000)
    var errs []string
    // Check all strings of 4 consecutive digits within 'db'
    // to see if all 10,000 combinations occur without duplication.
    for i := 0; i < le-3; i++ {
        s := db[i : i+4]
        if allDigits(s) {
            n, _ := strconv.Atoi(s)
            found[n]++
        }
    }
    for i := 0; i < 10000; i++ {
        if found[i] == 0 {
            errs = append(errs, fmt.Sprintf("    PIN number %04d missing", i))
        } else if found[i] > 1 {
            errs = append(errs, fmt.Sprintf("    PIN number %04d occurs %d times", i, found[i]))
        }
    }
    lerr := len(errs)
    if lerr == 0 {
        fmt.Println("  No errors found")
    } else {
        pl := "s"
        if lerr == 1 {
            pl = ""
        }
        fmt.Printf("  %d error%s found:\n", lerr, pl)
        fmt.Println(strings.Join(errs, "\n"))
    }
}

func reverse(s string) string {
    bytes := []byte(s)
    for i, j := 0, len(s)-1; i < j; i, j = i+1, j-1 {
        bytes[i], bytes[j] = bytes[j], bytes[i]
    }
    return string(bytes)
}

func main() {
    db := deBruijn(10, 4)
    le := len(db)
    fmt.Println("The length of the de Bruijn sequence is", le)
    fmt.Println("\nThe first 130 digits of the de Bruijn sequence are:")
    fmt.Println(db[0:130])
    fmt.Println("\nThe last 130 digits of the de Bruijn sequence are:")
    fmt.Println(db[le-130:])
    fmt.Println("\nValidating the de Bruijn sequence:")
    validate(db)

    fmt.Println("\nValidating the reversed de Bruijn sequence:")
    dbr := reverse(db)
    validate(dbr)

    bytes := []byte(db)
    bytes[4443] = '.'
    db = string(bytes)
    fmt.Println("\nValidating the overlaid de Bruijn sequence:")
    validate(db)
}

You may also check:How to resolve the algorithm Video display modes step by step in the Icon and Unicon programming language
You may also check:How to resolve the algorithm Input loop step by step in the UnixPipes programming language
You may also check:How to resolve the algorithm Statistics/Normal distribution step by step in the Python programming language
You may also check:How to resolve the algorithm Musical scale step by step in the VBA programming language
You may also check:How to resolve the algorithm Repeat a string step by step in the NewLISP programming language