Generate random "pattern-lock" sequence of digits

Question

Today my friend raised a challenge that I still can't solve: "Generate a random digit sequence in PHP"

The digits are arranged as dial-pad/pattern-lock that consist 1-9 keys in 3 rows and 3 columns:

 ---------------------------
|                           |
|     1       2      3      |
|                           |
|     4       5      6      |
|                           |
|     7       8      9      |
|                           |
 ---------------------------

Now, given a length, we have to generate a random, non-repeating sequence of digits of the provided length, using these criteria:

1. A generated sequence should follow a specific direction/pattern going only via neighboring digits (possibly diagonally), for example (length:8), 12569874:

    1 🡪 2
         🡫
    4    5 🡪 6
    🡩        🡫
    7 🡨 8 🡨 9 
   

2. Digits from the first row should never be followed by a digit from the third row, and vice-versa. The same goes for columns. For example a 1 cannot be followed by a 8, and a 6 cannot be followed by a 4.

3. can guess more criteria can easily from android pattern-lock system

Here are some example generated sequences for length 9: 12369874/5, 142536987, etc, and for length = 6: 987532, etc

I tried to do this with rand():

  $chars = "123456789";
  $length = 9;
  $clen   = strlen( $chars )-1;
  $id  = '';

  for ($i = 0; $i < $length; $i++) {
      $id .= $chars[mt_rand(0,$clen)];
  }
  return ($id);

but, still no luck...

How can I solve this question?

Answer 1

has some limitations but that's for you to work out. I only deal with headaches when I get paid :).

<pre>
<?php

// Keypad
$grid = [
    ['1', '2', '3'],
    ['4', '5', '6'],
    ['7', '8', '9'],
];

// Sequence Target Length
$target_length = 5;

// Place to store the Keypad sequence
$points = [];

// Starting Point
$x = rand(0, 2);
$y = rand(0, 2);

// Run through the process until we have the sequence at the desired length
while (count($points) < $target_length):

    // Check if the grid keypad entry has been used
    if ($grid[$x][$y]):
        // Hasn't been used, so stire it
        $points[] = $grid[$x][$y]; 
        // Mark it used 
        $grid[$x][$y] = NULL;
    endif;

    // Sanity Check, imagine if you will,.... target length of 9, and you hit 6 5 2 1,  You'll vault off into the twilight zone without this
    if ((!$grid[$x + 1][$y]) && (!$grid[$x][$y + 1]) && (!$grid[$x - 1][$y]) && (!$grid[$x][$y - 1])):
        // We have no where to go
        break;
    endif;

    // Start looking for possible values 
    do {
        $test_x = $x;
        $test_y = $y;
        $dir = rand(0, 3);

        switch ($dir):
            case (0):
                $test_y--; // Up
                break;
            case (1):
                $test_x++; // Right
                break;
            case (2):
                $test_y++; // Down
                break;
            case (3):
                $test_x--; // Left
                break;
        endswitch;
        // Optional Gibberish 
        echo "Moving from {$x}, {$y} to {$test_x}, {$test_y} --> " . (($grid[$test_x][$test_y] === NULL) ? 'FAILED' : 'OK!') . '<br>';

        // Keep going until we find a valid direction
    } while ($grid[$test_x][$test_y] === NULL);

    // assign the new coords
    $x = $test_x;
    $y = $test_y;

    // repeat
endwhile;

// report
echo implode('-', $points) . "\n";

?>
</pre>

Answer 2

Here is a solution that will apply these rules:

• a path can only step to neighboring cells, i.e. that are adjacent, including diagonally
• a path cannot contain the same cell twice

The following algorithm uses recursion for every digit that is added to the sequence. Whenever the sequence gets "stuck", backtracking happens, and an alternative path is tried. Backtracking continues if no more alternatives are available.

It is guaranteed that a path of the given length is returned, provided the given length is between 1 and 9:

function randomSequence($len) {
    if ($len < 1 || $len > 9) return []; // No results
    $row = [null, 1, 1, 1, 2, 2, 2, 3, 3, 3];
    $col = [null, 1, 2, 3, 1, 2, 3, 1, 2, 3];
    $neighbors = [[], [2, 4, 5],       [1, 4, 5, 6, 3],          [2, 5, 6],
                      [1, 2, 5, 7, 8], [1, 2, 3, 4, 6, 7, 8, 9], [2, 3, 5, 8, 9],
                      [4, 5, 8],       [4, 5, 6, 7, 9],          [5, 6, 8]];
    // Shuffle the neighbor lists to implement the randomness:
    foreach ($neighbors as &$nodes) shuffle($nodes);

    $recurse = function ($seq) use (&$len, &$row, &$col, &$neighbors, &$recurse) {
        if (count($seq) >= $len) return $seq; // found solution
        $last = end($seq);
        echo "try " . json_encode(array_keys($seq)) . "\n";
        foreach ($neighbors[$last] as $next) {
            if (isset($seq[$next])) continue; // Skip if digit already used
            $result = $recurse($seq + [$next => $next]);
            if (is_array($result)) return $result;
        }
    };
    $choice = rand(1, 9);
    return array_keys($recurse([$choice => $choice]));
}

echo "result: " . json_encode(randomSequence(9)) . "\n";

See it run on repl.it