saylenty / dotsplacementissue

Algorithm solves the problem of the points placement in accordance with the length specified in the matrix

dotsPlacementIssue

Algorithm solves the problem of the points placement according to the length which is specified in the matrix.

Implantation details

The main idea of this algorithm is to try every possible combination of calculated coordinates until the correct answer(s) is found. This is a recursive algorithm with backtracking approach.

Available solvers

• Python implementation - finds the first possible solution
• Java implementation
  • Simple single-thread approach
  • Rotation approach => optimized Simple one
  • Concurrent
    • Based on ForkJoin task - use concurrent technique for solving the task
    • Based on CountedCompleter task - similar to ForkJoin but with minimal interprocess communication

Available visualization

Java implementation has a JavaFX2 visualization:

Example

The following matrix has been specified:

0	2	2	4	4	6	6	8	8	8
2	0	4	2	6	4	8	6	10	8
2	4	0	6	2	8	4	10	6	8
4	2	6	0	8	2	10	4	12	8
4	6	2	8	0	10	2	12	4	8
6	4	8	2	10	0	12	2	14	8
6	8	4	10	2	12	0	14	2	8
8	6	10	4	12	2	14	0	16	8
8	10	6	12	4	14	2	16	0	8
8	8	8	8	8	8	8	8	8	0

Note: Matrix must be symmetric and square one.
We skip the first row and col which are in range [0; <rows_length or cols_length>)
According to the matrix we can say the distance between two dots.
Thus, the distances:

• From point [0] to point [0] = 0 (distance to itself is zero -> obvious)
• From point [0] to point [1] = 2
• Frm point [0] to point [2] = 2
  ...
• 0->9 = 8
• 1->0 = 2
• 1->1 = 0 (distance to itself is zero -> obvious)
  ...

The initial dot 0 always has coordinates (0, 0).
After running the program one of the results is:
[(0, 0), (-1, 1), (1, -1), (-2, 2), (2, -2), (-3, 3), (3, -3), (-3, 5), (5, -3), (4, 4)]
If we visualise the result using Cartesian coordinate system we will get the picture:



Note: Blue color was used to indicate rules of calculating the distance.
Pay attention: The distance is not weight of the line which directly connects two dots (lines may be angular).

dotsplacementissue's Issues

Add unit tests

Create Unit tests for the project using JUnit5 framework.

Doc improvents

Create animation to show how algorithm works in dynamic

Implement RotationPointsFinder

The main idea behind this implementation is to reduce the algorithm complexity using points rotation.

Noticeable that the number of available solutions is always N*4. So that, why not calculate N solutions and then rotate each of them across X and Y axis to get the final answer.