News for hackers. Stuff that matters.
Re:Game about squares by CyberShadow on Monday July 28, 2014 @02:19AM (#8095454)
Solver and solutions:

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.

Re:Game about squares by andor on Monday July 28, 2014 @08:55AM (#8096404)
DDD 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.p...

Re:Game about squares by Monkeyget on Monday July 28, 2014 @04:18PM (#8099104)
I wrote a solver as a chrome extension : https://github.com/tburette/gameaboutsquaressolver

Javascript is not the best language to write AI.

Re:Game about squares by teawithcarl on Monday July 28, 2014 @03:02AM (#8095530)
Nice work.