view release on metacpan or  search on metacpan

devel/one-of-eight.pl  view on Meta::CPAN

  }
  exit 0;
}


{
  # tree_depth_to_n() of 2^k
  #  1       1
  #  2       9
  #  4      33
  #  8     121
  # 16     465

  # total(1) = 1
  # total(2^k) = total(2^(k-1)) + 101010...1010101011000
  #            = total(2^(k-1)) + (4*4^k + 8)/3
  # k=1 total(2) = 1 + (4*4^1 + 8)/3 =
  #
  # k=16 total(16) = 121 + (4*4^4+8)/3 = 465
  # add   101011000
  #         1011000
  #           11000
  #            1000
  #               1
  #
  # total(2^k) = (4*4^k + 8)/3 + ... + (4*4^1 + 8)/3 + 1
  #            = (4*4^k + 8 + ... + 4*4^1 + 8)/3 + 1
  #            = (4*4^k + ... + 4*4^1  + 8*k)/3 + 1
  #            = (4*(4^k + ... + 4^1)  + 8*k)/3 + 1
  #            = (4*(4*4^k - 4)/3  + 8*k)/3 + 1
  #            = (16*(4^k - 1)/3  + 8*k)/3 + 1
  #            = (16*(4^k - 1) + 3*8*k)/9 + 1
  #            = (16*4^k - 16 + 3*8*k)/9 + 1
  #            = (16*4^k + 3*8*k - 16 + 9)/9
  #            = (16*4^k + 24*k - 7)/9

  # quarter
  # (total(2^k)-1)/4
  #    = ((16*4^k + 24*k - 7)/9 - 1) /4
  #    = (16*4^k + 24*k - 16)/9/4
  #    = (4*4^k + 6*k - 4)/9

  require Math::PlanePath::OneOfEightByCells;
  require Math::BaseCnv;
  my $c = Math::PlanePath::OneOfEightByCells->new;
  my $p = Math::PlanePath::OneOfEightByCells->new;
  my $prev_n = 0;
  for (my $k = 1; $k <= 16; $k++) {
    my $depth = 2**$k;

    my $n = $c->tree_depth_to_n($depth);
    my $n2 = Math::BaseCnv::cnv($n,10,2);

    my $pn = $p->tree_depth_to_n($depth);

    my $calc = (16*4**$k + 24*$k - 7) / 9;

    my $delta = $n - $prev_n;
    my $d2 = Math::BaseCnv::cnv($delta,10,2);

    printf "%5d path=%8d formula=%8d cells=%8d %20s\n",
      $depth, $pn, $calc, $n, $n2;
    # printf "%5d %8d  %20s\n", $depth, $delta, $d2;
    $prev_n = $n;
  }
  exit 0;
}
{
  # rect_to_n_range() on 2^k

  require Math::PlanePath::OneOfEight;
  require Math::PlanePath::OneOfEightByCells;
  my $c = Math::PlanePath::OneOfEightByCells->new;
  my $p = Math::PlanePath::OneOfEight->new;
  foreach my $k (0 .. 10) {
    my $depth = 2**$k;
    my $c_hi = $c->tree_depth_to_n($depth);

    my $x = my $y = 2**$k-1;
    my ($p_lo, $p_hi) = $p->rect_to_n_range(0,0,$x,$y);

    print "$k  $c_hi $p_hi\n";
  }
  exit 0;
}
{
  # side depth to N
  #
  # delta
  #  2        1                     1
  #  4        5                   101
  #  8       21                 10101
  # 16       85               1010101
  # 32      341             101010101
  #
  # total
  #   2        1                     1
  #   4        6                   110
  #   8       27                 11011
  #  16      112               1110000
  #  32      453             111000101
  #  64     1818           11100011010
  # 128     7279         1110001101111
  #
  # side(2^k) = (4^k-1)/3 + ... + 1
  #           = (4^k + ... + 1 - k)/3
  #           = ((4*4^k - 1)/3 0 k)/3
  #           = (4*4^k - 3*k - 1)/9
  #
  require Math::PlanePath::OneOfEightByCells;
  require Math::BaseCnv;
  require Math::BigRat;
  my $path = Math::PlanePath::OneOfEightByCells->new;
  my $prev_n = 0;

  for (my $k = 1; $k <= 16; $k++) {
    my $depth = 2**$k;

    my $n = 0;
    foreach my $x (0 .. $depth-1) {
      foreach my $y ($depth .. 2*$depth-1) {