Подсчитать максимальные заборы

9

Фон

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

вход

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

Доски представлены прямыми линиями между полюсами, и для простоты мы рассмотрим только горизонтальные и вертикальные доски. Два полюса могут быть соединены доской, если между ними нет других полюсов или досок, то есть доски не могут пересекать друг друга. Расположение столбов и досок является максимальным, если к нему нельзя добавить новые доски (эквивалентно, между любыми двумя горизонтально или вертикально выровненными полюсами есть либо столб, либо доска.

Вывод

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

пример

Рассмотрим список ввода

[(3,0),(1,1),(0,2),(-1,1),(-2,0),(-1,-1),(0,-2),(1,-1)]

Если смотреть сверху, соответствующее расположение полюсов выглядит примерно так:

  o
 o o
o    o
 o o
  o

Есть ровно три максимальных расположения, которые могут быть построены с использованием этих полюсов:

  o        o        o
 o-o      o|o      o-o
o----o   o||| o   o| | o
 o-o      o|o      o-o
  o        o        o

Таким образом, правильный вывод 3.

правила

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

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

[] -> 1
[(0,0),(1,1),(2,2)] -> 1
[(0,0),(1,0),(2,0)] -> 1
[(0,0),(0,1),(1,0),(1,1)] -> 1
[(1,0),(0,1),(-1,0),(0,-1)] -> 2
[(3,0),(1,1),(0,2),(-1,1),(-2,0),(-1,-1),(0,-2),(1,-1)] -> 3
[(0,0),(4,0),(1,1),(1,-2),(3,1),(3,-2),(2,-1),(4,-1)] -> 3
[(0,0),(4,0),(1,1),(1,-2),(3,1),(3,-2),(2,-1),(4,-1),(0,-1)] -> 4
[(0,0),(4,0),(1,1),(1,-2),(3,1),(3,-2),(2,-1),(0,-1),(2,2)] -> 5
[(0,0),(4,0),(1,1),(1,-2),(3,1),(3,-2),(2,-1),(4,-1),(0,-1),(2,2)] -> 8
Zgarb
источник
1
Пример, кажется, имеет (-2,0) дважды. Должен ли один из них быть (2,0)?
Исаак
@isaacg На самом деле, это должно быть (0,-2), хороший улов. Меняется сейчас.
Згарб

Ответы:

5

Mathematica, 301 байт

(t~SetAttributes~Orderless;u=Subsets;c=Complement;l=Select;f=FreeQ;Count[s=List@@@l[t@@@u[Sort@l[Sort/@#~u~{2},!f[#-#2&@@#,0]&]//.{a___,{x_,y_},{x_,z_},b___,{y_,z_},c___}:>{a,{x,y},b,{y,z},c}],f[#,t[{{a_,b_},{a_,c_}},{{d_,e_},{f_,e_}},___]/;d<a<f&&b<e<c]&],l_/;f[s,k_List/;k~c~l!={}&&l~c~k=={},{1}]])&

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

@ {{3, 0}, {1, 1}, {0, 2}, {-1, 1}, {-2, 0}, {-1, -1}, {0, -2}, {1, -1}}

С отступом:

(
  t~SetAttributes~Orderless;
  u = Subsets;
  c = Complement;
  l = Select;
  f = FreeQ;
  Count[
    s = List @@@ l[
      t @@@ u[
        Sort @ l[
          Sort /@ #~u~{2}, 
          !f[# - #2 & @@ #, 0] &
        ] //. {a___, {x_, y_}, {x_, z_}, b___, {y_, z_}, c___} :> 
              {a, {x, y}, b, {y, z}, c}
      ],
      f[
        #,
        t[{{a_, b_}, {a_, c_}}, {{d_, e_}, {f_, e_}}, ___] 
          /; d < a < f && b < e < c
      ] &
    ], 
    l_ /; f[
      s, 
      k_List /; k~c~l != {} && l~c~k == {}, 
      {1}
    ]
  ]
) &

Я даже не могу выразить, насколько наивна эта реализация ... она определенно не может быть более грубой силой ...

  • Получить все (неупорядоченные) пары полюсов.
  • Сортируйте каждую пару и все пары в каноническом порядке.
  • Откажитесь от пар, которые не разделяют одну координату (то есть которые не соединяются ортогональной линией).
  • Пары сброса могут быть сформированы из двух более коротких пар (так что o--o--oполучается только два забора вместо трех).
  • Получить все подмножества этих пар - то есть все возможные комбинации заборов.
  • Отфильтруйте комбинации, у которых заборы пересекаются.
  • Подсчитайте количество результирующих наборов ограждений, для которых в списке нет строгого надмножества.

Удивительно, но он решает все тесты практически сразу.

Я обнаружил, что по-настоящему изящный трюк заключается в том, Orderlessчтобы сократить количество паттернов, которым я должен соответствовать. По сути, когда я хочу разбить наборы ограждений пересекающимися изгородями, мне нужно найти пару вертикальных и горизонтальных ограждений и проверить их состояние. Но я не знаю, в каком порядке они будут отображаться. Поскольку шаблоны списков обычно зависят от порядка, это приведет к двум действительно длинным шаблонам. Поэтому вместо этого я заменяю окружающий список на функцию tс t @@@- которая не определена, поэтому она сохраняется как есть. Но эта функция есть Orderless, поэтому я могу просто проверить один порядок в шаблоне, а Mathematica проверит его по всем перестановкам. После этого я вернул списки на место List @@@.

Хотелось бы, чтобы была встроенная а) Orderless, б) нет Listable и в) не определена для 0 аргументов или списка аргументов. Тогда я мог бы заменить tэтим. Но, похоже, такого оператора нет.

Мартин Эндер
источник
Когда вы думаете, правильно ли Mathematica делает это правильно или достаточно быстро, ответ «да».
seequ
Ну, это примерно так же наивно, как моя эталонная реализация. : P
Zgarb
1

Haskell, 318 байт

import Data.List
s=subsequences
k[(_,a,b),(_,c,d)]|a==c=f(\w->(1,a,w))b d|1<2=f(\w->(2,w,b))a c
f t u v=[t x|x<-[min u v+1..max u v-1]]
q l=nub[x|x<-map(k=<<)$s[a|a@[(_,n,m),(_,o,p)]<-s l,n==o||m==p],x++l==nubBy(\(_,a,b)(_,c,d)->a==c&&b==d)(x++l)]
m=q.map(\(a,b)->(0,a,b))
p l=sum[1|x<-m l,all(\y->y==x||x\\y/=[])$m l]

Использование: p [(1,0),(0,1),(-1,0),(0,-1)]. Вывод:2

Как это работает:

  • создайте все подсписки входного списка и сохраните их с двумя элементами с одинаковыми координатами x или y. Это список всех пар полюсов, между которыми можно построить забор.
  • создать все его подсписки
  • добавить доски для каждого списка
  • удалить списки, где координата xy появляется дважды (доски и столбы)
  • удалить дубликаты списков (только доски) для обработки нескольких пустых списков из-за соседних полюсов (например, (1,0) и (1,1))
  • сохранить те, которые не являются строгим подсписком другого списка
  • подсчитать оставшиеся списки
Ними
источник