#!/usr/bin/perl -w
# Copyright 2011, 2012, 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/>.
use 5.004;
use strict;
use List::Util 'min', 'max';
use Math::PlanePath::SierpinskiTriangle;
use Math::PlanePath;
*_divrem_mutate = \&Math::PlanePath::_divrem_mutate;
use Math::PlanePath::Base::Digits
'digit_split_lowtohigh',
'digit_join_lowtohigh';
# uncomment this to run the ### lines
use Smart::Comments;
{
# number of children
my $path = Math::PlanePath::SierpinskiTriangle->new;
for (my $n = $path->n_start; $n < 180; $n++) {
my @n_children = $path->tree_n_children($n);
my $num_children = scalar(@n_children);
print "$num_children,";
print "\n" if path_tree_n_is_depth_end($path,$n);
}
print "\n";
exit 0;
sub path_tree_n_is_depth_end {
my ($path, $n) = @_;
my $depth = $path->tree_n_to_depth($n);
return defined($depth) && $n == $path->tree_depth_to_n_end($depth);
}
}
{
# Pascal's triangle
require Math::BigInt;
my @array;
my $rows = 10;
my $width = 0;
foreach my $y (0 .. $rows) {
foreach my $x (0 .. $y) {
my $n = Math::BigInt->new($y);
my $k = Math::BigInt->new($x);
$n->bnok($k);
my $str = "$n";
$array[$x][$y] = $str;
$width = max($width,length($str));
}
}
$width += 2;
if ($width & 1) { $width++; }
# $width |= 1;
foreach my $y (0 .. $rows) {
print ' ' x (($rows-$y) * int($width/2));
foreach my $x (0 .. $y) {
my $value = $array[$x][$y];
unless ($value & 1) { $value = ''; }
printf "%*s", $width, $value;
}
print "\n";
}
exit 0;
}
{
# NumSiblings run lengths
# lowest 1-bit of pos k
# NumChildren run lengths
# is same lowest 1-bit if NumChildren=0 leaf coalesced with NumChildren=1
my $path = Math::PlanePath::SierpinskiTriangle->new (align => 'diagonal');
require Math::NumSeq::PlanePathCoord;
my $seq = Math::NumSeq::PlanePathCoord->new (planepath_object => $path,
# coordinate_type => 'NumChildren',
coordinate_type => 'NumSiblings',
);
my $prev = 0;
my $run = 1;
for (my $n = $path->n_start+1; $n < 500; $n++) {
my ($i,$value) = $seq->next;
$value = 1-$value;
# if ($value == 1) { $value = 0; }
# if ($value == $prev) {
# $run++;
# } else {
# print "$run,";
# $run = 1;
# $prev = $value;
# }
# printf "%4b %d\n", $i, $value;
print "$value,";
}
print "\n";
exit 0;
sub path_tree_n_num_siblings {
my ($path, $n) = @_;
$n = $path->tree_n_parent($n);
return (defined $n
? $path->tree_n_num_children($n) - 1 # not including self
: 0); # any tree root considered to have no siblings
}
}
{
# height
use constant _INFINITY => do {
my $x = 999;
foreach (1 .. 20) {
$x *= $x;
}
$x;
};
my $path = Math::PlanePath::SierpinskiTriangle->new (align => 'diagonal');
require Math::NumSeq::PlanePathCoord;
my $seq = Math::NumSeq::PlanePathCoord->new (planepath_object => $path,
coordinate_type => 'SubHeight');
for (my $n = $path->n_start; $n < 500; $n++) {
my ($x,$y) = $path->n_to_xy($n);
my $s = $seq->ith($n);
# my $c = $path->_UNTESTED__NumSeq__tree_n_to_leaflen($n);
my $c = n_to_subheight($n);
if (! defined $c) { $c = _INFINITY; }
my $diff = ($s == $c ? '' : ' ***');
print "$x,$y $s $c$diff\n";
}
print "\n";
exit 0;
sub n_to_subheight {
my ($n) = @_;
# this one correct based on diagonal X,Y bits
my ($x,$y) = $path->n_to_xy($n);
if ($x == 0 || $y == 0) {
return _INFINITY();
}
my $mx = ($x ^ ($x-1)) >> 1;
my $my = ($y ^ ($y-1)) >> 1;
return max ($mx - ($y & $mx),
$my - ($x & $my));
# Must stretch out $n remainder to make X.
# my ($depthbits, $ndepth, $nwidth) = Math::PlanePath::SierpinskiTriangle::_n0_to_depthbits($n);
# $n -= $ndepth; # X
# my $y = digit_join_lowtohigh ($depthbits, 2, $n*0) - $n;
#
# if ($n == 0 || $y == 0) {
# return undef;
# }
# my $mx = ($n ^ ($n-1)) >> 1;
# my $my = ($y ^ ($y-1)) >> 1;
# return max ($mx - ($y & $mx),
# $my - ($n & $my));
# my $h = high_bit($y);
# my $m = ($h<<1)-1;
# return $y ^ $m;
# # return count_0_bits($y); # - count_0_bits($x);
}
sub high_bit {
my ($n) = @_;
my $bit = 1;
while ($bit <= $n) {
$bit <<= 1;
}
return $bit >> 1;
}
sub count_0_bits {
my ($n) = @_;
my $count = 0;
while ($n) {
$count += ($n & 1) ^ 1;
$n >>= 1;
}
return $count;
}
sub count_1_bits {
my ($n) = @_;
my $count = 0;
while ($n) {
$count += ($n & 1);
$n >>= 1;
}
return $count;
}
}
{
# number of children in replicate style
my $levels = 5;
my $height = 2**$levels;
sub replicate_n_to_xy {
my ($n) = @_;
my $zero = $n * 0;
my @xpos_bits;
my @xneg_bits;
my @y_bits;
foreach my $ndigit (digit_split_lowtohigh($n,3)) {
if ($ndigit == 0) {
push @xpos_bits, 0;
push @xneg_bits, 0;
push @y_bits, 0;
} elsif ($ndigit == 1) {
push @xpos_bits, 0;
push @xneg_bits, 1;
push @y_bits, 1;
} else {
push @xpos_bits, 1;
push @xneg_bits, 0;
push @y_bits, 1;
}
}
return (digit_join_lowtohigh(\@xpos_bits, 2, $zero)
- digit_join_lowtohigh(\@xneg_bits, 2, $zero),
digit_join_lowtohigh(\@y_bits, 2, $zero));
}
# xxx0 = 2 low digit 0 then num children = 2
# xxx0111 = 1 \ low digit != 0 then all low non-zeros must be same
# xxx0222 = 1 /
# other = 0 otherwise num children = 0
sub replicate_tree_n_num_children {
my ($n) = @_;
$n = int($n);
my $low_digit = _divrem_mutate($n,3);
if ($low_digit == 0) {
return 2;
}
while (my $digit = _divrem_mutate($n,3)) {
if ($digit != $low_digit) {
return 0;
}
}
return 1;
}
my $path = Math::PlanePath::SierpinskiTriangle->new;
my %grid;
for (my $n = 0; $n < 3**$levels; $n++) {
my ($x,$y) = replicate_n_to_xy($n);
my $path_num_children = path_xy_num_children($path,$x,$y);
my $repl_num_children = replicate_tree_n_num_children($n);
if ($path_num_children != $repl_num_children) {
print "$x,$y $path_num_children $repl_num_children\n";
exit 1;
}
$grid{$x}{$y} = $repl_num_children;
}
foreach my $y (0 .. $height) {
foreach my $x (-$height .. $y) {
print $grid{$x}{$y} // ' ';
}
print "\n";
}
exit 0;
sub path_xy_num_children {
my ($path, $x,$y) = @_;
my $n = $path->xy_to_n($x,$y);
return (defined $n
? $path->tree_n_num_children($n)
: undef);
}
}
{
my $path = Math::PlanePath::SierpinskiTriangle->new;
foreach my $y (0 .. 10) {
foreach my $x (-$y .. $y) {
if ($path->xy_to_n($x,$y)) {
print "1,";
} else {
print "0,";
}
}
}
print "\n";
exit 0;
}