#!/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 3

# must be xxx.xxx.xxx.xxx
sub validate
{
  if ($_[0] =~ /^[0-9]+\.[0-9]+\.[0-9]+\.[0-9]+$/)
  {
    my ($tmp1, $tmp2, $tmp3, $tmp4) = split(/\./, $_[0], 4);
    return ($tmp1 <= 255 && $tmp2 <= 255 && $tmp3 <= 255 && $tmp4 <= 255);
  }

  return 0;
}

# convert to int
sub aton
{
  my $n = 0;
  my ($tmp1, $tmp2, $tmp3, $tmp4) = split(/\./, $_[0], 4);

  $n += $tmp1 << 24;
  $n += $tmp2 << 16;
  $n += $tmp3 << 8;
  $n += $tmp4;

  return $n;
}

# return true if the first arg3 bits of arg1 and arg2 matches
sub match
{
  my $addr1 = aton($_[0]);
  my $addr2 = aton($_[1]);
  my $mask = 0xffffffff << $_[2];

  return (($addr1 & $mask) == ($addr2 & $mask));
}

# array, element
sub isin
{
  my ($larr, $item) = @_;

  foreach my $citem (@$larr)
  {
    if ($item == $citem)
    {
      return 1;
    }
  }

  return 0;
}

# curr, dest, ref to table, ref to result, ref to callstack
sub pathfind
{
  my ($curr, $dest, $lrtab, $lpath, $lstack) = @_;

  if ($curr == $dest)
  {
    push(@$lpath, $lrtab->{$curr}[1]);
    return 1;
  }

  for(my $i = 0, my $hop = 0; $i < scalar @{$lrtab->{$curr}[2]} && !$hop; $i++)
  {
    my $cond = $lrtab->{$curr}[2][$i][0];
    my $gw   = $lrtab->{$curr}[2][$i][1];
    my $len  = $lrtab->{$curr}[2][$i][2];

    # check if this is the default route, or if addr/mask matches
    if (length($cond) == 0 || match($dest, $cond, $len))
    {
      # check if we've been through this node before
      if (!isin($lstack, $gw))
      {
        my $res;
        
        push(@$lstack, $curr);
        $res = pathfind($gw, $dest, $lrtab, $lpath, $lstack);
        pop(@$lstack);
        
        if ($res)
        {
          $hop = 1;
          push(@$lpath, $lrtab->{$curr}[1]);
          return 1;
        }
      }
    }
  }
  return 0;
}

sub tabread
{
  my ($lrtab) = @_;

  while(my $line = <STDIN>)
  {
    my @aline;

    $line =~ s/	+/ /g;
    $line =~ s/ +/ /g;
    $line =~ s/ => /=>/g;

    chomp($line);

    if (length($line) > 1)
    {
      @aline = split(/ /, $line);

      if (!validate($aline[1]))
      {
        return 0;
      }
      
      $lrtab->{$aline[1]}[0] = $aline[1];
      $lrtab->{$aline[1]}[1] = $aline[0];
      
      for (my $i = 2; $i < @aline; $i++)
      {
        my ($tmp1, $tmp2) = split(/=>/, $aline[$i]);
      
        if (length($tmp2) != 0)
        {
          my ($tmp3, $tmp4) = split(/\//, $tmp1);

          if (!validate($tmp3) || !validate($tmp2) || $tmp4 < 0 || $tmp4 > 32)
          {
            return 0;
          }

          $lrtab->{$aline[1]}[2][$i - 2] = [ $tmp3, $tmp2, $tmp4 ];
        }
        else
        {
          if (!validate($tmp1))
          {
            return 0;
          }

          $lrtab->{$aline[1]}[2][$i - 2] = [ "", $tmp1, 0 ];
        }
      }
    }
  }

  return 1;
}

my @path;
my %rtab;
my @stack;

if (@ARGV != 2 || !validate($ARGV[0]) || !validate($ARGV[1]))
{
  printf(STDERR "usage: $0 <start ipaddr> <destination ipaddr>\n");
  exit 1;
}

if (!tabread(\%rtab))
{
  printf(STDERR "parse error\n");
  exit 2;
}

if ($rtab{$ARGV[0]} == "" || $rtab{$ARGV[1]} == "")
{
  printf(STDERR "start or destination ipaddr is not in route table\n");
  exit 3;
}

if (!pathfind($ARGV[0], $ARGV[1], \%rtab, \@path, \@stack))
{
  printf(STDERR "no route to %s\n", $ARGV[1]);
  exit 4;
}

while(my $node = pop(@path))
{
  printf("%s", $node);
}

printf("\n");

exit 0;