0
$\begingroup$

This question: Password 'spatial' pattern? gave me ideas about the properties of "walks" (continuous or relative, ordered paths) of keyboards (matrices), and now I am curious if there is a way to express such properties / relations on matrices using formal mathematical symbols.

Your (QWERTY) keyboard is kind of like a matrix $M$:

$$\begin{bmatrix}\mathbf{Q} & \mathbf{W} & \mathbf{E} & \mathbf{R} & \mathbf{T} & \mathbf{Y} & \mathbf{U} & \mathbf{I} & \mathbf{O} & \mathbf{P} & \\ \mathbf{A} & \mathbf{S} & \mathbf{D} & \mathbf{F} & \mathbf{G} & \mathbf{H} & \mathbf{J} & \mathbf{K} & \mathbf{L} & \mathbf{\cdot} \\ \mathbf{\cdot} & \mathbf{Z} & \mathbf{X} & \mathbf{C} & \mathbf{V} & \mathbf{B} & \mathbf{N} & \mathbf{M} & \mathbf{\cdot} & \mathbf{\cdot} \end{bmatrix}$$

To better illustrate my question, let me introduce the three basic kinds of walks1 over a matrix like this, since that is my use-case:

  • Linear: $\{\ \mathbf{A\ A\ S\ D}\ \}$, $\{\ \mathbf{E\ R\ F\ G}\ \}$ and $\{\ \mathbf{K\ U\ Y\ H\ J\ K}\ \}$ are all linear walks on this matrix, in that if you follow each set through the matrix, the following is always true of any two successive elements $A$ and $B$: $$\lvert\ (A_x, A_y) - (B_x, B_y)\ \rvert\leq (1, 1)\ $$

    That is, their coordinate pairs $(x, y)$ never differ by more than $(1, 1)$.

    A simple, recursive, contextless algorithm to determine whether a given set $S$ is a linear walk of a matrix $M$ can be written:

    1. If the difference between the coordinates of $S_{1+n}$ and $S_{2+n}$ is in $\{\ (0, 0),\ …\ (1, 1) \ \}$, repeat this step, letting $n$ be the number of previous steps.

    2. Otherwise, only the part of $S$ traversed thus far is a linear walk on $M$, which may be $\emptyset$.

  • Simple or trivial nonlinear: $\{\ \mathbf{F\ G\ H\ D}\ \}$, $\{\ \mathbf{A\ S\ D\ Q}\ \}$, $\{\ \mathbf{T\ G\ H\ R}\ \}$, and $\{\ \mathbf{Z\ X\ C\ V\ B\ S}\ \}$ are all simple nonlinear walks on this matrix, in that a single-lookaround, one-directional iterative algorithm on each of three or fewer states of $S$ (unsorted, sorted by $x$ then $y$, and $y$ then $x$) can show all elements have coordinates within $\{\ (0, 0),\ …\ (1, 1) \ \}$ of at least one other element, such as:

    1. Let $C$ be the coordinate pairs of each $S_n$, in the same order as $S$.
    2. Let $X$ be the ordering of $C$ by $C_{n_x}$, and $Y$ the ordering of $C$ by $C_{n_y}$.
    3. Accumulate three sets $V_n$ of the differences of successive pairs in each of $C$, $X$, $Y$.
    4. If any of $V_n$ has all its elements within $\{\ (0, 0),\ …\ (1, 1) \ \}$, $S$ is a simple nonlinear walk on $M$.
    5. Otherwise, $S$ may be a complex nonlinear walk on $M$.
  • Complex nonlinear: $\{\ \mathbf{A\ S\ D\ E\ Z}\ \}$, $\{\ \mathbf{A\ S\ D\ Q\ W\ E\ Z\ X\ C}\ \}$, and $\{\ \mathbf{R\ T\ Y\ D\ F\ G\ X\ C\ V}\ \}$ are all complex nonlinear walks on $M$ in that

    • all elements have coordinates within $\{\ (0, 0),\ …\ (1, 1) \ \}$ of at least one other element, and
    • a single-lookaround, one-directional iterative algorithm would need to be performed on every possible permutation of $S$ in order to tell if $S$ is a simple nonlinear walk on $M$,
    • and you only need $len(S)*{len(S) - 1}$ calculations to determine whether $S$ is a complex nonlinear walk on $M$.

(Note well, that all linear and simply nonlinear walks are in the set of complex nonlinear walks, but not the inverse.)

Is there another or better way to express these kinds of subsets, paths, or algorithms on a given "keyboard" matrix, perhaps using set notation?

(1): That I have determined to be disparate after spending 3 days programming and experimenting about this.

$\endgroup$
  • $\begingroup$ What can be improved, please let me know $\endgroup$ – cat May 31 '17 at 10:32
  • $\begingroup$ Treat the keyboard as a grid graph with diagonal edges and self-edges added, then a linear walk is just a path. I haven't thought about your other kinds of walks. $\endgroup$ – Rahul May 31 '17 at 10:47
  • 1
    $\begingroup$ I don't quite understand these definitions. I would look into the graph theory literature on the difference between walks, paths, Eulerian paths, etc. (I didn't downvote though.) $\endgroup$ – Jair Taylor Jun 1 '17 at 18:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.