Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
Perl Weekly Challenge 059
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();
}
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
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;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment