Arthur de Jong

Open Source / Free Software developer

summaryrefslogtreecommitdiffstats
Commit message (Collapse)AuthorAgeFilesLines
* Add basic documentationHEADmasterArthur de Jong2016-11-134-3/+143
| | | | This also adds copyright headers (MIT license) and renames the module.
* Add testsArthur de Jong2016-11-121-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 scoringArthur de Jong2016-11-121-14/+1
| | | | | Scoring only improves the performance of finding the first solution by about 2%.
* Use queue to do breadth-first traversalArthur de Jong2016-11-121-23/+20
| | | This results in the best (shortest) solution to be found first and is much quicker in finding all solutions.
* Add basic filesArthur de Jong2016-11-122-0/+22
|
* Try to find shorter paths to previously seen boardsArthur de Jong2016-11-101-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-circuitArthur de Jong2016-11-101-10/+4
|
* Do not recurse further when we have a solutionArthur de Jong2016-11-101-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 solutionsArthur de Jong2016-11-101-2/+11
| | | | | This increases processing time by about 30% but reduces average solution length by also about 30%.
* Support vertical moves and remove print statementsArthur de Jong2016-11-101-12/+17
|
* Change recursion to return found solutions earlyArthur de Jong2016-11-101-8/+16
|
* Also move cars to the leftArthur de Jong2016-11-101-13/+10
|
* Correctly find moves to the rightArthur de Jong2016-11-101-20/+34
|
* Work in progressArthur de Jong2016-11-101-0/+51
|
* Initial version of base algorithmArthur de Jong2016-11-102-0/+57
This is just the basic implementation of a backtracking search for a solution and is still lacking the real functionality.