GDD2011quiz_tree.pl

#!/usr/bin/perl

use strict;
use Data::Dumper;

open my $FH,"<prob";

my @depths;
my ($i,$j);

$i = 0;
while (<$FH>) {
	chomp;
	if ($i == 0) {
		#print "test cases count: ", my $testcases = $_, "\n";
	}
	elsif ($i % 2 != 0) {
		$j++;
		#print "test case ($j)\t";
	}
	else {
		my @prob = split(/\s/,$_);
		#print "numbers: ", my $nums = $_, "\n";
		solve(@prob);
	}
	$i++;
}

sub solve {
	@depths = ();
	create_root(@_);
	print min(@depths)."\n";
}

sub create_root {
	my %tree;
	$tree{'data'} = \@_;
	$tree{'depth'} = 1;
	$tree{'left'} = create_node(1,filter_all(@_));
	$tree{'right'} = create_node(1,half_all(@_));
	return \%tree;
}

sub create_node {
	my $tdepth = shift;
	if (not defined $_[0]) {
		return $_[0];
	}
	elsif ($_[0] == -1) {
		push(@depths,$tdepth);
		return $_[0];
	}
	my %pos;
	$pos{'data'} = \@_;
	$pos{'depth'} = ++$tdepth;
	$pos{'left'} = create_node($tdepth,filter_all(@_));
#	if ( != -1) {
		$pos{'right'} = create_node($tdepth,half_all(@_));
#	}
	return \%pos;	
}

sub filter_all {
	my $cnt = $#_;
	my @new_ary;
	my $solved = 0;
	foreach my $n (@_) {
		if ($n % 5 == 0 || $n == 0) {
			#print "$depth\n" if $cnt == 0;
			#print "$depth\n";
			$solved = 1;
		}
		else {
			$solved = 0;
			push(@new_ary,$n);
		}
	}
	return undef if is_same(\@_,\@new_ary);
	if ($#new_ary < 0) {
#		push(@depths,$depth);
		if ($solved == 1) {
			return (-1);
		}
	}
	return @new_ary;
}

sub half_all {
	my @ary = @_;
#	return -1 if $#_ < -1;
	my $zero_division = 1;

	my @new_ary = map {
		my $answer;
		if ($_ != 0) {
			$answer = int($_ / 2);
			$zero_division = 0;
		}
		else {
			$answer = $_;
		}
		$answer;
	} @ary;

	if ($zero_division == 1) {
		return undef;
	}
	return @new_ary;
}

sub is_same {
	my($a,$b) = @_;
	
	return 0 if @$a != @$b;
	
	for (0..$#$a){
		return 0 if $a->[$_] != $b->[$_];
	}
	
	return 1;
}

sub min {
    my $min_num;
    
    foreach my $num ( @_ ){
        if( !defined( $min_num ) ){
            $min_num = $num;
        }
        else{
            if( $num < $min_num ){
                $min_num = $num;
            }
        }
    }
    return $min_num;
}