viernes, 24 de octubre de 2014

Project Euler 92 in Perl

Esp: Para no olvidar Perl decidi echarme el Project Euler 92 en Perl. Como en el problema solo puedes moverte hacia abajo o a la derecha, el codigo se vuelve mucho mas simple. De otra manera tendria que implementar Dijkstra en matrices en Perl (demasiado para una noche de ocio despues del trabajo...). Pero bueno aqui les dejo mi solucion:

Eng: Trying not to lose my working knowledge of Perl I decided to write this problem using it. The more general solution is where you can move up, down, left and right in which case you must use Dijkstra's algorithm using a matrix as the data structure. However for this particular problem you can only move down or right which makes it a lot easier. The algorithm just traverses the matrix in diagonal strips and adds its upper and left cell:

 use strict;  
 use warnings;  
 $| = 1; #turn autoflush on  
 use Text::CSV;  
 my @data;  # 2D array for CSV data  
 my $file = 'matrix.txt';  
 my $csv = Text::CSV->new;  
 open my $fh, '<', $file or die "Could not open $file: $!";  
 while( my $row = $csv->getline( $fh ) ) {   
   print join(", ", @$row) ."\n";  
   #shift @$row;    # throw away first value  
   push @data, $row;  
 }  
 my $w = scalar @{$data[0]};  
 for (my $slice = 0; $slice < 2 * $w - 1; ++$slice) {  
  my $z = $slice < $w ? 0 : $slice - $w + 1;  
  for (my $j = $z; $j <= $slice - $z; ++$j) {  
   my $x = $j;  
   my $y = $slice - $j;  
   my $val = $data[$x][$y];  
   if($x - 1 <= 0 && $y - 1 >= 0){  
    $val += ($data[$x-1][$y] > $data[$x][$y-1])?$data[$x][$y-1]:$data[$x-1][$y];  
   } else {  
    if($x - 1 >= 0){  
     $val += $data[$x-1][$y];  
    }  
    if($y - 1 >= 0){  
     $val += $data[$x][$y-1];  
    }  
   }  
   print "x: $x, y: $y, data: $data[$x][$y], val: $val\n";  
   $data[$x][$y] = $val;  
  }  
 }  
 for (my $i = 0; $i < $w; $i++){  
  for(my $j = 0; $j < $w; $j++){  
   print $data[$i][$j] ." ";  
  }  
  print "\n";  
 }  
 print "res: " . $data[$w-1][$w-1];  

No hay comentarios:

Publicar un comentario