Commit message (Collapse) | Author | Age | Files | Lines | |
---|---|---|---|---|---|

* | Add basic documentationHEADmaster | Arthur de Jong | 2016-11-13 | 4 | -3/+143 |

| | | | | This also adds copyright headers (MIT license) and renames the module. | ||||

* | Add tests | Arthur de Jong | 2016-11-12 | 1 | -1/+100 |

| | | | | | | This adds a few doctests for the algortihm. Sadly a few of the tests are implementation-specific because for most boards there are a large number of possible equivalent solutions. | ||||

* | Remove scoring | Arthur de Jong | 2016-11-12 | 1 | -14/+1 |

| | | | | | Scoring only improves the performance of finding the first solution by about 2%. | ||||

* | Use queue to do breadth-first traversal | Arthur de Jong | 2016-11-12 | 1 | -23/+20 |

| | | | This results in the best (shortest) solution to be found first and is much quicker in finding all solutions. | ||||

* | Add basic files | Arthur de Jong | 2016-11-12 | 2 | -0/+22 |

| | |||||

* | Try to find shorter paths to previously seen boards | Arthur de Jong | 2016-11-10 | 1 | -3/+5 |

| | | | | | | This results in many more solutions (15k vs around 60 before) and taking around a hundred times longer but it does include the shortest solutions (albeit around the very end of the 15k solutions). | ||||

* | Better way to short-circuit | Arthur de Jong | 2016-11-10 | 1 | -10/+4 |

| | |||||

* | Do not recurse further when we have a solution | Arthur de Jong | 2016-11-10 | 1 | -0/+5 |

| | | | | | | | | | | | | | This saves about 5% in the process time, finds a few less solutions and the average solution length goes down by around 6%. Still still returns a sub-optiomal solution as the shortest. The reason is that non-efficient paths to a certain board configuration may be found first via a long path and will never be re-visited with a shorter path. A better way to do this would be to do a breadth-first search instead of a depth-first one. | ||||

* | Try scoring as a mechanism to find shorter solutions | Arthur de Jong | 2016-11-10 | 1 | -2/+11 |

| | | | | | This increases processing time by about 30% but reduces average solution length by also about 30%. | ||||

* | Support vertical moves and remove print statements | Arthur de Jong | 2016-11-10 | 1 | -12/+17 |

| | |||||

* | Change recursion to return found solutions early | Arthur de Jong | 2016-11-10 | 1 | -8/+16 |

| | |||||

* | Also move cars to the left | Arthur de Jong | 2016-11-10 | 1 | -13/+10 |

| | |||||

* | Correctly find moves to the right | Arthur de Jong | 2016-11-10 | 1 | -20/+34 |

| | |||||

* | Work in progress | Arthur de Jong | 2016-11-10 | 1 | -0/+51 |

| | |||||

* | Initial version of base algorithm | Arthur de Jong | 2016-11-10 | 2 | -0/+57 |

This is just the basic implementation of a backtracking search for a solution and is still lacking the real functionality. |