Recientemente encontré una presentación sobre F # para programadores de Python, y después de verlo, decidí implementar una solución para el "rompecabezas de las hormigas" por mi cuenta.

Hay una hormiga que puede caminar en una cuadrícula plana. La hormiga puede moverse un espacio a la izquierda, derecha, arriba o abajo. Es decir, desde la celda (x, y) la hormiga puede ir a las celdas (x + 1, y), (x-1, y), (x, y + 1) y (x, y-1). Los puntos donde la suma de los dígitos de las coordenadas xey son mayores que 25 son inaccesibles para la hormiga. Por ejemplo, el punto (59,79) es inaccesible porque 5 + 9 + 7 + 9 = 30, que es mayor que 25. La pregunta es: ¿a cuántos puntos puede acceder la hormiga si comienza en (1000, 1000), incluido (1000, 1000) en sí mismo

I implementé mi solución en 30 líneas deOCaml primero, y lo probé:

$ ocamlopt -unsafe -rectypes -inline 1000 -o puzzle ant.ml
$ time ./puzzle
Points: 148848

real    0m0.143s
user    0m0.127s
sys     0m0.013s

Neat, mi resultado es el mismo que el demplementación de @leonardo, en D y C ++. En comparación con la implementación de C ++ de leonardo, la versión de OCaml se ejecuta aproximadamente 2 veces más lento que C ++. Lo cual está bien, dado que Leonardo usó una cola para eliminar la recursividad.

Entonces yotradujo el código a F # ... y esto es lo que obtuve:

Thanassis@HOME /g/Tmp/ant.fsharp
$ /g/Program\ Files/FSharp-2.0.0.0/bin/fsc.exe ant.fs
Microsoft (R) F# 2.0 Compiler build 2.0.0.0
Copyright (c) Microsoft Corporation. All Rights Reserved.

Thanassis@HOME /g/Tmp/ant.fsharp
$ ./ant.exe

Process is terminated due to StackOverflowException.
Quit

Thanassis@HOME /g/Tmp/ant.fsharp
$ /g/Program\ Files/Microsoft\ F#/v4.0/Fsc.exe ant.fs
Microsoft (R) F# 2.0 Compiler build 4.0.30319.1
Copyright (c) Microsoft Corporation. All Rights Reserved.

Thanassis@HOME /g/Tmp/ant.fsharp
$ ./ant.exe

Process is terminated due to StackOverflowException

Desbordamiento de pila ... con ambas versiones de F # que tengo en mi máquina ... Por curiosidad, tomé el binario generado (ant.exe) y lo ejecuté en Arch Linux / Mono:

$ mono -V | head -1
Mono JIT compiler version 2.10.5 (tarball Fri Sep  9 06:34:36 UTC 2011)

$ time mono ./ant.exe
Points: 148848

real    1m24.298s
user    0m0.567s
sys     0m0.027s

orprendentemente, r, uns bajo Mono 2.10.5 (es decir, sin desbordamiento de la pila), pero tarda 84 segundos, es decir, 587 veces más lento que OCaml - oops.

Así que este programa ...

corre bien bajo OCaml no funciona en absoluto bajo .NET / F #works, pero es muy lento, en Mono / F #.

¿Por qué

EDITAR La rareza continúa: el uso de "--optimize + --checked-" hace que el problema desaparezca, pero solo en ArchLinux / Mono; bajo Windows XP y Windows 7 / 64bit, incluso la versión optimizada de la pila binaria se desborda.

FIT EDIT: Descubrí la respuesta por mí mismo, ver a continuación.