#!/usr/bin/perl -w
# Copyright 2011, 2012 Kevin Ryde
# This file is part of Math-PlanePath.
#
# Math-PlanePath is free software; you can redistribute it and/or modify it
# under the terms of the GNU General Public License as published by the Free
# Software Foundation; either version 3, or (at your option) any later
# version.
#
# Math-PlanePath is distributed in the hope that it will be useful, but
# WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
# or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
# for more details.
#
# You should have received a copy of the GNU General Public License along
# with Math-PlanePath. If not, see <http://www.gnu.org/licenses/>.
# Usage: perl alternate-paper-midpoint.pl
#
# Print state tables used by Math::PlanePath::AlternatePaperMidpoint.
#
use 5.010;
use strict;
# uncomment this to run the ### lines
#use Smart::Comments;
sub print_table {
my ($name, $aref) = @_;
print "my \@$name = (";
my $entry_width = max (map {length($_//'')} @$aref);
foreach my $i (0 .. $#$aref) {
printf "%*s", $entry_width, $aref->[$i]//'undef';
if ($i == $#$aref) {
print ");\n";
} else {
print ",";
if (($i % 16) == 15
|| ($entry_width >= 3 && ($i % 4) == 3)) {
print "\n ".(" " x length($name));
} elsif (($i % 4) == 3) {
print " ";
}
}
}
}
my @next_state;
my @state_to_dxdy;
sub make_state {
my %param = @_;
my $state = 0;
$state <<= 1; $state |= delete $param{'nextturn'}; # high
$state <<= 2; $state |= delete $param{'rot'};
$state <<= 1; $state |= delete $param{'prevbit'};
$state <<= 2; $state |= delete $param{'digit'}; # low
if (%param) { die; }
return $state;
}
sub state_string {
my ($state) = @_;
my $digit = $state & 3; $state >>= 2;
my $prevbit = $state & 1; $state >>= 1;
my $rot = $state & 3; $state >>= 2;
my $nextturn = $state & 1; $state >>= 1;
return "rot=$rot prevbit=$prevbit (digit=$digit)";
}
foreach my $nextturn (0, 1) {
foreach my $rot (0, 1, 2, 3) {
foreach my $prevbit (0, 1) {
my $state = make_state (nextturn => $nextturn,
rot => $rot,
prevbit => $prevbit,
digit => 0);
### $state
foreach my $digit (0 .. 3) {
my $new_nextturn = $nextturn;
my $new_prevbit = $digit;
my $new_rot = $rot;
if ($digit != $prevbit) { # count 0<->1 transitions
$new_rot++;
$new_rot &= 3;
}
# nextturn from bit above lowest 0
if ($digit == 0) {
$new_nextturn = $prevbit ^ 1;
} elsif ($digit == 1) {
$new_nextturn = $prevbit;
} elsif ($digit == 2) {
$new_nextturn = 0; # 1-bit at odd position
}
my $dx = 1;
my $dy = 0;
if ($rot & 2) {
$dx = -$dx;
$dy = -$dy;
}
if ($rot & 1) {
($dx,$dy) = (-$dy,$dx); # rotate +90
}
### rot to: "$dx, $dy"
my $next_dx = $dx;
my $next_dy = $dy;
if ($nextturn) {
($next_dx,$next_dy) = ($next_dy,-$next_dx); # right, rotate -90
} else {
($next_dx,$next_dy) = (-$next_dy,$next_dx); # left, rotate +90
}
my $frac_dx = $next_dx - $dx;
my $frac_dy = $next_dy - $dy;
my $masked_state = $state & 0x1C;
$state_to_dxdy[$masked_state] = $dx;
$state_to_dxdy[$masked_state + 1] = $dy;
$state_to_dxdy[$masked_state + 2] = $frac_dx;
$state_to_dxdy[$masked_state + 3] = $frac_dy;
my $next_state = make_state
(nextturn => $new_nextturn,
rot => $new_rot,
prevbit => $new_prevbit,
digit => 0);
$next_state[$state+$digit] = $next_state;
}
}
}
}
### @next_state
### @state_to_dxdy
### next_state length: 4*(4*2*2 + 4*2)
print "# next_state length ", scalar(@next_state), "\n";
print_table ("next_state", \@next_state);
print_table ("state_to_dxdy", \@state_to_dxdy);
print "\n";
{
my @pending_state = (0, 4, 8, 12); # in 4 arm directions
my $count = 0;
my @seen_state;
my $depth = 1;
foreach my $state (@pending_state) {
$seen_state[$state] = $depth;
}
while (@pending_state) {
my @new_pending_state;
foreach my $state (@pending_state) {
$count++;
### consider state: $state
foreach my $digit (0 .. 3) {
my $next_state = $next_state[$state+$digit];
if (! $seen_state[$next_state]) {
$seen_state[$next_state] = $depth;
push @new_pending_state, $next_state;
### push: "$next_state depth $depth"
}
}
$depth++;
}
@pending_state = @new_pending_state;
}
for (my $state = 0; $state < @next_state; $state += 2) {
$seen_state[$state] ||= '-';
my $state_string = state_string($state);
print "# used state $state depth $seen_state[$state] $state_string\n";
}
print "used state count $count\n";
}
exit 0;
# # lowdigit
# # my @state_to_dx = (1,1,0,0,
# # -1,-1,0,1,
# # -1,0,0,0,
# # 1,0,0,1,
# # );
# # my @state_to_dy = (0,0,1,1,
# # 0,0,-1,0,
# # 0,1,1,1,
# # 0,-1,-1,0,
# # );
#
# my @state_to_dx = (1,1,0,0,
# -1,-1,0,1,
# -1,0,0,0,
# 1,0,0,1,
# );
# my @state_to_dy = (0,0,1,1,
# 0,0,-1,0,
# 0,1,1,1,
# 0,-1,-1,0,
# );
#
# #use Smart::Comments;
#
# sub n_to_dxdy {
# my ($self, $n) = @_;
# ### AlternatePaperMidpoint n_to_dxdy(): $n
#
# if ($n < 0) { return; }
# if (is_infinite($n)) { return ($n, $n); }
#
# my $arm = _divrem_mutate ($n, $self->{'arms'});
# ### $arm
# ### $n
#
# my @digits = digit_split_lowtohigh($n,4);
# while (@digits >= 2 && $digits[0] == 3) { # strip low 3s
# shift @digits;
# }
# my $state = 0;
# my $lowdigit = (shift @digits || 0);
# foreach my $digit (reverse @digits) { # high to low
# $state = $next_state[$state+$digit];
# }
# ### $state
# # ### $lowdigit
# $state += $lowdigit;
# my $dx = $state_to_dx[$state];
# my $dy = $state_to_dy[$state];
#
# if ($arm & 1) {
# ($dx,$dy) = ($dy,$dx); # transpose
# }
# if ($arm & 2) {
# ($dx,$dy) = (-$dy,$dx); # rotate +90
# }
# if ($arm & 4) {
# $dx = - $dx; # rotate 180
# $dy = - $dy;
# }
#
# # ### rotated return: "$dx,$dy"
# return ($dx,$dy);
# }
#
#
# no Smart::Comments;