#!/usr/bin/perl -W

use Math::BigInt;
use strict;

my $length = int($ARGV[0]);
my $numbit = int($ARGV[1]);

print ">>>>\n";

my @c = manual_slog();

sub manual_slog {
  # This is a slog through, wont work for large numbers.
  my $size = 2**$length;
  my $last = 0;
  my $cast = 0;

  my @coverage;
  my @checks;
  my @cores;

  my @logs;
  # Loop for enough times to fill a binary bit wise for the length of the set input
  for my $i (1..$size) {
    my $bin = sprintf("%0".$length."b", $i);
    # Check to see if it has enough bits in it to be classed == ($numbit)
    my $count = ($bin =~ tr/1//);
    if($count == $numbit) {
      # Any combinations with B as the right most are set starts
      if(substr($bin, length($bin)-1, 1) eq '1') {
        my @results = print_set($bin);
        push @checks, @results;
        if($cast == int(@results)) {
          my $label = log_base(2, $i-$last);
          if($label != int($label)) {
            my $mod = $i-$last-(2**int($label));
            print sprintf("[%02d + %01d] ", $label, $mod);
          } else {
            print sprintf("[%02d    ] ", $label);
          }
        } else {
          my $label = log_base(2, $i-$last);
          my $mod = $i-$last-(2**int($label));
          push @logs, sprintf("<%02d + %01d> ", $label, $mod);
          print sprintf("<%02d + %01d> ", $label, $mod);
        }
        for my $c (@results) {
            print set($c);
        }
        print "\n";
        $cast = int(@results);
        $last = $i;
      }
      # All should be stored for a coverage check
      push @coverage, $bin;
      push @cores, $i;
    }
  }
  # Sanity Checker
  #A: for my $a (@checks) {
  #  B: for my $b (@coverage) {
  #    next A if $a == $b;
  #  }
  #  print "ERROR: Check failed $a\n";
  #}
  print "LOGS: ".join('; ', @logs)."\n\n";
  return @cores;
}

print "----\nNow for the Maths\n----\n";

# All first rows should end up in this array
my @results;

# This should contain the processing stack
my @queue;

my $start_value  = (2 ** $numbit) - 1;
my $start_factor = $numbit - 1;
my $start_level  = $length - $numbit + 1;

push @queue, [ $start_level, $start_factor, $start_value ];

for my $item (@queue) {
  my ($level, $factor, $value) = @{$item};
  #print "Found Item $factor, $level, $value\n";
  for my $x (1..$level) {
    push @results, $value * (2 ** ($x-1));
  }
  #push @results, $value;
  my $next_level = $level - 1;
  if($next_level) {
    foreach my $next_factor (1..$factor) {
      #print "Calculating value ($value * 2) - ((2 ** $next_factor) -1 )\n";
      my $next_value = ($value * 2) - ((2 ** $next_factor) -1);
      push @queue, [ $next_level, $next_factor, $next_value ];
    }
  }
}

print "MATH: ".join(",", sort @results)."\n";

# Manual Checking
my $max = 2**$length;
for my $r (@results) {
  print "A: ABOVE MAX $r > $max\n" and next if $r > $max;
  my $bin = sprintf("%0".$length."b", $r);
  my $count = ($bin =~ tr/1//);
  print "B: TOO MANY SET BITS $r $bin($count) > $numbit\n" and next if $count > $numbit;
}

sub log_base {
  my ($base, $value) = @_;
  return log($value)/log($base);
}

sub _C {
  my ($N, $r) = @_;
  return 1 if $N <= 0 or $r <= 0;
  $N = Math::BigInt->new($N);
  $r = Math::BigInt->new($r);
  my $x = $N->copy()->bsub($r);
  return $N->bfac() / ($r->bfac() * $x->bfac());
}

sub print_set {
  my ($set) = @_;

  my @check = ($set);
  my $scan = $set.$set;

  for my $x (0..length($set)-1) {
    my $r = substr($scan, $x, length($set));
    if(substr($r, length($r)-1, 1) eq substr($set, length($set)-1, 1)) {
      last if $x != 0;
      next;
    }
    push @check, $r;
  }
  return @check;
}

sub set {
  my ($bin) = @_;
  my $num = sprintf("%03d", oct("0b".$bin));
  # AB is easier to see and we're looking at sets not binary
  $bin =~ s/0/A/g;
  my $shadow = $bin;
  $bin =~ s/1/B/g;

  $shadow =~ s/1/0/g;
  $shadow =~ s/A/1/g;
  my $snum = sprintf("%03d", oct("0b".$shadow));
  return $bin." ($num/$snum) ";
}

print "<<<<\n";