# Catch those sheep!

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!

• 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} – Pavel Jun 15 '17 at 19:13
• @Phoenix Nope, each x,y input must be together. Nice thought though, I hadn't thought of that myself. – CzarMatt Jun 15 '17 at 19:19
• What are the bounds on the coordinates? Are 0s and negatives possible? – AGourd Jun 15 '17 at 19:54
• This is surprisingly hard. Every time I think I have a heuristic that handles all cases, there's something I missed. – xnor Jun 15 '17 at 20:38
• Wow, what a challenge. I concede my loss; screw doing this in 05AB1E. – Magic Octopus Urn Jun 16 '17 at 22:03

## JavaScript (ES6), 251244 275 bytes

a=>Math.min(...(P=(a,r=[[a]],c=a)=>(a&&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)=>(a&&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]]))

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

# k, 62 58 57 55 bytes

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


Try it online!