Perl Weekly Challenge 059

ch-1.pl

use strict;
use warnings;
##
# Write a script to partition a linked list such that 
# all nodes less than k come before nodes greater than or equal to k.
##
use LinkedList;

MAIN:{
    my $ll = new LinkedList();
    my $next = $ll->insert(1, undef);
    $next = $ll->insert(4, $next);
    $next = $ll->insert(3, $next);
    $next = $ll->insert(2, $next);
    $next = $ll->insert(5, $next);
    $next = $ll->insert(2, $next);
    print $ll->stringify();
    $ll->partition(3);
    print $ll->stringify();
}

ch-2.pl

use strict;
use warnings;
##
# Write a function which returns the count of 
# different bits of the binary representation of 
# positive numbers a and b. The script should 
# accept n positive numbers and sum the result 
# for every pair of numbers given.  
##
sub count_different_bits{
    my($a, $b) = @_;
    my $bits = 0;
    while($a || $b){
        $bits++ if ($a & 1) && !($b & 1);
        $bits++ if !($a & 1) && ($b & 1);
        $a = $a >> 1;
        $b = $b >> 1;
    }
    return $bits;
}

MAIN:{
    my $sum = 0;
    my $line; 
    while($line = <DATA>){
       chomp($line);
       my($a, $b) = split(/,/, $line);
       my $different_bits = count_different_bits($a, $b);
       print "($a, $b) = $different_bits\n";
       $sum += $different_bits; 
    } 
    print "sum of all bit differences: $sum\n"; 
}

__DATA__
2,3
2,4
3,4

LinkedList.pm

use strict;
use warnings;
package LinkedList{
    use boolean;
    use Tie::RefHash;
    use Class::Struct;
    package Node{
        use Class::Struct;

        struct(
            data => q/$/,
            next => q/Node/
        );
    }

    struct(
        head => q/Node/
    );

    sub stringify{
        my($self) = @_;
        my $s = "";
        my $next = $self->head()->next();
        while($next && $next->next()){
            $s .= " -> " if $s; 
            $s = $s . $next->data();
            $next = $next->next();
        }
        $s = $s . " -> " . $next->data() if $next->data();
        $s .= "\n"; 
        return $s;
    }

    sub insert{
        my($self, $data, $previous) = @_;
        if(!$previous){
            $previous=new Node(data => undef, next => undef);
            $self->head($previous);
        }
        my $next=new Node(data => $data, next => undef);
        $previous->next($next);
        return $next;
    }

    sub partition{
        my($self, $k) = @_;
        my $previous = $self->head();
        my $next = $self->head()->next();
        tie my %node_value, "Tie::RefHash";
        while($next){
            if($next->data() < $k){
                $node_value{$next} = $next->data();
                if($next->next()){
                    $previous->next($next->next());
                }
                else{
                    $previous->next(new Node());
                    $next = undef;
                    next;
                }
            }
            $previous = $next;
            $next = $next->next();
        }
        my @sorted_nodes = sort {$node_value{$b} <=> $node_value{$a}} keys %node_value;
        $previous = $self->head();
        my $old_first = $previous->next();
        while(@sorted_nodes){
           my $node = pop @sorted_nodes;
           $previous = insert($self,$node->data(), $previous);
        }
        $previous->next($old_first);
    }
    true;
}