#!/usr/bin/perl -w

use Time::HiRes qw(gettimeofday tv_interval);
use strict;

sub MakeStrings
{
  my $c = shift;

  my @res;

  for my $i(1..$c)
  {
    my @bits;
    for my $j(1..504)
    {
      my $bit = int(rand(2));
      push @bits, $bit;
    }
    push @res, \@bits;
  }
  return \@res;
}

sub HammDist
{
  my ($str1, $str2) = @_;

  my $count = 0;
  map { $count += ($str1->[$_] != $str2->[$_]) } (0..$#$str1);

  return $count;
}

sub MaxDistSlow
{
  my $strings = shift;

  my ($m1, $m2);
  my $dist = -1;

  for my $i(0..$#$strings)
  {
    for my $j($i+1..$#$strings)
    {
      my $d = HammDist( $strings->[$i], $strings->[$j] );
      if( $d > $dist )
      {
        $dist = $d;
        $m1 = $i;
        $m2 = $j;
      }
    }
  }
  return($m1,$m2,$dist);
}

sub MaxDistFast
{
  my $strings = shift;
 
  my $m1 = 0;
  my $m2 = 1;
  my $dist = -1;

  for my $i (2..$#$strings)
  {
    my $d1 = HammDist( $strings->[$i], $strings->[$m1] );
    my $d2 = HammDist( $strings->[$i], $strings->[$m2] );

    my $m = ($d1 > $d2) ? $m1 : $m2;
    my $d = ($d1 > $d2) ? $d1 : $d2;
    
    if( $d > $dist )
    {
      $dist = $d;
      $m1 = $i;  
      $m2 = $m;
    }
  }
  return($m1,$m2,$dist);
}

sub main
{
  my $strings = MakeStrings(128);

  my $t0 = [gettimeofday];
  my @res1 = MaxDistSlow($strings);
  my $t1 = [gettimeofday];
  my @res2 = MaxDistFast($strings);
  my $t2 = [gettimeofday];

  print "Slow: ", join(",",@res1), " <=> Fast: ", join(",",@res2), "\n";
  printf "Slow: %.2f, Fast: %.2f\n", tv_interval($t0, $t1), tv_interval($t1,$t2);
}
main();
