#!/usr/bin/perl -w

# Copyright 2010, 2011, 2012, 2013, 2014 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 warnings;

# uncomment this to run the ### lines
#use Smart::Comments;


{
  # depth_to_n()

  require Math::PlanePath::UlamWarburton;
  my $path = Math::PlanePath::UlamWarburton->new(parts=>'octant');
  for (my $depth = 0; $depth < 35; $depth++) {
    my $n = $path->tree_depth_to_n($depth);
    my ($x,$y) = $path->n_to_xy($n);
    my $rn = $path->xy_to_n($x,$y);
    my $diff = $rn - $n;
    print "$depth $n  $x,$y     $diff\n";
  }
  exit 0;
}

{
  # n_to_depth()                    1       6                16
  #                                 2       7,8              17,18
  #            14                   3       9,10             19,20
  #         15 10 13       20       4,5     11,12,13,14,15
  #       5     8    12    18 
  # 1  2  3  4  6  7  9 11 16 17 19
  # --------------------------
  # 0  1  2  3  4  5  6  7  8

  require Math::PlanePath::UlamWarburton;
  my $path = Math::PlanePath::UlamWarburton->new(parts=>'octant');
  for (my $n = 1; $n <= 35; $n++) {
    my $depth = $path->tree_n_to_depth($n);
    print "$n $depth\n";
  }
  exit 0;
}

{
  # height
  # my $class = 'Math::PlanePath::UlamWarburton';
  # my $class = 'Math::PlanePath::UlamWarburtonQuarter';
  # my $class = 'Math::PlanePath::ToothpickUpist';
   my $class = 'Math::PlanePath::LCornerTree';
  eval "require $class";
  require Math::BaseCnv;
  my $path = $class->new (parts => 1);
  my $prev_depth = 0;
  for (my $n = $path->n_start;; $n++) {
    my $depth = $path->tree_n_to_depth($n);
    my $n_depth = $path->tree_depth_to_n($depth);
    if ($depth != $prev_depth) {
      print "\n";
      last if $depth > 65;
      $prev_depth = $depth;
    }
    my $calc_height = $path->tree_n_to_subheight($n);
    my $search_height = path_tree_n_to_subheight_by_search($path,$n);
    my $n3 = Math::BaseCnv::cnv($n - $n_depth, 10,3);
    $search_height //= 'undef';
    $calc_height //= 'undef';
    my $diff = ($search_height eq $calc_height ? '' : '  ***');
    printf "%2d %2d %3s  %5s %5s%s\n",
      $depth, $n, $n3, $search_height, $calc_height, $diff;
  }
  exit 0;

  sub path_tree_n_to_subheight_by_search {
    my ($self, $n) = @_;
    my @n = ($n);
    my $height = 0;
    for (;;) {
      @n = map {$self->tree_n_children($_)} @n
        or return $height;
      $height++;
      if (@n > 400 || $height > 70) {
        return undef;  # presumed infinite
      }
    }
  }
}

{
  # number of children
  require Math::PlanePath::UlamWarburton;
  require Math::PlanePath::UlamWarburtonQuarter;
  # my $path = Math::PlanePath::UlamWarburton->new;
  my $path = Math::PlanePath::UlamWarburtonQuarter->new;
  my $prev_depth = 0;
  for (my $n = $path->n_start; ; $n++) {
    my $depth = $path->tree_n_to_depth($n);
    if ($depth != $prev_depth) {
      $prev_depth = $depth;
      print "\n";
      last if $depth > 40;
    }
    my $num_children = $path->tree_n_num_children($n);
    print "$num_children,";
  }
  print "\n";
  exit 0;
}
# turn on u(0) = 1
#         u(1) = 1
#         u(n) = 4 * 3^ones(n-1) - 1
# where ones(x) = number of 1 bits   A000120
#
{
  my @yx;
  sub count_around {
    my ($x,$y) = @_;
    return ((!! $yx[$y+1][$x])
            + (!! $yx[$y][$x+1])
            + ($x > 0 && (!! $yx[$y][$x-1]))
            + ($y > 0 && (!! $yx[$y-1][$x])));
  }
  my (@turn_x,@turn_y);
  sub turn_on {
    my ($x,$y) = @_;
    ### turn_on(): "$x,$y"
    if (! $yx[$y][$x] && count_around($x,$y) == 1) {
      push @turn_x, $x;
      push @turn_y, $y;
    }
  }

  my $print_grid = 1;
  my $cumulative = 1;


  my @lchar = ('a' .. 'z');
  $yx[0][0] = $lchar[0];
  for my $level (1 .. 20) {
    print "\n";

    printf "level %d  %b\n", $level, $level;
    if ($print_grid) {
      foreach my $row (reverse @yx) {
        foreach my $cell (@$row) {
          print ' ', (defined $cell #&& ($cell eq 'p' || $cell eq 'o')
                      ? $cell : ' ');
        }
        print "\n";
      }
      print "\n";
    }

    {
      my $count = 0;
      foreach my $row (reverse @yx) {
        foreach my $cell (@$row) {
          $count += defined $cell;
        }
      }
      print "total $count\n";
    }


    foreach my $y (0 .. $#yx) {
      my $row = $yx[$y];
      foreach my $x (0 .. $#$row) {
        $yx[$y][$x] or next;
        ### cell: $yx[$y][$x]

        turn_on ($x, $y+1);
        turn_on ($x+1, $y);
        if ($x > 0) {
          turn_on ($x-1, $y);
        }
        if ($y > 0) {
          turn_on ($x, $y-1);
        }
      }
    }
    print "extra ",scalar(@turn_x),"\n";

    my %seen_turn;
    for (my $i = 0; $i < @turn_x; ) {
      my $key = "$turn_x[$i],$turn_y[$i]";
      if ($seen_turn{$key}) {
        splice @turn_x,$i,1;
        splice @turn_y,$i,1;
      } else {
        $seen_turn{$key} = 1;
        $i++;
      }
    }

    my $e = 4*(scalar(@turn_x)-2)+4;
    $cumulative += $e;
    print "extra $e  cumulative $cumulative\n";
    ### @turn_x
    ### @turn_y
    while (@turn_x) {
      $yx[pop @turn_y][pop @turn_x] = ($lchar[$level]||'z');
    }
    ### @yx
  }
  exit 0;
}