#!/usr/bin/perl
#
# This program is free software; you can redistribute it and/or modify
# it under the terms of the GNU General Public License as published by
# the Free Software Foundation; either version 3 of the License, or
# (at your option) any later version.
#
# This program is distributed in the hope that it will be useful,
# but WITHOUT ANY WARRANTY; without even the implied warranty of
# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
# GNU General Public License for more details.
#
# You should have received a copy of the GNU General Public License
# along with this program.  If not, see <http://www.gnu.org/licenses/>.
#
# Copyright (C) 2008 Vino Fernando Crescini  <vfcrescini@gmail.com>

# Google Treasure Hunt 2008 Puzzle 4

use strict;
use bigint;

# we assume that the file contains a list of prime numbers, one prime per
# line, and that they're sorted in ascending order
sub get_primes
{
  my ($lparray, $fname) = @_;

  if (!open(FH, "<", $fname))
  {
    return 0;
  }

  # instead of just loading the primes, we load the partial sums
  while(my $line = <FH>)
  {
    if (!(scalar @$lparray))
    { 
      push(@$lparray, $line);
    }
    else
    {
      push(@$lparray, $line + $lparray->[$#{$lparray}]);
    }
  }

  close(FH);
  return 1;
}

# naive, obviously
sub is_prime
{
  my $num = $_[0];
  my $sqrt = int sqrt($num);

  if ($num <= 1)
  {
    return 0;
  }

  if ($num <= 3)
  {
    return 1;
  }

  if (($num % 2) == 0 || ($num % 3) == 0)
  {
    return 0;
  }

  for (my $i = 1; 1; $i++)
  {
    my $t1 = (6 * $i) + 1;
    my $t2 = (6 * $i) - 1;

    if (($t1 <= $sqrt && ($num % $t1) == 0) || ($t2 <= $sqrt && ($num % $t2) == 0))
    {
      return 0;
    }

    if ($t1 > $sqrt && $t2 > $sqrt)
    {
      return 1;
    }
  }
}

# return the sum of the first n prime numbers starting from offset
sub sum_primes
{
  my ($lparray, $offset, $n) = @_;

  return $lparray->[$n + $offset - 1] - ($offset ? $lparray->[$offset - 1] : 0);
}

# find the smallest prime number that can be expressed as the sum of
# A0, A1, A2, ..., An consecutive prime numbers
sub solve
{
  my ($lparray, $lnarray, $sum, $verbose) = @_;
  my $isum = 0;
  my $n;

  if (!scalar(@{$lnarray}))
  {
    return $sum;
  }

  $n = pop(@$lnarray);

  for(my $i = 0, my $stop = 0; $i < ($#{$lparray} - $n) && !$stop; $i++)
  {
    $isum = sum_primes($lparray, $i, $n);

    if (!$sum)
    {
      # first time
      if (is_prime($isum))
      {
        $verbose && printf("  found prime %s at %s\n", $isum, $n);

        if (solve($lparray, $lnarray, $isum, $verbose))
        {
          # finally!
          return $isum;
        }
      }
    }
    else
    {
      # not the first call so we need not check for primality
      if ($isum == $sum)
      {
        $verbose && printf("  matched %s at %s\n", $isum, $n);

        if (solve($lparray, $lnarray, $isum, $verbose))
        {
          return $isum;
        }
      }

      # there is really no point to go on if we exceed the number
      if ($isum > $sum)
      {
        $verbose && printf("  exceeded %s at %s\n", $isum, $n);
        $stop = 1;
      }
    }
  }

  # if we got here, we've exhausted all the primes
  # so put it back
  $verbose && printf("  no match for %s at %s\n", $isum, $n);
  push(@$lnarray, $n);

  return 0;
}

my @parray;
my @narray;

if (@ARGV < 2)
{
  printf(STDERR "usage: $0 <primes filename> <n1> [<n2> [...]]\n");
  exit 1;
}

for (my $i = 0; $i < @ARGV - 1; $i++)
{
  if ($ARGV[$i + 1] !~ m/^[1-9][0-9]*$/)
  {
    printf(STDERR "\"%s\" is not a positive integer\n", $ARGV[$i + 1]);
    exit 2;
  }

  push(@narray, int $ARGV[$i + 1]);
}

if (!get_primes(\@parray, $ARGV[0]))
{
  printf(STDERR "can't open \"%s\" for reading\n", $ARGV[0]);
  exit 3;
}

@narray = sort { $a <=> $b } @narray;

printf("%s\n", solve(\@parray, \@narray, 0, ($ENV{'DEBUG'} != 0)));

exit 0;