Skip to content

Instantly share code, notes, and snippets.

@jhunt
Created May 5, 2012 03:03
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
Star You must be signed in to star a gist
Save jhunt/2599305 to your computer and use it in GitHub Desktop.
Working solution in O(n) time and constant space for Canz' "Brawler's Puzzler"
#!/usr/bin/perl
sub fisher_yates_shuffle
{
my $array = shift;
my $i;
for ($i = @$array; --$i; ) {
my $j = int rand ($i+2);
next if $i == $j;
@$array[$i,$j] = @$array[$j,$i];
}
}
sub sequence
{
my ($n) = @_;
my $seq = [];
for (my $i = 1; $i <= $n; $i++) {
push @$seq, $i;
}
fisher_yates_shuffle($seq);
my $mis, $dup;
{
use integer;
$dup = rand($n);
do {
$mis = rand($n);
} while ($mis == $dup);
}
$seq->[$mis] = $seq->[$dup];
return $seq;
}
sub print_seq
{
my ($seq) = @_;
print join(" ", @$seq), "\n";
print join(" ", sort { $a <=> $b } @$seq), "\n";
}
my $N = shift(@ARGV) || 15;
my $seq = sequence($N);
# May want to comment this one out for larger runs
print_seq($seq);
# scaffold above
# ----------------8<----------------------------
# solution below
for (my $i = 0; $i < @$seq; $i++) {
if ($seq->[abs($seq->[$i])-1] > 0) {
$seq->[abs($seq->[$i])-1] *= -1;
} else {
print abs($seq->[$i]), " is duplicated\n";
}
}
for (my $i = 0; $i < @$seq; $i++) {
if ($seq->[$i] > 0) {
print $i+1, " is missing\n";
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment