Cómo frenar a un borracho de camino a casa

15

Considere un gráfico de cuadrícula n por n que se vea así.

gráfico de cuadrícula

Es importante notar que este gráfico es 11 por 11 .

En cualquier punto dado, un hombre se para en una intersección y solo se mueve vertical u horizontalmente paso a paso a la siguiente intersección. Lamentablemente, ha bebido demasiado, por lo que elige la dirección en la que se mueve aleatoriamente desde las 4 direcciones posibles (arriba, abajo, izquierda, derecha). Esto es hasta 4 como si estuviera parado en una pared, solo tiene 3 opciones, por supuesto, y en una esquina solo tiene 2.

Comienza en la esquina inferior izquierda y su objetivo es llegar a casa, que es la esquina superior derecha. El tiempo es simplemente la cantidad de pasos que le toma.

Sin embargo, eres un adversario malicioso que quiere que llegue a casa lo más lento posible. Puede eliminar cualquier número de bordes del gráfico en cualquier momento durante su caminata. La única restricción es que siempre debes dejarle algún camino para que llegue a casa y no puedes eliminar un borde que ya ha usado.

El desafío es idear un adversario lo más malicioso posible y luego probarlo en un gráfico de 100 por 100 20 por 20 con un caminante borracho al azar. Su puntaje es simplemente el tiempo promedio que le toma al caminante aleatorio llegar a casa más de 10 1000 carreras.

Puede usar cualquier idioma y bibliotecas que desee siempre que estén disponibles gratuitamente y sean fácilmente instalables en Linux.

¿Qué necesito implementar?

Debe implementar el código para el caminante aleatorio y también para el adversario, y el código debe combinarse para que la salida cuando se ejecute sea simplemente el promedio de 1000 ejecuciones utilizando su código de adversario. El código aleatorio del caminante debe ser muy simple de escribir, ya que solo elige entre (x-1, y), (x + 1, y), (x, y-1) y (x, y + 1) asegurándose de que ninguno de ellos ha sido eliminado o está fuera de rango.

El código del adversario es, por supuesto, más difícil y también necesita recordar qué bordes ha atravesado el borracho para que no intente eliminar ninguno de ellos y asegurarse de que todavía haya una ruta a casa para el borracho, lo cual es un poco más complicado que hacer rapido

El Anexo 10 no es suficiente, pero no quería castigar a las personas que lograron dar largas caminatas. Ahora lo he aumentado a 1000 debido a una solicitud popular. Sin embargo, si su caminata es tan larga que no puede hacer 1000 carreras en una cantidad de tiempo realista, solo informe la cantidad máxima de carreras que puede.

Tabla de puntaje alto para 100 por 100.

  • 976124.754 por Optimizer.
  • 103000363.218 por Peter Taylor.

Editar 1. Cambió el tamaño del gráfico a 20 por 20 para ayudar al tiempo de ejecución de las pruebas de las personas. Haré una nueva puntuación de tabla alta para ese tamaño a medida que las personas envíen las puntuaciones.

Tabla de puntaje alto para 20 por 20.

230,794.38 (100k runs) by justhalf
227,934 by Sparr 
213,000 (approx) by Peter Taylor
199,094.3 by stokastic
188,000 (approx) by James_pic
 64,281 by Geobits
code-challenge graph-theory
fuente
2
No entiendo; ¿No puedes eliminar todos los bordes al principio excepto los que forman el camino más largo?
Peter Olson
3
No veo ninguna regla que demuestre que el borracho no puede volver a caminar el mismo borde dos veces. Si puede tomar el mismo camino entre dos puntos dos veces, y elige giros al azar, entonces lógicamente, ¿no es el gráfico con el recorrido promedio (aleatorio) más largo el que tiene más bordes? Es decir, ¿no sería el gráfico óptimo (más largo) el que no tiene bordes eliminados?
millinon
3
No soy fanático de exigir cada entrada para reinventar la rueda (andador). Si alguien publica un arnés / marco de prueba, lo votaré y lo usaré.
Sparr
1
La ventaja de eliminar una parte de un camino para hacerlo volver a tomar el camino largo se pierde por completo cuando su camino es aleatorio; supuestamente es igualmente probable que retroceda en algún momento sin necesidad de que elimines un borde. Me gustaría ver algunos datos de prueba que muestran el tiempo promedio sin bordes eliminados, y luego con ciertos bordes eliminados como parece sugerir. En cuanto a este desafío, creo que sería mucho más interesante si el camino del borracho fuera determinista.
millinon
3
10 rondas no es suficiente. Incluso con un laberinto estático de 10x10, y mucho menos un adversario inteligente y un laberinto de 100x100, la desviación estándar es de alrededor del 50% del caso promedio. Estoy ejecutando 10000 rondas y todavía no consideraría los resultados dignos de comparación.
Sparr

Respuestas:

10

230,794.38 en 20x20, 100k carreras

Última actualización: finalmente construí una solución dinámica de 2 vías perfecta. Dije perfecto ya que la versión anterior en realidad no es simétrica, era más fácil obtener un camino más largo si el borracho tomaba un camino sobre el otro. El actual es simétrico, por lo que puede obtener un mayor número esperado de pasos. Después de algunas pruebas, parece estar alrededor de 230k, una mejora con respecto a la anterior que es de aproximadamente 228k. Pero estadísticamente hablando, esos números todavía están dentro de su gran desviación, por lo que no afirmo que esto sea significativamente mejor, pero creo que debería ser mejor que la versión anterior.

El código está al final de esta publicación. Se actualiza para que sea mucho más rápido que la versión anterior, completando 1000 ejecuciones en 23 segundos.

A continuación se muestra una ejecución de muestra y un laberinto de muestra:

Caminante perfecto
Promedio: 230794.384
Máx .: 1514506
Min: 25860
Completado en 2317.374s
 _ _ _ _ _ _ _ _ _ _ _ _. 
El | El | El | El | El | El | El | El | El | El | El | El | El | El | El | _ _ _ _  
El | El | El | El | El | El | El | El | El | El | El | El | El | El | El | | _ _ _ _  
El | El | El | El | El | El | El | El | El | El | El | El | El | El | El | _ _ _ _ |
El | El | El | El | El | El | El | El | El | El | El | El | El | El | El | | _ _ _ _  
El | El | El | El | El | El | El | El | El | El | El | El | El | El | El | _ _ _ _ |
El | El | El | El | El | El | El | El | El | El | El | El | El | El | El | | _ _ _ _  
El | El | El | El | El | El | El | El | El | El | El | El | El | El | El | _ _ _ _ |
El | El | El | El | El | El | El | El | El | El | El | El | El | | _ | | _ _ _ _  
El | El | El | El | El | El | El | El | El | El | El | El | El | _ _ _ _ _ _ |
El | El | El | El | El | El | El | El | El | El | El | El | El | | _ _ _ _ _ _  
El | El | El | El | El | El | El | El | El | El | El | El | El | _ _ _ _ _ _ |
El | El | El | El | El | El | El | El | El | El | El | El | El | | _ _ _ _ _ _  
El | El | El | El | El | El | El | El | El | El | El | El | El | _ _ _ _ _ _ |
El | El | El | El | El | | _ | | _ | | _ | | _ | | _ _ _ _ _ _  
El | El | El | El | El | _ _ _ _ _ _ _ _ _ _ _ _ _ _ |
El | El | El | El | El | | _ _ _ _ _ _ _ _ _ _ _ _ _ _  
El | El | El | El | El | _ _ _ _ _ _ _ _ _ _ _ _ _ _ |
El | | _ | | _ | | _ _ _ _ _ _ _ _ _ _ _ _ _ _  
| _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ |

Envíos anteriores

¡Finalmente puedo igualar el resultado de Sparr! = D

Basado en mis experimentos anteriores (ver al final de esta publicación), la mejor estrategia es tener un doble camino y cerrar uno cuando el borracho llegue a cualquiera de ellos, y la variable proviene de cuán bueno podemos predecir dinámicamente dónde irá el borracho. aumentar la posibilidad de que se meta en un camino más largo.

Entonces, según mi DOUBLE_PATHestrategia, construí otro, que cambia el laberinto (mi DOUBLE_PATHlaberinto era fácilmente modificable) dependiendo del movimiento del borracho. A medida que toma un camino con más de una opción disponible, cerraré los caminos para dejar solo dos opciones posibles (una de la que vino, otra la no viajada).

Esto suena similar a lo que Sparr ha logrado, como lo muestra el resultado. La diferencia con la suya es demasiado pequeña para que se considere mejor, pero diría que mi enfoque es más dinámico que él, ya que mi laberinto es más modificable que el de Sparr =)

El resultado con una muestra final de laberinto:

EXTREME_DOUBLE_PATH
Promedio: 228034.89
Máx .: 1050816
Min: 34170
Completado en 396.728s
 _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _
El | _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _
El | | _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _
El | _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ |
El | | _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _
El | _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ |
El | | _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _
El | _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ |
El | | _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _
El | _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ |
El | | _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _
El | _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ |
El | | _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _
| _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ |
 _ _ _ _ _ _ _ _ _ _ | | _ _ _ _ _ _ _ _
| _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ |
 _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ | El |
| _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ |
 _ _ _ _ _ | | _ _ _ _ _ _ _ _ _ _ _ _ _
| _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ |

Sección de Experimentos

Lo mejor resulta ser la misma estrategia que stokastic, me enorgullece experimentar usando varias estrategias e imprimir buenos resultados :)

Cada uno de los laberintos impresos a continuación es el último laberinto después de que el borracho haya llegado a casa, por lo que pueden ser ligeramente diferentes de una carrera a otra debido a la aleatoriedad en el movimiento del borracho y la dinamicidad del adversario.

Describiré cada estrategia:

Sendero Sencillo

Este es el enfoque más simple, que creará una única ruta desde la entrada hasta la salida.

SINGLE_PATH
Promedio: 162621.612
Max: 956694
Min: 14838
Completado en 149.430s
 _ _ _ _ _ _ _ _ _ _
El | | _ | | _ | | _ | | _ | | _ | | _ | | _ | | _ | | _ | El |
| _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ 
 _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ |
| _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ 
 _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ |
| _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ 
 _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ |
| _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ 
 _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ |
| _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ 
 _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ |
| _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ 
 _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ |
| _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ 
 _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ |
| _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ 
 _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ |
| _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ 
 _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ |

Isla (nivel 0)

Este es un enfoque que intenta atrapar al borracho en una isla casi aislada. No funciona tan bien como esperaba, pero esta es una de mis primeras ideas, así que la incluyo.

Hay dos caminos que conducen a la salida, y cuando el borracho se acerca a uno de ellos, el adversario lo cierra y lo obliga a encontrar la otra salida (y posiblemente queda atrapado nuevamente en la isla)

ISLA
Promedio: 74626.070
Máx .: 428560
Min: 1528
Completado en 122.512s
 _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _
El | _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _   
El | | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | El |
El | | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | El |
El | | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | El |
El | | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | El |
El | | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | El |
El | | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | El |
El | | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | El |
El | | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | El |
El | | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | El |
El | | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | El |
El | | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | El |
El | | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | El |
El | | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | El |
El | | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | El |
El | | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | El |
El | | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | El |
| _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | El |
| _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ |

Doble camino

Esta es la estrategia más discutida, que consiste en tener dos caminos de igual longitud hacia la salida, y cerrar uno de ellos cuando el borracho se acerque a uno de ellos.

DOUBLE_PATH
Promedio: 197743.472
Máx .: 1443406
Min: 21516
Completado en 308.177s
 _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _
| _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ 
 _ _ _ _ _ _ _ _ _ | | _ _ _ _ _ _ _ _ _
| _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ |
 _ _ _ _ _ _ _ _ _ | | _ _ _ _ _ _ _ _ _
| _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ |
 _ _ _ _ _ _ _ _ _ | | _ _ _ _ _ _ _ _ _
| _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ |
 _ _ _ _ _ _ _ _ _ | | _ _ _ _ _ _ _ _ _
| _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ |
 _ _ _ _ _ _ _ _ _ | | _ _ _ _ _ _ _ _ _
| _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ |
 _ _ _ _ _ _ _ _ _ | | _ _ _ _ _ _ _ _ _
| _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ |
 _ _ _ _ _ _ _ _ _ | | _ _ _ _ _ _ _ _ _
| _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ |
 _ _ _ _ _ _ _ _ _ | | _ _ _ _ _ _ _ _ _
| _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ |
 _ _ _ _ _ _ _ _ _ | | _ _ _ _ _ _ _ _ _
| _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ |

Isla (nivel 1)

Inspirados por los múltiples caminos de la isla y el alto conteo de caminatas en un solo camino, conectamos la isla a la salida y hacemos un laberinto de un solo camino en la isla, creando en total tres caminos para salir, y de forma similar al caso anterior, cerramos cualquiera de los salga cuando el borracho se acerque.

Esto funciona un poco mejor que la ruta simple, pero aún así no vence a la ruta doble.

ISLA
Promedio: 166265.132
Máx .: 1162966
Min: 19544
Completado en 471.982s
 _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _
El | _ _ _ _ _ _ _ _ _ | _
El | El | | _ | | _ | | _ | | _ | | _ | | _ | | _ | | _ | El |  
El | | _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ |
El | _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ | El |
El | | _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ |
El | _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ | El |
El | | _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ |
El | _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ | El |
El | | _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ |
El | _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ | El |
El | | _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ |
El | _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ | El |
El | | _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ |
El | _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ | El |
El | | _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ |
El | _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ | El |
El | | _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ |
El | _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ | El |
| _ | _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ |

Isla (nivel 2)

Intentando expandir la idea anterior, creé una isla anidada, creando en total cinco caminos, pero no parece funcionar tan bien.

ISLA
Promedio: 164222.712
Máx .: 927608
Min: 22024
Completado en 793.591
 _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _
El | _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ | _
El | El | _ _ _ _ _ _ _ _ | _ |  
El | El | El | | _ | | _ | | _ | | _ | | _ | | _ | | _ | El | El |
El | El | | _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ | El |
El | El | _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ | El | El |
El | El | | _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ | El |
El | El | _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ | El | El |
El | El | | _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ | El |
El | El | _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ | El | El |
El | El | | _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ | El |
El | El | _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ | El | El |
El | El | | _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ | El |
El | El | _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ | El | El |
El | El | | _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ | El |
El | El | _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ | El | El |
El | El | | _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ | El |
El | El | _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ | El | El |
| _ | _ | _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ | El |
| _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ |

Isla (nivel 3)

Al darse cuenta de que la doble ruta en realidad funciona mejor que la ruta única, ¡hagamos que la isla tenga doble ruta!

El resultado es una mejora sobre la Isla (nivel 1), pero aún así no supera el doble camino puro.

A modo de comparación, el resultado para el doble camino del tamaño de la isla es de 131,134.42 movimientos en promedio. Entonces, esto agrega un número bastante significativo de movimientos (alrededor de 40k), pero no lo suficiente como para vencer el doble camino.

ISLA
Promedio: 171730.090
Máx .: 769080
Min: 29760
Completado en 587.646
 _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _
El | _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ | _
El | | _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ |  
El | _ _ _ _ _ _ _ _ | | _ _ _ _ _ _ _ _ |
El | | _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ | El |
El | _ _ _ _ _ _ _ _ | | _ _ _ _ _ _ _ _ |
El | | _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ | El |
El | _ _ _ _ _ _ _ _ | | _ _ _ _ _ _ _ _ |
El | | _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ | El |
El | _ _ _ _ _ _ _ _ | | _ _ _ _ _ _ _ _ |
El | | _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ | El |
El | _ _ _ _ _ _ _ _ | | _ _ _ _ _ _ _ _ |
El | | _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ | El |
El | _ _ _ _ _ _ _ _ | | _ _ _ _ _ _ _ _ |
El | | _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ | El |
El | _ _ _ _ _ _ _ _ | | _ _ _ _ _ _ _ _ |
El | | _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ | El |
El | _ _ _ _ _ _ _ _ | | _ _ _ _ _ _ _ _ |
El | | _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ | El |
| _ | _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ |

Isla (nivel 4)

Nuevamente, experimentar con una isla anidada, y nuevamente no funciona tan bien.

ISLA
Promedio: 149723.068
Máx .: 622106
Min: 25752
Completado en 830.889s
 _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _    
El | _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ | _ |
El | El | _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ | _ |  
El | El | | _ _ _ _ _ _ _ _ _ _ _ _ _ _ |
El | El | _ _ _ _ _ _ _ | | _ _ _ _ _ _ _ | El |
El | El | | _ _ _ _ _ _ _ _ _ _ _ _ _ _ | El | El |
El | El | _ _ _ _ _ _ _ | | _ _ _ _ _ _ _ | El |
El | El | | _ _ _ _ _ _ _ _ _ _ _ _ _ _ | El | El |
El | El | _ _ _ _ _ _ _ | | _ _ _ _ _ _ _ | El |
El | El | | _ _ _ _ _ _ _ _ _ _ _ _ _ _ | El | El |
El | El | _ _ _ _ _ _ _ | | _ _ _ _ _ _ _ | El |
El | El | | _ _ _ _ _ _ _ _ _ _ _ _ _ _ | El | El |
El | El | _ _ _ _ _ _ _ | | _ _ _ _ _ _ _ | El |
El | El | | _ _ _ _ _ _ _ _ _ _ _ _ _ _ | El | El |
El | El | _ _ _ _ _ _ _ | | _ _ _ _ _ _ _ | El |
El | El | | _ _ _ _ _ _ _ _ _ _ _ _ _ _ | El | El |
El | El | _ _ _ _ _ _ _ | | _ _ _ _ _ _ _ | El |
El | | _ | _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ | El | El |
| _ | _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ | El |
| _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ |

Conclusión

Con todo, esto prueba que tener un solo camino largo desde la posición actual del borracho hasta la salida funciona mejor, lo que se logra mediante la estrategia de doble camino, ya que después de cerrar una salida, el borracho tendrá que recorrer la distancia máxima posible para llegar a la salida.

Esto sugiere que la estrategia básica debe seguir siendo el doble camino, y solo podemos modificar la dinámica en la que se crean los caminos, lo que ha hecho Sparr. ¡Así que creo que su estrategia es el camino a seguir!

Código

import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.TreeSet;

public class Walker {

    enum Strategy{
        SINGLE_PATH,
        ISLAND,
        DOUBLE_PATH,
        EXTREME_DOUBLE_PATH,
        PERFECT_DOUBLE_PATH,
    }

    int width,height;
    int x,y; //walker's position
    int dX,dY; //destination
    Point[][] points;
    int stepCount = 0;

    public static void main(String[]args){
        int side = 20;
//      runOnce(side, Strategy.EXTREME_DOUBLE_PATH, 0);
        runOnce(side, Strategy.PERFECT_DOUBLE_PATH, 0);
//      for(Strategy strategy: Strategy.values()){
//          runOnce(side, strategy, 0);
//      }
//      runOnce(side, Strategy.ISLAND, 1);
//      runOnce(side, Strategy.ISLAND, 2);
//      Scanner scanner = new Scanner(System.in);
//      System.out.println("Enter side, strategy (SINGLE_PATH, ISLAND, DOUBLE_PATH, EXTREME_DOUBLE_PATH), and level:");
//      while(scanner.hasNext()){
//          side = scanner.nextInt();
//          Strategy strategy = Strategy.valueOf(scanner.next());
//          int level = scanner.nextInt();
//          scanner.nextLine();
//          runOnce(side, strategy, level);
//          System.out.println("Enter side, strategy (SINGLE_PATH, ISLAND, DOUBLE_PATH, EXTREME_DOUBLE_PATH), and level:");
//      }
//      scanner.close();
    }

    private static Walker runOnce(int side, Strategy strategy, int level) {
        Walker walker = null;
        long total = 0;
        int max = 0;
        int min = Integer.MAX_VALUE;
        double count = 1000;
        long start = System.currentTimeMillis();
        for(int i=0; i<count; i++){
            walker = new Walker(0,0,side,side,side-1,side-1, strategy, level, false);
            total += walker.stepCount;
            max = Math.max(walker.stepCount, max);
            min = Math.min(walker.stepCount, min);
//          System.out.println("Iteration "+i+": "+walker.stepCount);
        }
        System.out.printf("%s\nAverage: %.3f\nMax: %d\nMin:%d\n",strategy, total/count, max, min);
        System.out.printf("Completed in %.3fs\n", (System.currentTimeMillis()-start)/1000.0);
        walker.printPath();
        return walker;
    }

    private void createIsland(int botLeftX, int botLeftY, int topRightX, int topRightY){
        for(int i=botLeftY+1; i<topRightY; i++){
            if(i>botLeftY+1) deletePath(points[botLeftX][i].right());
            if(i<topRightY-1) deletePath(points[topRightX][i].left());
        }
        for(int i=botLeftX+1; i<topRightX; i++){
            if(i>botLeftX+1) deletePath(points[i][botLeftY].up());
            if(i<topRightX-1) deletePath(points[i][topRightY].down());
        }
    }

    private void createSinglePath(int botLeftX, int botLeftY, int topRightX, int topRightY){
        for(int i=botLeftY; i<topRightY; i++){
            if(i==topRightY-1 && (topRightY+1-botLeftY)%2==0){
                for(int j=botLeftX; j<topRightX; j++){
                    if(j==topRightX-1 && (j-botLeftX)%2==0){
                        deletePath(points[topRightX][topRightY].down());
                    } else {
                        deletePath(points[j][topRightY-1+((j-botLeftX)%2)].right());
                    }
                }
            } else {
                for(int j=botLeftX+(i-botLeftY)%2; j<topRightX+((i-botLeftY)%2); j++){
                    deletePath(points[j][i].up());
                }
            }
        }
    }

    private void createDoublePath(int botLeftX, int botLeftY, int topRightX, int topRightY){
        for(int i=botLeftY; i<topRightY; i++){
            if(i>botLeftY && (width%4!=1 || i<topRightY-1)) deletePath(points[width/2-1][i].right());
            if(i==topRightY-1 && (topRightY+1-botLeftY)%2==1){
                for(int j=botLeftX; j<topRightX; j++){
                    if((j-botLeftX)%2==0 || j<topRightX-1){
                        deletePath(points[j][topRightY-1+((j-botLeftX)%2)].right());
                    } else {
                        deletePath(points[topRightX-1][topRightY-1].right());
                    }
                }
            } else {
                if((i-botLeftY)%2==0){
                    for(int j=botLeftX+1; j<topRightX; j++){
                        deletePath(points[j][i].up());
                    }
                } else {
                    for(int j=botLeftX; j<topRightX+1; j++){
                        if(j!=width/2 && j!=width/2-1){
                            deletePath(points[j][i].up());
                        }
                    }
                }
            }
        }
    }

    public Walker(int startingX,int startingY, int Width, int Height, int destinationX, int destinationY, Strategy strategy, int level, boolean animate){
        width = Width;
        height = Height;
        dX = destinationX;
        dY = destinationY;
        x=startingX;
        y=startingY;
        points = new Point[width][height];
        for(int y=0; y<height; y++){
            for(int x=0; x<width; x++){
                points[x][y] = new Point(x,y);
            }
        }
        for(int y=0; y<height; y++){
            for(int x=0; x<width; x++){
                if(x<width-1) new Edge(points[x][y], points[x+1][y]);
                if(y<height-1) new Edge(points[x][y], points[x][y+1]);
            }
        }

        if(strategy == Strategy.SINGLE_PATH) createSinglePath(0,0,width-1,height-1);

        if(strategy == Strategy.DOUBLE_PATH) createDoublePath(0,0,width-1,height-1);

        List<EdgeList> edgeLists = new ArrayList<EdgeList>();
        if(strategy == Strategy.ISLAND){
            List<Edge> edges = new ArrayList<Edge>();
            if(level==0){
                createIsland(0,0,width-1,height-1);
                deletePath(points[width-2][height-2].right());
                deletePath(points[width-2][height-2].up());
            } else {
                for(int i=0; i<level; i++){
                    createIsland(i,i,width-1-i, height-1-i);
                }
                createDoublePath(level,level,width-1-level,height-1-level);
                for(int i=height-1; i>=height-level; i--){
                    edges.add(points[i-2][i].right());
                    edges.add(points[i][i-2].up());
                    edgeLists.add(new EdgeList(points[i-1][i].right(), points[i][i-1].up()));
                }
            }
            edges.add(points[width-1-level][height-1-level].down());
            edges.add(points[width-1-level][height-1-level].left());
            edgeLists.add(new EdgeList(edges.toArray(new Edge[0])));
        }

        int[] availableVerticals = new int[height];
        if(strategy == Strategy.EXTREME_DOUBLE_PATH){
            for(int i=1; i<width-1; i++){
                deletePath(points[i][0].up());
            }
            availableVerticals[0] = 2;
            for(int i=1; i<height; i++){
                availableVerticals[i] = width;
            }
        }

        boolean[][] available = new boolean[width][height];
        if(strategy == Strategy.PERFECT_DOUBLE_PATH){
            for(int x=0; x<width; x++){
                for(int y=0; y<height; y++){
                    if(x%2==1 && y%2==1){
                        available[x][y] = true;
                    } else {
                        available[x][y] = false;
                    }
                }
            }
        }
//      printPath();
        while(!walk()){
            if(animate)try{Thread.sleep(500);}catch(InterruptedException e){}
            if(strategy == Strategy.ISLAND){
                if(x==y && (x==1 || (x>=2 && x<=level))){
                    if(!hasBeenWalked(points[x][x].down())){
                        deletePath(points[x][x].down());
                    } else if(!hasBeenWalked(points[x][x].left())){
                        deletePath(points[x][x].left());
                    }
                }
            }
            if(strategy == Strategy.EXTREME_DOUBLE_PATH){
                Point cur = points[x][y];
                int untravelled = 0;
                for(Edge edge: cur.edges) if(edge!=null && !edge.walked) untravelled++;
                if(untravelled>1){
                    if(cur.up()!=null && availableVerticals[y]>2 && !cur.up().walked){
                        deletePath(cur.up());
                        availableVerticals[y]--;
                    }
                    if(cur.down()!=null && !cur.down().walked){
                        deletePath(cur.down());
                        availableVerticals[y-1]--;
                    }
                    if(cur.up()!=null && cur.left()!=null && !cur.left().walked){
                        deletePath(cur.left());
                        deletePath(points[x][y+1].left());
                    }
                    if(cur.up()!=null && cur.right()!=null && !cur.right().walked){
                        deletePath(cur.right());
                        if(y<height-1) deletePath(points[x][y+1].right());
                    }
                }
            }
            if(strategy == Strategy.PERFECT_DOUBLE_PATH){
                Point cur = points[x][y];
                int untravelled = 0;
                for(Edge edge: cur.edges) if(edge!=null && !edge.walked) untravelled++;
                if(x%2!=1 || y%2!=1){
                    if(untravelled>1){
                        if(cur.down()==null && hasBeenWalked(cur.right())){
                            if(canBeDeleted(cur.up())) deletePath(cur.up());
                        }
                        if(cur.down()==null && hasBeenWalked(cur.left())){
                            if(x%2==0 && y%2==1 && canBeDeleted(cur.right())) deletePath(cur.right());
                            else if(cur.right()!=null && canBeDeleted(cur.up())) deletePath(cur.up());
                        }
                        if(cur.left()==null && hasBeenWalked(cur.up())){
                            if(canBeDeleted(cur.right())) deletePath(cur.right());
                        }
                        if(cur.left()==null && hasBeenWalked(cur.down())){
                            if(x%2==1 && y%2==0 && canBeDeleted(cur.up())) deletePath(cur.up());
                            else if (cur.up()!=null && canBeDeleted(cur.right())) deletePath(cur.right());
                        }
                    }
                } else {
                    if(!hasBeenWalked(cur.left())){
                        if(x>1 && available[x-2][y]){
                            if(untravelled>1){
                                available[x-2][y] = false;
                                deletePath(cur.up());
                            }
                        } else if(cur.up()!=null){
                            if(canBeDeleted(cur.left())) deletePath(cur.left());
                            if(canBeDeleted(points[x][y+1].left())) deletePath(points[x][y+1].left());
                        }
                    }
                    if(!hasBeenWalked(cur.down())){
                        if(y>1 && available[x][y-2]){
                            if(untravelled>1){
                                available[x][y-2] = false;
                                deletePath(cur.right());
                            }
                        } else if(cur.right()!=null){
                            if(canBeDeleted(cur.down())) deletePath(cur.down());
                            if(canBeDeleted(points[x+1][y].down())) deletePath(points[x+1][y].down());
                        }
                    }
                }
            }
            if(strategy == Strategy.DOUBLE_PATH || strategy == Strategy.EXTREME_DOUBLE_PATH
                    || strategy == Strategy.PERFECT_DOUBLE_PATH){
                if(x==width-2 && y==height-1 && points[width-1][height-1].down()!=null){
                    deletePath(points[width-1][height-1].left());
                }
                if(x==width-1 && y==height-2 && points[width-1][height-1].left()!=null){
                    deletePath(points[width-1][height-1].down());
                }
            } else if(strategy == Strategy.ISLAND){
                for(EdgeList edgeList: edgeLists){
                    boolean deleted = false;
                    for(Edge edge: edgeList.edges){
                        if(edge.start.x == x && edge.start.y == y){
                            if(!hasBeenWalked(edge)){
                                deletePath(edge);
                                edgeList.edges.remove(edge);
                                if(edgeList.edges.size() == 1){
                                    edgeLists.remove(edgeList);
                                }
                                deleted = true;
                                break;
                            }
                        }
                    }
                    if(deleted) break;
                }
            }
            if(animate)printPath();
        }
    }

    public boolean hasBeenWalked(Edge edge){
        if(edge == null) return false;
        return edge.walked;
    }

    public boolean canBeDeleted(Edge edge){
        if(edge == null) return false;
        return !edge.walked;
    }

    public List<Edge> getAdjacentUntravelledEdges(){
        List<Edge> result = new ArrayList<Edge>();
        for(Edge edge: points[x][y].edges){
            if(edge!=null && !hasBeenWalked(edge)) result.add(edge); 
        }
        return result;
    }

    public void printPath(){
        StringBuilder builder = new StringBuilder();
        for(int y=height-1; y>=0; y--){
            for(int x=0; x<width; x++){
                Point point = points[x][y];
                if(this.x==x && this.y==y){
                    if(point.up()!=null) builder.append('?');
                    else builder.append('.');
                } else {
                    if(point.up()!=null) builder.append('|');
                    else builder.append(' ');
                }
                if(point.right()!=null) builder.append('_');
                else builder.append(' ');
            }
            builder.append('\n');
        }
        System.out.print(builder.toString());
    }

    public boolean walk(){
        ArrayList<Edge> possibleMoves = new ArrayList<Edge>();
        Point cur = points[x][y];
        for(Edge edge: cur.edges){
            if(edge!=null) possibleMoves.add(edge);
        }
        int random = (int)(Math.random()*possibleMoves.size());
        Edge move = possibleMoves.get(random);
        move.walked = true;
        if(move.start == cur){
            x = move.end.x;
            y = move.end.y;
        } else {
            x = move.start.x;
            y = move.start.y;
        }
        stepCount++;
        if(x==dX && y == dY){
            return true;
        } else {
            return false;
        }
    }

    public boolean isSolvable(){
        TreeSet<Point> reachable = new TreeSet<Point>();
        Queue<Point> next = new LinkedList<Point>();
        next.offer(points[x][y]);
        reachable.add(points[x][y]);
        while(next.size()>0){
            Point cur = next.poll();
            ArrayList<Point> neighbors = new ArrayList<Point>();
            if(cur.up()!=null) neighbors.add(cur.up().end);
            if(cur.right()!=null) neighbors.add(cur.right().end);
            if(cur.down()!=null) neighbors.add(cur.down().start);
            if(cur.left()!=null) neighbors.add(cur.left().start);
            for(Point neighbor: neighbors){
                if(!reachable.contains(neighbor)){
                    if(neighbor == points[dX][dY]) return true;
                    reachable.add(neighbor);
                    next.offer(neighbor);
                }
            }
        }
        return false;
    }

    public boolean deletePath(Edge toDelete){
        if(toDelete == null) return true;
//      if(toDelete.walked){
//          System.err.println("Edge already travelled!");
//          return false;
//      }
        int startIdx = toDelete.getStartIdx();
        int endIdx = toDelete.getEndIdx();
        toDelete.start.edges[startIdx] = null;
        toDelete.end.edges[endIdx] = null;
//      if(!isSolvable()){
//          toDelete.start.edges[startIdx] = toDelete;
//          toDelete.end.edges[endIdx] = toDelete;
//          System.err.println("Invalid deletion!");
//          return false;
//      }
        return true;
    }

    static class EdgeList{
        List<Edge> edges;

        public EdgeList(Edge... edges){
            this.edges = new ArrayList<Edge>();
            this.edges.addAll(Arrays.asList(edges));
        }
    }

    static class Edge implements Comparable<Edge>{
        Point start, end;
        boolean walked;

        public Edge(Point start, Point end){
            walked = false;
            this.start = start;
            this.end = end;
            this.start.edges[getStartIdx()] = this;
            this.end.edges[getEndIdx()] = this;
            if(start.compareTo(end)>0){
                Point tmp = end;
                end = start;
                start = tmp;
            }
        }

        public Edge(int x1, int y1, int x2, int y2){
            this(new Point(x1,y1), new Point(x2,y2));
        }

        public boolean exists(){
            return start.edges[getStartIdx()] != null || end.edges[getEndIdx()] != null;
        }

        public int getStartIdx(){
            if(start.x == end.x){
                if(start.y < end.y) return 0;
                else return 2;
            } else {
                if(start.x < end.x) return 1;
                else return 3;
            }
        }

        public int getEndIdx(){
            if(start.x == end.x){
                if(start.y < end.y) return 2;
                else return 0;
            } else {
                if(start.x < end.x) return 3;
                else return 1;
            }
        }

        public boolean isVertical(){
            return start.x==end.x;
        }

        @Override
        public int compareTo(Edge o) {
            int result = start.compareTo(o.start);
            if(result!=0) return result;
            return end.compareTo(o.end);
        }
    }

    static class Point implements Comparable<Point>{
        int x,y;
        Edge[] edges;

        public Point(int x, int y){
            this.x = x;
            this.y = y;
            edges = new Edge[4];
        }

        public Edge up(){ return edges[0]; }
        public Edge right(){ return edges[1]; }
        public Edge down(){ return edges[2]; }
        public Edge left(){ return edges[3]; }

        public int compareTo(Point o){
            int result = Integer.compare(x, o.x);
            if(result!=0) return result;
            result = Integer.compare(y, o.y);
            if(result!=0) return result;
            return 0;
        }
    }
}
justo
fuente
Esto es muy impresionante ¿Cuánto tiempo lleva correr? Si las entradas ganadoras permanecen tan cerca, tendremos que aumentar el número de carreras para ver si podemos separarlas.
1
El tiempo ya está incluido en el fragmento. Alrededor de 400 s para 1000 carreras. Eso incluye la verificación de solvencia en cada eliminación de ruta. Puedo eliminar eso para tener alrededor de 170 durante 1000 carreras. Entonces puedo hacer 20k carreras en aproximadamente una hora.
justhalf
En realidad, optimizando aún más, podría ejecutar 100k en 3.5 horas.
justhalf
Mi puntaje es con 100k carreras y tardé 10 minutos. @justhalf muy agradable en el laberinto de doble ruta más flexible. Sé cómo hacer uno aún mejor, pero no tengo la paciencia para implementarlo en este momento.
Sparr
2
Feliz de ver implementada la solución simétrica. Tengo otra idea para mejorar esta solución, y esta vez creo que podría implementarla yo mismo :)
Sparr
10

227934 (20x20)

Mi tercer intento. Utiliza el mismo enfoque general que @stokastic con dos caminos hacia la salida. Cuando el caminante llega al final de un camino, se cierra, lo que requiere que regrese para llegar al final del otro camino para salir. Mi mejora es generar las rutas a medida que avanza el caminante, de modo que cualquier ruta que avance más en la primera mitad del proceso terminará siendo más larga que la otra ruta.

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <math.h>
#include <iostream>

#define DEBUG 0
#define ROUNDS 10000

#define Y 20
#define X 20
#define H (Y*2+1)
#define W (X*2+1)

int maze[H][W];
int scores[ROUNDS];

int x, y;

void print_maze(){
    char line[W+2];
    line[W+1]=0;
    for(int row=0;row<H;row++) {
        for(int col=0;col<W;col++) {
            switch(maze[row][col]) {
                case 0:
                    line[col]=' ';
                    break;
                case 1:
                    line[col]=row%2?'-':'|';
                    break;
                case 8:
                    line[col]=(row==y*2+1&&col==x*2+1)?'@':'?';
                    break;
                case 9:
                    line[col]=(row==y*2+1&&col==x*2+1)?'@':'*';
                    break;
            }
        }
        line[W]='\n';
        printf("%s",line);
    }
    printf("%d %d\n",y,x);
}

int main(){
    srand (time(NULL));
    long long total_turns = 0;
    for(int round=0;round<ROUNDS;round++) {
        for (int r=0;r<H;r++) {
            for (int c=0;c<W;c++) {
                maze[r][c]=0;
            }
        }
        maze[1][1]=9;
        maze[1][2]=1;
        maze[2][1]=1;
        maze[1][3]=8;
        maze[3][1]=8;
        int progress_l = 0;
        int progress_r = 0;
        int side = 0;
        int closed_exit = 0;
        x=0;
        y=0;
        if (DEBUG) print_maze();
        long long turn = 0;
        int in = 0;
        while (x!=X-1||y!=Y-1) {
            turn++;
            int r = y*2+1;
            int c = x*2+1;
            int dx=0, dy=0;
            if (DEBUG) {
                std::cin>>in;
                switch(in) {
                    case 0:
                        dy=-1; dx=0; break;
                    case 1:
                        dy=0; dx=1; break;
                    case 2:
                        dy=1; dx=0; break;
                    case 3:
                        dy=0; dx=-1; break;
                    default:
                        dy=0; dx=0; break;
                }
            } else {
                int exits = maze[r-1][c] + maze[r][c+1] + maze[r+1][c] + maze[r][c-1];
                int exit_choice = -1;
                do {
                    if (rand()%exits == 0) {
                        exit_choice = exits;
                        break;
                    } else {
                        exits--;
                    }
                }while(exits);

                --exits;

                if (maze[r-1][c]&&!dx&&!dy) {
                    if (exits) {
                        --exits;
                    } else {
                        dy = -1;
                        dx = 0;
                    }
                }
                if (maze[r][c+1]&&!dx&&!dy) {
                    if (exits) {
                        --exits;
                    } else {
                        dy = 0;
                        dx = 1;
                    }
                }
                if (maze[r+1][c]&&!dx&&!dy) {
                    if (exits) {
                        --exits;
                    } else {
                        dy = 1;
                        dx = 0;
                    }
                }
                if (maze[r][c-1]&&!dx&&!dy) {
                    if (exits) {
                        --exits;
                    } else {
                        dy = 0;
                        dx = -1;
                    }
                }
            }

            x+=dx;
            y+=dy;

            if(x==X-1 && y==Y-1) continue;

            if (x==0&&y==1) side=-1;
            if (x==1&&y==0) side=1;
            if (maze[y*2+1][x*2+1]==8) { // room needs another exit, maybe
                if (side==-1) { // left half of maze
                    if (y==1) { // top of a column
                        if (x%2) { // going up, turn right
                            maze[y*2+1][x*2+2]=1;
                            maze[y*2+1][x*2+3]=8;
                        } else { // going right, turn down
                            maze[y*2+2][x*2+1]=1;
                            maze[y*2+3][x*2+1]=8;
                        }
                    } else if (y==Y-1) { // bottom of a column
                        if (x%2 && x<(X-progress_r-3)) { // going right, turn up if there's room
                            maze[y*2+0][x*2+1]=1;
                            maze[y*2-1][x*2+1]=8;
                            progress_l=x+1;
                        } else { // going down or exiting, go right
                            if (x!=X-2 or closed_exit==1) {
                                maze[y*2+1][x*2+2]=1;
                                maze[y*2+1][x*2+3]=8;
                            } else {
                                closed_exit = -1;
                            }
                        }
                    } else { // in a column
                        if (maze[y*2+0][x*2+1]) { // going down
                            maze[y*2+2][x*2+1]=1;
                            maze[y*2+3][x*2+1]=8;
                        } else { // going up
                            maze[y*2+0][x*2+1]=1;
                            maze[y*2-1][x*2+1]=8;
                        }
                    }
                } else { // right half of maze
                    if (y==0) { // top row
                        if (x<X-1) { // go right
                            maze[y*2+1][x*2+2]=1;
                            maze[y*2+1][x*2+3]=8;
                        } else { // go down
                            maze[y*2+2][x*2+1]=1;
                            maze[y*2+3][x*2+1]=8;
                        }
                    } else if (y==Y-2) { // heading right to the exit
                        if (x<X-1) { // go right
                            maze[y*2+1][x*2+2]=1;
                            maze[y*2+1][x*2+3]=8;
                        } else { // go down
                            if (x!=X-1 or closed_exit==-1) {
                                maze[y*2+2][x*2+1]=1;
                                maze[y*2+3][x*2+1]=8;
                            } else {
                                closed_exit = 1;
                            }
                        }
                    } else if (y==Y-3) { // bottom of a column
                        if (x>progress_l+1) { // do we have room for another column?
                            if (!(x%2)&&y>1) { // going left, turn up
                                maze[y*2+0][x*2+1]=1;
                                maze[y*2-1][x*2+1]=8;
                            } else { // going down, turn left
                                maze[y*2+1][x*2+0]=1;
                                maze[y*2+1][x*2-1]=8;
                                progress_r=X-x-1;
                            }
                        } else { // abort, move down to escape row
                            maze[y*2+2][x*2+1]=1;
                            maze[y*2+3][x*2+1]=8;
                        }
                    } else if (y==1) { // top of a column
                        if (!(x%2)) { // going up, turn left
                            maze[y*2+1][x*2+0]=1;
                            maze[y*2+1][x*2-1]=8;
                        } else { // going left, turn down
                            maze[y*2+2][x*2+1]=1;
                            maze[y*2+3][x*2+1]=8;
                        }
                    } else { // in a column
                        if (maze[y*2+0][x*2+1]) { // going down
                            maze[y*2+2][x*2+1]=1;
                            maze[y*2+3][x*2+1]=8;
                        } else { // going up
                            maze[y*2+0][x*2+1]=1;
                            maze[y*2-1][x*2+1]=8;
                        }
                    }

                }
                maze[y*2+1][x*2+1]=9;
            }

            if (DEBUG) print_maze();
        }
        // print_maze();
        printf("turns:%lld\n",turn);
        scores[round] = turn;
        total_turns += turn;
    }
    printf("%d rounds in a %d*%d maze\n",ROUNDS,X,Y);
    long long avg = total_turns/ROUNDS;
    printf("average: % 10lld\n",avg);
    long long var = 0;
    for(int r=0;r<ROUNDS;r++){
        var += (scores[r]-avg)*(scores[r]-avg);
    }
    var/=ROUNDS;
    // printf("variance: %lld\n",var);
    int stddev=sqrt(var);
    printf("stddev:  % 10d\n",stddev);

}

salida (con tiempo):

...
turns:194750
turns:506468
turns:129684
turns:200712
turns:158664
turns:156550
turns:311440
turns:137900
turns:86948
turns:107134
turns:81806
turns:310274
100000 rounds in a 20*20 maze
average:     227934
stddev:      138349
real    10m54.797s
...

Ejemplo de mi laberinto, con mitades de aproximadamente la misma longitud del camino, que muestra el camino izquierdo / inferior cortado de la salida (abajo a la derecha)

  _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _
 |  _   _   _   _   _   _   _   _   _  |
 | | | | | | | | | | | | | | | | | | | |
 | | | | | | | | | | | | | | | | | | | |
 | | | | | | | | | | | | | | | | | | | |
 | | | | | | | | | | | | | | | | | | | |
 | | | | | | | | | | | | | | | | | | | |
 | | | | | | | | | | | | | | | | | | | |
 | | | | | | | | | | | | | | | | | | | |
 | | | | | | | | | | | | | | | | | | | |
 | | | | | | | | | | | | | | | | | | | |
 | | | | | | | | | | | | | | | | | | | |
 | | | | | | | | | | | | | | | | | | | |
 | | | | | | | | | | | | | | | | | | | |
 | | | | | | | | | | | | | | | | | | | |
 | | | | | | | | | | | | | | | | | | | |
 | | | | | | | | | | | | | | | | | | | |
 | | | | | | | | | | |_| |_| |_| |_| |_|
 | | | | | | | | | |_ _ _ _ _ _ _ _ _ _
 |_| |_| |_| |_| |_ _ _ _ _ _ _ _ _ _  !

PD: Soy consciente de una mejora muy pequeña en este algoritmo que requiere un código más inteligente para generar una forma diferente para los dos caminos, escaleras en lugar de zigzags de altura constante.

Sparr
fuente
Coloreame impresionado. Tienes mi voto señor!
estokástica
1
Eso es bastante impresionante. ¿Recuerdas cuando dibujamos las caras de los borrachos?
Dennis
Es bastante difícil discernir su gráfico, ¿tal vez pueda cambiar la impresión de su gráfico a algo similar al mío?
justhalf
1
@justhalf tu deseo es mi orden
Sparr
1
@justhalf Lo tengo dibujado en papel. Solo necesito escribir la lógica. Si no lo hago en un par de días más, ¿te daré el boceto? :)
Sparr
6

135,488,307.9 para 98x98

199094.3 para 20x20

He implementado una solución que crea dos caminos hacia el final, y cierra exactamente uno de ellos una vez que el borracho lo alcanza. Esto simula una longitud de ruta que, como mínimo, será 1,5 veces la longitud de una ruta única de principio a fin. Después de 27 carreras llegué a un promedio de alrededor de 135 millones. Desafortunadamente, toma varios minutos por caminata, así que tendré que correrlo durante las próximas horas. Una advertencia: mi generador de doble ruta solo funciona si el tamaño del gráfico tiene la forma 4 * n + 2, lo que significa que lo más cerca que puedo llegar a 100 es 102 o 98. Voy a publicar resultados usando 98, que espero aún superar el método de la ruta en zigzag. Trabajaré en un mejor sistema de ruta más adelante. Actualmente los resultados se muestran en forma de (numSteps, currentAverage) después de cada caminata.

EDITAR: corregido, por lo que el código ahora funciona en tamaños de gráfico que son múltiplos de 2, en lugar de 4 * n + 2.

Código: (agregue el argumento 'Verdadero' al constructor de caminantes en la línea 187 para dibujar tortugas en el gráfico).

import random
import turtle

WIDTH  = 20
HEIGHT = 20
L, U, R, D = 1, 2, 4, 8

def delEdge(grid, x1, y1, x2, y2):

    # check that coordinates are in-bounds
    if not (0 <= x1 < WIDTH):  return False
    if not (0 <= y1 < HEIGHT): return False
    if not (0 <= x2 < WIDTH):  return False
    if not (0 <= y2 < HEIGHT): return False

    # swap order such that x1 <= x2 and y1 <= y2
    if x2 < x1:
        x2 ^= x1
        x1 ^= x2
        x2 ^= x1
    if x2 < x1: print "Swap failure: {}, {}".format(x1, x2)

    if y2 < y1:
        y2 ^= y1
        y1 ^= y2
        y2 ^= y1
    if y2 < y1: print "Swap failure: {}, {}".format(y1, y2)

    # check that only one of the deltas is = 1
    dx = x2 - x1
    dy = y2 - y1

    if dx and dy:       return False
    if not (dx or dy):  return False
    if dx > 1:          return False
    if dy > 1:          return False

    #print "<{}, {}>, <{}, {}>".format(x1, y1, x2, y2)

    if dx > 0:
        try: grid[x1][y1].remove(R)
        except: pass
        try: grid[x2][y2].remove(L)
        except: pass
    if dy > 0:
        try: grid[x1][y1].remove(D)
        except: pass
        try: grid[x2][y2].remove(U)
        except: pass

    return True

def newGrid():

    grid = [[[] for y in xrange(HEIGHT)] for x in xrange(WIDTH)]

    for x in xrange(WIDTH):
        for y in xrange(HEIGHT):
            if x > 0:
                grid[x][y].append(L)
            if x < WIDTH-1:
                grid[x][y].append(R)
            if y > 0:
                grid[x][y].append(U)
            if y < HEIGHT-1:
                grid[x][y].append(D)

    return grid

class walker:

    def __init__(self, grid, mode, draw=False):
        self.x  = 0
        self.y  = 0
        self.dx = WIDTH-1
        self.dy = HEIGHT-1

        self.grid     = grid
        self.mode     = mode
        self.draw     = draw
        self.numSteps = 0

        self.initGrid()

    def initGrid(self):
        if self.mode == 0:
            #pass
            if self.draw: drawGrid(grid)

        elif self.mode == 1:

            for y in xrange(HEIGHT-1):
                if y % 2 == 0:
                    for x in xrange(WIDTH - 1):
                        delEdge(grid, x, y, x, y+1)
                else:
                    for x in xrange(1, WIDTH):
                        delEdge(grid, x, y, x, y+1)
            if self.draw: drawGrid(grid)

        elif self.mode == 2:
            for y in xrange(HEIGHT/2):
                if y % 2 == 0:
                    for x in xrange(1, WIDTH-1):
                        delEdge(grid, x, y, x, y+1)
                else:
                    for x in xrange(2, WIDTH):
                        delEdge(grid, x, y, x, y+1)
            for y in xrange(HEIGHT/2, HEIGHT-1):
                if y%2 == 0:
                    for x in xrange(1, WIDTH-1):
                        delEdge(grid, x, y, x, y+1)
                else:
                    for x in xrange(0, WIDTH-2):
                        delEdge(grid, x, y, x, y+1)
            for y in xrange(1, HEIGHT-1):
                midpoint = HEIGHT/2
                if HEIGHT % 4 == 0: 
                    midpoint = HEIGHT/2 + 1
                if y < midpoint:
                    delEdge(grid, 0, y, 1, y)
                else:
                    delEdge(grid, WIDTH-1, y, WIDTH-2, y)
            if self.draw: drawGrid(grid)

    def walk(self):
        self.numSteps += 1
        choices = grid[self.x][self.y]
        direction = random.choice(choices)
        #print (self.x, self.y), grid[self.x][self.y], direction
        if direction   == L: self.x -= 1
        elif direction == U: self.y -= 1
        elif direction == R: self.x += 1
        elif direction == D: self.y += 1

    def main(self):
        hasBlocked = False
        while (self.x, self.y) != (self.dx, self.dy):
            #print (self.x, self.y), (self.dx, self.dy)
            self.walk()
            if self.mode == 2:
                if not hasBlocked:
                    if (self.x, self.y) == (WIDTH-2, HEIGHT-1):
                        delEdge(self.grid, WIDTH-2, HEIGHT-1, WIDTH-1, HEIGHT-1)
                        hasBlocked = True
                    elif (self.x, self.y) == (WIDTH-1, HEIGHT-2):
                        delEdge(self.grid, WIDTH-1, HEIGHT-1, WIDTH-1, HEIGHT-2)
                        hasBlocked = True

        return self.numSteps

def drawGrid(grid):
    size = 3
    turtle.speed(0)
    turtle.delay(0)
    turtle.ht()
    for x in xrange(WIDTH):
        for y in xrange(HEIGHT):
            dirs = grid[x][y]
            for dir in dirs:
                if dir == L:
                    turtle.pu()
                    turtle.setpos((x*4, y*4))
                    turtle.pd()
                    turtle.setpos(((x-1)*4, y*4))
                elif dir == R:
                    turtle.pu()
                    turtle.setpos((x*4, y*4))
                    turtle.pd()
                    turtle.setpos(((x+1)*4, y*4))
                elif dir == U:
                    turtle.pu()
                    turtle.setpos((x*4, y*4))
                    turtle.pd()
                    turtle.setpos((x*4, (y-1)*4))
                elif dir == D:
                    turtle.pu()
                    turtle.setpos((x*4, y*4))
                    turtle.pd()
                    turtle.setpos((x*4, (y+1)*4))
    turtle.mainloop()

numTrials  = 100
totalSteps = 0.0
i = 0
try:
    while i < numTrials:
        grid = newGrid()

        w = walker(grid, 2)
        steps = w.main()
        totalSteps += steps
        print steps, totalSteps/(i+1)
        i += 1

    print totalSteps / numTrials

except KeyboardInterrupt:
    print totalSteps / i

Datos sin procesar: (numSteps actual, promedio de ejecución)

358796490 358796490.0
49310430 204053460.0
106969130 171692016.667
71781702 146714438.0
49349086 127241367.6
40874636 112846912.333
487607888 166384194.571
56423642 152639125.5
71077302 143576700.667
101885368 139407567.4
74423642 133499937.818
265170542 144472488.167
59524778 137938048.923
86919630 134293876.143
122462528 133505119.6
69262650 129489965.25
85525556 126903823.529
161165512 128807250.667
263965384 135920836.632
128907594 135570174.5
89535930 133378067.619
97344576 131740181.636
98772132 130306788.174
140769524 130742735.5
198274280 133443997.28
95417374 131981434.846
226667006 135488307.852
estocástico
fuente
Reduje el tamaño del gráfico a 20 por 20 para agilizar los tiempos de ejecución. Espero que ayude.
Actualmente estás ganando :)
¿Su puntaje de 20 por 20 supera las 1000 carreras?
@Lembik sí lo es.
stokastic
1
@Dennis au contraire :)
Sparr
6

Enfoque de 4 caminos, 213k

El enfoque de un camino es

Línea recta de S a E

y puntúa un promedio de N^2.

El enfoque de dos caminos es

Bucle con S y E uno frente al otro

pero luego, la primera vez que el borracho se acerca al punto final, se corta:

El bucle se corta para dar una línea curva de S a E

Se puntúa un promedio de (N/2)^2 + N^2.

El enfoque de cuatro caminos usa dos cortes:

Bucles anidados, unidos en dos tenedores, uno a cada lado de E Cortar una de las horquillas en el lado E En el otro lado, corte la horquilla en el lado que no sea E. Esto deja un camino complicado

Suponga que el bucle externo es de longitud xNy el bucle interno de longitud (1-x)N. Por simplicidad, lo normalizaré N=1.

Desde el comienzo hasta el primer corte se obtiene un promedio de (x/2)^2. Desde el primer corte hasta el segundo corte tiene dos opciones, de longitudes xy 1-x; esto da un promedio de (1-x)x^2 + x(1-x)^2 = x-x^2. Finalmente el camino restante da 1. Entonces el puntaje total es N^2 (1 + x - 3/4 x^2).

Inicialmente supuse que mantener las rutas disponibles de igual longitud en cada paso sería óptimo, por lo que mi enfoque inicial solía x = 1/2dar una puntuación de 1.3125 N^2. Pero después de hacer el análisis anterior, resulta que la división óptima se da cuando se x = 2/3puntúa 1.3333 N^2.

1000 walks with average 210505.738 in 202753ms


1000 walks with average 212704.626 in 205191ms

con código

import java.awt.Point;
import java.util.*;

// http://codegolf.stackexchange.com/q/37484/194
public class RandomWalker {
    private static final int SIZE = 19;
    private static final Point dest = new Point(SIZE, SIZE);

    private final Random rnd = new Random();
    private Point p = new Point(0, 0);
    private int step = 0;
    private Set<Set<Point>> edges;
    private Map<Set<Point>, String> cuttableEdgeNames;
    private Set<String> cutSequences;
    private String cutSequence = "";

    public static void main(String[] args) {
        long start = System.nanoTime();
        long total = 0;
        int walks = 0;
        while (walks < 1000 && total < 1L << 40) {
            RandomWalker rw = new RandomWalker();
            total += rw.walk();
            walks++;
        }

        long timeTaken = System.nanoTime() - start;
        System.out.println(walks + " walks with average " + total / (double)walks + " in " + (timeTaken / 1000000) + "ms");
    }

    RandomWalker() {
        loadMaze(
            "+-+ +-+ +-+ +-+ +-+ +-+ +-+-+-+-+-+-+-+",
            "| | | | | | | | | | | | |             |",
            "+ + + + + + + + + + + + + +-+ +-+ +-+ +",
            "| | | | | | | | | | | | | | | | | | | |",
            "+ + + + + + + + + + + + + + + + + + + +",
            "| | | | | | | | | | | | | | | | | | | |",
            "+ + + + + + + + + + + +-+ + + + + + + +",
            "| | | | | | | | | | |     | | | | | | |",
            "+ + + + + + + + + + + +-+-+ + + + + + +",
            "| | | | | | | | | | | |     | | | | | |",
            "+ + + + + + + + + + + + +-+ + + + + + +",
            "| | | | | | | | | | | | | | | | | | | |",
            "+ + + + + + + + + + + + + + + + + + + +",
            "| | | | | | | | | | | | | | | | | | | |",
            "+ + + + + + + + + + + + + + + + + + + +",
            "| | | | | | | | | | | | | | | | | | | |",
            "+ + + + + + + + + + + + + + + + + + + +",
            "| | | | | | | | | | | | | | | | | | | |",
            "+ +-+ +-+ +-+ +-+ +-+ + + + + + + + + +",
            "|                     | | | | | | | | |",
            "+ +-+ +-+ +-+ +-+ +-+ + + + + + + + + +",
            "| | | | | | | | | | | | | | | | | | | |",
            "+ + + + + + + + + + + + + + + + + + + +",
            "| | | | | | | | | | | | | | | | | | | |",
            "+ + + + + + + + + + + + + + + + + + + +",
            "| | | | | | | | | | | | | | | | | | | |",
            "+ + + + + + + + + + + + + + + + + + + +",
            "| | | | | | | | | | | | | | | | | | | |",
            "+ + + + + + + + + + + + + + + + + + + +",
            "| | | | | | | | | | | | | | | | | | | |",
            "+ + + + + + + + + + + +-+ + + + + + + +",
            "| | | | | | | | | | |     | | | | | | |",
            "+ + + + + + + + + + + +-+ + + + + + + +",
            "| | | | | | | | | | | | | | | | | | | d",
            "+ + + + + + + + + + + + + + +-+ +-+ +c+",
            "| | | | | | | | | | | | | |           |",
            "+ + + + + + + + + + + + + +-+-+-+-+-+ +",
            "| | | | | | | | | | | | |           f b",
            "+-+ +-+ +-+ +-+ +-+ +-+ +-+-+-+-+-+e+a+"
        );
        cutSequences = new HashSet<String>();
        cutSequences.add("ac");
        cutSequences.add("ad");
        cutSequences.add("be");
        cutSequences.add("bf");
    }

    private void loadMaze(String... row) {
        edges = new HashSet<Set<Point>>();
        cuttableEdgeNames = new HashMap<Set<Point>, String>();

        // Horizontal edges
        for (int y = 0; y <= SIZE; y++) {
            for (int x0 = 0; x0 < SIZE; x0++) {
                char ch = row[y * 2].charAt(x0 * 2 + 1);
                if (ch == ' ') continue;
                Set<Point> edge = new HashSet<Point>();
                edge.add(new Point(x0, y));
                edge.add(new Point(x0 + 1, y));
                edges.add(edge);
                if (ch != '-') cuttableEdgeNames.put(edge, "" + ch);
            }
        }

        // Vertical edges
        for (int y0 = 0; y0 < SIZE; y0++) {
            for (int x = 0; x <= SIZE; x++) {
                char ch = row[y0 * 2 + 1].charAt(x * 2);
                if (ch == ' ') continue;
                Set<Point> edge = new HashSet<Point>();
                edge.add(new Point(x, y0));
                edge.add(new Point(x, y0 + 1));
                edges.add(edge);
                if (ch != '|') cuttableEdgeNames.put(edge, "" + ch);
            }
        }
    }

    int walk() {
        while (!p.equals(dest)) {
            List<Point> neighbours = neighbours(p);
            int idx = rnd.nextInt(neighbours.size());
            p = neighbours.get(idx);
            step++;
        }

        return step;
    }

    List<Point> neighbours(Point p) {
        List<Point> rv = new ArrayList<Point>();
        if (p.x > 0) handlePossibleNeighbour(rv, p, new Point(p.x - 1, p.y));
        if (p.x < SIZE) handlePossibleNeighbour(rv, p, new Point(p.x + 1, p.y));
        if (p.y > 0) handlePossibleNeighbour(rv, p, new Point(p.x, p.y - 1));
        if (p.y < SIZE) handlePossibleNeighbour(rv, p, new Point(p.x, p.y + 1));
        return rv;
    }

    private void handlePossibleNeighbour(List<Point> neighbours, Point p1, Point p2) {
        if (edgeExists(p1, p2)) neighbours.add(p2);
    }

    private boolean edgeExists(Point p1, Point p2) {
        Set<Point> edge = new HashSet<Point>();
        edge.add(p1);
        edge.add(p2);

        // Is it cuttable?
        String id = cuttableEdgeNames.get(edge);
        if (id != null) {
            String prefix = cutSequence + id;
            for (String seq : cutSequences) {
                if (seq.startsWith(prefix)) {
                    // Cut it
                    cutSequence = prefix;
                    edges.remove(edge);
                    return false;
                }
            }
        }

        return edges.contains(edge);
    }
}
Peter Taylor
fuente
Ah, ya veo, por eso mi enfoque de isla no funciona, no equilibré la longitud del camino. Solo para aclarar mi comprensión, la longitud desde fhasta cen su código se trata N/2, sea a través de e(y d) o no, ¿verdad?
justhalf
¿Cómo es la longitud de ruta yE N en lugar de la longitud N / 2?
Sparr
@justhalf, sí. Hay 400 vértices, por lo que hay 401 aristas (después de un corte, el gráfico es un ciclo hamiltoniano); los dos caminos exteriores tienen 100 bordes cada uno y, por lo tanto, el bucle interno tiene 101 bordes.
Peter Taylor
Entendido. dos observaciones: a) los laberintos más grandes se beneficiarían de 2 ^ n caminos mayores. b) si hace que la longitud de su ruta sea dinámica, vencerá a los líderes actuales con soluciones dinámicas de dos rutas (yo y @justhalf)
Sparr
@Sparr: es N^2, no 2^N. Y sí, hacer que esta dinámica sea la mejor, el desafío es cómo hacerlo dinámico manteniendo la propiedad de cuatro rutas. @PeterTaylor: ¡Buenas imágenes!
justhalf
5

Experimenté cortando la cuadrícula casi por completo en cada kfila. Esto efectivamente lo convierte en algo similar a una caminata aleatoria en un kbyN * N/k rejilla. La opción más efectiva es cortar cada fila para que obliguemos al borracho a zigzaguear.

Para el caso 20x20 ( SIZE=19) tengo

time java RandomWalker 
1000 walks with average 148577.604

real    0m14.076s
user    0m13.713s
sys     0m0.360s

con código

import java.awt.Point;
import java.util.*;

// http://codegolf.stackexchange.com/q/37484/194
// This handles a simpler problem where the grid is mutilated before the drunkard starts to walk.
public class RandomWalker {
    private static final int SIZE = 19;
    private final Random rnd = new Random();

    public static void main(String[] args) {
        RandomWalker rw = new RandomWalker();
        long total = 0;
        int walks = 0;
        while (walks < 1000 && total < 1L << 40) {
            total += rw.walk();
            walks++;
        }

        System.out.println(walks + " walks with average " + total / (double)walks);
    }

    int walk() {
        Point dest = new Point(SIZE, SIZE);
        Point p = new Point(0, 0);
        int step = 0;

        while (!p.equals(dest)) {
            List<Point> neighbours = neighbours(p);
            int idx = rnd.nextInt(neighbours.size());
            p = neighbours.get(idx);
            step++;
        }

        return step;
    }

    List<Point> neighbours(Point p) {
        List<Point> rv = new ArrayList<Point>();
        if (p.x > 0) handlePossibleNeighbour(rv, p, new Point(p.x - 1, p.y));
        if (p.x < SIZE) handlePossibleNeighbour(rv, p, new Point(p.x + 1, p.y));
        if (p.y > 0) handlePossibleNeighbour(rv, p, new Point(p.x, p.y - 1));
        if (p.y < SIZE) handlePossibleNeighbour(rv, p, new Point(p.x, p.y + 1));
        return rv;
    }

    private void handlePossibleNeighbour(List<Point> neighbours, Point p1, Point p2) {
        if (edgeExists(p1, p2)) neighbours.add(p2);
    }

    private boolean edgeExists(Point p1, Point p2) {
        return p1.x != p2.x || p1.x == SIZE * (Math.max(p1.y, p2.y) & 1);
    }
}
Peter Taylor
fuente
¿Estoy en lo cierto al pensar que toda la eliminación de bordes ocurre antes de que comience la caminata en su solución?
@Lembik, sí. Pensé que el comentario en la parte superior lo dejaría claro.
Peter Taylor
Sí, gracias. Me pregunto cuánta diferencia puedes hacer al eliminar bordes durante la caminata.
Por curiosidad, ¿cuánto tiempo tarda esto en ejecutarse (en total y por ejecución)?
stokastic
@stokastic, aproximadamente 3 segundos por carrera.
Peter Taylor
3

Para los que no quieren reinventar la rueda.

No te preocupes Lo reinventaré por ti :)

Esto está en Java, por cierto.

Creé una clase Walker que trata de caminar al azar. También incluye un método útil para determinar si un movimiento es válido (si ya se ha pisado).

Supongo que todos ustedes, personas inteligentes, pueden resolver poner números aleatorios para el constructor, se lo dejé a ustedes para que pudieran probar ciertos casos. Además, solo llame a la función walk () para (¡lo adivinó!) Hacer que el borracho camine (al azar).

Implementaré la función canComeHome () en otro momento. Preferiblemente después de buscar la mejor manera de hacerlo.

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.TreeSet;

public class Walker {
    int width,height;
    int x,y; //walker's position (does anyone else keep thinking about zombies?!?)
    int dX,dY; //destination
    TreeSet<Edge> pathsNoLongerAvailable = new TreeSet<Edge>();
    TreeSet<Edge> previouslyTraveled = new TreeSet<Edge>();
    int stepCount = 0;

    public static void main(String[]args){
        int side = 10;
        Walker walker = null;
        int total = 0;
        double count = 1000;
        for(int i=0; i<count; i++){
            walker = new Walker(0,0,side,side,side-1,side-1);
            total += walker.stepCount;
            System.out.println("Iteration "+i+": "+walker.stepCount);
        }
        System.out.printf("Average: %.3f\n", total/count);
        walker.printPath();
    }

    public Walker(int startingX,int startingY, int Width, int Height, int destinationX, int destinationY){
        width = Width;
        height = Height;
        dX = destinationX;
        dY = destinationY;
        x=startingX;
        y=startingY;
        while(!walk()){
            // Do something
        }
    }

    public void printPath(){
        for(int i=0; i<width-1; i++){
            if(!pathsNoLongerAvailable.contains(new Edge(i,height-1,i+1,height-1))){
                System.out.print(" _");
            } else {
                System.out.print("  ");
            }
        }
        System.out.println();
        for(int i=height-2; i>=0; i--){
            for(int j=0; j<2*width-1; j++){
                if(j%2==0){
                    if(!pathsNoLongerAvailable.contains(new Edge(j/2,i,j/2,i+1))){
                        System.out.print("|");
                    } else {
                        System.out.print(" ");
                    }
                } else {
                    if(!pathsNoLongerAvailable.contains(new Edge(j/2,i,j/2+1,i))){
                        System.out.print("_");
                    } else {
                        System.out.print(" ");
                    }
                }
            }
            System.out.println();
        }
    }

    public boolean walk(){
        ArrayList<int[]> possibleMoves = new ArrayList<int[]>();
        if(x!=0 && !pathsNoLongerAvailable.contains(new Edge(x,y,x-1,y))){
            possibleMoves.add(new int[]{-1,0});
        }
        if(x!=width-1 && !pathsNoLongerAvailable.contains(new Edge(x,y,x+1,y))){
            possibleMoves.add(new int[]{1,0});
        }
        if(y!=0 && !pathsNoLongerAvailable.contains(new Edge(x,y,x,y-1))){
            possibleMoves.add(new int[]{0,-1});
        }
        if(y!=height-1 && !pathsNoLongerAvailable.contains(new Edge(x,y,x,y+1))){
            possibleMoves.add(new int[]{0,1});
        }
        int random = (int)(Math.random()*possibleMoves.size());
        int[] move = possibleMoves.get(random);
        previouslyTraveled.add(new Edge(x,y,x+move[0],y+move[1]));
        x+=move[0];
        y+=move[1];
        stepCount++;
        if(x==dX && y == dY){
            return true;
        } else {
            return false;
        }
    }

    public boolean isSolvable(){
        TreeSet<Point> reachable = new TreeSet<Point>();
        Queue<Point> next = new LinkedList<Point>();
        next.offer(new Point(x,y));
        reachable.add(new Point(x,y));
        while(next.size()>0){
            Point cur = next.poll();
            int x = cur.x;
            int y = cur.y;
            ArrayList<Point> neighbors = new ArrayList<Point>();
            if(x!=0 && !pathsNoLongerAvailable.contains(new Edge(x,y,x-1,y))){
                neighbors.add(new Point(x-1, y));
            }
            if(x!=width-1 && !pathsNoLongerAvailable.contains(new Edge(x,y,x+1,y))){
                neighbors.add(new Point(x+1, y));
            }
            if(y!=0 && !pathsNoLongerAvailable.contains(new Edge(x,y,x,y-1))){
                neighbors.add(new Point(x, y-1));
            }
            if(y!=height-1 && !pathsNoLongerAvailable.contains(new Edge(x,y,x,y+1))){
                neighbors.add(new Point(x, y+1));
            }
            for(Point neighbor: neighbors){
                if(!reachable.contains(neighbor)){
                    if(neighbor.compareTo(new Point(dX, dY))==0){
                        return true;
                    }
                    reachable.add(neighbor);
                    next.offer(neighbor);
                }
            }
        }
        return false;
    }

    public boolean hasBeenWalked(int x1, int y1, int x2, int y2){
        return previouslyTraveled.contains(new Edge(x1, y1, x2, y2));
    }

    public boolean hasBeenWalked(Edge edge){
        return previouslyTraveled.contains(edge);
    }

    public void deletePath(int startX, int startY, int endX, int endY){
        Edge toAdd = new Edge(startX,startY,endX,endY);
        if(hasBeenWalked(toAdd)){
            System.out.println("Edge already travelled!");
            return;
        }
        pathsNoLongerAvailable.add(toAdd);
        if(!isSolvable()){
            pathsNoLongerAvailable.remove(toAdd);
            System.out.println("Invalid deletion!");
        }
    }

    static class Edge implements Comparable<Edge>{
        Point start, end;

        public Edge(int x1, int y1, int x2, int y2){
            start = new Point(x1, y1);
            end = new Point(x2, y2);
            if(start.compareTo(end)>0){
                Point tmp = end;
                end = start;
                start = tmp;
            }
        }

        @Override
        public int compareTo(Edge o) {
            int result = start.compareTo(o.start);
            if(result!=0) return result;
            return end.compareTo(o.end);
        }
    }

    static class Point implements Comparable<Point>{
        int x,y;
        public Point(int x, int y){
            this.x = x;
            this.y = y;
        }
        public int compareTo(Point o){
            int result = Integer.compare(x, o.x);
            if(result!=0) return result;
            result = Integer.compare(y, o.y);
            if(result!=0) return result;
            return 0;
        }
    }
}
Estiramiento Maniaco
fuente
Esto contiene algunos errores e inconsistencias. previouslyTraveled.add(new int[]{x,y,move[0],move[1]})debería ser x+move[0]y y+move[1]. El Width-1y Height-1, y la ineficiencia en la comprobación de las rutas eliminadas. He editado tu código (con función adicional para imprimir el laberinto). Siéntase libre de retroceder si cree que es inapropiado.
justhalf
Tu Edge no se implementa correctamente Comparable<Edge>. Si desea que las aristas se comparen como iguales, incluso si las invierte, debe tener en cuenta la inversión también en el caso no igual. La forma más fácil de hacerlo sería cambiar el constructor para mantener los puntos ordenados.
Peter Taylor
@ PeterTaylor: Gracias por el aviso. Pensé un poco en el caso no igual, pero no pude entender por qué es importante. ¿Sabes dónde puedo buscar el requisito de implementación Comparable?
justhalf
1
docs.oracle.com/javase/7/docs/api/java/lang/Comparable.html La clave es que necesita definir un pedido total. Pero si Ay Bse invierte el mismo borde y Ces diferente, puede obtener A.compareTo(B) == B.compareTo(A) == 0but A.compareTo(C) < 0y B.compareTo(C) > 0.
Peter Taylor
¿Que tal ahora? Agregué otra clase. Y agregué la función para verificar si es solucionable (o canComeHome())
solo el
3

64,281

Actualización desde que la cuadrícula se cambió de 100x100 a 20x20 (1000 pruebas). La puntuación en 100x100 (100 pruebas) fue aproximadamente 36M.

Si bien esto no va a superar una caminata de 1D, quería jugar con una idea que tenía.

La idea básica es que la cuadrícula se divide en habitaciones cuadradas, con solo un camino que conduce 'hacia el hogar' de cada una. El camino abierto es el que el borracho se acerca al último , lo que significa que tiene que explorar todas las salidas posibles, solo para que todos menos uno se estrellen en su cara.

Después de jugar con el tamaño de las habitaciones, llegué a la misma conclusión que Peter, dividirlo más pequeño es mejor. Las mejores puntuaciones vienen con un tamaño de habitación de 2.

Average score over 100 trials: 36051265

El código es descuidado, no importa el desorden. Puede activar el SHOWinterruptor y mostrará una imagen de los caminos en cada SHOW_INTpaso para que pueda verlo en acción. Una ejecución completa se parece a:

ingrese la descripción de la imagen aquí

(Esta es la imagen de la cuadrícula anterior de 100x100. 20x20 es así, pero, bueno, más pequeño. El siguiente código se ha actualizado para nuevos tamaños / ejecuciones).

import java.awt.Color;
import java.awt.Graphics;
import java.awt.Point;
import java.awt.image.*;
import java.util.*;
import javax.swing.*;

public class DrunkWalk {

    boolean SHOW = false;
    int SHOW_INT = 10;
    int SIZE = 20;
    Random rand = new Random();
    Point pos;
    int[][] edges;
    int[][] wally;
    int[] wallx;
    int roomSize = 2;
    JFrame frame;
    final BufferedImage img;

    public static void main(String[] args){
        long total=0,runs=1000;
        for(int i=0;i<runs;i++){
            int steps = new DrunkWalk().run();
            total += steps;
            System.out.println("("+i+") "+steps);
        }
        System.out.println("\n Average " + (total/runs) + " over " + runs + " trials.");
    }

    DrunkWalk(){
        edges = new int[SIZE][SIZE];
        for(int x=0;x<SIZE;x++){
            for(int y=0;y<SIZE;y++){
                if(x>0) edges[x][y] |= WEST;
                if(x+1<SIZE) edges[x][y] |= EAST;
                if(y>0) edges[x][y] |= NORTH;
                if(y+1<SIZE) edges[x][y] |= SOUTH;
            }
        }
        wallx = new int[SIZE/roomSize+1];
        wally = new int[SIZE/roomSize+1][SIZE/roomSize+1];
        pos = new Point(SIZE-1,SIZE-1);
        img = new BufferedImage(SIZE*6+1,SIZE*6+1, BufferedImage.TYPE_INT_RGB);
        frame = new JFrame(){
            public void paint(Graphics g) {
                g.drawImage(img, 50, 50, null);
            }
        };
        frame.setSize(700,700);
        if(SHOW)
            frame.show();
    }

    void draw(){
        try {
            Thread.sleep(200);
        } catch (InterruptedException e) {
            e.printStackTrace();
        }

        Graphics g = img.getGraphics();
        g.setColor(Color.WHITE);
        g.clearRect(0, 0, img.getWidth(), img.getHeight());
        for(int x=0;x<SIZE;x++){
            for(int y=0;y<SIZE;y++){
                if((edges[x][y]&EAST)==EAST)
                    g.drawLine(x*6, y*6, x*6+5, y*6);
                if((edges[x][y]&SOUTH)==SOUTH)
                    g.drawLine(x*6, y*6, x*6, y*6+5);
            }
        }
        g.setColor(Color.RED);
        g.drawOval(pos.x*6-2, pos.y*6-2, 5, 5);
        g.drawOval(pos.x*6-1, pos.y*6-1, 3, 3);
        frame.repaint();
    }

    int run(){
        int steps = 0;
        Point home = new Point(0,0);
        while(!pos.equals(home)){
            if(SHOW&&steps%SHOW_INT==0){
                System.out.println(steps);
                draw();
            }
            step();
            adversary();
            steps++;
        }
        if(SHOW)
            draw();
        return steps;
    }

    void adversary(){
        int rx = pos.x / roomSize;
        int ry = pos.y / roomSize;
        int maxWalls = roomSize - 1;
        if(wally[rx][ry] < maxWalls){
            if(pos.y%roomSize==0)
                if(delete(pos.x,pos.y,NORTH))
                    wally[rx][ry]++;
        }
        maxWalls = SIZE-1;
        if(pos.x%roomSize==0){
            if(wallx[rx] < maxWalls)
                if(delete(pos.x, pos.y,WEST))
                    wallx[rx]++;


        }       
    }

    void step(){
        List<Integer> choices = getNeighbors(pos);
        Collections.shuffle(choices);
        int dir = choices.get(0);
        pos.x += dir==WEST?-1:dir==EAST?1:0;
        pos.y += dir==NORTH?-1:dir==SOUTH?1:0;
    }

    boolean delete(int x, int y, int dir){
        if((edges[x][y] & dir) != dir)
            return false;
        edges[x][y] -= dir;
        if(dir == NORTH)
            if(y>0) edges[x][y-1] -= SOUTH;
        if(dir == SOUTH)
            if(y+1<SIZE) edges[x][y+1] -= NORTH;
        if(dir == EAST)
            if(x+1<SIZE) edges[x+1][y] -= WEST;
        if(dir == WEST)
            if(x>0) edges[x-1][y] -= EAST;
        return true;
    }

    List<Integer> getNeighbors(Point p){
        if(p.x==SIZE || p.y==SIZE){
            System.out.println("wtf");
            System.exit(0);
        }
        List<Integer> choices = new ArrayList<Integer>();
        if((edges[p.x][p.y] & NORTH) == NORTH)
            choices.add(NORTH);
        if((edges[p.x][p.y] & SOUTH) == SOUTH)
            choices.add(SOUTH);
        if((edges[p.x][p.y] & EAST) == EAST)
            choices.add(EAST);
        if((edges[p.x][p.y] & WEST) == WEST)
            choices.add(WEST);
        return choices;
    }

    final static int NORTH=1,EAST=2,SOUTH=4,WEST=8;
}
Geobits
fuente
Acabo de notar que debería ir desde bot / left-> top / right, mientras que el mío va bot / right-> top / left. Puedo cambiarlo si realmente importa, pero ...
Geobits
Esto es muy bueno y creo que es la primera solución dinámica. Estoy interesado en que tu camino no sea tan largo como los estáticos todavía.
Si por "no tan largo" quieres decir ~ 1/3 mientras uno y ~ 36 veces más que el otro? : P
Geobits
3

188k, con 2 caminos

Todas las mejores entradas parecen adoptar el enfoque de generar 2 caminos, y luego cortar uno cuando el borracho se acerca al final del camino. No creo que pueda superar la entrada de justhalf, pero no pude evitar preguntarme: ¿por qué 2 caminos? ¿Por qué no 3, 5 o 20?

TL; DR : 2 caminos parecen ser óptimos

Entonces hice un experimento. Basado en el marco de Stretch Maniac, escribí una entrada para probar varios números de caminos. Puede ajustar el featureSizeparámetro para variar el número de rutas. A featureSizede 20 da 1 ruta, 10 da 2 rutas, 7 da 3, 5 da 4, y así sucesivamente.

import java.util.ArrayList;
import java.util.BitSet;
import java.util.HashSet;
import java.util.LinkedHashSet;
import java.util.LinkedList;
import java.util.Objects;
import java.util.Queue;
import java.util.Set;
import java.util.concurrent.ThreadLocalRandom;

public class Walker {
    final int width,height;
    int x,y; //walker's position (does anyone else keep thinking about zombies?!?)
    final int dX,dY; //destination
    final int featureSize;
    Set<Edge> pathsNoLongerAvailable = new HashSet<>();
    Set<Edge> previouslyTraveled = new HashSet<>();
    int stepCount = 0;
    private final BitSet remainingExits;

    public static void main(String[]args){
        int side = 20;
        Walker walker = null;
        int total = 0;
        int featureSize = 10;
        double count = 1000;
        for(int i=0; i<count; i++){
            walker = new Walker(0,0,side,side,side-1,side-1, featureSize);
            total += walker.stepCount;
            System.out.println("Iteration "+i+": "+walker.stepCount);
        }
        System.out.printf("Average: %.3f\n", total/count);
        walker.printPath();
    }

    public Walker(int startingX,int startingY, int Width, int Height, int destinationX, int destinationY, int featureSize){
        width = Width;
        height = Height;
        dX = destinationX;
        dY = destinationY;
        x=startingX;
        y=startingY;
        this.featureSize = featureSize;

        deleteBars();

        remainingExits = new BitSet();
        for (int yy = 0; yy < height; yy++) {
            if (!pathsNoLongerAvailable.contains(new Edge(width - 2, yy, width - 1, yy))) {
                remainingExits.set(yy);
            }
        }

        while(!walk()){
            if (x == width - 2
                    && remainingExits.get(y)
                    && remainingExits.cardinality() > 1) {
                deletePath(x, y, x + 1, y);
                remainingExits.set(y, false);
            }
        }
    }

    private void deleteBars() {
        for (int xx = 0; xx < width - 1; xx++) {
            for (int yy = 0; yy < height / featureSize + 1; yy++) {
                if (xx != 0) deletePath(xx, featureSize * yy + featureSize - 1, xx, featureSize * yy + featureSize);
                boolean parity = xx % 2 == 0;
                if (yy == 0) parity ^= true; // First path should be inverted
                for (int i = 0; i < featureSize && featureSize * yy + i < height; i++) {
                    if (i == 0 && !parity) continue;
                    if ((i == featureSize - 1 || featureSize * yy + i == height - 1) && parity) continue;
                        deletePath(xx, featureSize * yy + i, xx + 1, featureSize * yy + i);
                }
            }
        }
    }

    public void printPath(){
        for(int i=0; i<width-1; i++){
            if(!pathsNoLongerAvailable.contains(new Edge(i,height-1,i+1,height-1))){
                System.out.print(" _");
            } else {
                System.out.print("  ");
            }
        }
        System.out.println();
        for(int i=height-2; i>=0; i--){
            for(int j=0; j<2*width-1; j++){
                if(j%2==0){
                    if(!pathsNoLongerAvailable.contains(new Edge(j/2,i,j/2,i+1))){
                        System.out.print("|");
                    } else {
                        System.out.print(" ");
                    }
                } else {
                    if(!pathsNoLongerAvailable.contains(new Edge(j/2,i,j/2+1,i))){
                        System.out.print("_");
                    } else {
                        System.out.print(" ");
                    }
                }
            }
            System.out.println();
        }
    }

    public boolean walk(){
        ArrayList<int[]> possibleMoves = new ArrayList<int[]>();
        if(x!=0 && !pathsNoLongerAvailable.contains(new Edge(x,y,x-1,y))){
            possibleMoves.add(new int[]{-1,0});
        }
        if(x!=width-1 && !pathsNoLongerAvailable.contains(new Edge(x,y,x+1,y))){
            possibleMoves.add(new int[]{1,0});
        }
        if(y!=0 && !pathsNoLongerAvailable.contains(new Edge(x,y,x,y-1))){
            possibleMoves.add(new int[]{0,-1});
        }
        if(y!=height-1 && !pathsNoLongerAvailable.contains(new Edge(x,y,x,y+1))){
            possibleMoves.add(new int[]{0,1});
        }
        int random = ThreadLocalRandom.current().nextInt(possibleMoves.size());
        int[] move = possibleMoves.get(random);
        previouslyTraveled.add(new Edge(x,y,x+move[0],y+move[1]));
        x+=move[0];
        y+=move[1];
        stepCount++;
        if(x==dX && y == dY){
            return true;
        } else {
            return false;
        }
    }

    public boolean isSolvable(){
        Set<Point> reachable = new HashSet<>();
        Queue<Point> next = new LinkedList<>();
        next.offer(new Point(x,y));
        reachable.add(new Point(x,y));
        while(next.size()>0){
            Point cur = next.poll();
            int x = cur.x;
            int y = cur.y;
            ArrayList<Point> neighbors = new ArrayList<>();
            if(x!=0 && !pathsNoLongerAvailable.contains(new Edge(x,y,x-1,y))){
                neighbors.add(new Point(x-1, y));
            }
            if(x!=width-1 && !pathsNoLongerAvailable.contains(new Edge(x,y,x+1,y))){
                neighbors.add(new Point(x+1, y));
            }
            if(y!=0 && !pathsNoLongerAvailable.contains(new Edge(x,y,x,y-1))){
                neighbors.add(new Point(x, y-1));
            }
            if(y!=height-1 && !pathsNoLongerAvailable.contains(new Edge(x,y,x,y+1))){
                neighbors.add(new Point(x, y+1));
            }
            for(Point neighbor: neighbors){
                if(!reachable.contains(neighbor)){
                    if(neighbor.compareTo(new Point(dX, dY))==0){
                        return true;
                    }
                    reachable.add(neighbor);
                    next.offer(neighbor);
                }
            }
        }
        return false;
    }

    public boolean hasBeenWalked(int x1, int y1, int x2, int y2){
        return previouslyTraveled.contains(new Edge(x1, y1, x2, y2));
    }

    public boolean hasBeenWalked(Edge edge) {
        return previouslyTraveled.contains(edge);
    }

    public void deletePath(int startX, int startY, int endX, int endY){
        Edge toAdd = new Edge(startX,startY,endX,endY);
        if(hasBeenWalked(toAdd)){
            System.out.println("Edge already travelled!");
            return;
        }
        pathsNoLongerAvailable.add(toAdd);
        if(!isSolvable()){
            pathsNoLongerAvailable.remove(toAdd);
            System.out.println("Invalid deletion!");
        }
    }

    public static class Edge implements Comparable<Edge>{
        Point start, end;

        public Edge(int x1, int y1, int x2, int y2){
            start = new Point(x1, y1);
            end = new Point(x2, y2);
            if(start.compareTo(end)>0){
                Point tmp = end;
                end = start;
                start = tmp;
            }
        }

        @Override
        public int compareTo(Edge o) {
            int result = start.compareTo(o.start);
            if(result!=0) return result;
            return end.compareTo(o.end);
        }

        @Override
        public String toString() {
            return start.toString() + "-" + end.toString();
        }

        @Override
        public int hashCode() {
            int hash = 7;
            hash = 83 * hash + Objects.hashCode(this.start);
            hash = 83 * hash + Objects.hashCode(this.end);
            return hash;
        }

        @Override
        public boolean equals(Object obj) {
            if (obj == null) {
                return false;
            }
            if (getClass() != obj.getClass()) {
                return false;
            }
            final Edge other = (Edge) obj;
            if (!Objects.equals(this.start, other.start)) {
                return false;
            }
            if (!Objects.equals(this.end, other.end)) {
                return false;
            }
            return true;
        }


    }

    static class Point implements Comparable<Point>{
        int x,y;
        public Point(int x, int y){
            this.x = x;
            this.y = y;
        }
        public int compareTo(Point o){
            int result = Integer.compare(x, o.x);
            if(result!=0) return result;
            result = Integer.compare(y, o.y);
            if(result!=0) return result;
            return 0;
        }
        @Override
        public String toString() {
            return "(" + x + "," + y + ")";
        }

        @Override
        public int hashCode() {
            int hash = 7;
            hash = 23 * hash + this.x;
            hash = 23 * hash + this.y;
            return hash;
        }

        @Override
        public boolean equals(Object obj) {
            if (obj == null) {
                return false;
            }
            if (getClass() != obj.getClass()) {
                return false;
            }
            final Point other = (Point) obj;
            if (this.x != other.x) {
                return false;
            }
            if (this.y != other.y) {
                return false;
            }
            return true;
        }


    }
}

Hay algunas optimizaciones que podría hacer pero que no he hecho, y no es compatible con ninguno de los trucos de adaptación que solo utiliza.

De todos modos, aquí están los resultados para varios featureSizevalores:

20 (1 path):  156284 
10 (2 paths): 188553
7 (3 paths):  162279
5 (4 paths):  152574
4 (5 paths):  134287
3 (7 paths):  118843
2 (10 paths): 94171
1 (20 paths): 64515

Y aquí hay un mapa con 3 caminos:

 _   _   _   _   _   _   _   _   _    
| | | | | | | | | | | | | | | | | | | |
| | | | | | | | | | | | | | | | | | | |
| | | | | | | | | | | | | | | | | | | |
| | | | | | | | | | | | | | | | | | | |
| |_| |_| |_| |_| |_| |_| |_| |_| |_| |
|_   _   _   _   _   _   _   _   _   _|
| | | | | | | | | | | | | | | | | | | |
| | | | | | | | | | | | | | | | | | | |
| | | | | | | | | | | | | | | | | | | |
| | | | | | | | | | | | | | | | | | | |
| | | | | | | | | | | | | | | | | | | |
| |_| |_| |_| |_| |_| |_| |_| |_| |_| |
|  _   _   _   _   _   _   _   _   _  |
| | | | | | | | | | | | | | | | | | | |
| | | | | | | | | | | | | | | | | | | |
| | | | | | | | | | | | | | | | | | | |
| | | | | | | | | | | | | | | | | | | |
| | | | | | | | | | | | | | | | | | | |
|_| |_| |_| |_| |_| |_| |_| |_| |_| | |
James_pic
fuente
Gracias por esto. Parece que todo el dinero está en el truco adaptativo ahora :)
¿Por qué cortas el camino en la parte inferior? Creo que puedes cortar el camino entre el camino inferior y el medio para obtener una mejor puntuación.
justhalf
@justhalf Sí, espero que lo haga. Decidí no hacerlo, ya que habría complicado el código y no habría sido una entrada ganadora de ninguna manera.
James_pic
1
Las tres rutas (suponiendo una ruta 3 óptima) serán, en promedio, las mismas que una ruta única: Nsea ​​la longitud de la ruta (que es n^2-1), la ruta única requerirá N^2movimientos en promedio , mientras que las tres rutas (N/3)^2 + (2N/3)^2 + (2N/3)^2 = N^2más un valor relativamente pequeño, entonces tres las rutas no tienen una ganancia significativa sobre la ruta única, y mucho menos la ruta doble. (El cálculo se basa en el resultado de probabilidad que establece que el movimiento aleatorio en la trayectoria 1-D de longitud Nrequiere un N^2movimiento promedio de un extremo al otro.)
solo el
@justhalf Niza. Estaba luchando por encontrar un buen argumento de primeros principios sobre por qué 2 era el mejor, pero esto lo logra.
James_pic
2

131k (20x20)

Mi primer intento fue eliminar todos los bordes horizontales, excepto la fila superior e inferior, luego, cada vez que el caminante llegaba al final de una columna, eliminaba el borde delante de él, hasta que visitaba el fondo de cada columna y finalmente lo hacía. poder llegar a la salida. Esto dio como resultado un promedio de 1/8 tantos pasos como el enfoque de 1d caminata de @ PeterTaylor.

Luego decidí probar algo un poco más tortuoso. He dividido el laberinto en una serie de galones huecos anidados, y le pido que atraviese el perímetro de cada galón al menos 1,5 veces. Esto tiene un tiempo promedio de aproximadamente 131k pasos.

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <iostream>
#include <math.h>

#define DEBUG 0
#define ROUNDS 10000

#define Y 20
#define X 20
#define H (Y*2+1)
#define W (X*2+1)

int maze[H][W];
int scores[ROUNDS];

int x, y;

void print_maze(){
    char line[W+2];
    line[W+1]=0;
    for(int row=0;row<H;row++) {
        for(int col=0;col<W;col++) {
            switch(maze[row][col]) {
                case 0:
                    line[col]=' ';
                    break;
                case 1:
                    line[col]=row%2?'-':'|';
                    break;
                case 9:
                    line[col]=(row==y*2+1&&col==x*2+1)?'@':' ';
                    break;
            }
        }
        line[W]='\n';
        printf("%s",line);
    }
    printf("%d %d\n",y,x);
}

int main(){
    srand (time(NULL));
    long long total_turns = 0;
    for(int round=0;round<ROUNDS;round++) {
        for (int r=0;r<H;r++) {
            for (int c=0;c<W;c++) {
                if (r==0 || r==H-1 || c==0 || c==W-1) maze[r][c]=0; // edges
                else if (r%2) { // rows with cells and E/W paths
                    if (c%2) maze[r][c] = 9; // col with cells
                    else if (r==1 || r==H-2) maze[r][c]=1; // E/W path on N/Smost row
                    else if (c>r) maze[r][c]=1; // E/W path on chevron perimeter
                    else maze[r][c]=0; // cut path between cols
                } else { // rows with N/S paths
                    if (c%2==0) maze[r][c] = 0; // empty space
                    else if (c==1 || c==W-2) maze[r][c]=1; // N/S path on E/Wmost row
                    else if (r>c) maze[r][c]=1; // N/S path on chevron perimeter
                    else maze[r][c]=0;
                }
            }
        }
        int progress = 0;
        int first_cut = 0;
        x=0;
        y=0;
        if(DEBUG) print_maze();
        long long turn = 0;
        while (x!=X-1||y!=Y-1) {
            if(DEBUG) std::cin.ignore();
            turn++;
            int r = y*2+1;
            int c = x*2+1;
            int exits = maze[r-1][c] + maze[r][c+1] + maze[r+1][c] + maze[r][c-1];
            int exit_choice = -1;
            do {
                if (rand()%exits == 0) {
                    exit_choice = exits;
                    break;
                } else {
                    exits--;
                }
            }while(exits);
            int dx=0, dy=0;
            --exits;
            if (maze[r-1][c]&&!dx&&!dy) {
                if (exits) {
                    --exits;
                } else {
                    dy = -1;
                    dx = 0;
                }
            }
            if (maze[r][c+1]&&!dx&&!dy) {
                if (exits) {
                    --exits;
                } else {
                    dy = 0;
                    dx = 1;
                }
            }
            if (maze[r+1][c]&&!dx&&!dy) {
                if (exits) {
                    --exits;
                } else {
                    dy = 1;
                    dx = 0;
                }
            }
            if (maze[r][c-1]&&!dx&&!dy) {
                if (exits) {
                    --exits;
                } else {
                    dy = 0;
                    dx = -1;
                }
            }
            x+=dx;
            y+=dy;
            if (first_cut==0) {
                if(x==X-1 && y==progress*2+1) {
                    first_cut = 1;
                    maze[y*2+2][x*2+1]=0;
                }
                if(y==Y-1 && x==progress*2+1) {
                    first_cut = 2;
                    maze[y*2+1][x*2+2]=0;
                }
            }
            else if (first_cut==1) {
                if (y==Y-1 && x==progress*2) {
                    maze[y*2+1][x*2+2]=0;
                    progress++;
                    first_cut=0;
                }
                else if (y==Y-2 && x==progress*2+1) {
                    maze[y*2+2][x*2+1]=0;
                    progress++;
                    first_cut=0;
                }
            }
            else if (first_cut==2) {
                if (x==X-1 && y==progress*2) {
                    maze[y*2+2][x*2+1]=0;
                    progress++;
                    first_cut=0;
                }
                else if (x==X-2 && y==progress*2+1) {
                    maze[y*2+1][x*2+2]=0;
                    progress++;
                    first_cut=0;
                }
            }
            if(DEBUG) print_maze();
        }
        // printf("turns:%lld\n",turn);
        scores[round] = turn;
        total_turns += turn;
    }
    long long avg = total_turns/ROUNDS;
    printf("average: % 10lld\n",avg);
    long long var = 0;
    for(int r=0;r<ROUNDS;r++){
        var += (scores[r]-avg)*(scores[r]-avg);
    }
    var/=ROUNDS;
    // printf("variance: %lld\n",var);
    int stddev=sqrt(var);
    printf("stddev:  % 10d\n",stddev);

}
Sparr
fuente
0

Hacer nada

Como el hombre se mueve al azar, uno podría pensar que eliminar cualquier nodo solo aumentará sus posibilidades de llegar a casa a largo plazo.

Primero, echemos un vistazo al caso unidimensional, esto se puede lograr eliminando nodos hasta que termine con un camino ondulado, sin interminables o ciclos, que visite (casi) cada punto de la cuadrícula. En una N x Ncuadrícula, la longitud máxima de dicha ruta es L = N*N - 2 + N%2 (98 para una cuadrícula de 10x10). Caminar a lo largo del camino puede ser descrito por una matriz de transición generada por T1d. matriz de transición

(La ligera asimetría hace que sea difícil encontrar una solución analítica, excepto para matrices muy pequeñas o infinitas, pero de todos modos obtenemos una solución numérica más rápida de lo que tomaría diagonalizar la matriz).
El vector de estado tiene un solo 1en la posición inicial y después de los Kpasos (T1d**K) * statenos da la distribución de probabilidad de estar a una cierta distancia desde el inicio (¡eso es equivalente a promediar todas 2**Klas caminatas posibles a lo largo del camino!)

Ejecutar la simulación de 10*L**2pasos y guardar el último elemento del vector de estado después de cada paso, lo que nos da la probabilidad de haber llegado a la meta después de un cierto número total de pasos: la distribución de probabilidad acumulativa cd(t). La diferenciación nos da la probabilidad pde alcanzar la meta exactamente en un momento determinado. Para encontrar el tiempo promedio que integramos t*p(t) dt
El tiempo promedio para alcanzar la meta es proporcional a L**2un factor que va muy rápidamente a 1. La desviación estándar es casi constante en alrededor del 79% del tiempo promedio.
Este gráfico muestra el tiempo promedio para alcanzar la meta para diferentes longitudes de ruta (correspondiente a tamaños de cuadrícula de 5x5 a 15x15) ingrese la descripción de la imagen aquí

Así es como se ve la probabilidad de alcanzar la meta. La segunda curva parece completa porque en cada paso extraño la posición es extraña y, por lo tanto, no puede estar en la meta. ingrese la descripción de la imagen aquí

De eso podemos ver que la estrategia equilibrada de doble ruta funciona mejor aquí. Para cuadrículas más grandes, donde la sobrecarga de hacer más caminos es insignificante en comparación con su tamaño, podríamos estar mejor aumentando el número de caminos, de forma similar a como lo describió Peter Taylor, pero manteniendo las longitudes equilibradas

¿Qué pasa si no eliminamos ningún nodo?

Entonces tendríamos el doble de nodos transitables, más cuatro direcciones posibles en lugar de dos. Parecería que hace muy poco probable llegar a alguna parte. Sin embargo, las simulaciones demuestran lo contrario, después de tan sólo 100 pasos en una cuadrícula de 10x10 el hombre es bastante probable que llegue a su objetivo, por lo que le Trappin en las islas es un intento inútil, ya que usted está negociando un potencial de N**2largo y sinuoso camino con un tiempo promedio de finalización de N**4por una isla que se pasa por N**2pasos

probabilidad de caminar en la cuadrícula 2d

from numpy import *
import matplotlib.pyplot as plt

def L(N): # maximal length of a path on an NxN grid
    return N*N - 2 + N%2

def T1d(N): # transition along 1d path
    m = ( diag(ones(N-1),1) + diag(ones(N-1),-1) )/2.
    m[1,0] = 1
    m[-2,-1] = 0
    m[-1,-1] = 1
    return m

def walk(stepmatrix, state, N):
    data = zeros(N)
    for i in xrange(N):
        data[i] = state[-1]
        state = dot(stepmatrix, state)
    return data

def evaluate(data):
    rho = diff(data)/data[-1]
    t = arange(len(rho))
    av = sum(rho*t)
    stdev = sum((t-av)**2 * rho)**.5
    print 'average: %f\nstd: %f'%(av, stdev)
    return rho, av, stdev

gridsize = 10
M = T1d(L(gridsize))
initpos = zeros(L(gridsize))
initpos[0] = 1
cd = walk(M, initpos, L(gridsize)**2*5)

plt.subplot(2,1,1)
plt.plot(cd)
plt.title('p of reaching the goal after N steps')
plt.subplot(2,1,2)
plt.plot(evaluate(cd)[0])
plt.title('p of reaching the goal at step N')
plt.show()


''' 
# uncomment to run the 2D simulation
# /!\ WARNING /!\ generates a bunch of images, dont run on your desktop

def links(k,n):
    x = [k-n, k+n]
    if k%n != 0: x.append(k-1)
    if k%n != n-1: x.append(k+1)
    x = [i for i in x if 0<= i <n*n]
    return x

N = 10 # gridsize    

MM = zeros((N*N, N*N)) # build transition matrix
for i in range(N*N):
    temp = links(i,N)
    for j in temp: MM[i,j] = 1./len(temp)
MM[:,-1] = zeros(N*N)
MM[-1,-1] = 1

pos = zeros(N*N)
pos[0] = 1
for i in range(N*N):
    plt.imsave('grid_%.2d'%i, kron(pos.reshape((N,N)), ones((10,10))), cmap='gray')
    pos = dot(MM, pos)
'''
DenDenDo
fuente
+1 por esfuerzo y buenos gráficos. Pero esto no responde la pregunta, y las dos primeras palabras son contradictorias con la conclusión de su análisis. Y, realmente debería etiquetar los ejes de sus gráficos. ¿Para qué tamaño de cuadrícula es aplicable su gráfico de probabilidad?
justhalf
Hermosas fotos, pero no estoy seguro de que tengas la pregunta correcta. Por ejemplo, "Dado que el hombre se mueve al azar, uno podría pensar que eliminar cualquier nodo solo aumentará sus posibilidades de llegar a casa a largo plazo". 1) el hombre siempre llegará a casa eventualmente bajo las reglas establecidas para que esto no parezca relevante y 2) estamos eliminando bordes, no nodos.