use strict;
use warnings;

#use Math::Random qw(random_uniform random_set_seed_from_phrase random_binomial random_set_seed);
#use Math::Random qw(random_binomial random_set_seed);
#use Data::Dumper;
#use List::Util qw(sum shuffle);
use List::Util qw(sum);
use Carp;
#use Crypt::Random qw( makerandom );
#use File::Slurp; #for large list of real randoms

#my @rands = read_file('rand.txt');
#print sum(@rands), "\n";
#croak;
#my $r = makerandom ( Size => 10, Strength => 1 );
#print $r;
#croak;

#random_set_seed_from_phrase(2);
#my @seed = (1 + int(rand(2147483562)), 1 + int(rand(2147483398)));
#random_set_seed(@seed);
#my @a = random_uniform($n);
#my $runs = 1000;
#my $counter = 1; # global: subroutine entry counter
my $counter = 0; # global: subroutine entry counter
#increment($runs, \@rands);
start();

sub start {
#	my $runs = 1000;
#	my $runs = 1;
#	my $n = 2**8;
#	my $n = 2**3;
#	for my $n (1..12) {
	my $aref = [];
	my $param = shift @ARGV;
	$param ||= 8;

	for my $n (1..$param) {
#		increment($runs, $n);
#		increment($runs, 2**$n);
#		$aref = increment($runs, 2**$n, $aref);
		$aref = increment($aref);
	}
}

sub increment {
#	my ($runs, $randsref) = @_;
#	my ($runs, $n, $aref) = @_;
	my ($aref) = @_;
#	my (@axis, @data);
#	my @axis = 0;
#	my @data = 1;
#	my $start = 16655;
#	my $end = 16675;
#	my $start = 1;
#	my $start = 0;
#	my $end = 100;
#	my $end = 255;
#	my $end = $n;
#	my $total = 0;
#	my @a;
#	for my $inc (16655..16675) {
#	for my $inc ($start..$end) {

#		my @seed = (1 + int(rand(2147483562)), 1 + int(rand(2147483398)));
#		random_set_seed(@seed);
	#	my $counter = 0;
		my $av = 0;
#		my $p = $inc/100;

#		my %a = perms($inc, $n);
		$aref = perms($aref);
#		@a = perms(@a);
#print Dumper $aref;
	#	my @a = keys perms($inc, $n);
	#print join('', @a), "\n";
#		my @a = map {$_} keys %a;
#		print join("\n", @a), "\n";
		my %splits;

		for (@$aref) {
#		for (1..$runs) {
#			my $p = $inc/100;
#			my $p = $inc/100000;
#			$counter = 1;
			$counter = 0;
	#		my $p = 0.002374;
#			countit($p, $randsref);
#			countit($p, $n);
#			countit($inc, $n);
			my @bits = split '', $_;
			my $sum = sum(@bits);
#			countit(split '', $_);
			countit(@bits);
			$splits{$sum} += $counter; 
			$av += $counter;
	#		$counter = 0;
#			$counter = 1;
		}

		print $_, ' ', $splits{$_}, "\n" for sort {$a <=> $b} keys %splits;
#		print $inc/100, ' ', sprintf("%.1f", $av/$runs), "\n";
#		print $inc, ' ', sprintf("%.1f", $av/$runs), "\n";
#		print $inc, ' ', $av, "\n";
#		push @axis, $inc/100;# if $inc/10 == int($inc/10);
#		push @axis, $inc;
#		push @data, sprintf("%.1f", $av/$runs);
#		$total += $av;

#	}
	
#	print "$total\n";
	print "$av\n";
#	dograph(\@axis, \@data, $start, $end);
	return $aref;
}

sub countit {
	my (@a) = @_;
#	my ($inc, $n) = @_;
#	my ($p, $n) = @_;
#	my ($p, $randsref) = @_;
#	my $nt = 1;
#	my $n = 2**8;
#	my @seed = (1 + int(rand(2147483562)), 1 + int(rand(2147483398)));
#	random_set_seed(@seed);
#	my @a = random_binomial($n, $nt, $p);
#	my $bits = 10;
#	my $r = makerandom ( Size => $bits, Strength => 1 );
#	my $divfactor = 2**$bits;
#	my $pmult = $p*$divfactor;
#	my @a = map {makerandom ( Size => $bits, Strength => 1 ) > $pmult ? 0 : 1} 1..$n;
#print Dumper @a;
#print "pmult $pmult\n";
#print makerandom ( Size => $bits, Strength => 1 ), "\n";
#croak;
#	my @a = map {rand > $p ? 0 : 1} 1..$n;
#	my @string = split '', join '', 1 x $inc, 0 x ($n - $inc);
#print "$string/n";
#	my @a = shuffle map { split '', $string } 1..$n;
#	my @a = shuffle @string;
#	my %a = perms($inc, $n);
#	my @a = keys perms($inc, $n);
#print join('~', @a), "\n";
#	my @a = map {$_} keys %a;
#print join("\n", @a), "\n";
#	my @a = map {(rand > $p)} 1..$n;
#	print $offset*$n, "\n";
#	my $r = shift @rands;
#print "$r, $p\n";
#	my @a = map {shift(@rands) > $p ? 0 : 1} 1..$n;

# my @a = makedist($n, $randsref, $p);

#	@a = (0, 1, 0, 0, 0, 0, 1, 0);
	my %h = map {$_ => 0} 0..$#a;

#	print Dumper @a;
#croak;
#	print Dumper %h;
#	print "bs\n";
#	if (sum(@a) > 0) {
#		my %temp = map {$h{$_} == 1} keys %h;
#		%h = %temp;
#		$counter++;
#	} else {
#		$counter++;
		binary_search(\@a, 0, \%h);
		my @misses = grep {$h{$_} != 1} keys %h;
		if (scalar @misses) {
			print join('', $_, ' ', $misses[$_], "\n") for @misses;
			croak "missed some\n";
		}
#	}
#	my @misses = grep {$h{$_} != 1} keys %h;
#	croak "missed some\n/" if scalar @misses;

#	print "bs over $counter\n";
#	print Dumper %h;
#	print Dumper @misses;
}

use POSIX qw(floor ceil);

sub binary_search {
  my ($aref, $pos, $href) = @_;
	$counter++;
#print scalar @$aref;
#print " $pos \n";
#print Dumper $aref;
#  my $mid;
#	my @aref = @$aref;
	my $bigness = scalar(@$aref);
	if ($bigness == 1) {
		$href->{$pos}++;
	} else {
		my $mid = $bigness/2; # for two there is equality
		if (sum(@$aref) > 0) {
		  my @aref1 = @$aref[ceil($mid)..$#$aref];
#		  my @aref1 = @$aref[$mid..$#$aref];
#	  	binary_search(\@aref1, $mid+$pos, $href);
		  binary_search(\@aref1, ceil($mid)+$pos, $href);
#		  my @aref2 = @$aref[0..--$mid];
			my $thismid = floor($mid) == $mid ? $mid-1 : floor($mid);
#		  my @aref2 = @$aref[0..--$mid];
#		  my @aref2 = @$aref[0..(floor($mid)-1)];
		  my @aref2 = @$aref[0..$thismid];
		  binary_search(\@aref2, $pos, $href);
		} else {
			$href->{$_}++ for $pos..$pos+$bigness-1;			
		}
	}
}

sub makedist {
	my ($n, $randsref, $p) = @_;
	my @a;

	for (1..$n) {
		my $thisone = shift @$randsref;
		my $bit = $thisone > $p ? 0 : 1;
		push @a, $bit;
	}

	return @a;
}

sub dograph {
#	my ($axisref, $dataref, $p, $n) = @_;
	my ($axisref, $dataref, $start, $end) = @_;
#	use GD::Graph::bars;
	use GD::Graph::points;
	use GD::Graph::Data;
	#use Carp;

	#my $data = GD::Graph::Data->new([
	#    ["1st","2nd","3rd","4th","5th","6th","7th", "8th", "9th"],
	#    [    1,    2,    5,    6,    3,  1.5,    1,     3,     4],
	#]) or croak GD::Graph::Data->error;

#	my $data = GD::Graph::Data->new([\@xaxis, \@data]) or croak GD::Graph::Data->error;
	my $data = GD::Graph::Data->new([$axisref, $dataref]) or croak GD::Graph::Data->error;

#	my $graph = GD::Graph::lines->new(800, 600);
#	my $graph = GD::Graph::bars->new(800, 600);
	my $graph = GD::Graph::points->new(800, 600);

	$graph->set( 
	#    x_label         => 'X Label',
	#    y_label         => 'Y label',
#		title           => $p,
		transparent     => 0,
		t_margin				=> 10,
		b_margin				=> 10,
		l_margin				=> 10,
		r_margin				=> 10,
#		y_max_value     => 520,
		y_max_value     => 528,
#		y_max_value     => 0.2,
#		y_min_value     => -0.2,
		y_min_value     => 0,
#		y_label_skip		=> 10
#		x_label_skip		=> 10,
		x_label_skip		=> 4,
#		y_tick_number		=> 16,
#		y_tick_number		=> 8,
		y_tick_number		=> 33,
#		x_tick_number		=> 10,
#		x_tick_number		=> 26,
		markers					=> 8,
		marker_size			=> 2,
		long_ticks			=> 1,
#		x_max_value			=> 1,
		x_min_value     => 0,
	) or croak $graph->error;
	 
	$graph->plot($data) or croak $graph->error;
	 
	my $file = "bars$start-$end.png";
#	my $file = $n."bars$p.png";
	#my $file = "barssplicy$p.png";
	open(my $out, '>', $file) or croak "Cannot open '$file' for write: $!";
	binmode $out;
	print $out $graph->gd->png;
	close $out;

#	use GD::Graph::lines;
	use GD::Graph::points;
}

use Algorithm::Permute;
 
# default is to create n of n objects permutation generator
#my $p = Algorithm::Permute->new(\@string);

sub perms {
	my $perms = shift;
	return [0, 1] unless scalar @$perms;
	my @aperm = map {"0$_"} @$perms;
	my @bperm = map {"1$_"} @$perms;
	return [@aperm, @bperm];
}

sub permsolder {
	my ($inc, $n) = @_;

	my @string = split '', join '', 1 x $inc, 0 x ($n - $inc);
	#print join('', @string), "\n\n";
	my $p = Algorithm::Permute->new(\@string);
	my %h;

	while (my @res = $p->next) {
		my $string = join('', @res);
		$h{$string} = 0;
	}

	#	print "$_\n" for keys %h;
	#	print "\n";
	return %h;
}

use Math::Combinatorics;

sub permsold {
	my ($inc, $n) = @_;

	my @string = split '', join '', 1 x $inc, 0 x ($n - $inc);
	#print join('', @string), "\n\n";my @n = qw(a b c);
	my $combinat = Math::Combinatorics->new(count => scalar @string, data => [@string]);
	my %h;
#print "starting next_permutation\n";
#my $count = 0;
	while(my @permu = $combinat->next_permutation) {
#print $count++, "\n";
		my $string = join('', @permu);
		$h{$string} = 0;
	}

	#	print "$_\n" for keys %h;
	#	print "\n";
	return %h;
}