Releases: raj-open/code-challenges
🚀 Parallelisation + improvements to algorithmic + representations
Qualitatively improved the GS algorithm as follows:
-
we separately keep track of the obstacle and the dithered obstactle, instead of computing this for every pair of pieces. This results in a linear time improvement.
-
instead of the order in the depth-first tree search, we dynamallyically sort to prioritise placing pieces, for which the number of possibilities is the fewest. This results in a significant time improvement.
-
we implemented parallelisation which allows us to efficiently determine all solution in a short amount of time.
In addition to this, the logging of solutions has improved. E.g.
just run-rust GeniusSquare A5 B1 C3 C6 D2 E4 F1results in
Roll: A5 B1 C3 C6 D2 E4 F1
Problem:
╔═══╦═══╦═══╦═══╦═══╦═══╗
║ A ║ B ║ C ║ D ║ E ║ F ║
╚═══╩═══╩═══╩═══╩═══╩═══╝
╔═══╗ ┼───┼ ┼───┼
║ 1 ║ │ ■ │ │ ■ │
╠═══╣ ┼───┼ ┼───┼ ┼───┼
║ 2 ║ │ ■ │
╠═══╣ ┼───┼───┼
║ 3 ║ │ ■ │
╠═══╣ ┼───┼ ┼───┼
║ 4 ║ │ ■ │
╠═══╣ ┼───┼ ┼───┼
║ 5 ║ │ ■ │
╠═══╣ ┼───┼ ┼───┼
║ 6 ║ │ ■ │
╚═══╝ ┼───┼
Compute solution ... found 69 solutions.
Time for 1st solution: 7.499ms
Average time per solution: 2.555521ms
Total time: 176.331ms
Solution 1:
╔═══╦═══╦═══╦═══╦═══╦═══╗
║ A ║ B ║ C ║ D ║ E ║ F ║
╚═══╩═══╩═══╩═══╩═══╩═══╝
╔═══╗ ┼───┼───┼───┼───┼───┼───┼
║ 1 ║ │ 1 │ ■ │ 2 │ Z Z │ ■ │
╠═══╣ ┼───┼───┼ ┼───┼ ┼───┼
║ 2 ║ │ X X │ 2 │ ■ │ Z Z │
╠═══╣ ┼ ┼───┼───┼───┼───┼
║ 3 ║ │ X X │ ■ │ 3 3 3 │
╠═══╣ ┼───┼───┼───┼───┼───┼───┼
║ 4 ║ │ 4 4 4 4 │ ■ │ L │
╠═══╣ ┼───┼───┼───┼───┼───┼ ┼
║ 5 ║ │ ■ │ C │ T T T │ L │
╠═══╣ ┼───┼ ┼───┼ ┼───┼ ┼
║ 6 ║ │ C C │ ■ │ T │ L L │
╚═══╝ ┼───┼───┼───┼───┼───┼───┼
which eases readability. We also fixed the use of terminal fonts, so the latter appears in the console with colour coded pieces.
Added Binary: Genius Square solver
-
Cleaned up infrastructure to develop and run binaries.
-
Added first (non-helloworld) binary:
GeniusSquare(see README.md). -
Example execution:
Calling
just run-rust GeniusSquare B1 C4 D6 F1 F2 F3 F5
results in
Roll: B1, C4, D6, F1, F2, F3, F5. Problem: ╔═══╦═══╤═══╤═══╤═══╤═══╤═══╕ ║ ║ A │ B │ C │ D │ E │ F │ ╠═══╬═══╪═══╪═══╪═══╪═══╪═══╡ ║ 1 ║ │ ■ │ │ │ │ ■ │ ╠───╬───┼───┼───┼───┼───┼───┤ ║ 2 ║ │ │ │ │ │ ■ │ ╠───╬───┼───┼───┼───┼───┼───┤ ║ 3 ║ │ │ │ │ │ ■ │ ╠───╬───┼───┼───┼───┼───┼───┤ ║ 4 ║ │ │ ■ │ │ │ │ ╠───╬───┼───┼───┼───┼───┼───┤ ║ 5 ║ │ │ │ │ │ ■ │ ╠───╬───┼───┼───┼───┼───┼───┤ ║ 6 ║ │ │ │ ■ │ │ │ ╙───╨───┴───┴───┴───┴───┴───┘ Compute solution... ...completed in 725.18ms Solution: ╔═══╦═══╤═══╤═══╤═══╤═══╤═══╕ ║ ║ A │ B │ C │ D │ E │ F │ ╠═══╬═══╪═══╪═══╪═══╪═══╪═══╡ ║ 1 ║ 1 │ ■ │ 2 │ 2 │ Z │ ■ │ ╠───╬───┼───┼───┼───┼───┼───┤ ║ 2 ║ L │ X │ X │ Z │ Z │ ■ │ ╠───╬───┼───┼───┼───┼───┼───┤ ║ 3 ║ L │ X │ X │ Z │ T │ ■ │ ╠───╬───┼───┼───┼───┼───┼───┤ ║ 4 ║ L │ L │ ■ │ T │ T │ T │ ╠───╬───┼───┼───┼───┼───┼───┤ ║ 5 ║ 4 │ 4 │ 4 │ 4 │ C │ ■ │ ╠───╬───┼───┼───┼───┼───┼───┤ ║ 6 ║ 3 │ 3 │ 3 │ ■ │ C │ C │ ╙───╨───┴───┴───┴───┴───┴───┘in the console.
Initialised Repository
Initialised repository including
- developer recipes (including unit tests)
- workflows
- an initial solved problem