Combinatorics & Algorithms Design assignment. The purpose of this assignment is to create an algorithm that computes all possible and legal Android scheme lock patterns.

A pattern is legal iff:

• Each pattern must connect at least four dots.
• The dots in the pattern must all be distinct.
• If the line segment connecting any two consecutive dots in the pattern passes through any other dots, the other dots must have previously been in the pattern.

Android provides a 3*3 matrix by default.

This project uses CMake 3.8 and newer

$ git clone https://github.com/HippoBaro/android_scheme_pattern.git
$ cd android_scheme_pattern && mkdir build && cd build
$ cmake ..
$ make
$ ./cellphone_cellphone_password

The implementation consists of a directed graph traversed by a recursive algorithm that heuristically constructs all possible schemes.

The code uses some C++17 features. It has been compiled successfully on:

• GCC 7.1 and newer
• Clang 3.9.0 and newer

If you don't have the required setup, here's a Compiler Explorer link

The code is tuned for performance with the exclusive use of fixed-sized arrays (no dynamic allocation).

The algorithm is not limited by a 3 * 3 matrix but is able to work with arbitrary-sized matrices by using password_space<Collumns, Rows>.

I took this opportunity to play with C++ constexpr keyword and compile-time evaluation. The algorithm is fully compliant with constexpr limits. As a result, for a specified matrix of 2 by 2, the produced assembly is as follows (compiled with GCC 7.2) :

.LC0:
  .string "%d nodes combinations: %lu\n"
.LC1:
  .string "Total: %lu\n"
main:
  sub rsp, 8
  mov edx, 24
  mov esi, 4
  mov edi, OFFSET FLAT:.LC0
  xor eax, eax
  call printf
  mov esi, 24
  mov edi, OFFSET FLAT:.LC1
  xor eax, eax
  call printf
  xor eax, eax
  add rsp, 8
  ret

The produced assembly directly incorporates the result of the computation (24 schemes of 4 nodes possibles).

The recursive algorithm implements only pure functions, and thus is completely stateless. When compile-time evaluation in not enabled, the program takes advantage of this and shard the workload across multiple threads.

Using symmetry, the algorithm reduces the computational cost of resolving all schemes by 85% in a best-case scenario.