lockpatterncomplexity.jl
Solving the most complex lock patterns with Julia Language, MiniZinc, and Google OR-Tools.
Science Score: 54.0%
This score indicates how likely this project is to be science-related based on various indicators:
-
✓CITATION.cff file
Found CITATION.cff file -
✓codemeta.json file
Found codemeta.json file -
✓.zenodo.json file
Found .zenodo.json file -
○DOI references
-
✓Academic publication links
Links to: zenodo.org -
○Committers with academic emails
-
○Institutional organization owner
-
○JOSS paper metadata
-
○Scientific vocabulary similarity
Low similarity (10.9%) to scientific vocabulary
Keywords
Repository
Solving the most complex lock patterns with Julia Language, MiniZinc, and Google OR-Tools.
Basic Info
- Host: GitHub
- Owner: jaantollander
- License: mit
- Language: Julia
- Default Branch: master
- Homepage: https://jaantollander.github.io/LockPatternComplexity.jl/dev/
- Size: 2.91 MB
Statistics
- Stars: 2
- Watchers: 1
- Forks: 0
- Open Issues: 0
- Releases: 10
Topics
Metadata Files
README.md
Solving the Most Complex Lock Patterns
3×3 | 4×4
:-:|:-:
| 
distance: 22* | distance: 61*
5×5 | 6×6
:-:|:-:
| 
distance: 119 | distance: 207
7×7 | 7×7
:-: | :-:
| 
distance=315 | distance=317
About
In this repository, we present solutions for the most complex lock patterns using the MiniZinc modeling language and the powerful Google OR-Tools solver. Additionally, we use the Julia Language to generate the input data and analyze the results.
This repository was inspired by the video What Is The Most Complicated Lock Pattern? by Dr. Zye. I highly recommend watching it! Also, you can try out lock patterns with lock pattern demo by @tympanix.
We use a generalized definition of maximum complexity for a lock pattern, presented in Dr. Zye's video, such that it has solutions for all n×n grids while preserving the original solutions. Our definition requires all lines in the pattern to have a unique "type" (slope), and we maximize the total "taxicab" distance of the pattern, which results in greater visual complexity for the patterns. The problem is a combinatorial optimization problem. The documentation covers the theoretical aspect of the problem.
Structure
The source code in this repository is structured as follows.
- The
src/directory contains Julia code. - The
models/directory contains the MiniZinc models. - The
models/instances/contains the datafiles for different grid sized instances of the model. - The
models/fzn/contains FlatZinc files generated from each model instances. These are useful to understand the size of a model instance and verify that variables have sensible bounds. - The
scripts/directory contains scripts for generating data files for instances, running the model, and plotting the results.
The output is located in the following directories.
- The
results/directory contains the text output from the models. - The
plots/directory contains the generated SVG plots for each grid size and taxicab distance in format<grid>/<distance>/<id>.svg. The<id>is a unique identified generated using hash of the pattern.
Instructions
To begin, we need to install MiniZinc and Google OR-Tools. On Linux, we can use the following shell scripts for the installation. After the installation, we can run shell scripts from the scripts directory and write the output to the results/3x3.txt file. For example, we can run the optimization model using the following command.
bash
./scripts/nxn_opt.sh 3 results/3x3.txt
The output generated by the solver will appear to the results/ directory.
Open Questions
~~Can we find a max complexity pattern for a 4×4 grid that provably maximizes the taxicab distance?~~
Can we find a max complexity pattern for a 5×5 grid that provably maximizes the taxicab distance?
~~Can we find a max complexity pattern for a 7×7 grid?~~
Owner
- Name: Jaan Tollander de Balsch
- Login: jaantollander
- Kind: user
- Location: Finland
- Company: CSC - IT Center for Science
- Website: jaantollander.com
- Repositories: 73
- Profile: https://github.com/jaantollander
Citation (CITATION.cff)
cff-version: 1.2.0 message: "If you use this software, please cite it as below." authors: - family-names: "Tollander de Balsch" given-names: "Jaan" orcid: "https://orcid.org/0000-0002-4814-5554" title: "jaantollander/LockPatternComplexity.jl" version: 0.0.0 doi: 10.5281/zenodo.5758608 date-released: 2021-12-04 url: "https://doi.org/10.5281/zenodo.5758608"
GitHub Events
Total
Last Year
Committers
Last synced: 9 months ago
Top Committers
| Name | Commits | |
|---|---|---|
| Jaan Tollander de Balsch | j****n@h****m | 51 |
| semantic-release-bot | s****t@m****t | 9 |
Committer Domains (Top 20 + Academic)
Issues and Pull Requests
Last synced: 9 months ago
All Time
- Total issues: 0
- Total pull requests: 0
- Average time to close issues: N/A
- Average time to close pull requests: N/A
- Total issue authors: 0
- Total pull request authors: 0
- Average comments per issue: 0
- Average comments per pull request: 0
- Merged pull requests: 0
- Bot issues: 0
- Bot pull requests: 0
Past Year
- Issues: 0
- Pull requests: 0
- Average time to close issues: N/A
- Average time to close pull requests: N/A
- Issue authors: 0
- Pull request authors: 0
- Average comments per issue: 0
- Average comments per pull request: 0
- Merged pull requests: 0
- Bot issues: 0
- Bot pull requests: 0