Наивысший периметр полиомино

14

Это код гольф. Победителем является действительный код с наименьшим количеством байтов.

Вызов

Учитывая входные данные M и N , ширину и высоту прямоугольной сетки квадратов, выведите многоугольник, который удовлетворяет следующему:

  • Ребра многоугольника состоят только из квадратных ребер: диагональных ребер нет - все они вертикальные или горизонтальные.
  • Многоугольник не имеет отверстий: каждый квадрат за пределами многоугольника может быть достигнут с помощью ортогональных шагов на квадратах за пределами многоугольника, начиная с квадрата за пределами многоугольника на внешней границе прямоугольника.
  • Многоугольник не имеет самопересечения: из ребер квадрата, встречающихся в вершине, не более 2 может быть частью периметра многоугольника.
  • Многоугольник связан: любой квадрат в многоугольнике должен быть доступен из любого другого квадрата в многоугольнике с помощью ортогональных шагов, которые остаются внутри многоугольника.
  • Полигон имеет максимально возможный периметр: согласно формуле, показанной ниже.

Ваш код должен работать для M и N от 1 до 255.

Формула для максимального периметра

Задача здесь - найти наиболее пригодные для игры в гольф из тех полигонов с максимальным периметром. Максимальный периметр всегда определяется по формуле:

Это верно, потому что для максимального периметра каждая квадратная вершина должна быть по периметру. Для нечетного числа вершин это невозможно, и лучшее, что может быть достигнуто, - это на одну вершину меньше (поскольку периметр всегда четный).

Выход

Выведите форму в виде строки символов, разделенных новой строкой ( N строк ровно из M символов). Здесь я использую пространство для квадратов за пределами многоугольника и '#' для квадратов внутри многоугольника, но вы можете использовать любые два визуально отличных символа, если их значение согласовано для всех входных данных.

Вы можете включить до одной новой строки перевода и до одной новой строки.

Если вы хотите, вы можете вместо этого вывести M строк ровно из N символов, и вы можете выбрать вывод M на N для одних входов и вывод N на M для других.

Примеры

Неверно из-за дыры:

###
# #
###

Неправильно из-за пересечения (касание по диагонали - вершины с 4 квадратными ребрами по периметру) и, кстати, отверстия:

##
# #
###

Недействительно из-за отключения:

#
# #
  #

Допустимый полигон с максимальным периметром:

# #
# #
###

кредиты

Сначала я недооценил, как быстро можно рассчитать значение максимального периметра, и собирался просто запросить это значение в качестве выходного. Спасибо замечательным людям в чате, которые объяснили, как определить максимальный периметр для произвольных N и M, и помогли превратить это в испытание, которое будет длиться более одного ответа ...

В частности, благодаря:

Спарр , Згарб , Ферсум , Джимми23013 .

code-golf grid Trichoplax
источник
Я мог бы назвать этот вопрос, используя polyominos или многоугольники (так как оба применяются). У кого-нибудь есть предпочтения? Вы можете указать с комментариями голосования следующее:
trichoplax
5
Полиамино с наивысшим периметром
трихоплакс
1
Полигон с наивысшим периметром
трихоплакс,
N строк ровно из M символов: можем ли мы поменять два входных значения, если мы сочтем это удобным для определенных входных данных?
Уровень Река St
3
@steveverrill Я редактировал раздел вывода. Это соответствует вашему запросу?
Трихоплакс

Ответы:

4

CJam, 47 байтов

l~_2%{\}|_'#:H*@({N+1$(2md\HS+*H+\SH+R=*++}fR\;

Попробуйте онлайн

Объяснение:

l~      Get and convert input.
_2%     Calculate second value modulo 2.
{\}|    If value is even, swap the two inputs. This puts odd on top if one is odd.
_'#:H*  Create top row of all # signs. Also save away # character as shortcut for later.
@(      Pull number of rows to top, and decrement because first is done.
{       Start loop over rows.
N+      Add newline.
1$      Copy row length to top of stack.
(2md    Decrement, and calculate mod/div with 2.
\       Swap mod and div, will use div first.
HS+     "# "
*       Repeat it based on div 2 of row length.
H+      Add one more #.
\       Swap mod of earlier division to top.
SH+     " #"
R=      Pick space or # depending on even/odd row number.
*       Repeat 0 or 1 times depending on mod 2 of row length.
+       Add the possible extra character to line.
+       Add line to result.
}fR     End of for loop over lines.
\;      Remove row length from stack, leaving only result string.

Есть два основных случая для результата. Если хотя бы один из размеров является нечетным, шаблон представляет собой простой «рейк». Например, для ввода 7 6:

#######
# # # #
# # # #
# # # #
# # # #
# # # #

Если оба размера четные, есть дополнительный столбец, где каждый второй квадрат "включен". Например, для ввода 8 6:

########
# # # # 
# # # ##
# # # # 
# # # ##
# # # #

Теперь, чтобы показать, что эти шаблоны достигают теоретического максимума периметра, как указано в описании проблемы, мы должны подтвердить, что первый шаблон имеет периметр (M + 1) * (N + 1), а второй - то же значение минус 1.

Для первого шаблона у нас есть периметр с Mнечетным размером:

  1. M для верхнего края.
  2. 2 на стороне верхнего ряда.
  3. (M - 1) / 2 за щели между зубами.
  4. (M + 1) / 2зубы с периметром 2 * (N - 1) + 1каждый.

Это в сумме составляет:

M + 2 + (M - 1) / 2 + (M + 1) / 2 * (2 * (N - 1) + 1) =
M + 2 + (M - 1) / 2 + (M + 1) * (N - 1) + (M + 1) / 2 =
2 * M + 2 + (M + 1) * (N - 1) =
(M + 1) * 2 + (M + 1) * (N - 1) =
(M + 1) * (N + 1)

Для второго случая, когда оба Mи Nявляются четными, периметр складывается из:

  1. M для верхнего края.
  2. 2 на стороне верхнего ряда.
  3. M / 2 для открытого # в верхнем ряду.
  4. M / 2 зубы с периметром 2 * (N - 1) + 1 каждый для простых зубов.
  5. Крайний правый зуб имеет дополнительный 2 * (N / 2 - 1) части периметра для зубцов.

Добавляем все это вместе:

M + 2 + M / 2 + (M / 2) * (2 * (N - 1) + 1) + 2 * (N / 2 - 1) =
M + 2 + (M / 2) * (2 * (N - 1) + 2) + N - 2 =
M + M * N + N =
(M + 1) * (N + 1) - 1
Рето Коради
источник
Я думаю, что могу сэкономить пару байтов, поместив зубчатую часть слева. Должно потребоваться немного меньше перетасовки стека. Но пора спать ...
Рето Коради
5

Ruby, Rev 1, 66

->(m,n){n.times{|i|puts ("#"*m**(1-i%2)).rjust(m,i>n-2?"# ":" ")}}

Используется повышение mдо 0 0, чтобы решить, 1 илиm # будут ли напечатаны s.

Используется >для проверки последней строки вместо ==.

Не могу избавиться ни от места после пут, ни от скобок!

Ruby, Rev 0, 69

->(m,n){n.times{|i|puts ("#"*(i%2==0?m:1)).rjust(m,i==n-1?"# ":" ")}}

Это анонимная лямбда-функция. Используйте это так:

f=->(m,n){n.times{|i|puts ("#"*(i%2==0?m:1)).rjust(m,i==n-1?"# ":" ")}}

M=gets.to_i
N=gets.to_i
f.call(M,N)

В конце концов, после того, как я спросил, можно ли поменять местами М и N, мне это не нужно.

Типичные выходы для N нечетных. Если мы удалим #их самостоятельно с правой стороны, ясно, что у нас будет (N + 1) (M + 1). Включение их в форму удаляет 2 квадрата горизонтального периметра и добавляет 2 квадрата вертикального периметра, поэтому изменений нет.

Здесь мы полагаемся на выражение, "#"*(i%2==0?m:1)чтобы задать чередующиеся строки из M #символов и один #символ, и выравнивание по правому краю для M символов.

5                        6
5                        5
#####                    ######
    #                         #
#####                    ######
    #                         #
#####                    ######

Типичные выходы для четного N 5 6явно имеет тот же периметр 6 5, что и приращение M + 1 = 6, по сравнению с 5 5добавлением вертикального периметра из-за зачистки нижнего ряда. 6 6имеет то же самое, что и 6 5плюс приращение (M + 1) -1 = 6 в вертикальном периметре. Таким образом, они соответствуют формуле.

5                        6
6                        6
#####                    ######
    #                         #
#####                    ######
    #                         #
#####                    ######
# # #                    # # ##

Очень удобно, что Ruby rjustпозволяет вам указать заполнение для пустых ячеек. Обычно для заполнения задано значение, " "но для последней строки мы переключаемся на "# "(обратите внимание, что заполнение будет необходимо только в последней строке, если N четное. Если N нечетное, последняя строка будет завершена и не будет никакого оправдания, поэтому вы не увидят зубцы.)

Проверьте это здесь.

Уровень реки St
источник
@ Vioz- Спасибо за идеон! Я проверил программу до низких значений N и M, чтобы увидеть, есть ли какие-либо крайние случаи, но я не стал проверять, будет ли она работать для таких высоких значений. Очевидно, что и кренелляция, и кренелизация верны, поэтому я оставлю это. Вернусь позже, чтобы посмотреть, смогу ли я удалить некоторые скобки и пробелы.
Уровень Река St
Нет проблем по ссылке? Я подумал, что это будет полезно для других, так как я использовал его для проверки: P Что касается редактирования правописания, я изменил его на первый результат, который я смог найти, потому что я никогда не видел фактически использованного слова. Я не знаю много о Ruby (ничего, на самом деле), но вы можете изменить i%2==0его, i%2<1чтобы сохранить байт (я сделал это изменение для ссылки на ideone).
Каде
Вы действительно нуждаетесь в #заполнении даже для последнего ряда? Например, на последнем рисунке периметр не совпадает без #нижнего правого угла?
Рето Коради
@RetoKoradi это действительно будет тот же периметр - похоже, что код включает в себя дополнительный #просто потому, что это уже способ, которым заканчивается каждая строка, так что это меньше байтов, чем место пробела. (Хотя я не знаю рубина ...).
Трихоплакс
1
@trichoplax Ваша интуиция верна. Заполнение "# "не " #"потому, что последний дал бы 2 смежных #для нечетных M, что определенно нежелательно. 2 соседних #даже для М не причиняют вреда, поэтому я пошел с этим. Я не пробовал ljust, возможно, можно было бы сделать это более аккуратно, но было бы не так очевидно, что я печатаю ровно M символов в строке.
Уровень Река St
5

C 109 97 байт и корректность

Я писал свое решение, но @steveverrill опередил меня. Я думал, что поделюсь этим все же, так как я включил доказательство правильности использованной стратегии.

Сокращенный код:

m,n,x;main(){for(scanf("%i%i",&m,&n); n;)putchar(x<m?"# "[x%2*(++x^m||~n&1)&&n^1]:(x=0,n--,10));}

До сокращения:

m,n,x;

main(){
    for(scanf("%i%i",&m,&n); n;) 

        /* If x == m, prints out a newline, and iterates outer 
         * loop (x=0,n--) using comma operator.
         * Otherwise, paints a '#' on :
         *     Every even column (when x%2 is 0)
         *     On odd columns of the last row (++x^m||~n&1 is 0)
         *     On the first row (when n^1 is 0)
         * And a ' ' on anything else (when predicate is 1) */
        putchar(x<m?"# "[x%2*(++x^m||~n&1)&&n^1]:(x=0,n--,10));
}

Стратегия и Доказательство:

Предполагая правильность уравнения максимального периметра (M + 1) (N + 1) - ((M + 1) (N + 1)) mod 2 , следующее объясняет используемую оптимальную стратегию и доказывает ее правильность по индукции:

Для нечетного M мы рисуем форму руки с пальцами M / 2 + 1, например:

3x2
# # 
###

5x3
# # #
# # #
#####

Теперь докажем, что эта стратегия оптимальна для всех нечетных M по индукции:

Базовый случай: M = N = 1
Одна ячейка заполнена. Решение является правильным, поскольку (1 + 1) * (1 + 1) = 2 * 2 = 4, а квадрат имеет 4 стороны.

Индукция по ширине:
Предположим, что стратегия формы руки работает для (N, M-2), где M нечетно, то есть его периметр оптимален и равен (N + 1) (M - 2 + 1) + ((M -1) (N + 1)) мод 2 . Теперь покажем, что это будет работать для (N, M) .

Процесс добавления пальца удаляет один край из многоугольника и добавляет 3 + 2N . Например:

 5x3 -> 7x3
 # # # $
 # # # $
 #####$$

Объединяя это с нашей гипотезой, что предыдущий периметр был оптимальным, новый периметр:

(N + 1)*(M - 2 + 1) - ((M+1)*(N+1)) mod 2 - 1 + 3 + 2*N
(N + 1)*(M + 1) - ((M-1)*(N+1)) mod 2 - 2(N + 1) - 1 + 3 + 2*N
(N + 1)*(M + 1) - ((M-1)*(N+1)) mod 2

Поскольку мы имеем дело с арифметикой по модулю 2, 

((M-1)*(N+1)) mod 2 = ((M+1)*(N+1)) mod 2

Таким образом, доказательство того, что увеличение ширины путем добавления пальцев приводит к оптимальному периметру.

Индукция по высоте:
предположим, что стратегия формы руки работает для (N-1, M) , где M нечетно, то есть его периметр является оптимальным и имеет N (M + 1) + ((M + 1) N) mod 2 . Покажем теперь, что это будет работать для (N, M) .

Увеличение высоты кисти просто удлиняет пальцы, расположенные на первом и на каждом другом x-index. Для каждого увеличения высоты каждый палец добавляет два к периметру, и есть (M + 1) / 2 пальца, таким образом, увеличение N приводит к увеличению 2 (M + 1) / 2 = M + 1 в периметр.

Объединяя это с гипотезой, мы получаем, что новый периметр:

N*(M + 1) + ((M+1)*N) mod 2 + M + 1
(N + 1)*(M + 1) + ((M+1)*N) mod 2

Модульная арифметика позволяет нам упростить последний член, чтобы мы получили:

(N + 1)*(M + 1) + ((M+1)*(N+1)) mod 2

Доказательство того, что решение оптимально для всех N> 0 и нечетного M> 0.

Для четного M мы заполняем доску так же, как и для нечетного M, но мы добавляем символизацию к последнему сегменту, например:

4x3
# ##
# # 
####

6x4
# # #
# # ##
# # #
######

Теперь докажем, что эта стратегия оптимальна.

Индукция для четного M:
предположим, что решение является правильным для (N, M-1) с нечетным M-1 (как было доказано в последнем случае), который имеет оптимальный периметр (N + 1) M - ( М (Н + 1)) мод 2 . Покажем теперь, что это будет работать для (N, M).

Подобно увеличению пальцев, каждая синергетика добавляет два к периметру многоугольника. Общее количество зубцов составляет (N + N mod 2) / 2 , для всего добавленного периметра N + N mod 2 .

Объединяя это с гипотезой, мы получаем, что новый периметр:

(N + 1)*M - (M*(N+1)) mod 2 + N + N mod 2
(N + 1)*(M + 1) - (M*(N+1)) mod 2 + N mod 2 - 1
(N + 1)*(M + 1) - (M*(N+1)) mod 2 - (N + 1) mod 2

У нас есть это

(M*(N+1)) mod 2 - (N + 1) mod 2 = ((M+1)*(N+1)) mod 2

Потому что, если N нечетно, то это сводится к 0 = 0, а если N четно, то сводится к 

- A mod 2 - 1 = -(A + 1) mod 2

Таким образом, стратегия оптимальна для всех M, N> 0 .

Андре Хардер
источник
2
Это много математики! Не могли бы вы просто рассчитать периметр формы, которую вы создаете, и показать, что она соответствует предоставленному максимальному значению? Вы знаете, сколько у вас «пальцев», сколько у каждого пальца и т. Д. Поэтому вычисление периметра должно быть достаточно простым.
Рето Коради
Правда. В некоторых отношениях я считаю, что индукционный путь более интуитивен, поскольку он аддитивен, но да, он ведет к более длинному объяснению.
Андре Хардер
Возможно, вы захотите узнать, что периметр равен количеству целых точек, которые он проходит.
jimmy23013