my @tilings = tile(4);
print map { my $x = $_; $x->[1].$x->[2] } @tilings;
print scalar(@tilings)," total\n";

sub tile($) {
    my $n = shift;
    return ([0,"\n","\n\n"]) unless $n>0;
    my @a = map { vertical($_) } tile($n-1);
    push @a, map { horizontal($_) } tile($n-2) if $n>=2;
    return @a;
}

sub vertical($) {
    my $s = shift;
    my ($k,$t,$b) = @$s;
    $k++;
    $t = "$k$t";
    $b = "$k$b";
    return [$k,$t,$b];
}

sub horizontal($) {
    my $s = shift;
    my ($k,$t,$b) = @$s;
    $k++;
    $t = "$k$k$t";
    $k++;
    $b = "$k$k$b";
    return [$k,$t,$b];
}