9
\$\begingroup\$

Background

I want to build a fence. For that, I have collected a bunch of poles, and stuck them to the ground. I have also collected lots of boards that I'll nail to the poles to make the actual fence. I tend to get carried away when building stuff, and most likely I'll just keep nailing the boards to the poles until there's no more place to put them. I want you to enumerate the possible fences that I can end up with.

Input

Your input is a list of two-dimensional integer coordinates representing the positions of the poles, in any convenient format. You can assume that it contains no duplicates, but you cannot assume anything about its order.

The boards are represented by straight lines between the poles, and for simplicity, we only consider horizontal and vertical boards. Two poles can be joined by a board if there are no other poles or boards between them, meaning that the boards cannot cross each other. An arrangement of poles and boards is maximal if no new boards can be added to it (equivalently, there is either a pole or a board between any two horizontally or vertically aligned poles).

Output

Your output is the number of maximal arrangements that can be constructed using the poles.

Example

Consider the input list

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

Viewed from the top, the corresponding arrangement of poles looks something like this:

  o
 o o
o    o
 o o
  o

There are exactly three maximal arrangements that can be constructed using these poles:

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

Thus the correct output is 3.

Rules

You can write either a function or a full program. The lowest byte count wins, and standard loopholes are disallowed.

Test Cases

[] -> 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
\$\endgroup\$
  • 1
    \$\begingroup\$ The example seems to have (-2,0) twice. Should one of those be (2,0)? \$\endgroup\$ – isaacg Mar 12 '15 at 17:17
  • \$\begingroup\$ @isaacg Actually, it should be (0,-2), good catch. Changing now. \$\endgroup\$ – Zgarb Mar 12 '15 at 19:02
5
\$\begingroup\$

Mathematica, 301 bytes

(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}]])&

This is an unnamed function which takes the coordinates as a nested List and returns an integer. That is, you can either give it a name and call it, or just append

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

With indentation:

(
  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}
    ]
  ]
) &

I can't even begin to express how naive this implementation is... it definitely couldn't be more brute force...

  • Get all (unordered) pairs of poles.
  • Sort each pair and all pairs into a canonical order.
  • Discard pairs which don't share one coordinate (i.e. which aren't connectible by an orthogonal line).
  • Discard pairs can be formed from two shorter pairs (so that o--o--o yields only two fences instead of three).
  • Get all subsets of those pairs - i.e. all possible combinations of fences.
  • Filter out combinations which have fences crossing each other.
  • Count the number of resulting fence sets for which no strict superset can be found in the list.

Surprisingly it does solve all the test cases virtually immediately.

A really neat trick I discovered for this is the use of Orderless to cut down on the number of patterns I have to match. Essentially, when I want to ditch fence sets with crossing fences, I need to find a pair of vertical and horizontal fence and check the condition on them. But I don't know what order they'll appear in. Since list patterns are normally order dependent, this would result in two really long patterns. So instead I replace with surrounding list with a function t with t @@@ - which isn't defined so it is held as it is. But that function is Orderless, so I can just check a single order in the pattern, and Mathematica will check it against all permutations. Afterwards, I put the lists back in place with List @@@.

I wish there was a built-in that is a) Orderless, b) not Listable and c) not defined for 0 arguments or list arguments. Then I could replace t by that. But there doesn't seem to be such an operator.

\$\endgroup\$
  • \$\begingroup\$ When you're thinking if Mathematica does it right or fast enough, the answer is "yes". \$\endgroup\$ – seequ Mar 12 '15 at 20:35
  • \$\begingroup\$ Well, that's about as naive as my reference implementation. :P \$\endgroup\$ – Zgarb Mar 13 '15 at 14:00
1
\$\begingroup\$

Haskell, 318 bytes

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]

Usage: p [(1,0),(0,1),(-1,0),(0,-1)]. Output: 2

How it works:

  • create all sublists of the input list and keep those with two elements and with either equal x or equal y coordinates. This is a list of all pairs of poles where a fence can be build in between.
  • create all sublists of it
  • add boards for every list
  • remove lists where a x-y coordinate appears twice (boards and poles)
  • remove duplicate lists (boards only) to handle multiple empty lists, because of directly adjacent poles (e.g. (1,0) and (1,1))
  • keep those which are not a strict sublist of another list
  • count remaining lists
\$\endgroup\$

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.