Your task is to assemble the integers from 1 to N (given as input) into a rectangle of width W and height H (also given as input). Individual numbers may be rotated by any multiple of 90 degrees, but they must appear as contiguous blocks in the rectangle. That is, you cannot break one of the numbers into multiple digits and place the digits in the rectangle individually, neither can you bend three digits of a number around a corner. You could consider each number a brick from which you're building a wall.

Here is an example. Say your input is (N, W, H) = (12, 5, 3). One possible solution is:


For clarity, here are two copies of this grid, one with the one-digit numbers hidden and one with the two-digit numbers hidden:

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

It's fine if the rectangle cannot be disassembled again in a unique way. For instance, in the above example, the 12 could also have been placed like this:

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


You may assume that N is positive and that W*H matches the number of digits in the integers from 1 to N inclusive, and that a tiling of the rectangle into the given numbers exists. I don't currently have a proof whether this is always possible, but I'd be interested in one if you do.

Output may either be a single linefeed-separated string or a list of strings (one for each line) or a list of lists of single-digit integers (one for each cell).

The results of your submission must be determinstic and you should be able to handle all test cases in less than a minute on reasonable desktop machine.

You may write a program or a function and use any of the our standard methods of receiving input and providing output.

You may use any programming language, but note that these loopholes are forbidden by default.

This is , so the shortest valid answer – measured in bytes – wins.

Test Cases

Except for the first one, none of these are unique. Each test case is N W H followed by a possible output. Make sure that your answer works when the rectangle is too narrow to write the larger numbers horizontally.

1 1 1

6 6 1

6 2 3

10 1 11

11 13 1

27 9 5

183 21 21

200 41 12
  • 8
    \$\begingroup\$ Is there a proof that this is always possible? \$\endgroup\$ – Fatalize Aug 2 '16 at 12:04
  • \$\begingroup\$ @Fatalize Good question actually. You can assume it's possible for all given inputs, but a proof either way would be interesting. \$\endgroup\$ – Martin Ender Aug 2 '16 at 12:06
  • \$\begingroup\$ @Fatalize: At least in the trivial case of input (10, 1, 1), it's not possible (assuming that all numbers from 1 to N MUST be used in the construction). If that constraint is held, the area of the rectangle in units must be at least the number of digits in 1..N in order to make it possible. If that constraint is relaxed, it's possible in all cases (but then the challenge isn't much fun :P) \$\endgroup\$ – Sebastian Lenartowicz Aug 2 '16 at 17:35
  • 2
    \$\begingroup\$ @SebastianLenartowicz: I think you missed the part where it says the area of the rectangle matches the sum of the digits of the numbers in [1,N]. If N == 10, then width and height have to be 1 and 11. If the width or height is 1, this problem is always solvable. \$\endgroup\$ – Yay295 Aug 2 '16 at 17:45
  • 1
    \$\begingroup\$ @MartinEnder The opposite challenge could be interesting too : a rectange of digits as input (and eventually N, but the program could calculate it from the width and height), and the program needs to check if the rectangle is a valide answer to this challenge.... \$\endgroup\$ – Dada Aug 2 '16 at 20:46

Pyth, 35 bytes


Credits to mbomb007. I used his algorithm. Originally I only wanted to help Steven H., but then I really wanted to see a short version.

Takes N on the first line, and W,H on the second line: Try it online: Demonstration

Found a nasty bug in the Pyth implementation of .[ (my own fault, since I implemented it). Gotta fix it tomorrow. This resulted in +3 bytes.


                                  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:
j                                     at the end print every row on a separate line

Python 2, 210 200 bytes

Edit: Works now!

Fills from top to bottom, left to right, starting with the largest numbers. Then, transpose and do it again. Then transpose and print. I had to pad with spaces for the transposition to work, since the lines aren't to their full length yet.

I had trouble getting a nested exec working (to do exec'exec"..."*w\n;...'*2. If someone can figure it out, let me know.

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

Try it online - Uses a modified function so it can run multiple test cases more easily (and it couldn't use exec). Uncomment the other version and modify stdin to see it run.

Less golfed:

def f(n,w,h):
    for x in 1,2:
        for j in[0]*w:
            for i in range(h):
        s=[r.ljust(w)for r in s]
        s=map(lambda x:`x`[2::5],zip(*s))
        s=[r.replace(' ','')for r in s]
  • \$\begingroup\$ It's very likely that this should work for all cases now, but an (informal) proof would still be appreciated. ;) \$\endgroup\$ – Martin Ender Aug 2 '16 at 21:34
  • \$\begingroup\$ @MartinEnder A proof is probably beyond me. For the numbers to vary more in length, the test cases get very large. It's probably related to or the same as the proof of whether there is always a solution. \$\endgroup\$ – mbomb007 Aug 2 '16 at 21:47

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],

for (let test of test_data)

  • 1
    \$\begingroup\$ Save 1 byte by using - instead of != to test whether two numbers are different. \$\endgroup\$ – Neil Aug 7 '16 at 17:10

Pyth, 79 50 48 Bytes

Noncompeting until I work out bugs (for example, [6,6,1] returns the same as [6,1,6]). It's my first time trying to use Pyth, so I'm probably missing a lot of features.

Thanks to Jakube, saved 29 bytes and made my code actually work!

Saved another two byte by realizing that the repr() calls were unnecessary.

It's basically just a translation of mbomb007's Python 2 answer.


Takes input in the form of

  • 2
    \$\begingroup\$ Answers should be deleted until they are a valid solution. \$\endgroup\$ – mbomb007 Aug 3 '16 at 1:18
  • \$\begingroup\$ I think most of the code is correct. The only error I see happens during the transposition. mbomb007 transposes by carefully filling up the remaining columns with spaces, then zips and removes the spaces. This guarentees. that the after transposing the matrix has w length. =.TZ can't guarantee that, since it doesn't know the length w. \$\endgroup\$ – Jakube Aug 3 '16 at 14:10
  • \$\begingroup\$ Actually the main error is, that !>+@ZN`zK should be !>+@ZN`zJ. Then all the small test cases work. But you can create test-cases, where the transposing fails (like described above). For this to work you need something like =.[.TZkK (fill the missing columns with empty strings) instead of =.TZ. \$\endgroup\$ – Jakube Aug 3 '16 at 21:34
  • \$\begingroup\$ And try to not confuse yourself with Pyth. In your code you have two multiple variable that point to the same values (like K and @Q1). It was quite hard to track which variable is which value, ... And don't just copy the code. Keep it simple. The boolean trick =Y... may be a good idea for Python, but a simple I (if) would be much more readable (and also shorter). \$\endgroup\$ – Jakube Aug 3 '16 at 21:41
  • \$\begingroup\$ Here's a really simple solution using mbomb007's code: Link It takes n on the first line (this way we don't have to assign the value to an extra variable, we can simply use Q). And w and h on the second line, which get immediately assigned to G and H with AE. \$\endgroup\$ – Jakube Aug 3 '16 at 21:41

Stax, 27 bytes


Run and debug it

It takes input on one line in the for {N} {H} {W}.

This program starts with a grid of spaces of the specified size. For each number from N .. 1, it attempts to do a single string replacement from a string of spaces of the appropriate size to the formatted number. If no replacement can be performed, then it tries again with a transposed grid.

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

Run this one


Pip, 59 bytes

Oy, Pip can be verbose for a golfing language sometimes...

YsXbRLcJnWa{T` `X#a~yx:Y(t:{J*Z:a^n}Jny)Y$`.a.$'--a}x?(ty)y

Try it online!


Approach: store the grid as a newline-separated string, using regex to replace a run of spaces with the current number, and transposing if there isn't a run of spaces long enough.

; Command-line arguments are: a (the number), b (the width), c (the height)
; x is "", a falsey value

; Set up the initial string:
;  sXb  String of b spaces
;  RLc  Make a list of c of those
;  Jn   Join on newline
Y sXb RL c J n

; Define a function t that transposes a newline-separated string:
;  a^n  Split argument on newlines
;  Z    Zip (transposes, but results in a list of lists of characters)
;  J*   Join each of the sublists into a string
;  Jn   Join those strings on newline
t: {(J* Z (a^n)) J n}

; Loop while a is nonzero:
W a {

  ; Loop till a regex made of len(a) spaces matches in y:
  T y ~ ` `X#a

    ; Transpose y and set x to a truthy value to indicate that we've transposed it:
    ;  (t y)  Call the t function on y
    ;  Y      Assign the result back to y
    ;  x:     Assign it to x also
    x: Y (ty)

  ; When we break out of the loop, we have matched the first run of len(a) spaces
  ; in y; now we want to replace that with the number a:
  ;  $`   The part of the string before the match
  ;  .a   Concatenated to a
  ;  .$'  Concatenated to the part of the string after the match
  ;  Y    Assign that to y
  Y $`.a.$'

  ; Decrement a

; After the main loop, we need to transpose y back if we transposed it:
;  x?     Is x truthy?
;  (t y)  If so, transpose y
;  y      If not, return y as-is
x ? (ty) y

; The result is autoprinted.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.