Working solution in O(n) time and constant space for Canz' "Brawler's Puzzler"

brawlers-puzzler.pl

#!/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";
    }
}