Los enteros, ensamblar!

30

Su tarea es ensamblar los enteros de 1a N(dado como entrada) en un rectángulo de ancho Wy alto H(también dado como entrada). Los números individuales pueden rotarse por cualquier múltiplo de 90 grados, pero deben aparecer como bloques contiguos en el rectángulo. Es decir, no puede dividir uno de los números en varios dígitos y colocar los dígitos en el rectángulo individualmente, ni puede doblar tres dígitos de un número en una esquina. Podrías considerar cada número como un ladrillo con el que estás construyendo un muro.

Aquí hay un ejemplo. Digamos que tu aportación es (N, W, H) = (12, 5, 3). Una posible solución es:

18627
21901
53114

Para mayor claridad, aquí hay dos copias de esta cuadrícula, una con los números de un dígito ocultos y otra con los números de dos dígitos ocultos:

1####    #8627
2##01    #19##
##11#    53##4

Está bien si el rectángulo no se puede volver a desmontar de una manera única. Por ejemplo, en el ejemplo anterior, el 12también podría haberse colocado así:

#####    18627
21#01    ##9##
##11#    53##4

Reglas

Usted puede asumir que Nes positivo y que W*Hcoincide con el número de dígitos de los números enteros de 1al Ninclusive, y que existe un mosaico del rectángulo en los números dados. Actualmente no tengo una prueba de si esto siempre es posible, pero estaría interesado en uno si lo tiene.

La salida puede ser una sola cadena separada por salto de línea o una lista de cadenas (una para cada línea) o una lista de listas de enteros de un solo dígito (una para cada celda).

Los resultados de su envío deben ser determinantes y debe poder manejar todos los casos de prueba en menos de un minuto en una máquina de escritorio razonable.

Puede escribir un programa o una función y utilizar cualquiera de nuestros métodos estándar para recibir entradas y proporcionar salidas.

Puede usar cualquier lenguaje de programación , pero tenga en cuenta que estas lagunas están prohibidas de forma predeterminada.

Este es el , por lo que gana la respuesta válida más corta, medida en bytes .

Casos de prueba

Excepto por el primero, ninguno de estos es único. Cada caso de prueba es N W Hseguido por una posible salida. Asegúrate de que tu respuesta funcione cuando el rectángulo sea demasiado estrecho para escribir los números más grandes horizontalmente.

1 1 1
1

6 6 1
536142

6 2 3
16
25
34

10 1 11
1
0
8
9
2
6
7
3
1
5
4

11 13 1
1234567891011

27 9 5
213112117
192422581
144136119
082512671
205263272

183 21 21
183116214112099785736
182516114011998775635
181116013911897765534
180415913811796755433
179115813711695745332
178315713611594735231
177115613511493725130
176215513411392715029
175115413311291704928
174115313211190694827
173115213111089684726
172015113010988674625
171915012910887664524
170814912810786654423
169714812710685644322
168614712610584634221
167514612510483624120
166414512410382614019
165314412310281603918
164214312210180593817
163114212110079583716

200 41 12
81711132917193661114105533118936111184136
50592924448815915414562967609909953662491
89529721161671582389717813151113658811817
41418184511110119010183423720433017331118
35171183614003547461181197275184300111711
41874381132041861871718311415915921116264
11914245014112711011594492626831219331845
17125112629222085166344707736090956375181
94507611291431121128817413566319161275711
11011540021119913511011169939551729880780
92725141607727665632702567369893534277304
78118311405621148296417218591118562161856
Martin Ender
fuente
8
¿Hay alguna prueba de que esto siempre es posible?
Fatalize el
@Fatalize Buena pregunta en realidad. Puede suponer que es posible para todas las entradas dadas, pero una prueba de cualquier manera sería interesante.
Martin Ender
@Fatalize: al menos en el caso trivial de entrada (10, 1, 1), no es posible (suponiendo que todos los números del 1 al NDEBEN usarse en la construcción). Si se mantiene esa restricción, el área del rectángulo en unidades debe ser al menos el número de dígitos 1..Npara que sea posible. Si esa restricción es relajada, es posible en todos los casos (pero el desafío no es muy divertido: P)
Sebastian Lenartowicz
2
@SebastianLenartowicz: Creo que te perdiste la parte donde dice que el área del rectángulo coincide con la suma de los dígitos de los números en [1, N]. Si N == 10, entonces el ancho y la altura deben ser 1 y 11. Si el ancho o la altura es 1, este problema siempre se puede resolver.
Yay295
1
@MartinEnder El desafío opuesto también podría ser interesante: un rectángulo de dígitos como entrada (y eventualmente N, pero el programa podría calcularlo a partir del ancho y la altura), y el programa necesita verificar si el rectángulo es una respuesta válida a este desafío. ...
Dada

Respuestas:

3

Pyth, 35 bytes

juum+WghHl+dQd~tQN<+.TGmkeHeH)_BvzY

Créditos a mbomb007. Usé su algoritmo. Originalmente solo quería ayudar a Steven H., pero realmente quería ver una versión corta.

Toma Nla primera línea y W,Hla segunda línea: Pruébelo en línea: demostración

Encontré un error desagradable en la implementación de Pyth de .[(mi propia culpa, desde que lo implementé). Tengo que arreglarlo mañana. Esto resultó en +3 bytes.

Explicación:

juum+WghHl+dQd~tQN<+.TGmkeHeH)_BvzY
                                  Y   start with the empty list []
                                      I'll perform all operations on this list. 
                                      Sometimes it is called G, sometimes N. 
                                vz    read the second line and evaluate it: [W, H]
                              _B      bifurcate it with reverse: [[W, H], [H, W]]
 u                                    for each pair H in ^:
                    .TG                  transpose G
                   +   mkeH              append H[1] empty strings
                  <        eH            use only the first H[1] strings
                                         lets call this result N
  u                          )           modify N, until it doesn't change anymore:
   m                        N               map each d in N to:
     WghHl+dQ                                  if H[0] >= len(d+Q):
    +        d  Q                                 d + Q
              ~t                                  and decrement Q by 1
             d                                 else:
                                                  d
j                                     at the end print every row on a separate line
Jakube
fuente
7

Python 2, 210 200 bytes

Editar: ¡ Funciona ahora!

Se llena de arriba a abajo, de izquierda a derecha, comenzando con los números más grandes. Luego, transponer y hacerlo de nuevo. Luego transponer e imprimir. Tuve que rellenar con espacios para que la transposición funcione, ya que las líneas aún no están completas.

Tuve problemas para conseguir un exectrabajo anidado (para hacer exec'exec"..."*w\n;...'*2. Si alguien puede resolverlo, avíseme).

n,w,h=input()
s=[""]*h
for x in 1,2:
    exec"for i in range(h):l=len(s[i]+`n`)<=w;s[i]+=`n`*l;n-=l\n"*w;s=[r.replace(" ","")for r in map(lambda x:`x`[2::5],zip(*[r.ljust(w)for r in s]))];w,h=h,w
print s

Pruébelo en línea : utiliza una función modificada para que pueda ejecutar múltiples casos de prueba más fácilmente (y no podría usarloexec). Elimine el comentario de la otra versión y modifique stdin para verla ejecutarse.

Menos golfizado:

def f(n,w,h):
    s=[""]*h
    for x in 1,2:
        for j in[0]*w:
            for i in range(h):
                l=len(s[i]+`n`)<=w
                s[i]+=`n`*l
                n-=l
        s=[r.ljust(w)for r in s]
        s=map(lambda x:`x`[2::5],zip(*s))
        s=[r.replace(' ','')for r in s]
        w,h=h,w
    print"\n".join(s)
mbomb007
fuente
Es muy probable que esto funcione para todos los casos ahora, pero aún se agradecería una prueba (informal). ;)
Martin Ender
@MartinEnder Una prueba es probablemente más allá de mí. Para que los números varíen más en longitud, los casos de prueba se vuelven muy grandes. Probablemente esté relacionado o sea lo mismo que la prueba de si siempre hay una solución.
mbomb007
6

JavaScript, 284 259 245 241 240 223 209 205 bytes

// Golfed
let f = (N,W,H)=>eval('a=Array(H).fill("");while(N)g:{s=""+N--;d=s[L="length"];for(i in a)if(a[i][L]+d<=W){a[i]+=s;break g}for(p=0;d;++p){l=a[p][L];for(k=p+d;k>p;)l=a[--k][L]-l?W:l;while(l<W&&d)a[p+--d]+=s[d]}}a');

// Ungolfed
(N,W,H) => {
    a = Array(H).fill(""); // Create `H` empty rows.

    while (N) g : {
        s = "" + N--; // Convert the number to a string.
        d = s[L="length"]; // Count the digits in the number.

        // Loop through the rows trying to fit the number in horizontally.
        for (i in a) {
            if (a[i][L] + d <= W) { // If it fits.
                a[i] += s; // Append the number to the row.
                break g; // This is what a goto statement looks like in JavaScript.
            }
        }

        // Loop through the rows trying to fit the number in vertically.
        for (p = 0; d; ++p) {
            l = a[p][L]; // Get the length of the row.

            // Find `d` adjacent rows of the same length.
            for (k = p + d; k > p; ) {
                // If `a[--k][L] == l`, continue.
                // Else set `l` to `W` so the next loop doesn't run.
                l = a[--k][L] - l ? W : l;
            }

            // Put the characters in position.
            while (l < W && d)
                a[p+--d] += s[d];
        }
    }

    return a;
}

let test_data = [[1,1,1],
                 [6,6,1],
                 [6,2,3],
                 [10,1,11],
                 [10,11,1],
                 [11,13,1],
                 [27,9,5],
                 [183,21,21],
                 [184,2,222],
                 [200,41,12],
                 [1003,83,35]];

for (let test of test_data)
    console.log(f(test[0],test[1],test[2]));

Yay295
fuente
1
Ahorre 1 byte usando en -lugar de !=probar si dos números son diferentes.
Neil
2

Pyth, 79 50 48 Bytes

No competir hasta que solucione errores (por ejemplo, [6,6,1] devuelve lo mismo que [6,1,6]). Es la primera vez que intento usar Pyth, por lo que probablemente me faltan muchas funciones.

¡Gracias a Jakube, ahorré 29 bytes e hice que mi código realmente funcionara!

Ahorró otros dos bytes al darse cuenta de que las repr()llamadas eran innecesarias.

Básicamente es solo una traducción de la respuesta de Python 2 de mbomb007.

AEJmkHFb2VHVGIgGl+@JNQ XNJ~tQ)))=.[.TJkGA,HG)jJ

Toma entrada en forma de
n
w,h.

Steven H.
fuente
2
Las respuestas deben eliminarse hasta que sean una solución válida.
mbomb007
Creo que la mayor parte del código es correcto. El único error que veo ocurre durante la transposición. mbomb007 se transpone rellenando cuidadosamente las columnas restantes con espacios, luego comprime y elimina los espacios. Esto garantiza. que después de transponer la matriz tiene wlongitud. =.TZNo puedo garantizar eso, ya que no conoce la longitud w.
Jakube
En realidad, el error principal es que !>+@ZN`zKdebería ser !>+@ZN`zJ. Entonces todos los casos de prueba pequeños funcionan. Pero puede crear casos de prueba, donde la transposición falla (como se describió anteriormente). Para que esto funcione, necesita algo como =.[.TZkK(llenar las columnas que faltan con cadenas vacías) en lugar de =.TZ.
Jakube
Y trata de no confundirte con Pyth. En su código tiene dos variables múltiples que apuntan a los mismos valores (como Ky @Q1). Fue bastante difícil rastrear qué variable es qué valor, ... Y no solo copie el código. Mantenlo simple. El truco booleano =Y...puede ser una buena idea para Python, pero un simple I(si) sería mucho más legible (y también más corto).
Jakube
Aquí hay una solución realmente simple usando el código de mbomb007: Enlace Toma nla primera línea (de esta manera no tenemos que asignar el valor a una variable adicional, simplemente podemos usar Q). Y wy hen la segunda línea, que se asignan inmediatamente a Gy Hcon AE.
Jakube
1

Stax , 27 bytes

é!L↑?∞S░♠╔)¥¼/ÿµ◄÷│♦╫Δò6√√╣

Ejecutar y depurarlo

Toma entrada en una línea en el para {N} {H} {W}.

Este programa comienza con una cuadrícula de espacios del tamaño especificado. Para cada número de N... 1, intenta hacer un reemplazo de una sola cadena desde una cadena de espacios del tamaño apropiado hasta el número formateado. Si no se puede realizar un reemplazo, lo intenta nuevamente con una cuadrícula transpuesta.

z)A+*   create "grid" of spaces and newlines of specified size
,Rr     create range [n ... 1]
F       for each number execute the indented section; it will fit the value into the grid
  $%z(  make a string out of spaces the same length as the number; e.g. 245 => "   "
  Y     store the space string in register Y; this will be used as a search substring
  [#    count the number of occurrences of y in the grid; the grid is still on the stack
  X     store the count in register X; this will be used as a condition
  G     jump to routine at closing curly brace
  y_$|e replace the first instance of y (the spaces) with the current number
  xG    push x; then jump to routine at closing curly brace
        end program
}       called routine jump target
C       pop top of stack; if it's truthy terminate routine
|jM|J   split on newlines; transpose; join with newlines

Ejecute este

recursivo
fuente