Skip to content

Instantly share code, notes, and snippets.

@masak

masak/filtering-out.p6 Secret

Last active August 29, 2015 14:15
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save masak/81409152053431cac80b to your computer and use it in GitHub Desktop.
Save masak/81409152053431cac80b to your computer and use it in GitHub Desktop.
Download ZIP
Filtering out grids with fundamental cycles, leaving only the 4x4 mazes
Raw
filtering-out.p6
# bitstring; positions 0..11 correspond to vertical walls; 12..23 to horizontal;
# RAKUDO: can't do `0 x 24` here: RT #123602
my $s = "000000000000000111111111";
# These bitmasks were generated from
# https://gist.github.com/masak/66735ee4c40a5d5c2eee -- but they were also
# sorted by increasing count of 1s.
#
# .say for lines.sort({ +.comb(/1/) })
#
# This because of the supposition that cycles with few walls occur more often,
# and therefore checking for them first lets us finish faster.
#
# And it did help, a little. It brought the runtime on my laptop down from 47
# minutes to 38 minutes.
my @cycles =
0b000000000001000000000001,
0b000000000100000000001000,
0b001000000000000100000000,
0b100000000000100000000000,
0b000000000010000000000011,
0b000000000010000000001100,
0b000000000011000000000010,
0b000000000110000000000100,
0b000000001000000000010001,
0b000000001001000000010000,
0b000000100000000010001000,
0b000000100100000010000000,
0b000001000000000100010000,
0b000100000000100010000000,
0b001001000000000000010000,
0b010000000000001100000000,
0b010000000000110000000000,
0b011000000000001000000000,
0b100100000000000010000000,
0b110000000000010000000000,
0b000000000000000000001111,
0b000000000000000011110000,
0b000000000000111100000000,
0b000000000001000000001110,
0b000000000100000000000111,
0b000000000101000000000110,
0b000000001010000000010010,
0b000000010010000000110000,
0b000000010010000011000000,
0b000000011000000000100010,
0b000000100010000010000100,
0b000000110000000001000100,
0b000001001000000100000001,
0b000001001001000100000000,
0b000011000000001000100000,
0b000100100000100000001000,
0b000100100100100000000000,
0b000110000000010001000000,
0b001000000000111000000000,
0b001001001000000000000001,
0b001001001001000000000000,
0b010001000000001000010000,
0b010010000000000000110000,
0b010010000000000011000000,
0b010010010010000000000000,
0b010100000000010010000000,
0b100000000000011100000000,
0b100100100000000000001000,
0b100100100100000000000000,
0b101000000000011000000000,
0b000000001000000000011110,
0b000000001000000011100001,
0b000000001001000011100000,
0b000000001100000000010110,
0b000000010000000000110011,
0b000000010000000000111100,
0b000000010000000011000011,
0b000000010000000011001100,
0b000000010001000000110010,
0b000000010001000011000010,
0b000000010100000000110100,
0b000000010100000011000100,
0b000000011010000000100001,
0b000000011011000000100000,
0b000000100000000001111000,
0b000000100000000010000111,
0b000000100001000010000110,
0b000000100100000001110000,
0b000000110010000001001000,
0b000000110110000001000000,
0b000001000000000111100000,
0b000001000000111000010000,
0b000001001010000100000010,
0b000001010010000100100000,
0b000010000000001100110000,
0b000010000000001111000000,
0b000010000000110000110000,
0b000010000000110011000000,
0b000010010010001100000000,
0b000010010010110000000000,
0b000100000000011110000000,
0b000100000000100001110000,
0b000100010010100001000000,
0b000100100010100000000100,
0b001001000000000011100000,
0b001001001010000000000010,
0b001001010010000000100000,
0b001010000000001000110000,
0b001010000000001011000000,
0b001010010010001000000000,
0b001100000000011010000000,
0b010001001000001000000001,
0b010001001001001000000000,
0b010010001000000000100001,
0b010010001001000000100000,
0b010010010000000000000011,
0b010010010000000000001100,
0b010010010001000000000010,
0b010010010100000000000100,
0b010010100000000001001000,
0b010010100100000001000000,
0b010011000000000100100000,
0b010100100000010000001000,
0b010100100100010000000000,
0b010110000000100001000000,
0b011011000000000000100000,
0b100001000000011000010000,
0b100010000000010000110000,
0b100010000000010011000000,
0b100010010010010000000000,
0b100100000000000001110000,
0b100100010010000001000000,
0b100100100010000000000100,
0b110110000000000001000000,
0b000000001010000011100010,
0b000000011000000000101101,
0b000000011000000011010010,
0b000000011001000000101100,
0b000000011100000000100101,
0b000000011101000000100100,
0b000000100010000001110100,
0b000000101000000001100110,
0b000000101000000001101001,
0b000000101000000010010110,
0b000000101001000001101000,
0b000000101100000001100001,
0b000000101101000001100000,
0b000000110000000001001011,
0b000000110000000010110100,
0b000000110001000001001010,
0b000000110100000001000011,
0b000000110101000001000010,
0b000001001000000100001110,
0b000001001000111000000001,
0b000001001001111000000000,
0b000001001100000100000110,
0b000001010000000100100011,
0b000001010000000100101100,
0b000001010001000100100010,
0b000001010100000100100100,
0b000001100000000101101000,
0b000001100100000101100000,
0b000010001000001100100001,
0b000010001000110000100001,
0b000010001001001100100000,
0b000010001001110000100000,
0b000010010000001100000011,
0b000010010000001100001100,
0b000010010000110000000011,
0b000010010000110000001100,
0b000010010001001100000010,
0b000010010001110000000010,
0b000010010100001100000100,
0b000010010100110000000100,
0b000010100000001101001000,
0b000010100000110001001000,
0b000010100100001101000000,
0b000010100100110001000000,
0b000011000000001011010000,
0b000011000000110100100000,
0b000011010010001000010000,
0b000011011000001000000010,
0b000100001000100001100001,
0b000100001001100001100000,
0b000100010000100001000011,
0b000100010000100001001100,
0b000100010001100001000010,
0b000100010100100001000100,
0b000100100000011100001000,
0b000100100000100000000111,
0b000100100001100000000110,
0b000100100100011100000000,
0b000101000000011001100000,
0b000101000000011010010000,
0b000101000000100101100000,
0b000110000000010010110000,
0b000110000000101101000000,
0b000110010010010010000000,
0b000110110000010000000100,
0b001001001000000000001110,
0b001001001100000000000110,
0b001001010000000000100011,
0b001001010000000000101100,
0b001001010001000000100010,
0b001001010100000000100100,
0b001001100000000001101000,
0b001001100100000001100000,
0b001010001000001000100001,
0b001010001001001000100000,
0b001010010000001000000011,
0b001010010000001000001100,
0b001010010001001000000010,
0b001010010100001000000100,
0b001010100000001001001000,
0b001010100100001001000000,
0b001011000000110000100000,
0b001100100000011000001000,
0b001100100100011000000000,
0b001101000000100001100000,
0b001110000000101001000000,
0b010001000000001011100000,
0b010001001010001000000010,
0b010001010010001000100000,
0b010010001010000000100010,
0b010010011000000000010010,
0b010010100010000001000100,
0b010010110000000010000100,
0b010100000000010001110000,
0b010100010010010001000000,
0b010100100010010000000100,
0b100001001000011000000001,
0b100001001001011000000000,
0b100010001000010000100001,
0b100010001001010000100000,
0b100010010000010000000011,
0b100010010000010000001100,
0b100010010001010000000010,
0b100010010100010000000100,
0b100010100000010001001000,
0b100010100100010001000000,
0b100011000000010100100000,
0b100100001000000001100001,
0b100100001001000001100000,
0b100100010000000001000011,
0b100100010000000001001100,
0b100100010001000001000010,
0b100100010100000001000100,
0b100100100000000000000111,
0b100100100001000000000110,
0b100101000000000101100000,
0b100110000000001101000000,
0b101011000000010000100000,
0b101101000000000001100000,
0b101110000000001001000000,
0b000000001000000011101110,
0b000000001100000011100110,
0b000000100000000001110111,
0b000000100001000001110110,
0b000000101010000001100101,
0b000000101010000001101010,
0b000000101011000001100100,
0b000000101110000001100010,
0b000000111000000001011010,
0b000000111000000010100101,
0b000000111001000010100100,
0b000000111100000001010010,
0b000001000000111011100000,
0b000001001010111000000010,
0b000001010010111000100000,
0b000001011000000111000010,
0b000001100010000101100100,
0b000001101000000110000110,
0b000001110000000110100100,
0b000010001010001100100010,
0b000010001010110000100010,
0b000010011000001100010010,
0b000010011000110000010010,
0b000010100010001101000100,
0b000010100010110001000100,
0b000010110000001110000100,
0b000010110000110010000100,
0b000011001000001011000001,
0b000011001001001011000000,
0b000011010000001000010011,
0b000011010000001000011100,
0b000011010001001000010010,
0b000011010100001000010100,
0b000011011010001000000001,
0b000011011011001000000000,
0b000011100000001001011000,
0b000011100100001001010000,
0b000100000000011101110000,
0b000100001010100001100010,
0b000100010010011101000000,
0b000100011000100001010010,
0b000100100010011100000100,
0b000100101000100000010110,
0b000100110000100000110100,
0b000101001000011010000001,
0b000101001001011010000000,
0b000101100000011000011000,
0b000101100100011000010000,
0b000110001000010010100001,
0b000110001001010010100000,
0b000110010000010010000011,
0b000110010000010010001100,
0b000110010001010010000010,
0b000110010100010010000100,
0b000110100000010000111000,
0b000110100100010000110000,
0b000110110010010000001000,
0b000110110110010000000000,
0b000111000000010110100000,
0b000111000000101001010000,
0b001001011000000011000010,
0b001001100010000001100100,
0b001001101000000010000110,
0b001001110000000010100100,
0b001010001010001000100010,
0b001010011000001000010010,
0b001010100010001001000100,
0b001010110000001010000100,
0b001100000000011001110000,
0b001100010010011001000000,
0b001100100010011000000100,
0b001111000000010010100000,
0b010001001000001000001110,
0b010001001100001000000110,
0b010001010000001000100011,
0b010001010000001000101100,
0b010001010001001000100010,
0b010001010100001000100100,
0b010001100000001001101000,
0b010001100100001001100000,
0b010010001000000000101110,
0b010010001100000000100110,
0b010010100000000001000111,
0b010010100001000001000110,
0b010011011000000100000010,
0b010100001000010001100001,
0b010100001001010001100000,
0b010100010000010001000011,
0b010100010000010001001100,
0b010100010001010001000010,
0b010100010100010001000100,
0b010100100000010000000111,
0b010100100001010000000110,
0b010101000000010101100000,
0b010101000000101001100000,
0b010110110000100000000100,
0b011011011000000000000010,
0b011101000000010001100000,
0b100001000000011011100000,
0b100001001010011000000010,
0b100001010010011000100000,
0b100010001010010000100010,
0b100010011000010000010010,
0b100010100010010001000100,
0b100010110000010010000100,
0b100100001010000001100010,
0b100100011000000001010010,
0b100100101000000000010110,
0b100100110000000000110100,
0b100111000000001001010000,
0b110101000000001001100000,
0b110110110000000000000100,
0b000001001000111000001110,
0b000001001100111000000110,
0b000001010000111000100011,
0b000001010000111000101100,
0b000001010001111000100010,
0b000001010100111000100100,
0b000001100000000101100111,
0b000001100000111001101000,
0b000001100001000101100110,
0b000001100100111001100000,
0b000001111000000101001010,
0b000001111100000101000010,
0b000010001000001100101110,
0b000010001000110000101110,
0b000010001100001100100110,
0b000010001100110000100110,
0b000010100000001101000111,
0b000010100000110001000111,
0b000010100001001101000110,
0b000010100001110001000110,
0b000011001010001011000010,
0b000011011000001000001101,
0b000011011000110100000010,
0b000011011001001000001100,
0b000011011100001000000101,
0b000011011101001000000100,
0b000011100010001001010100,
0b000011101000001001000110,
0b000011101000001001001001,
0b000011101001001001001000,
0b000011101100001001000001,
0b000011101101001001000000,
0b000011110000001010010100,
0b000100001000011101100001,
0b000100001000100001101110,
0b000100001001011101100000,
0b000100001100100001100110,
0b000100010000011101000011,
0b000100010000011101001100,
0b000100010001011101000010,
0b000100010100011101000100,
0b000100100000011100000111,
0b000100100001011100000110,
0b000100111000100000100101,
0b000100111001100000100100,
0b000101001010011010000010,
0b000101010010011001010000,
0b000101010010011010100000,
0b000101011000011001000010,
0b000101011000100101000010,
0b000101100010011000010100,
0b000101101000011000000110,
0b000101101000011000001001,
0b000101101000100100000110,
0b000101101001011000001000,
0b000101101100011000000001,
0b000101101101011000000000,
0b000101110000011000100100,
0b000101110000100100100100,
0b000110001010010010100010,
0b000110011000010010010010,
0b000110100010010000110100,
0b000110101000010000100110,
0b000110101000010000101001,
0b000110101001010000101000,
0b000110101100010000100001,
0b000110101101010000100000,
0b000110110000010000001011,
0b000110110000101100000100,
0b000110110001010000001010,
0b000110110100010000000011,
0b000110110101010000000010,
0b000111001000101001000001,
0b000111001001101001000000,
0b000111100000010100101000,
0b000111100100010100100000,
0b001001100000000001100111,
0b001001100001000001100110,
0b001001111000000001001010,
0b001001111100000001000010,
0b001010001000001000101110,
0b001010001100001000100110,
0b001010100000001001000111,
0b001010100001001001000110,
0b001011011000110000000010,
0b001100001000011001100001,
0b001100001001011001100000,
0b001100010000011001000011,
0b001100010000011001001100,
0b001100010001011001000010,
0b001100010100011001000100,
0b001100100000011000000111,
0b001100100001011000000110,
0b001101011000100001000010,
0b001101101000100000000110,
0b001101110000100000100100,
0b001110110000101000000100,
0b001111100000010000101000,
0b001111100100010000100000,
0b010001011000001011000010,
0b010001100010001001100100,
0b010001101000001010000110,
0b010001110000001010100100,
0b010010101000000001010110,
0b010010101000000010100110,
0b010100001010010001100010,
0b010100011000010001010010,
0b010100101000010000010110,
0b010100110000010000110100,
0b100001001000011000001110,
0b100001001100011000000110,
0b100001010000011000100011,
0b100001010000011000101100,
0b100001010001011000100010,
0b100001010100011000100100,
0b100001100000011001101000,
0b100001100100011001100000,
0b100010001000010000101110,
0b100010001100010000100110,
0b100010100000010001000111,
0b100010100001010001000110,
0b100011011000010100000010,
0b100100001000000001101110,
0b100100001100000001100110,
0b100100111000000000100101,
0b100100111001000000100100,
0b100101011000000101000010,
0b100101101000000100000110,
0b100101110000000100100100,
0b100110110000001100000100,
0b100111001000001001000001,
0b100111001001001001000000,
0b101011011000010000000010,
0b101101011000000001000010,
0b101101101000000000000110,
0b101101110000000000100100,
0b101110110000001000000100,
0b000001011000111011000010,
0b000001100010111001100100,
0b000001101000111010000110,
0b000001110000111010100100,
0b000010101000001101010110,
0b000010101000001110100110,
0b000010101000110001010110,
0b000010101000110010100110,
0b000011001000001011001110,
0b000011001100001011000110,
0b000011100000001001010111,
0b000011100001001001010110,
0b000011101010001001000101,
0b000011101010001001001010,
0b000011101011001001000100,
0b000011101110001001000010,
0b000011111000001010000101,
0b000011111001001010000100,
0b000100001010011101100010,
0b000100011000011101010010,
0b000100101000011100010110,
0b000100110000011100110100,
0b000101001000011010001110,
0b000101001100011010000110,
0b000101010000011001010011,
0b000101010000011001011100,
0b000101010000011010100011,
0b000101010000011010101100,
0b000101010001011001010010,
0b000101010001011010100010,
0b000101010100011001010100,
0b000101010100011010100100,
0b000101011010011001000001,
0b000101011011011001000000,
0b000101100000011000010111,
0b000101100001011000010110,
0b000101101010011000000101,
0b000101101010011000001010,
0b000101101011011000000100,
0b000101101110011000000010,
0b000101110010011000101000,
0b000101110110011000100000,
0b000110001000010010101110,
0b000110001100010010100110,
0b000110100000010000110111,
0b000110100001010000110110,
0b000110101010010000100101,
0b000110101010010000101010,
0b000110101011010000100100,
0b000110101110010000100010,
0b000110111000010000011010,
0b000110111100010000010010,
0b000111001010101001000010,
0b000111011000010110000010,
0b000111100010010100100100,
0b000111110000101000010100,
0b001010101000001001010110,
0b001010101000001010100110,
0b001100001010011001100010,
0b001100011000011001010010,
0b001100101000011000010110,
0b001100110000011000110100,
0b001111011000010010000010,
0b001111100010010000100100,
0b010001100000001001100111,
0b010001100001001001100110,
0b010001111000001001001010,
0b010001111100001001000010,
0b010011101000000101000110,
0b010100001000010001101110,
0b010100001100010001100110,
0b010100111000010000100101,
0b010100111001010000100100,
0b010101011000010101000010,
0b010101011000101001000010,
0b010101101000010100000110,
0b010101101000101000000110,
0b010101110000010100100100,
0b010101110000101000100100,
0b010110101000100000100110,
0b011011101000000001000110,
0b011101011000010001000010,
0b011101101000010000000110,
0b011101110000010000100100,
0b100001011000011011000010,
0b100001100010011001100100,
0b100001101000011010000110,
0b100001110000011010100100,
0b100010101000010001010110,
0b100010101000010010100110,
0b100111001010001001000010,
0b100111110000001000010100,
0b110101011000001001000010,
0b110101101000001000000110,
0b110101110000001000100100,
0b110110101000000000100110,
0b000001100000111001100111,
0b000001100001111001100110,
0b000001111000111001001010,
0b000001111100111001000010,
0b000011101000110101000110,
0b000100001000011101101110,
0b000100001100011101100110,
0b000100111000011100100101,
0b000100111001011100100100,
0b000101011000011001001101,
0b000101011001011001001100,
0b000101011100011001000101,
0b000101011101011001000100,
0b000101110000011000101011,
0b000101110001011000101010,
0b000101110100011000100011,
0b000101110101011000100010,
0b000110101000101100100110,
0b000111001000101001001110,
0b000111001100101001000110,
0b000111100000010100100111,
0b000111100001010100100110,
0b000111111000010100001010,
0b000111111000101000000101,
0b000111111001101000000100,
0b000111111100010100000010,
0b001011101000110001000110,
0b001100001000011001101110,
0b001100001100011001100110,
0b001100111000011000100101,
0b001100111001011000100100,
0b001110101000101000100110,
0b001111100000010000100111,
0b001111100001010000100110,
0b001111111000010000001010,
0b001111111100010000000010,
0b100001100000011001100111,
0b100001100001011001100110,
0b100001111000011001001010,
0b100001111100011001000010,
0b100011101000010101000110,
0b100110101000001100100110,
0b100111001000001001001110,
0b100111001100001001000110,
0b100111111000001000000101,
0b100111111001001000000100,
0b101011101000010001000110,
0b101110101000001000100110,
;
MAZE:
repeat until $s eq "1" x 9 ~ "0" x 15 {
# this is a quick way to find the next bitstring with the same amount of 1s
# trick learned long ago from http://blog.plover.com/CS/parentheses.html
$s ~~ s[ .* <( 01 (.*) ] = "10" ~ $0.comb.sort.join;
my $n = :2($s);
for @cycles -> $c {
next MAZE
if $n +& $c == $c;
}
say $s;
}
# real 38m15.813s
# user 37m29.623s
# sys 0m6.537s
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment