4 ms·
Solver and solutions: https://gist.github.com/CyberShadow/39f43cf25dac0534f8a9 https://gist.github.com/CyberShadow/39f43cf25dac0534f8a9 The solver uses BFS wi
by CyberShadow 12y ago
Solver and solutions:
https://gist.github.com/CyberShadow/39f43cf25dac0534f8a9 https://gist.github.com/CyberShadow/39f43cf25dac0534f8a9
The solver uses BFS with delayed duplicate detection for pruning visited states (instead of, say, hash tables).
The DDD part can be summed up in two lines of code:
prevStates = (prevStates ~ states).sort.uniq.array();
states = nextStates.sort.uniq.setDifference(prevStates).array();
// ... expand states into nextStates ...
These were part of the solver's code at one point, although now I've expanded them a bit to improve memory efficiency.
I love D.
- teawithcarl 12y agoNice work.
- andor 12y agoDDD was new to me, and I was wondering how sorting all previously visited states could be faster than checking a hash table. The answer appears to be: 1. Duplicate detection is done delayed and in bulk, not after expanding each node 2. The linear memory access of the bulk check is more cache friendly than random-like hash table access Allow me to quote from the first Google result: Surprisingly, delayed duplicate detection is useful even when all nodes fit in memory, resulting in reduced running time due to improved cache performance. In the standard implementation of breadth-first search in memory, the Open list is stored in a hash table. As each new node is generated, it is looked up in the hash table, which often results in a cache miss, since the hash function is designed to randomly scatter the nodes. http://www.ijcai.org/Past%20Proceedings/IJCAI-2003/PDF/267.pdf http://www.ijcai.org/Past%20Proceedings/IJCAI-2003/PDF/267.p...
- Monkeyget 12y agoI wrote a solver as a chrome extension : https://github.com/tburette/gameaboutsquaressolver https://github.com/tburette/gameaboutsquaressolver Javascript is not the best language to write AI.