prob220-shlomif.p6

Source code: prob220-shlomif.p6

#!/usr/bin/env perl6

# The Expat License
#
# Copyright (c) 2018, Shlomi Fish
#
# Permission is hereby granted, free of charge, to any person obtaining a copy
# of this software and associated documentation files (the "Software"), to deal
# in the Software without restriction, including without limitation the rights
# to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
# copies of the Software, and to permit persons to whom the Software is
# furnished to do so, subject to the following conditions:
#
# The above copyright notice and this permission notice shall be included in
# all copies or substantial portions of the Software.
#
# THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
# IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
# FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
# AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
# LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
# OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
# SOFTWARE.

class XY { has $.x = 0; has $.y = 0; };
multi infix:<+> (XY \a, XY \o) {
    a.clone: |([«+»] (a, o)».Capture».hash)
};
multi infix:<-> (XY \a, XY \o) {
    a.clone: |([«-»] (a, o)».Capture».hash)
};
class State {
    has $.cur is rw = XY.new;
    has $.dir1 is rw = 0;
    has $.n is rw = 0;
};
multi infix:<+> (State \a, State \o) {
    a.clone: |([«+»] (a, o)».Capture».hash)
};
multi infix:<-> (State \a, State \o) {
    a.clone: |([«-»] (a, o)».Capture».hash)
};

sub master($maxdepth, $mn)
{
my $s1 = State.new;
my %Cache;
my @dirs = [XY.new(x=> 0, y=> 1), XY.new(x=> 1, y=> 0), XY.new(x=> 0, y=> -1), XY.new(x=> -1, y=> 0) ];
my $printed = False;

sub dragon($depth, $seq)
{
    my $init = $s1.clone;
    my $key = ($depth, $seq, ($s1.dir1 +& 3));
    if ( %Cache{$key}:exists ) {
        my $val = %Cache{$key};
        if $val.n + $s1.n < $mn {
            $s1 = $s1 + $val;
            return;
        }
    }
    for $seq.comb() -> $c {
        if $c eq 'a' {
            if $depth < $maxdepth {
                dragon($depth+1, 'aRbFR')
            }
        }
        elsif $c eq 'b' {
            if $depth < $maxdepth {
                dragon($depth+1, 'LFaLb')
            }
        }
        elsif $c eq 'R' {
            ++$s1.dir1;
        }
        elsif $c eq 'L' {
            --$s1.dir1;
        }
        elsif $c eq 'F' {
            ++$s1.n;
            $s1.cur = $s1.cur + @dirs[$s1.dir1 +& 3];
        }
        else {
            die $c;
            ...;
        }
        if $s1.n >= $mn {
            if $s1.n == $mn {
                if not $printed {
                    printf("cur = %d,%d\n", $s1.cur.x, $s1.cur.y);
                    $printed = True
                }
            }
            return;
        }
    }
    %Cache{$key} = $s1 - $init;
}
dragon(0, 'Fa');
return;
}

master(10, 500);
master(50, 1000000000000);