2 ms·
Tangential: I once shrunk a representation from 65 bits to 60 - it sped up my program considerably: I wrote a solver (https://github.com/phimuemue/brainball_so
by phimuemue 3y ago
Tangential: I once shrunk a representation from 65 bits to 60 - it sped up my program considerably:
I wrote a solver (https://github.com/phimuemue/brainball_solver https://github.com/phimuemue/brainball_solver) for "brainball" (https://twistypuzzles.com/cgi-bin/puzzle.cgi?pkey=889 https://twistypuzzles.com/cgi-bin/puzzle.cgi?pkey=889), a (rubik-like) puzzle involving 13 cells arranged in a circle.
Each cell has: A number (from 1 to 13). - 4 bits. Two sides colored white resp. yellow. - 1 bit.
The goal is to arrange the cells in number-ascending order, all white sides face up.
Representing each cell would lead to 13*(4+1)=65 bits. A "canonicalized" representation where the cell number 13 is implicitly at a certain position shrinks the representation to 12*(4+1)=60 bits and fits into a 64-bit integer (https://github.com/phimuemue/brainball_solver/blob/master/src/main.rs#L95-L120 https://github.com/phimuemue/brainball_solver/blob/master/sr...).
This was one of the things that made my solver reasonably fast (others were lookup tables (https://github.com/phimuemue/brainball_solver/blob/master/build.rs#L38-L79 https://github.com/phimuemue/brainball_solver/blob/master/bu...), and aggressive function inlining (e.g. https://github.com/phimuemue/brainball_solver/blob/master/src/main.rs#L247-L253 https://github.com/phimuemue/brainball_solver/blob/master/sr...)).