Introducción
Casi todos están familiarizados con el problema del vendedor ambulante (TSP). La tarea es, dada una lista de N
ciudades, encontrar el ciclo hamiltoniano mínimo , es decir, el camino más corto que visita cada ciudad y vuelve al círculo completo desde el principio. De eso no se trata este desafío. Este desafío es implementar la solución de Chuck Norris al TSP:
Chuck Norris resolvió el problema del vendedor ambulante a
O(1)
tiempo: divida al vendedor en N piezas; patear cada pieza a una ciudad diferente.
Desafío
Para resolver el TSP de esta manera, necesitamos un vendedor lo suficientemente duradero que no evite las frivolidades como el desmembramiento; varias ciudades para visitar; un conjunto de productos para vender; un método concreto para el desmembramiento; y un cálculo para puntuar.
Especificación
- Ciudades
N
es la cantidad de citas que visitará nuestro vendedor
- Vendedor
- El programa o función principal
- Escrito en lenguaje
X
- Con mod de longitud
N
igual a0
- Productos
- Los nombres completos de los elementos en la tabla periódica
- Esto incluye los nombres de elementos recientemente aceptados
- Desmembramiento
- Cortando al vendedor en
N
piezas continuas de igual longitud - Cada pieza debe ser una función o programa válido en lenguaje
X
- Cortando al vendedor en
- Salida
- Cuando se ejecuta, el vendedor debe mostrar
Chuck Norris
y las piezas cortadas deben generar un producto distinto - Solo se aceptan espacios en blanco finales adicionales
- Cuando se ejecuta, el vendedor debe mostrar
- Puntuación
- La longitud,
L
del Vendedor en bytes dividida por el número de ciudadesN
, al cuadrado. Score = L/(N*N)
- El puntaje más pequeño gana
- Incluya 3 cifras significativas al publicar su puntaje decimal
- La longitud,
Ejemplos
- Este vendedor visita 3 ciudades así
N=3
y tiene una longitud de 9 asíL=9
. Por lo tanto, la puntuación para esta respuesta seríaS = 9 / (3 * 3) = 9/9 = 1
.- Tenga en cuenta que el vendedor y cada pieza en rodajas (de las cuales hay 3), deben ser programas o funciones válidas en el mismo idioma.
Program -> Output
------- ------
aaaBBBccc -> Chuck Norris
aaa -> Helium
BBB -> Iridium
ccc -> Tennessine
N=4
yL=20
entoncesS=20/16=1.25
Program -> Output
------- ------
aaaaaBBBBBcccccDDDDD -> Chuck Norris
aaaaa -> Hydrogen
BBBBB -> Cadmium
ccccc -> Mercury
DDDDD -> Iron
fuente
ElementData
permitidos los complementos como el de Mathematica ? (Dudo que ahorre mucho, pero no lo sé)Respuestas:
CJam, L = 1482, N = 114, puntaje 0.114
Pruébalo en línea!
Cada programa tiene 13 bytes de longitud. Aquí se dividen en líneas individuales:
Los elementos que faltan son Darmstadtium, Praseodimio, Protactinium y Rutherfordium, que tienen 12 o 13 caracteres de longitud, lo que significa que no puedo imprimirlos en 13 caracteres cada uno.
La idea es que los primeros pocos programas, que imprimen los elementos con nombres cortos, usen sus caracteres extraños para construir la cadena
Chuck Norri
en la variableL
, lo que no afecta la salida cuando se usan solos. El programa final verifica si ya hay algo en la pila y lo usa para elegir entreL
(máss
) yXenon
.Se guardan algunos bytes adicionales utilizando el carácter que acabamos de agregar
L
como parte del nombre del elemento, específicamente paraC
arbon,N
ickel, Copper
y Silver
.fuente
Python, L = 2596, N = 118, Puntaje = 0.186
La longitud de cada segmento es 22, por lo que esto es bastante largo.
Aquí está el vendedor después de cortar y cortar en cubitos:
Actualizar
fuente
lambda:"Actinium";print""
salida de Actinium? ¿Es esto quizás particular para Python 3?Actinium
. Elprint ""
no hace nada útil después de que el vendedor ha sido desmembrado.