#!/usr/bin/perl -w
# Copyright 2011, 2013 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 beta-omega-table.pl
#
# Print the state tables used in BetaOmega.pm.
#
# This isn't a thing of beauty. A state incorporates the beta vs omega
# shape and the orientation of that shape as 4 rotations by 90-degrees, a
# transpose swapping X,Y, and a reversal for numbering points the opposite
# way around.
#
# The reversal is only needed for the beta, as noted in the
# Math::PlanePath::BetaOmega POD. For an omega the reverse is the same as
# the forward. make_state() collapses a reverse omega down to corresponding
# plain forward omega.
#
# State values are 0, 4, 8, etc. Having them 4 apart means a base 4 digit
# from N in n_to_xy() can be added state+digit to make an index into the
# tables.
#
# For @max_digit and @min_digit the input is instead 3*3=9 values, and in
# those tables the index is "state*3 + input". 3*state puts states 12
# apart, which is more than the 9 input values needs, but 3*state is a
# little less work in the code than say (state/4)*9 to change from 4-stride
# to exactly 9-stride.
#
use 5.010;
use strict;
use List::Util 'max';
# 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 " ";
}
}
}
}
sub print_table12 {
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 % 12) == 11) {
print "\n ".(" " x length($name));
} elsif (($i % 4) == 3) {
print " ";
}
}
}
}
my @next_state;
my @digit_to_x;
my @digit_to_y;
my @xy_to_digit;
my @min_digit;
my @max_digit;
sub state_string {
my ($state) = @_;
my $digit = $state % 4; $state = int($state/4);
my $transpose = $state % 2; $state = int($state/2);
my $rot = $state % 4; $state = int($state/4);
my $rev = $state % 2; $state = int($state/2);
my $omega = $state % 2; $state = int($state/2);
my $omega_str = ($omega ? 'omega' : 'beta');
return "$omega_str transpose=$transpose rot=$rot rev=$rev";
}
sub make_state {
my ($omega, $rev, $rot, $transpose, $digit) = @_;
if ($omega && $rev) {
$rev = 0;
if ($transpose) {
$rot--;
} else {
$rot++;
}
$transpose ^= 1;
}
$transpose %= 2;
$rev %= 2;
$rot %= 4;
return $digit + 4*($transpose + 2*($rot + 4*($rev + 2*$omega)));
}
foreach my $omega (0, 1) {
foreach my $rev (0, ($omega ? () : (1))) {
foreach my $rot (0, 1, 2, 3) {
foreach my $transpose (0, 1) {
my $state = make_state ($omega, $rev, $rot, $transpose, 0);
### $state
# range 0 [X,_]
# range 1 [X,X]
# range 2 [_,X]
foreach my $xrange (0,1,2) {
foreach my $yrange (0,1,2) {
my $xr = $xrange;
my $yr = $yrange;
my $bits = $xr + 3*$yr; # before transpose etc
if ($rot & 1) {
($xr,$yr) = ($yr,2-$xr);
}
if ($rot & 2) {
$xr = 2-$xr;
$yr = 2-$yr;
}
if ($transpose) {
($xr,$yr) = ($yr,$xr);
}
if ($rev) {
# 2--1
# | |
# 3 0
$xr = 2-$xr;
}
my ($min_digit, $max_digit);
# 1--2
# | |
# 0 3
if ($xr == 0) {
# 0 or 1 only
if ($yr == 0) {
# x,y both low, 0 only
$min_digit = 0;
$max_digit = 0;
} elsif ($yr == 1) {
# y either, 0 or 1
$min_digit = 0;
$max_digit = 1;
} elsif ($yr == 2) {
# y high, 1 only
$min_digit = 1;
$max_digit = 1;
}
} elsif ($xr == 1) {
# x either, any 0,1,2,3
if ($yr == 0) {
# y low, 0 or 3
$min_digit = 0;
$max_digit = 3;
} elsif ($yr == 1) {
# y either, 0,1,2,3
$min_digit = 0;
$max_digit = 3;
} elsif ($yr == 2) {
# y high, 1,2 only
$min_digit = 1;
$max_digit = 2;
}
} else {
# x high, 2 or 3
if ($yr == 0) {
# y low, 3 only
$min_digit = 3;
$max_digit = 3;
} elsif ($yr == 1) {
# y either, 2 or 3
$min_digit = 2;
$max_digit = 3;
} elsif ($yr == 2) {
# y high, 2 only
$min_digit = 2;
$max_digit = 2;
}
}
### range store: $state+$bits
my $key = 3*$state + $bits;
if (defined $min_digit[$key]) {
die "oops min_digit[] already: state=$state bits=$bits value=$min_digit[$state+$bits], new=$min_digit";
}
$min_digit[$key] = $min_digit;
$max_digit[$key] = $max_digit;
}
}
### @min_digit
foreach my $orig_digit (0, 1, 2, 3) {
my $digit = $orig_digit;
if ($rev) {
$digit = 3-$digit;
}
my $xo = 0;
my $yo = 0;
my $new_transpose = $transpose;
my $new_rot = $rot;
my $new_omega = 0;
my $new_rev = $rev;
if ($omega) {
# 1---2
# | |
# --0 3--
$new_omega = 0;
if ($digit == 0) {
$new_transpose = $transpose ^ 1;
if ($transpose) {
$new_rot = $rot + 1;
} else {
$new_rot = $rot - 1;
}
} elsif ($digit == 1) {
$yo = 1;
if ($transpose) {
$new_rot = $rot - 1;
} else {
$new_rot = $rot + 1;
}
} elsif ($digit == 2) {
$xo = 1;
$yo = 1;
$new_transpose = $transpose ^ 1;
$new_rev ^= 1;
} elsif ($digit == 3) {
$xo = 1;
$new_rot = $rot + 2;
$new_rev ^= 1;
}
} else {
# 1---2
# | |
# --0 3
# |
if ($digit == 0) {
$new_transpose = $transpose ^ 1;
if ($transpose) {
$new_rot = $rot + 1;
} else {
$new_rot = $rot - 1;
}
} elsif ($digit == 1) {
$yo = 1;
if ($transpose) {
$new_rot = $rot - 1;
} else {
$new_rot = $rot + 1;
}
} elsif ($digit == 2) {
$xo = 1;
$yo = 1;
$new_transpose = $transpose ^ 1;
$new_rev ^= 1;
} elsif ($digit == 3) {
$xo = 1;
if ($transpose) {
$new_rot = $rot + 1;
} else {
$new_rot = $rot - 1;
}
$new_omega = 1;
}
}
### base: "$xo, $yo"
if ($transpose) {
($xo,$yo) = ($yo,$xo);
}
### transp to: "$xo, $yo"
if ($rot & 2) {
$xo ^= 1;
$yo ^= 1;
}
if ($rot & 1) {
($xo,$yo) = ($yo^1,$xo);
}
### rot to: "$xo, $yo"
$digit_to_x[$state+$orig_digit] = $xo;
$digit_to_y[$state+$orig_digit] = $yo;
$xy_to_digit[$state + $xo*2+$yo] = $orig_digit;
my $next_state = make_state
($new_omega, $new_rev, $new_rot, $new_transpose, 0);
$next_state[$state+$orig_digit] = $next_state;
}
}
}
}
}
### @next_state
### @digit_to_x
### @digit_to_y
### next_state length: 4*(4*2*2 + 4*2)
### next_state length: scalar(@next_state)
my $next_state_size = scalar(@next_state);
my $state_count = $next_state_size/4;
print "# next_state table has $next_state_size entries, is $state_count states\n";
print_table ("next_state", \@next_state);
print_table ("digit_to_x", \@digit_to_x);
print_table ("digit_to_y", \@digit_to_y);
print_table ("xy_to_digit", \@xy_to_digit);
print_table12 ("min_digit", \@min_digit);
print_table12 ("max_digit", \@max_digit);
my $invert_state = make_state (0, # omega
0, # rev
3, # rot
1, # transpose
0); # digit
### $invert_state
print "\n";
{
my @pending_state = (0);
my $count = 0;
my @seen_state;
my $depth = 0;
$seen_state[0] = $depth;
while (@pending_state) {
$depth++;
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 (! defined $seen_state[$next_state]) {
$seen_state[$next_state] = $depth;
push @new_pending_state, $next_state;
### push: "$next_state depth $depth"
}
}
}
@pending_state = @new_pending_state;
}
for (my $state = 0; $state < @next_state; $state += 4) {
print "# used state $state depth $seen_state[$state]\n";
}
print "used state count $count\n";
}
{
print "\n";
print "initial 0: ",state_string(0),"\n";
print "initial 28: ",state_string(28),"\n";
require Graph::Easy;
my $g = Graph::Easy->new;
for (my $state = 0; $state < scalar(@next_state); $state += 4) {
my $next = $next_state[$state];
$g->add_edge("$state: ".state_string($state),
"$next: ".state_string($next));
}
print $g->as_ascii();
}
exit 0;