Android scheme pattern resolver

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

Lock Schemes

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.

Instructions

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

CMake options

Option	Description	Default
COMP_TIME_EVAL	Computes the results at compile-time using constexpr.	OFF
PRINT_SCHEMES	Prints all found combinations on stdout.	OFF
USE_SYMMETRY	Computes the results using symmetry (reduces computational cost)	ON

Implementation

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

Compiler support

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

Performances

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

Bonus

Arbitrary-sized matrix

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>.

Fully compile-time evaluated

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).

Multithreaded Pure functional

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.

Symmetry resolve

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