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

Published on 12 May 2024 09:40 PM
#Clu

How to resolve the algorithm De Bruijn sequences step by step in the CLU 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 CLU programming language

Source code in the clu programming language

% Generate the De Bruijn sequence consisiting of N-digit numbers
de_bruijn = cluster is generate
    rep = null
    own k: int := 0
    own n: int := 0
    own a: array[int] := array[int]$[]
    own seq: array[int] := array[int]$[]
    
    generate = proc (k_, n_: int) returns (string)
        k := k_
        n := n_
        a := array[int]$fill(0, k*n, 0)
        seq := array[int]$[]
        db(1, 1)
        s: stream := stream$create_output()
        for i: int in array[int]$elements(seq) do
            stream$puts(s, int$unparse(i))
        end
        return(stream$get_contents(s))
    end generate
    
    db = proc (t, p: int)
        if t>n then 
            if n//p = 0 then
                for i: int in int$from_to(1, p) do
                    array[int]$addh(seq, a[i])
                end
            end
        else
            a[t] := a[t - p]
            db(t+1, p)
            for j: int in int$from_to(a[t - p] + 1, k-1) do
                a[t] := j
                db(t + 1, t)
            end
        end
    end db
end de_bruijn

% Reverse a string
reverse = proc (s: string) returns (string)
    r: array[char] := array[char]$predict(1, string$size(s))
    for c: char in string$chars(s) do
        array[char]$addl(r, c)
    end
    return(string$ac2s(r))
end reverse 

% Find all missing N-digit values
find_missing = proc (db: string, n: int) returns (sequence[string])
    db := db || string$substr(db, 1, n) % wrap
    missing: array[string] := array[string]$[]
    s: stream := stream$create_output()
    for i: int in int$from_to(0, 10**n-1) do
        %s: stream := stream$create_output()
        stream$reset(s)
        stream$putzero(s, int$unparse(i), n)
        val: string := stream$get_contents(s)
        if string$indexs(val, db) = 0 then
            array[string]$addh(missing, val)
        end
    end
    return(sequence[string]$a2s(missing))
end find_missing

% Report all missing values, or 'none'.
validate = proc (s: stream, db: string, n: int)
    stream$puts(s, "Validating...")
    missing: sequence[string] := find_missing(db, n)
    for v: string in sequence[string]$elements(missing) do
        stream$puts(s, " " || v)
    end
    if sequence[string]$size(missing) = 0 then
        stream$puts(s, " none")
    end
    stream$putl(s, " missing.")
end validate

start_up = proc ()
    po: stream := stream$primary_output()
    
    % Generate the De Bruijn sequence for 4-digit numbers
    db: string := de_bruijn$generate(10, 4)
    
    % Report length and first and last digits
    stream$putl(po, "Length: " || int$unparse(string$size(db)))
    stream$putl(po, "First 130 characters:")
    stream$putl(po, string$substr(db, 1, 130))
    stream$putl(po, "Last 130 characters:")
    stream$putl(po, string$substr(db, string$size(db)-130, 130))
    
    % See if there are any missing values in the sequence
    validate(po, db, 4)
    
    % Reverse and validate again
    stream$putl(po, "Reversing...")
    validate(po, reverse(db), 4)
    
    % Replace the 4444'th element with '.' and validate again
    stream$putl(po, "Setting the 4444'th character to '.'...")
    db := string$substr(db, 1, 4443) || "." || string$rest(db, 4445)
    validate(po, db, 4)
end start_up

You may also check:How to resolve the algorithm Read a file line by line step by step in the M2000 Interpreter programming language
You may also check:How to resolve the algorithm Check that file exists step by step in the Maple programming language
You may also check:How to resolve the algorithm Tree datastructures step by step in the Haskell programming language
You may also check:How to resolve the algorithm Stair-climbing puzzle step by step in the Racket programming language
You may also check:How to resolve the algorithm Even or odd step by step in the zkl programming language