Skip to content

🚀 Parallelisation + improvements to algorithmic + representations

Latest
Latest

Choose a tag to compare

View all tags
@raj-open raj-open released this 07 Sep 19:31
v0.3.0
2936efc
This commit was created on GitHub.com and signed with GitHub’s verified signature.
GPG key ID: B5690EEEBB952194
Verified
Learn about vigilant mode.

Qualitatively improved the GS algorithm as follows:

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

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

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

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

Assets 2
Loading