Entiers, assemblons!

30

Votre tâche consiste à assembler les entiers de 1à N(donnés en entrée) dans un rectangle de largeur Wet de hauteur H(également donné en entrée). Les nombres individuels peuvent être tournés de n'importe quel multiple de 90 degrés, mais ils doivent apparaître sous la forme de blocs contigus dans le rectangle. Autrement dit, vous ne pouvez pas diviser l'un des nombres en plusieurs chiffres et placer les chiffres dans le rectangle individuellement, vous ne pouvez pas non plus plier trois chiffres d'un nombre autour d'un coin. Vous pouvez considérer chaque numéro comme une brique à partir de laquelle vous construisez un mur.

Voici un exemple. Dites que votre entrée est (N, W, H) = (12, 5, 3). Une solution possible est:

18627
21901
53114

Pour plus de clarté, voici deux copies de cette grille, l'une avec les nombres à un chiffre cachés et l'autre avec les nombres à deux chiffres cachés:

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

C'est bien si le rectangle ne peut pas être démonté à nouveau d'une manière unique. Par exemple, dans l'exemple ci-dessus, le 12pourrait également avoir été placé comme ceci:

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

Règles

Vous pouvez supposer que Nc'est positif et que cela W*Hcorrespond au nombre de chiffres dans les entiers de 1à Ninclus, et qu'il existe une mosaïque du rectangle dans les nombres donnés. Je n'ai pas actuellement de preuve si c'est toujours possible, mais je serais intéressé par une si vous le faites.

La sortie peut être soit une chaîne séparée par un saut de ligne soit une liste de chaînes (une pour chaque ligne) ou une liste de listes d'entiers à un chiffre (une pour chaque cellule).

Les résultats de votre soumission doivent être déterminants et vous devriez être en mesure de gérer tous les cas de test en moins d'une minute sur une machine de bureau raisonnable.

Vous pouvez écrire un programme ou une fonction et utiliser l'une de nos méthodes standard de réception d'entrée et de sortie.

Vous pouvez utiliser n'importe quel langage de programmation , mais notez que ces failles sont interdites par défaut.

Il s'agit de , donc la réponse valide la plus courte - mesurée en octets - l'emporte.

Cas de test

À l'exception du premier, aucun d'entre eux n'est unique. Chaque cas de test est N W Hsuivi d'une sortie possible. Assurez-vous que votre réponse fonctionne lorsque le rectangle est trop étroit pour écrire les plus grands nombres horizontalement.

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
la source
8
Existe-t-il une preuve que cela est toujours possible?
Fatalize
@Fatalize Bonne question en fait. Vous pouvez supposer que c'est possible pour toutes les entrées données, mais une preuve dans les deux cas serait intéressante.
Martin Ender
@Fatalize: au moins dans le cas trivial de l'entrée (10, 1, 1), ce n'est pas possible (en supposant que tous les nombres de 1 à NDOIVENT être utilisés dans la construction). Si cette contrainte est maintenue, la zone du rectangle en unités doit être au moins le nombre de chiffres 1..Nafin de le rendre possible. Si cette contrainte est relâchée, c'est possible dans tous les cas (mais alors le défi n'est pas très amusant: P)
Sebastian Lenartowicz
2
@SebastianLenartowicz: Je pense que vous avez manqué la partie où il est dit que l'aire du rectangle correspond à la somme des chiffres des nombres dans [1, N]. Si N == 10, alors la largeur et la hauteur doivent être 1 et 11. Si la largeur ou la hauteur est 1, ce problème est toujours résoluble.
Yay295
1
@MartinEnder Le défi opposé pourrait aussi être intéressant: un rectangle de chiffres en entrée (et éventuellement N, mais le programme pourrait le calculer à partir de la largeur et de la hauteur), et le programme doit vérifier si le rectangle est une réponse valide à ce défi. ...
Dada

Réponses:

3

Pyth, 35 octets

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

Crédits à mbomb007. J'ai utilisé son algorithme. À l'origine, je voulais seulement aider Steven H., mais je voulais vraiment voir une version courte.

Prend Nsur la première ligne et W,Hsur la deuxième ligne: Essayez-le en ligne: Démonstration

Trouvé un bogue désagréable dans l'implémentation Pyth de .[(ma faute, depuis que je l'ai implémenté) Je dois le réparer demain. Cela s'est traduit par +3 octets.

Explication:

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
la source
7

Python 2, 210 200 octets

Edit: fonctionne maintenant!

Remplit de haut en bas, de gauche à droite, en commençant par les plus grands nombres. Ensuite, transposez et recommencez. Ensuite, transposez et imprimez. J'ai dû remplir des espaces pour que la transposition fonctionne, car les lignes ne sont pas encore à leur pleine longueur.

J'ai eu du mal à obtenir un exectravail imbriqué (à faire exec'exec"..."*w\n;...'*2. Si quelqu'un peut le comprendre, faites le moi savoir.

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

Essayez-le en ligne - Utilise une fonction modifiée pour qu'il puisse exécuter plusieurs cas de test plus facilement (et il ne pouvait pas l'utiliserexec). Décommentez l'autre version et modifiez stdin pour la voir s'exécuter.

Moins golfé:

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
la source
Il est très probable que cela fonctionne pour tous les cas maintenant, mais une preuve (informelle) serait toujours appréciée. ;)
Martin Ender
@MartinEnder Une preuve me dépasse probablement. Pour que les nombres varient plus en longueur, les cas de test deviennent très volumineux. Elle est probablement liée ou identique à la preuve qu'il existe toujours une solution.
mbomb007
6

JavaScript, 284 259 245 241 240 223 209 205 octets

// 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
la source
1
Enregistrez 1 octet en utilisant -au lieu de !=pour tester si deux nombres sont différents.
Neil
2

Pyth, 79 50 48 octets

Ne pas concurrencer jusqu'à ce que j'élabore des bogues (par exemple, [6,6,1] renvoie la même chose que [6,1,6]). C'est la première fois que j'essaie d'utiliser Pyth, donc je manque probablement beaucoup de fonctionnalités.

Merci à Jakube, économisé 29 octets et fait fonctionner mon code!

Enregistré deux octets supplémentaires en réalisant que les repr()appels n'étaient pas nécessaires.

Il s'agit essentiellement d'une traduction de la réponse Python 2 de mbomb007.

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

Prend entrée sous la forme de
n
w,h.

Steven H.
la source
2
Les réponses doivent être supprimées jusqu'à ce qu'elles soient une solution valide.
mbomb007
Je pense que la plupart du code est correct. La seule erreur que je vois se produit lors de la transposition. mbomb007 transpose en remplissant soigneusement les colonnes restantes avec des espaces, puis zippe et supprime les espaces. Cela garantit. que la transposition de la matrice a une wlongueur. =.TZne peut pas garantir cela, car il ne connaît pas la longueur w.
Jakube
En fait, la principale erreur est que cela !>+@ZN`zKdevrait être !>+@ZN`zJ. Ensuite, tous les petits cas de test fonctionnent. Mais vous pouvez créer des cas de test, où la transposition échoue (comme décrit ci-dessus). Pour que cela fonctionne, vous avez besoin de quelque chose comme =.[.TZkK(remplir les colonnes manquantes avec des chaînes vides) au lieu de =.TZ.
Jakube
Et essayez de ne pas vous confondre avec Pyth. Dans votre code, vous avez deux variables multiples qui pointent vers les mêmes valeurs (comme Ket @Q1). Il était assez difficile de suivre quelle variable est quelle valeur, ... Et ne copiez pas simplement le code. Rester simple. L'astuce booléenne =Y...peut être une bonne idée pour Python, mais un simple I(si) serait beaucoup plus lisible (et aussi plus court).
Jakube
Voici une solution très simple en utilisant le code de mbomb007: Link Cela prend nla première ligne (de cette façon, nous n'avons pas à assigner la valeur à une variable supplémentaire, nous pouvons simplement l'utiliser Q). Et wet hsur la deuxième ligne, qui sont immédiatement affectées à Get Havec AE.
Jakube
1

Stax , 27 octets

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

Exécuter et déboguer

Il prend l'entrée sur une ligne dans le for {N} {H} {W}.

Ce programme commence par une grille d'espaces de la taille spécifiée. Pour chaque nombre de N.. 1, il essaie de remplacer une seule chaîne d'une chaîne d'espaces de la taille appropriée par le nombre formaté. Si aucun remplacement ne peut être effectué, il essaie à nouveau avec une grille transposée.

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

Exécutez celui-ci

récursif
la source