¿Cuánto tiempo le tomará a Santa entregar sus regalos?

12

Publiqué este desafío hace un tiempo, que se refiere a cuántos elfos necesita Santa para entregar regalos.

Debido al aumento de la población, Santa está un poco más presionado por el tiempo este año. Aunque en el pasado operamos de forma muy asincrónica, estamos comenzando a experimentar con una sincronización cada vez mayor. Entonces, Santa necesita saber cuánto tiempo le llevará entregar regalos a cada región con un número determinado de elfos.

El peso del carbón no ha cambiado en los últimos dos años: sigue siendo más pesado que los presentes, por lo que Santa necesita tres elfos por persona traviesa en la casa y dos elfos por persona agradable en la casa.

Los elfos pasan todo el año entrenando para Navidad, por lo que no necesitan descansar entre partos. Solo pueden entregar regalos a una casa a la vez, y deben regresar al trineo de Papá Noel y recoger el próximo regalo antes de ir a la siguiente. Por razones que no tengo libertad para compartir, los elfos no pasan tiempo viajando entre el trineo de Santa y las casas (pero solo pueden viajar cuando el trineo de Santa está en el techo), ni su trineo pasa tiempo moviéndose de casa en casa. (Trineo de Santa Claus hace necesita moverse de casa en casa con el fin de recoger el combustible, pero ya estoy diciendo demasiado).

Los elfos que entregan regalos deben gastar cuatro segundos * cada uno entregando los regalos, y los elfos que entregan carbón deben gastar cinco segundos * cada uno entregándolo (según las regulaciones de la Administración de Aviación de Santa, los guantes con polvo de carbón deben incinerarse inmediatamente después abordar el trineo, que lleva algo de tiempo). Además, las casas deben ser visitadas en el orden en que están en el mapa, de izquierda a derecha, y los elfos no pueden comenzar a entregar regalos a otras casas hasta que todos los regalos hayan sido entregados a la casa en la que se encuentran actualmente.

Si asumimos que Papá Noel tiene más que suficientes elfos para esta región, solo llevaría el tiempo necesario para entregar un regalo a alguien en la lista traviesa, 5 segundos, por casa, o 4 segundos por casa si todos son amables.

Sin embargo, a diferencia de las temporadas anteriores, esta próxima Navidad Santa puede no tener elfos más que suficientes para cada región, por lo que 4 segundos es el tiempo mínimo * absoluto que llevará entregar los regalos a cualquier casa, a menos que haya 0 gente agradable y 0 personas traviesas en cuyo caso tomará 0 segundos.

Además, si incluso una de las casas tiene a alguien en la lista traviesa, Santa necesitará al menos tres elfos. Si al menos una de las casas tiene a alguien en la lista agradable y ninguna de ellas tiene personas en la lista traviesa, Santa necesitará al menos dos elfos. Si ninguna de las casas tiene el espíritu navideño, cualquier número de elfos (incluido 0) tomará 0 segundos.

En el mapa de Santa, una casa está representada por a *, y cada casa está dividida por a +. Santa todavía usa los mismos mapas que en el otro desafío , pero incluiré documentación sobre ellos aquí.

Habrá un número a cada lado de la casa: el de la izquierda que representa el número de personas traviesas en la casa y el de la derecha que representa el número de personas agradables en la casa. Si no hay un número en un lado, se interpreta como un 0.

Sé que puede parecer una locura, pero a algunas personas "no les gusta la Navidad", así que a veces, una casa puede no tener un número a cada lado.

Uno de los mapas de Santa podría verse así.

1*3+2*+*5+*+4*7

Digamos que Santa tiene nueve elfos en su trineo.

  1. (0s) La primera casa tiene 1 gente traviesa y 3 agradables. Tres de los elfos entregan carbón, demorando cinco segundos, y seis entregan regalos, demorando cuatro segundos. Después de cinco segundos, el trineo de Papá Noel se traslada a la siguiente casa.

  2. (5s) La segunda casa tiene 2 personas traviesas y 0 agradables. Seis de los elfos entregan carbón, tardando cinco segundos. Después de cinco segundos, el trineo de Papá Noel se traslada a la siguiente casa.

  3. (10s) La tercera casa tiene 0 personas traviesas y 5 agradables. Ocho de los elfos van a entregar cuatro regalos (el que queda atrás no puede entregar un regalo). Después de cuatro segundos, todos los elfos están de regreso, y dos de ellos van a entregar el otro regalo (el trineo debe esperar a que los elfos regresen antes de ir a la siguiente casa), tomando otros cuatro segundos

  4. (18 años) La cuarta casa no está en el espíritu navideño, por lo que tiene 0 personas traviesas y 0 agradables, y se omite

  5. (18 años) La quinta casa tiene 4 personas traviesas y 7 agradables. Esto se vuelve un poco complicado ...

    I. Los nueve elfos van a entregar tres regalos de carbón (dejar t + 0s, devolver t + 5s) II. Después de 5 segundos, todos están de vuelta en el trineo, y tres de ellos van a entregar el último regalo de carbón (deje t + 5s, devuelva t + 10s) mientras que los otros seis van a entregar tres regalos bonitos (deje t + 5s, devuelve t + 9s).

    III. Después de cuatro segundos, seis de los elfos están de vuelta y van a entregar tres regalos más bonitos (deje t + 9s, devuelva t + 13s).

    IV. Un segundo después de que se van, los tres elfos que estaban entregando el presente de carbón regresan, y dos de ellos se van para entregar el último buen regalo (dejar + 10s, regresar t + 14s)

  6. (18 + 14 = 32 segundos ) Santa ha terminado de entregar regalos a esa región.

Como podemos ver, a Santa le toma un total de 32 segundos entregar regalos a esta región. Sin embargo, esa era una versión simplificada de uno de los mapas de Santa. Normalmente, los mapas de Papá Noel tienen varias líneas y tienen una forma cuadrada para ajustarse mejor a su lista. Un mapa normal podría verse así (un \nal final de cada línea)

1*2+*+*4+1*
2*4+3*+1*6+*
*+*+4*2+1*1
*4+*3+1*+2*3
3*10+2*+*5+*

Con 26 elfos (o cualquier cantidad mayor), le tomaría a Santa 71 segundos .
Con 20 elfos , le tomaría a Santa 76 segundos .
Con 15 elfos , le tomaría a Santa 80 segundos .
Con 3 elfos , le tomaría a Santa 288 segundos .
Con 2 elfos (o cualquier cantidad menor), sería imposible.

Ah, y una cosa más: el orden en que los elfos entregan los regalos es importante (debido a la diferencia horaria de entregar regalos a personas traviesas / agradables), por lo que su código siempre debe generar la menor cantidad de tiempo que los elfos pueden tomar entregando regalos.

Desafío

Ayuda a Santa a determinar cuánto tiempo le llevará a un determinado número de elfos entregar regalos.

Casas

  • Una casa está representada por un *
  • Las casas están divididas por +
  • El número a la izquierda de la casa simboliza el número de personas traviesas (ningún número significa 0)
  • El número a la derecha simboliza el número de personas agradables (ningún número significa 0)
  • Puede haber nuevas líneas ( \n) en la entrada, que también se deben manejar como una división

Duendes

  • Santa necesita la ayuda de tres elfos para personas traviesas (el carbón es mucho más pesado que los regalos), y estos elfos tardarán cinco segundos * en entregar los regalos.
  • Santa necesita la ayuda de dos elfos para gente amable, y estos elfos tardarán cuatro segundos * en entregar los regalos.
  • Si no hay un número a cada lado de la casa, Santa no visitará esa casa y, por lo tanto, no tomará ningún tiempo (las personas que no están en el espíritu navideño ni siquiera merecen carbón)

Papa Noel

  • Papá Noel debe entregar regalos a las casas uno por uno
  • Papá Noel no puede pasar a la siguiente casa hasta que todos los elfos estén de vuelta en el trineo y todos los regalos hayan sido entregados a esa casa (no queremos dejar a los elfos atrás, ¿verdad?)
  • El trineo de Papá Noel no pasa ningún tiempo viajando de casa en casa (Nuevamente, por razones que no estoy en libertad de compartir)

Qué hacer

Dado un mapa de casas y un número de elfos, imprima cuánto tiempo le tomará a Santa entregar regalos a las casas en el mapa.

* (Es posible que no comparta la cantidad de tiempo que tardan los elfos en entregar regalos. No puedo confirmar ni negar que los tiempos incluidos en este desafío sean correctos)

Reglas

  • Hay dos entradas: el mapa y el número de elfos. Las entradas pueden tomarse como argumentos para una función, o desde STDIN o equivalente. Si es imposible tomar dos entradas en su idioma, entonces y solo entonces puede aceptar las dos entradas como una sola cadena de entrada, delimitada por algún carácter que normalmente no está en una entrada (no una +*\no 0-9- la cadena de entrada no puede ser ambigua) por ej ,.
  • El número de elfos siempre será un número entero no negativo (0 es válido)
  • La salida puede ser el valor de retorno de una función o imprimirse en STDOUT o equivalente. Si es imposible que Papá Noel entregue regalos a la región dada con un número dado de elfos, debe enviar un número negativo consistente o un mensaje consistente sin ningún número en él.
  • Todo lo impreso en STDERR se ignorará, por lo que no puede imprimir el resultado o el mensaje de error a STDERR
  • Su programa no puede bloquearse dado un número inválido de elfos para una región
  • La salida debe ser solo la cantidad de tiempo total que le tomará a Santa entregar los regalos con el número dado de elfos.
  • La salida siempre debe ser la menor cantidad de tiempo que les toma a los elfos entregar regalos
  • La entrada sólo contendrá los números, +, *, y saltos de línea \n(a menos que se especifique otro carácter que la entrada incluirá si la lengua no puede tener dos entradas (vistazo a la primera regla) )
  • Se aplican lagunas estándar

Casos de prueba

"1*1", 5 elves => 5
"1*1", 3 elves => 9
"1*2", 7 elves => 5
"1*2", 5 elves => 10
"1*2", 3 elves => 13
"2*1", 8 elves => 5
"2*1", 5 elves => 9
"2*1", 3 elves => 14
"1*" , 3 elves => 5
"1*" , 2 elves => (error message)
"*1" , 2 elves => 4
"*1" , 0 elves => (error message)
"*"  , 0 elves => 0

"1*1+1*1",   5 elves => 10
"1*1+1*1",   3 elves => 18
"1*1+*+1*1", 3 elves => 18
"1*2+2*1",   8 elves => 10
"1*2+2*1",   7 elves => 14
"1*2+2*1",   6 elves => 18
"1*2+2*1",   3 elves => 27
"1*2+2*1",   2 elves => (error message)
"*+*+*+*",   2 elves => 0
"*+*+*+*",   0 elves => 0

"1*3+2*+*5+*+4*7", 9 elves => 32

(con suerte entendí todo eso correctamente)

Puntuación

Santa pasa todos los días mirando muchas cosas: todos los regalos que entregará, todos los elfos que tiene, todas las casas a las que entrega regalos ... Para Santa, el mejor regalo de Navidad sería capaz de ver un poco de algo. Por esta razón, gana el envío más corto en bytes .

Tabla de clasificación

Este es un fragmento de pila que genera una tabla de clasificación y una descripción general de los ganadores por idioma.

Para asegurarse de que su respuesta se muestre, comience con un título usando la siguiente plantilla de Markdown

## Language Name, N bytes

Donde N es el tamaño, en bytes, de su envío

Si desea incluir varios números en su encabezado (por ejemplo, tachar los puntajes antiguos o incluir marcas en el recuento de bytes), solo asegúrese de que el puntaje real sea el último número en su encabezado

## Language Name, <s>K</s> X + 2 = N bytes

Mostrar fragmento de código

code-golf string Jojodmo
fuente
Creo que 288 debería leer 281 : (1+0+0+1+2+3+1+0+0+0+4+1+0+0+1+2+3+2+0+0)*5+(2+0+4+0+4+0+6+0+0+0+2+1+4+3+0+3+10+0+5+0)*4=21*5+44*4=105+176=281(¡aunque debo decir que no he leído todo el "ensayo"!)
Jonathan Allan
@JonathanAllan Sí ... accidentalmente pasé demasiado tiempo escribiendo el desafío ... oops ... De todos modos, lo que falta es que el trineo de Santa Claus tiene que esperar a que todos los elfos vuelvan a bordo antes de mudarse. la casa de al lado, así que aunque sumar todos los números y multiplicarlos podría funcionar en algunos casos, no funciona en la mayoría. Por ejemplo, con 9 elfos, la casa 4*7tarda 14 segundos (eso está cubierto aproximadamente a la mitad del "ensayo", justo antes de que se introduzca el mapa 2D) pero (4 * 5) + (7 * 4) = 48
Jojodmo
El valor 288 es para el ejemplo con 3 elfos, por lo que siempre tendrían que realizar el golpe completo naughty*5+nice*4en cada casa, ¿verdad? (tenga en cuenta que no hay 4*7en ese ejemplo)
Jonathan Allan
¿Los elfos siempre eliminan primero el carbón (como en su ejemplo) o programan de manera eficiente? Por ejemplo, si el mapa fuera 5*15y hubiera 9elfos, ¿tomaría los (mínimos) 20 segundos o 22 segundos? Vea estas representaciones textuales para ver una ilustración de ese ejemplo.
Jonathan Allan
EDITAR a lo anterior 5*15debería leer 4*15.
Jonathan Allan

Respuestas:

4

Ruby , 433 400 bytes

Bueno, este es realmente difícil, porque resulta que la programación de los elfos es NP difícil.

Además, sea amable, esta es mi primera presentación, por lo que podría haber perdido algunas optimizaciones obvias:

->e,h{h.split(/\+|\n/).map{|h|n,g=h.split(?*).map(&:to_i)+[0,0];return-1if(g>0&&e<2)||(n>0&&e<3);([[3,5]]*n+[[2,4]]*g).permutation.map{|j|c=[0]*e;j.map{|q|w,y=q;k=l=0;r=c.map{|x|a=b=0;c[k..e].map{|r|r<=x ?a+=1:break};(t=k+=1).times{c[t-=1]<=x ?b+=1:break};[a,b]};d=r.inject([]){|v,x|v<<l if x[0]>=w;l+=1;v}.min{|a,b|c[a]<=>c[b]};b=d-r[d][1]+1;z=c[d]+y;(b..(b+w-1)).map{|x|c[x]=z}};c.max}.min||0}.sum}

Pruébalo en línea!

Inicialmente tuve casos de prueba más largos, pero debido a que estoy iterando sobre todas las permutaciones posibles para la programación, en algunos casos lleva mucho tiempo, por lo que las eliminé.

elyalvarado
fuente
2
Bienvenido a PPCG! Definitivamente elegiste un desafío difícil para tu primera respuesta
Jo King
2

Java (OpenJDK 8) , 344 bytes

La programación de los elfos es más difícil de lo que pensaba, así que esto llevó un poco de tiempo y es bastante largo.

A pesar de eso, ¡este ha sido definitivamente mi desafío favorito para codificar golf! 

(e,d)->{int r=0,x,y,c,p,b,g,m;for(String h:d[0].split("\\+")){d=h.split("\\*",-1);b=new Byte("0"+d[0]);g=new Byte("0"+d[1]);m=-1>>>1;for(y=1;y<=e/3&(x=(e-y*3)/2)>0;c=b/y+(b%y++<1?0:1),p=g/x+(g%x<1?0:1),x=c*5>p*4?c*5:p*4,m=x<m?x:m);for(y=0;b+g>0;b-=c,g-=p){c=e/3<b?e/3:b;x=(e-c*3)/2;p=x<g?x:g;if(c+p<1)return-1;y+=c>0?5:4;}r+=m<y?m:y;}return r;}

¡Pruébelo en línea (con todas las pruebas)!

Explicación;

Prepárate: es largo

    int r=0,x,y,c,p,b,g,m;               // Define all the variables I need

    for(String h:d[0].split("\\+")){     // Split houses on '+' and loop through them

        d=h.split("\\*",-1);             // Split the current house on '*' using the limit
                                         // to preserve empty strings.

        b=new Byte("0"+d[0]);            // Parse the naughty (b) and nice (g) people
        g=new Byte("0"+d[1]);

        m=-1>>>1;                        // Initialise minimum time as max integer using
                                         // overflow

        for(y=1;y<=e/3&(x=(e-y*3)/2)>0;  // For each number of elves that can concurrently
                                         // deliver coal, and still leave enough elves to
                                         // deliver presents

            c=b/y+(b%y++<1?0:1),         // Determine the number of runs needed to deliver
                                         // all coal using this number of elves

            p=g/x+(g%x<1?0:1),           // Determine the number of runs needed to deliver
                                         // all presents using this number of elves

            x=c*5>p*4?c*5:p*4,           // Get the maximum time required for the
                                         // delivery of coal or presents

            m=x<m?x:m);                  // If this is less than the current minimum time,
                                         // set it as the minimum time


        for(y=0;b+g>0;b-=c,g-=p){        // While there are still people to deliver to;

            c=e/3<b?e/3:b;               // Determine the max amount of coal to deliver

            x=(e-c*3)/2;                 // Determine how many presents can be
                                         // delivered with the remaining elves.

            p=x<g?x:g;                   // If this number is more than nice people
                                         // remaining, just use the nice people remaining

            if(c+p<1)return-1;           // If no presents can be delivered, return the
                                         // error code (-1)

            y+=c>0?5:4;                  // Increase the time by 5 if coal was
                                         // delivered, and 4 if only presents

        }                                // At the end of each loop (see above)
                                         // remove the presents and coal delivered
                                         // from the number of naughty and nice houses

        r+=m<y?m:y;                      // Increment the total time by which ever
                                         // is smaller of the calculated times
    }
    return r;                            // Return the total time

NB: esta respuesta depende de que mis correcciones a los casos de prueba sean correctas

Luke Stevens
fuente
Creo que (e-y*3)/2-> e-y*3>>1guarda un byte. (Lo más probable también se aplica a (e-c*3)/2).
Jonathan Frech
runTest("1*4",5,12);falla (entiendes "1*4", 5 elves => 13 FAILED. Me sorprendió la forma en que tu algoritmo era tan bueno para programar en tan pocos bytes, así que lo comparé con todas las combinaciones posibles de 0 a 7 (elfos, traviesos y agradables) y encontré solo algunas en las que no funciona. dar el tiempo óptimo. Esta es la combinación más pequeña donde falla. Por cierto, una lógica increíble para programar, durante mucho tiempo no tuve idea de cómo lo hiciste.
elyalvarado