16
\$\begingroup\$

You're a farmer and your flock of sheep has escaped! Oh no!

Round up those sheep by building fences to contain them. As a farmer on a budget you want to use the least amount of fence possible. Luckily for you though, they aren't the smartest sheep in the world and don't bother moving after having escaped.

Task

Given a list of coordinates, output the least amount of fence segments necessary to contain the sheep.

Rules

  • Sheep are contained if they cannot wander off (no holes in the fence).
  • You do not have to contain all the sheep in one block of fence - there could be multiple fenced-off areas independent from each other.
  • Fence segments are oriented in cardinal directions.
  • Each coordinate tuple represents a single sheep.
  • Input must be positive integer pairs, x>0 & y>0, but can be formatted appropriately for your language.
    • i.e.: {{1,1},{2,1},{3,7}, .. } or [1,2],[2,1],[3,7], ..
  • Empty spaces inside a fenced-off area are okay.
  • You cannot assume coordinates are input in any specific order.

For example, a single sheep requires 4 fence segments to be fully contained.

Test cases

[1,1]
4

[1,1],[1,2],[2,2]
8

[2,1],[3,1],[2,3],[1,1],[1,3],[3,2],[1,2],[3,3]
12

[1,1],[1,2],[2,2],[3,7],[4,9],[4,10],[4,11],[5,10]
22

[1,1],[2,2],[3,3],[4,4],[5,5],[6,6],[7,7],[8,8],[9,9]
36

[1,1],[2,2],[3,3],[4,4],[6,6],[7,7],[8,8],[9,9]
32

[2,1],[8,3],[8,4]
10

Notes

  • You can assume input coordinates are valid.
  • Your algorithm should theoretically work for any reasonably large integer coordinate (up to your language's maximum supported value).
  • Either full program or function answers are okay.

This is , so shortest answer in bytes wins!

\$\endgroup\$
  • \$\begingroup\$ Can input be a list of x coordinates, followed by a list of y coordinates? e.g. {1,2,3,4},{5,6,7,8} -> {1,5},{2,6},{3,7},{4,8} \$\endgroup\$ – Pavel Jun 15 '17 at 19:13
  • \$\begingroup\$ @Phoenix Nope, each x,y input must be together. Nice thought though, I hadn't thought of that myself. \$\endgroup\$ – CzarMatt Jun 15 '17 at 19:19
  • \$\begingroup\$ What are the bounds on the coordinates? Are 0s and negatives possible? \$\endgroup\$ – AGourd Jun 15 '17 at 19:54
  • 3
    \$\begingroup\$ This is surprisingly hard. Every time I think I have a heuristic that handles all cases, there's something I missed. \$\endgroup\$ – xnor Jun 15 '17 at 20:38
  • 1
    \$\begingroup\$ Wow, what a challenge. I concede my loss; screw doing this in 05AB1E. \$\endgroup\$ – Magic Octopus Urn Jun 16 '17 at 22:03
5
\$\begingroup\$

JavaScript (ES6), 251 244 275 bytes

a=>Math.min(...(P=(a,r=[[a]],c=a[0])=>(a[1]&&P(a.slice(1)).map(l=>(r.push([[c],...l]),l.map((_,i)=>r.push([[c,...l[i]],...((b=[...l]).splice(i,1),b)])))),r))(a).map(L=>L.reduce((p,l)=>l.map(([h,v])=>(x=h<x?h:x,X=h<X?X:h,y=v<y?v:y,Y=v<Y?Y:v),x=y=1/0,X=Y=0)&&p+X-x+Y-y+2,0)))*2

How?

We use the recursive function P() to create a list of all possible partitions of the input list. This function is currently sub-optimal, in that it's returning some duplicated partitions -- which does not however alter the final result.

For each partition, we compute the number of fences required to surround all sheep in each group with a rectangle. The sum of these fences gives the score of the partition. We eventually return the lowest score.

Test cases

let f =

a=>Math.min(...(P=(a,r=[[a]],c=a[0])=>(a[1]&&P(a.slice(1)).map(l=>(r.push([[c],...l]),l.map((_,i)=>r.push([[c,...l[i]],...((b=[...l]).splice(i,1),b)])))),r))(a).map(L=>L.reduce((p,l)=>l.map(([h,v])=>(x=h<x?h:x,X=h<X?X:h,y=v<y?v:y,Y=v<Y?Y:v),x=y=1/0,X=Y=0)&&p+X-x+Y-y+2,0)))*2

console.log(f([[1,1]]))
console.log(f([[1,1],[1,2],[2,2]]))
console.log(f([[2,1],[3,1],[2,3],[1,1],[1,3],[3,2],[1,2],[3,3]]))
console.log(f([[1,1],[1,2],[2,2],[3,7],[4,9],[4,10],[4,11],[5,10]]))
console.log(f([[1,1],[2,2],[3,3],[4,4],[5,5],[6,6],[7,7],[8,8],[9,9]]))
console.log(f([[1,1],[2,2],[3,3],[4,4],[6,6],[7,7],[8,8],[9,9]]))
console.log(f([[2,1],[8,3],[8,4]]))

| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ About step 2, why not [ [1,1],[2,2] ] , [ [1,2] ] ? \$\endgroup\$ – edc65 Jun 16 '17 at 7:59
  • \$\begingroup\$ @edc65 Hopefully it should now be fixed. \$\endgroup\$ – Arnauld Jun 18 '17 at 10:07
2
\$\begingroup\$

k, 62 58 57 55 bytes

{+//2*1+{(|/x)-&/x}'(x@?(&|/2>(|/'{x|-x}x-\:)')')/,:'x}

Try it online!

| improve this answer | |
\$\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.