30
2
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:
18627
21901
53114
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
Rules
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 code-golf, 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
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
8Is there a proof that this is always possible? – Fatalize – 2016-08-02T12:04:35.753
@Fatalize Good question actually. You can assume it's possible for all given inputs, but a proof either way would be interesting. – Martin Ender – 2016-08-02T12:06:53.230
@Fatalize: At least in the trivial case of input
(10, 1, 1)
, it's not possible (assuming that all numbers from 1 toN
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 in1..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) – Sebastian Lenartowicz – 2016-08-02T17:35:55.5972@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. – Yay295 – 2016-08-02T17:45:46.240
@MartinEnder Some test cases to add:
(100,2,96); (99,3,63); (183,21,21)
(And their transpositions) – mbomb007 – 2016-08-02T19:35:36.730Helpful tool for creating test cases – mbomb007 – 2016-08-02T20:04:49.350
1@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.... – Dada – 2016-08-02T20:46:36.280@Dada Well, that was actually my original challenge idea but I ended up deciding to post this direction, because I wasn't sure whether there would be any feasible non-brute force solutions to the other one. – Martin Ender – 2016-08-02T21:33:09.267