Fondo
El llamado "Protocolo Urinario", que describe el orden en que se recogen los urinarios individuales en el baño de hombres, se ha discutido en varios lugares. Se da una versión en esta publicación de blog xkcd . Esta pregunta se refiere a una ligera variación:
Disposición : n urinarios en línea.
Protocolo : cada nueva persona selecciona uno de los urinarios más distantes de los que ya están en uso.
Tenga en cuenta que esto no impone restricciones sobre qué urinario es elegido por la primera persona.
Actualización : La secuencia de la cantidad de formas diferentes en que n personas pueden seleccionar n urinarios comienza con 1, 2, 4, 8, 20 ... Tenga en cuenta que esto no es lo mismo que OEIS A095236 , que describe restricciones ligeramente más estrictas que en este pregunta.
Tarea
Dado un número entero n entre 0 y 10, genera (en cualquier orden) todos los ordenamientos posibles en los que n personas pueden ocupar n urinarios. Cada pedido debe imprimirse como disposición final: una secuencia de dígitos que representa a las personas (1-9 para las primeras 9 personas, 0 para la décima), comenzando desde el orinal más a la izquierda, con separadores opcionales no alfanuméricos entre (pero no antes o después) los dígitos. Por ejemplo, las siguientes salidas son válidas:
>> 3
132
213
312
231
>> 4
1|3|4|2
1|4|3|2
3|1|4|2
4|1|3|2
2|3|1|4
2|4|1|3
2|3|4|1
2|4|3|1
Puede escribir un programa o función, tomando datos a través de STDIN (o la alternativa más cercana), argumento de línea de comandos o argumento de función. Los resultados deben imprimirse en STDOUT (o la alternativa más cercana).
Tanteo
El código más corto gana. Aplican términos y condiciones estándar.
fuente
span
de longitud 1, donde hay unaspan
de longitud 2 disponible. De repente me las arreglé para confundirme. Parece que el OP se deriva intencionalmente del enlace y, por lo tanto, ¿se debe seguir el enlace?Respuestas:
Pyth,
5351Este es un enfoque iterativo. Dado un posible conjunto parcialmente ordenado de ubicaciones ordenadas, encontramos todas las ubicaciones óptimas adicionales, luego generamos la lista de ubicaciones correspondiente y repetimos.
Los resultados se generan en la forma
[<first person's location>, <second person's location> ...]
, luego esto se transforma en el formato deseado.MhSm^-dG2H
define una función auxiliar que encuentra las distancias mínimas desde un puesto dado a un puesto ocupado (al cuadrado). Divertidamente, el separador es gratis.Ejemplo de ejecución.
Explicación:
Primero, la función auxiliar
g
, que encuentra la distancia al cuadrado mínima entre G y cualquier valor en H.A continuación, encontramos las ubicaciones máximas sobre urinarios de la distancia mínima al cuadrado entre ese urinario y cualquier urinario ocupado:
(
Q
es la entrada)d
en este caso es la lista de urinarios ocupados, mientras queb
itera sobre las ubicaciones de los urinarios.A continuación, encontramos todas las ubicaciones de urinarios cuya distancia al cuadrado mínima desde el orinal ocupado más cercano es igual al valor máximo que se encuentra arriba.
A continuación, generaremos las listas de ubicación de urinarios creadas agregando las ubicaciones de urinarios que se encuentran arriba
d
. Haremos esto para cada lista anterior de ubicaciones de urinarios, extendiendo así las listas de longitudN
aN+1
.G
es la lista de listas legales de ubicaciones de urinarios ocupadas de una longitud determinada.A continuación, aplicaremos la expresión anterior repetidamente para generar la lista completa de listas de ubicaciones de urinarios ocupadas.
u
, la función reducir, hace exactamente esto, tantas veces como haya elementos en su segundo argumento.Convertir de la representación anterior, que va
[<1st location>, <2nd location>, ... ]
, a la forma de salida deseada,[<person in slot 1>, <person in slot 2>, ... ]
. Luego, el formulario de salida se une a la cadena de salida y se imprime. La impresión es implícita.fuente
kajsdlkas^23asdjkla1lasdkj~JZasSSA
- Casi la mitad del tamaño.Pyth,
757167Solución combinatoria recursiva.
Es una traducción bastante directa de esta solución de Python:
fuente
C,
929878 bytesEste es un monstruo, muchachos. Lo siento.
Define 3 funciones,
f(int*,int)
,P(int*,int,int,int,int)
, yL(int)
. LlamaL(n)
y sale a STDOUT.Salida para
n=5
:Actualización: eliminé los separadores y arreglé el código. El código anterior no solo falló para n = 7 +, sino que no pudo generar nada para n = 10 (¡Uy!). He probado más a fondo este grupo. Ahora admite entradas de hasta n = 13 (aunque
"%d"
debería cambiarse para"%x"
que se imprima en hexadecimal). El tamaño de la entrada dependesizeof(long)
y se supone que está8
en la práctica.Aquí hay una explicación de cómo funciona y por qué existe una restricción tan extraña:
Estos se usaron mucho, por lo que los definimos para guardar un par de bytes:
typedef unsigned long U; typedef unsigned char C;
Aqui esta
f
:f
toma una matriz de enteros de tamañon
, y enn
sí mismo. El único bit inteligente aquí es que devuelve ununsigned long
, que se convierte en achar[8]
por la función de llamada. Por lo tanto, cada carácter de la matriz se establece0xFF
en un índice o apunta a un urinario válido para la siguiente persona. Paran<10
, nunca necesitamos más de 5 bytes para contener cada urinario válido que la siguiente persona pueda usar.Aqui esta
P
:P
toma una matrizu
de tamañon
en el que exactamente se establece un elemento1
, y el resto lo son0
. Luego encuentra e imprime cada permutación posible de forma recursiva.Aqui esta
L
:L
simplemente llamaP
n
tiempos con diferentes posiciones de inicio cada vez.Para los interesados, esto (menos golfizado)
f
generará la secuencia en A095236 .fuente
14352
significa que la persona # 1 eligió el orinal más a la izquierda. La persona n. ° 2 eligió la más a la derecha, que luego forzó a la n. ° 3 al centro. No es el número del urinario elegido a continuación lo que debe salir.Pitón 2, 208
Enfoque recursivo.
fuente
JavaScript (ES6) 153
160 169Edite usando Math.min para encontrar (por supuesto) la distancia máxima: código simplificado y 16 bytes guardados.
Búsqueda recursiva, puede funcionar con n> 10, simplemente elimine% 10 (y prepárese para esperar mientras la consola desenrolla toda su salida).
Utilizo una sola matriz para almacenar la ranura en uso (números positivos) o la distancia actual desde la ranura más cercana (los números negativos así
<
y>
se intercambian en el código).Sin golf
Prueba en la consola Firefox / FireBug
fuente
Mathematica,
123104fuente
n~f~s~Join~{#}
se convertiráJoin[f[n,s],{#}]
.MATLAB, 164
fuente
Perl, 174
No muy corto, pero divertido. No cuento
use feature 'say';
para el total de bytes.De-golf:
fuente
C, 248 bytes
Este código utiliza un algoritmo recursivo para generar el resultado deseado.
Expandido:
fuente
Bash,
744674 bytesEsto todavía es demasiado largo :). Utilizo una cadena para representar la fila de urinarios y un algoritmo de inundación para encontrar los urinarios más distantes en cada fase de recursión. El código sin golf es casi autoexplicativo. El número de urinarios se lee desde el teclado.
Código (golfizado):
Utilizar:
Y sin golf va:
fuente