Euler #13, #14, #15 y #16

https://projecteuler.net/problem=13

Problema trivial, se resuelve en una sola línea Python:

   1 input = [37107287533902102798797998220837590246510135740250,
   2 46376937677490009712648124896970078050417018260538,
   3 74324986199524741059474233309513058123726617309629,
   4 91942213363574161572522430563301811072406154908250,
   5 23067588207539346171171980310421047513778063246676,
   6 89261670696623633820136378418383684178734361726757,
   7 28112879812849979408065481931592621691275889832738,

 ... 
 100 53503534226472524250874054075591789781264330331690]
 101 
 102 print str(sum(input))[0:10]

---

https://projecteuler.net/problem=14

En PHP:

   1 <?php
   2 
   3 function generateCollatz($num) {
   4   $ret = array($num);
   5   $next = end($ret);
   6   while (true) {
   7     $next = $next % 2 == 0 ? $next / 2 : 3*$next + 1;
   8     $ret []= $next;
   9     if ($next == 1) break;
  10   }
  11   return $ret;
  12 }
  13 
  14 
  15 $longest = 1;
  16 $maxCount = 0;
  17 for ($x = 1; $x < 1000000; $x++) {
  18   $collatz = generateCollatz($x);
  19   $nCollatz = count($collatz);
  20   if ($nCollatz > $maxCount) {
  21     $longest = $x;
  22     $maxCount = $nCollatz;
  23     echo "El número $x tiene $nCollatz términos\n";
  24   }
  25 
  26 }
  27 

---

https://projecteuler.net/problem=15

En Python, implementación recursiva. No es muy buena para valores muy grandes. De hecho, tras varias horas de ejecución, el script no termina.

   1 nPaths = 0;
   2 def move_point(point, limit):
   3     global nPaths
   4     if point == limit:
   5         # print("Finished!")
   6         nPaths += 1
   7     if point[1] < limit[1]:
   8         # Continue down...
   9         new_point = (point[0], point[1]+1)
  10         # print("From", point, "to", new_point)
  11         move_point(new_point, limit)
  12         # And lets go right too
  13         if point[0] < limit[0]:
  14             new_point = (point[0]+1, point[1])
  15             # print("From", point, "to", new_point)
  16             move_point(new_point, limit)
  17     elif point[0] < limit[0]:
  18         new_point = (point[0]+1, point[1])
  19         # print("From", point, "to", new_point)
  20         move_point(new_point, limit)
  21 
  22 move_point((0, 0), (20, 20))
  23 print("N Paths", nPaths)
  24 

Probamos el mismo algoritmo en C:

   1 #include <stdio.h>
   2 
   3 unsigned long n_paths = 0;
   4 void move_point(int x, int y, int xmax, int ymax) {
   5   if (x == xmax && y == ymax) {
   6     n_paths++;
   7   } else if (y < ymax) {
   8     move_point(x, y + 1, xmax, ymax);
   9     if (x < xmax) {
  10       move_point(x + 1, y, xmax, ymax);
  11     }
  12   } else if (x < xmax) {
  13     move_point(x + 1, y, xmax, ymax);
  14   }
  15 }
  16 
  17 int main() {
  18   move_point(0, 0, 20, 20);
  19   printf("n_paths: %lu\n", n_paths);
  20   return (0);
  21 }
  22 

Ahora sí. En una hora el problema está resuelto. Se sabe que Python no se lleva especialmente con la recursividad.

---

https://projecteuler.net/problem=16

El problema 16 son tres líneas de código, se puede hacer el el mismo intérprete.

Python 2.7.11 (default, Aug  9 2016, 15:45:42) 
[GCC 5.3.1 20160406 (Red Hat 5.3.1-6)] on linux2
Type "help", "copyright", "credits" or "license" for more information.
>>> sum = 0
>>> for a in str(2**1000):
...   sum += int(a)
... 
>>> print sum
1366
>>>