Целые числа, собрать!

30

Ваша задача состоит в том, чтобы собрать целые числа от 1до N(в качестве входных данных) в прямоугольник ширины Wи высоты H(также в качестве входных данных). Отдельные числа могут быть повернуты на любое кратное 90 градусов, но они должны появляться в виде непрерывных блоков в прямоугольнике. То есть вы не можете разбить одно из чисел на несколько цифр и разместить цифры в прямоугольнике по отдельности, а также нельзя согнуть три цифры числа за угол. Вы можете считать каждый номер кирпичом, из которого вы строите стену.

Вот пример. Предположим, что ваш вход (N, W, H) = (12, 5, 3). Одним из возможных решений является:

18627
21901
53114

Для ясности, вот две копии этой сетки, одна со скрытыми однозначными числами и одна со скрытыми двузначными числами:

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

Это хорошо, если прямоугольник не может быть снова разобран уникальным способом. Например, в приведенном выше примере, также 12может быть размещен так:

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

правила

Вы можете предположить, что Nэто положительно и W*Hсоответствует количеству цифр в целых числах от 1до Nвключительно, и что существует разбиение прямоугольника на заданные числа. В настоящее время у меня нет доказательств того, возможно ли это всегда, но я бы заинтересовался, если вы это сделаете.

Выходными данными может быть либо строка, разделенная переводом строки, либо список строк (по одному на каждую строку) или список списков из однозначных целых чисел (по одному для каждой ячейки).

Результаты вашего представления должны быть решающими, и вы сможете справиться со всеми контрольными случаями менее чем за минуту на подходящем настольном компьютере.

Вы можете написать программу или функцию и использовать любой из наших стандартных методов получения ввода и предоставления вывода.

Вы можете использовать любой язык программирования , но учтите, что эти лазейки по умолчанию запрещены.

Это , поэтому самый короткий действительный ответ - измеренный в байтах - выигрывает.

Тестовые случаи

За исключением первого, ни один из них не является уникальным. Каждый тестовый пример N W Hсопровождается возможным выводом. Убедитесь, что ваш ответ работает, когда прямоугольник слишком узок, чтобы писать большие цифры по горизонтали.

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
Мартин Эндер
источник
8
Есть ли доказательства того, что это всегда возможно?
Fatalize
@Fatalize Хороший вопрос на самом деле. Вы можете предположить, что это возможно для всех заданных входных данных, но в любом случае было бы интересно получить доказательства.
Мартин Эндер
@Fatalize: по крайней мере, в тривиальном случае ввода (10, 1, 1)это невозможно (при условии, что все числа от 1 до NДОЛЖНЫ использоваться в конструкции). Если это ограничение удерживается, площадь прямоугольника в единицах должна составлять не менее количества цифр 1..N, чтобы сделать это возможным. Если это ограничение ослаблено, это возможно во всех случаях (но тогда задача не очень веселая: P)
Себастьян Ленартович
2
@SebastianLenartowicz: Я думаю, что вы пропустили ту часть, где говорится, что площадь прямоугольника совпадает с суммой цифр чисел в [1, N]. Если N == 10, то ширина и высота должны быть 1 и 11. Если ширина или высота равна 1, эта проблема всегда решаема.
Yay295
1
@MartinEnder Противоположная задача также может быть интересной: прямоугольник цифр в качестве ввода (и в конечном итоге N, но программа может рассчитать его по ширине и высоте), и программе необходимо проверить, является ли прямоугольник верным ответом на этот вызов. ...
Дада

Ответы:

3

Pyth, 35 байтов

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

Кредиты на mbomb007. Я использовал его алгоритм. Первоначально я только хотел помочь Стивену Х., но потом я действительно хотел увидеть короткую версию.

Занимает Nв первой строке, а W,Hво второй строке: попробуйте онлайн: Демонстрация

Нашел неприятную ошибку в реализации Pyth .[(по моей вине, так как я ее реализовал). Должен исправить это завтра. Это привело к +3 байта.

Объяснение:

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
источник
7

Python 2, 210 200 байт

Изменить: работает сейчас!

Заполняет сверху вниз, слева направо, начиная с самых больших чисел. Затем перенесите и сделайте это снова. Затем перенесите и распечатайте. Мне пришлось заполнить пробелами для транспонирования, чтобы работать, так как линии еще не до полной длины.

У меня были проблемы с получением вложенной execработы (чтобы сделать exec'exec"..."*w\n;...'*2. Если кто-то может понять это, дайте мне знать.

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

Попробуйте онлайн - использует модифицированную функцию, чтобы было проще выполнять несколько тестовых случаев (и их нельзя было использоватьexec). Раскомментируйте другую версию и измените stdin, чтобы он работал.

Менее гольф:

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
источник
Весьма вероятно, что сейчас это должно работать для всех случаев, но (неофициальное) доказательство все равно будет приветствоваться. ;)
Мартин Эндер
@MartinEnder Доказательство, вероятно, за мной. Чтобы числа различались по длине, контрольные примеры становятся очень большими. Это, вероятно, связано или совпадает с доказательством того, что решение всегда существует.
mbomb007
6

JavaScript, 284 259 245 241 240 223 209 205 байт

// 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
источник
1
Сохраните 1 байт, используя -вместо !=проверки, отличаются ли два числа.
Нил
2

Pyth, 79 50 48 Bytes

Неконкурентоспособен, пока я не исправлю ошибки (например, [6,6,1] возвращает то же самое, что и [6,1,6]). Я впервые пытаюсь использовать Pyth, поэтому мне, вероятно, не хватает многих функций.

Благодаря Jakube, сэкономил 29 байт и сделал мой код на самом деле работать!

Сохранил еще два байта, осознав, что repr()вызовы не нужны.

В основном это просто перевод ответа mbomb007 на Python 2.

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

Принимает вход в виде
n
w,h.

Стивен Х.
источник
2
Ответы следует удалять до тех пор, пока они не станут действительным решением.
mbomb007
Я думаю, что большая часть кода верна. Единственная ошибка, которую я вижу, происходит во время транспонирования. mbomb007 транспонирует, аккуратно заполняя оставшиеся столбцы пробелами, затем архивирует и удаляет пробелы. Это гарантирует. что после транспонирования матрица имеет wдлину. =.TZне могу этого гарантировать, так как не знает длины w.
Якуб
На самом деле главная ошибка в том, что так и !>+@ZN`zKдолжно быть !>+@ZN`zJ. Тогда все маленькие тестовые случаи работают. Но вы можете создавать тестовые случаи, в которых транспонирование не выполняется (как описано выше). Чтобы это работало, вам нужно что-то вроде =.[.TZkK(заполнить пропущенные столбцы пустыми строками) вместо =.TZ.
Якуб
И постарайся не путать себя с Пифом. В вашем коде у вас есть две переменные, которые указывают на одинаковые значения (например, Kи @Q1). Было довольно сложно отследить, какая переменная и какое значение ... И не просто скопировать код. Будь проще. Логический трюк =Y...может быть хорошей идеей для Python, но простой I(если) будет гораздо более читабельным (и также более коротким).
Якуб
Вот действительно простое решение, использующее код mbomb007: Ссылка занимает nпервую строку (таким образом, нам не нужно присваивать значение дополнительной переменной, которую мы можем просто использовать Q). А wи hна второй линии, которые получают сразу присвоенного Gи Hс AE.
Якуб
1

Stax , 27 байт

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

Запустите и отладьте его

Требуется ввод в одну строку для {N} {H} {W}.

Эта программа начинается с сетки пробелов заданного размера. Для каждого числа из N.. 1он пытается выполнить замену одной строки из строки пробелов соответствующего размера на форматированное число. Если никакая замена не может быть выполнена, то он пытается снова с транспонированной сеткой.

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

Запустите этот

рекурсивный
источник