Lock-chart solving algorithm testbed
Clone or download


Lock-chart solving algorithm testbed

Build Status Build status codecov

Lock-chart solving aka master-key system (MKS) solving is the discipline of finding mechanical key cuttings and lock components that match user-specified access rights.

This project contains prototypes of algorithms and supportive functions for lock-chart solving.

Original authors of this project are affiliated with the commercial “CyberCalc” project. The two projects are independent; no code is shared between them. While CyberCalc is scalable, highly polished, tuned, well tested and production-ready, this project is experimental. The trade-off between execution speed and convenience of programming is skewed towards the latter here. We aim for a “hackable” code, which attracts enthusiasts to try their algorithmic ideas.


The main developer and maintainer of the project is Radomír Černoch.

Important contributions were made by (in chronological order)

  • Marek Kryška
  • Václav Voráček
  • Martin Hořeňovský

Compilation quick-guide

This is a short version of a long build guide on project's wiki

The simplest build procedure looks as following:

  1. Install Ubuntu 16.04.

  2. Prepare the environment

$ sudo apt-get install git build-essential
$ git submodule init
$ git submodule update
  1. Build the C++ code:
$ cmake -Bbuild -H. -DCMAKE_BUILD_TYPE=RelWithDebInfo
$ cd build
$ make -j
$ ctest -j
$ cd ..
  1. Install Java 8 JDK. WebUpd8 PPAs provide an easy way.

  2. Build the Java code

$ sudo apt-get install maven
$ export PATH="$(pwd)/build:$PATH"
$ mvn test


The project contains several benchmarks, which can be executed.

Shear-lines in a GVC

The data/MinGvl*.csv files contain lock-chart solving benchmarks that minimise the number of shear-lines in a global virtual cylinder. The files can be recreated using:

$ mvn -Dtest=MinGvlBenchmark test

Find the largest diagonal lock-chart

The data/SatDiag.csv file contains the size of the largest diagonal lock-chart that can be found by MiniSat. The file can be recreated using:

$ data/SatDiag/make.sh
$ mv *.csv data/SatDiag/
$ mvn -Dtest=SatDiagBenchmark test

The data/PolyDiag.csv file contains the size of the largest diagonal lock-chart that can be found by polynomial approximations. The file can be recreated using:

$ mvn -Dtest=PolyDiagBenchmark test