Introducción relacionada con los niños
Cada vez que llevo a mis hijos a un parque de diversiones, los niños se ponen más nerviosos cuanto más cerca estamos del parque, con el nervio máximo cuando estamos en el estacionamiento y no encontramos un lugar para estacionar. Así que he decidido que necesito un método para encontrar el espacio de estacionamiento gratuito más cercano para minimizar el tiempo de estacionamiento.
Introducción técnica
Imagine una representación de un estacionamiento como este:
*****************
* *
* ··CC··C··CC·· *
* ************* *
* ··CCCCCCCCC·· *
* *
**********E******
En esta representación, *
significa un muro, un ·
espacio de estacionamiento gratuito, un E
punto de entrada y C
un automóvil ya estacionado. Cada espacio en blanco es una posición que el automóvil para estacionar puede usar para moverse por el estacionamiento. Ahora ampliemos este concepto a 3D para crear un estacionamiento de varios niveles:
1st floor 2nd floor 3rd floor 4th floor
***************** ***************** ***************** *****************
* 1 * 2 * 3 * *
* CCCCCCCCCCCCC * * CCCCCCCCCCCCC * * ····C··CCCCCC * * ······C······ *
* ************* * * ************* * * ************* * * ************* *
* CCCCCCCCCCCCC * * CCCCCCCCCCCCC * * ···CCCCCCCCCC * * ··C·······C·· *
* * * 1 * 2 * 3
**********E****** ***************** ***************** *****************
Los números 1
, 2
y 3
representan las conexiones entre niveles. El 1
del primer piso se conecta con el 1
del segundo piso, por lo que un automóvil que entra en la 1
posición del primer piso aparece en la 1
posición del segundo piso.
Desafío
Dando un esquema de un estacionamiento como el mostrado anteriormente, escriba el programa más corto que calcule la distancia al espacio de estacionamiento libre más cercano, de acuerdo con lo siguiente
Reglas
- La entrada será una matriz de caracteres 3D o una serie de cadenas 2D o equivalente, y la salida será un número entero único que representa el número de pasos que debe seguir el automóvil para llegar al espacio de estacionamiento libre más cercano. Si recibe una matriz de caracteres 3D, el primer índice puede representar el número de piso y el segundo y tercer índices la posición (x, y) para cada piso, pero esto depende de usted.
- No habrá más de 9 rampas, representadas por
[1-9]
. - El automóvil comienza desde la
E
posición (solo habrá un punto de entrada por mapa) y se mueve utilizando los espacios en blanco en una de las cuatro direcciones cada vez: arriba, abajo, izquierda, derecha. El automóvil también puede subir a·
posiciones y[1-9]
posiciones. - Cada cambio de posición (paso) cuenta como 1, y cada vez que el automóvil va de un piso a otro cuenta como 3, ya que el automóvil debe tomar una rampa. En este caso, el movimiento de un espacio en blanco al lado de un
1
a1
sí mismo es lo que cuenta como 3 pasos, porque como resultado de este movimiento, el automóvil aparece en la1
posición en el otro piso. - El automóvil no puede ir más allá de los límites de la matriz.
- El conteo finalizará cuando el automóvil a estacionar esté en la misma posición que a
·
. Si no hay espacios de estacionamiento gratuitos accesibles, puede devolver cero, un número entero negativo, un valor nulo o un error.
Ejemplos
En el ejemplo anterior, el resultado sería 32, ya que es más barato ir al cuarto piso y estacionar en el espacio de estacionamiento más cercano 3
. Los espacios de estacionamiento gratuitos más cercanos en el tercer piso están a una distancia de 33 y 34.
Otros ejemplos:
1st floor 2nd floor 3rd floor 4th floor
***************** ***************** ***************** *****************
* 1 * 2 * 3 * *
* CCCCCCCCCCCCC * * CCCCCCCCCCCCC * * ····C··CCCCCC * * ······C······ *
* ************* * * ************* * * ************* * * ************* *
* CCCCCCCCCCCCC * * ·CCCCCCCCCCCC * * ···CCCCCCCCCC * * ··C·······C·· *
* * * 1 * 2 * 3
**********E****** ***************** ***************** *****************
Answer: 28 (now the parking space in the 2nd floor is closer)
1st floor 2nd floor 3rd floor 4th floor
***************** ***************** ***************** *****************
* 1 4 2 5 3 6 *
* CCCCCCCCCCCCC * * CCCCCCCCCCCCC * * ····C··CCCCCC * * ······C······ *
* ************* * * ************* * * ************* * * ************* *
* CCCCCCCCCCCCC * * CCCCCCCCCCCCC * * ···CCCCCCCCCC * * ··C·······C·· *
4 * 5 1 6 2 * 3
**********E****** ***************** ***************** *****************
Answer: 24 (now it's better to go to ramp 4 and then to ramp 5 to the third floor)
1st floor 2nd floor 3rd floor 4th floor
***************** ***************** ***************** *****************
* 1 * * * 3 * 2
* CCCCCCCCCCCCC * * CCCCCCCCCCCCC * * ····C··CCCCCC * * ······C······ *
* ************* * * ************* * * ************* * * ************* *
* CCCCCCCCCCCCC * * ·CCCCCCCCCCCC * * ···CCCCCCCCCC * * ··C·······C·· *
* * * 3 * 2 * 1
**********E****** ***************** ***************** *****************
Answer: 16 (now the parking space in the 4th floor is closer)
1st floor 2nd floor 3rd floor 4th floor 5th floor
************ ************ ************ ************ ************
*CCCCCCCCC 1 *CCCCCCCCC 2 *CCCCCCCCC 3 *·CCCCCCCC 4 *········C *
* * * * * * * * * *
*CCCCCCCCC E *CCCCCCCCC 1 *CCCCCCCCC 2 *··CCCCCCC 3 *·······CC 4
************ ************ ************ ************ ************
Answer: 29 (both the nearest parking spaces at the 4th and 5th floors are at the same distance)
1st floor 2nd floor 3rd floor
************ ************ ************
*CCCCCCCCC 1 *CCCCCCCCC 2 *CCCCCCCCC *
* * * * * *
*CCCCCCCCC E *CCCCCCCCC 1 *CCCCCCCCC 2
************ ************ ************
Answer: -1 (no free parking space)
1st floor
************
* *
* *
* E*
************
Answer: -1 (no parking space at all)
1st floor
************
* ····· *
*· ****
* ····· * E
*********
Answer: -1 (the parking lot designer was a genius)
Alternativas
- Puede usar los caracteres que desee para representar el mapa del estacionamiento, solo especifique en su respuesta cuáles son los caracteres elegidos y qué significan.
Este es el código de golf , ¡así que puede ganar el programa / método / lambda / lo que sea más corto para cada idioma!
Si necesita ayuda con el algoritmo, verifique mi implementación (sin protección) en C # .
Respuestas:
JavaScript (ES6), 199 bytes
Pruébalo en línea!
¿Cómo?
La función recursiva g () toma como entrada:
Si f está definida, simplemente copiamos a la planta actual F . De lo contrario, debemos buscar el nuevo piso y las nuevas coordenadas iterando sobre cada piso y sobre cada fila hasta encontrar el punto de entrada c :
Definimos r como la fila actual en el piso actual:
El siguiente paso es asegurarse de que la celda actual c en (x, y) esté definida:
Si es así, lo marcamos como visitado estableciéndolo en g , un valor que no activa ninguna de las próximas pruebas:
Si c es un espacio de estacionamiento gratuito, detenemos la recursividad. Y si el número total de movimientos es menor que nuestro mejor puntaje anterior, actualizamos m en consecuencia:
Si acabamos de llegar a un nuevo piso ( f no está definido ) o c es un espacio, procesamos una llamada recursiva para cada celda circundante:
De lo contrario, si c es un marcador de rampa (es decir, un dígito distinto de cero), procesamos una única llamada recursiva para llegar al nuevo piso:
Finalmente, restauramos la celda actual a su valor inicial para que pueda ser visitada nuevamente en otras rutas de recursión:
fuente
Kotlin , 768 bytes
período utilizado en lugar de ·. Ojalá entendiera la respuesta de Arnauld porque estaría bien perder 500 bytes.
Pruébalo en línea!
fuente
Powershell,
299292 bytesSe supone que el mapa es rectángulo .
Se utiliza en su
x
lugar·
. Para llegar·
, es necesario guardar la escritura como ASCII (no UTF-8) y vuelva a colocarx
en·
.Ungolfed y script de prueba:
Salida:
Salida extendida para estacionamiento con 16 pasos:
Explicación
Es una especie de algoritmo de búsqueda de rutas de Lee . Solo una cosa inteligente: 3 pasos en la rampa se realizan como estados ficticios
H->G->F->E
Powershell para un genio diseñador de estacionamientos,
377369 bytesEl diseño del estacionamiento es un
2D string array
. No hay suposiciones sobre el mapa: cadenas de cualquier longitud, pisos sin paredes, estacionamiento sin un punto de entrada, rampas de múltiples pisos y múltiples salidas. El costo de género es + 26%.Ungolfed y script de prueba:
fuente