# Shoes for seahorses

Seahorses, of course, need shoes. However, a seahorse, having just one tail, needs just one shoe. Unfortunately, the shoes only come in pairs. Money is tight for the seahorse government, so they need to buy as few pairs as possible. Each seahorse has a shoe size x where x is a positive integer. However, a seahorse can wear a shoe of size x - 1 or x + 1 if need be.

Your task is to output the minimum number of pairs the seahorse government must buy to put shoes on all their seahorses.

You may take input however you want, standard loopholes, etc.

As this is , shortest code in bytes wins.

## Test cases

2 4 6 6 8 14 ->        4
2 1 3 1 1 ->           3
4 1 4 9 1 8 9 1 8 4 -> 6
1 2 3 5 7 8 10 12 ->   4

• This can be done trivially by sorting the array and looping through it, but I would like to see something creative (this has no bearing on the actual scoring, I just think it would be interesting to see another approach) Jul 14, 2017 at 6:12
• I don't see how it can be done trivially... Jul 14, 2017 at 6:13
• @bushdid911 I suppose I can't explain how Jelly works in a comment Jul 14, 2017 at 6:31
• @CodyGray You can have a size 3 pair, which covers 2 and 4. Jul 14, 2017 at 8:07
• Potential Title edit: Sea-horseshoes Jul 14, 2017 at 11:43

## Husk, 15 14 bytes

Γ0(→₀?tI↑<+3)O


Uses the greedy algorithm: sort and pair from the left. Try it online!

Thanks to Leo for saving 1 byte.

## Explanation

This is the first Husk answer that uses Γ, the function for pattern matching a list. In this use case, if a is a value and g is a function, then Γag corresponds to the function f defined by the Haskell snippet

f [] = a
f (x:xs) = g x xs


I define the base case as a = 0 and

g x xs = 1 + line0 (if head xs < x+3 then tail xs else xs)


where line0 refers to the entire line. In the Husk code, x and xs are implicit arguments to the lambda function, and line0 is ₀. The list is sorted again in each recursive call, but that doesn't matter in a golf challenge.

Γ0(→₀?tI↑<+3)O
O  Sort
Γ               and pattern match
0              giving 0 for an empty list
(         )   and applying this function to a non-empty list:
+3     Add 3 to first argument (x),
<       make a "test function" for being less than that,
↑        take values from second argument (xs) while they pass the test.
?           If that prefix is nonempty (next value can be paired),
t          take tail of xs,
I         otherwise take xs as is.
₀            Apply the main function (line0) to this list
→             and add 1 for the singleton/pair we just processed.

• All these people using their own languages makes me want to create my own. First I have to come up with a name :P Jul 14, 2017 at 21:22

# Python 2, 49 bytes

f=lambda a:a>[a.sort()]and-~f(a[[3+a.pop(0)]>a:])


Try it online!

Based on Leaky Nun's recursive solution.

Python 2, 59 bytes

p=c=0
for x in sorted(input()):c+=x>p;p=(x>p)*(x+2)
print c


Try it online!

Iterates through the sizes x in sorted order. Remembers the upper threshold p for the current size to the paired with the previous one. If so (x>p), reset the threshold to 0 to make it impossible for the next one to be paired. If not, increment the output count c and set the next threshold p to x+2.

The new threshold p=(x>p)*(x+2) is a bloated expression. I'd like to find a way to shorten it.

# 05AB1E, 13 bytes

Uses the approach OP described in the comments.

{¥3‹J0¡€gÌ2÷O


Try it online!

### Explanation

{¥3‹J0¡€gÌ2÷O   Argument l
{               Sort l
¥              Push deltas
3‹            Map to lower than 3 (1 for true, 0 for false)
J0¡         Join and split on 0
€g       Map to length
Ì      Each + 2
2÷    Integer division by 2
O   Sum

• The returns 3 for 2 4 6 6 8 14. Feb 21, 2021 at 23:00

# Python 3, 6966 60 bytes

9 bytes thanks to xnor.

f=lambda a:a[1:a.sort()]and-~f(a[1+(a[1]-a[0]<3):])or len(a)


Try it online!

• I think you can do a.sort().
– xnor
Jul 14, 2017 at 6:45
• @xnor done, thanks. Jul 14, 2017 at 6:46
• The sorting can be stuck into a lambda: f=lambda a:a[1:a.sort()]and-~f(a[1+(a[1]-a[0]<3):])or len(a)
– xnor
Jul 14, 2017 at 7:14
• or[]<a to save 3 bytes Jul 17, 2017 at 12:16

# Jelly, 20 18 bytes

ṢLµIḢ<3+2⁸ṫß‘µLỊ$?  Try it online! Fork of my Python answer. • -4 bytes: IḢ<3+2⁸ṫß‘µLḊ? (basically I don't see any reason to do Ṣ before L, and Ḋ would return [] if list if of length 1 or 0, and then I can remove an µ from LµḊ?) Jul 14, 2017 at 9:58 • But you didn't sort anywhere... Jul 14, 2017 at 10:04 • Now I'm a bit confused tbf...I think your intent is a bit different than what your code actually does? You may want to prepend an Ṣ to my golf if I understand correctly. Jul 14, 2017 at 10:07 • Something is wonky with your sort. [1, 1, 1, 1, 4, 4, 4, 8, 8, 9, 9] works but [4,1,4,9,1,8,9,1,8,4,1] doesn't. Jul 14, 2017 at 15:40 • @bushdid911 They both work. Could you demonstrate? Jul 14, 2017 at 17:06 ## C#, 111108137 102 bytes This will never win but I wanted to solve the exercise anyway: Array.Sort(a);var c=0;for(var i=0;i<a.Length;i++){c++;i+=a.Length-i>1&&a[i+1]-a[i]<3?1:0;}Console.WriteLine(c);  Thanks to the comment of @grabthefish, I was able to nibble of a few more bytes: Array.Sort(a);int c=0,i=0;for(;i<a.Length;i++){c++;i+=a.Length-i>1&&a[i+1]-a[i‌​]<3?1:0;}Console.Wri‌​teLine(c);  Following the PC&G special C# rules: class P{static void Main(){Array.Sort(a);int c=0,i=0;for(;i<a.Length;i++){c++;i+=a.Length-i>1&&a[i+1]-a[i]<3?1:0;}Console.WriteLine(c);}}  Using a lambda function: a=>{System.Array.Sort(a);int c=0,i=0;for(;i<a.Length;c++)i+=a.Length-i>1&&a[i+1]-a[i]<3?2:1;return c;}  • Comments are not for extended discussion; this conversation has been moved to chat. Jul 14, 2017 at 18:16 • Thank you for keeping the progression through the answers - that's just as interesting as the final answer. Jul 16, 2017 at 7:36 ## Perl, 113 bytes say sub{for(1..$#_){$x{$i}++;$i++if$_[$_]-$_[$_-1]>2}$x{$i}++;$-+=$_/2+$_%2for values%x;$-}->(sort{$a<=>$b}@ARGV)  Takes list of arguments from command line (as @ARGV), prints to STDOUT by default. ## In Seahorseville... A neighbourhood is a sequence of neighbouring shoe sizes. When sorted, each seahorse has immediate neighbours that can share the same shoe size. There can be multiple neighbours in the neighbourhood and no neighbours can differ in value by more than two: e.g. 3 3 4 5 5 6 is a single neighbourhood, as are 2 4 6 6, and 1 2 3 5 7 8 10 12 e.g. 1 1 1 4 5 6 contains two neighbourhoods: 1 1 1 and 4 5 6. ## Basis of the algorithm There are two types of neighbourhood: • Even-sized For these, n/2 pairs is always sufficient: e.g. 3 3 4 5 5 6 requires three pairs for 3 3, 4 5 and 5 6 • Odd-sized For these, ceil(n/2) pairs is always sufficient: e.g. 12 13 13 14 15 requires three pairs for 12 13, 13 14, and 15 alone. ## Ungolfed code to test the algorithm sub pairs { @_ = sort {$a <=> $b } @_; my @hood; my$i = 0;
for (1..$#_) { push @{$hood[$i]},$_[$_-1];$i++ if $_[$_]-$_[$_-1]>2
}
push @{$hood[$i]}, $_[$#_];
my $pairs;$pairs += int(@{$hood[$_]} / 2) + @{$hood[$_]} % 2 for 0..$#hood; return "$pairs : @{[map qq([@$_]), @hood]}\n"; }  ## Sample Results (Neighbourhoods enclosed in [ ] ) 4 : [2 4 6 6 8] [14] 3 : [1 1 1 2 3] 6 : [1 1 1] [4 4 4] [8 8 9 9] 4 : [1 2 3 5 7 8 10 12] 17 : [1 2 3] [6 8 9 11 13 13 15 17 19 20 21] [27 28 29 30 32 33 35 35] [38 38 40] [43 45 45 46] [49] 18 : [3 3 3] [8 10 11 11 11 12 14] [18] [21 22 23] [29] [32 33 34 34 34 35 37 38 39 41] [44 46 48 49 49] 18 : [1 2 3] [6] [9] [12 13 15 17 18 19 20 21 21 23 24 25 25] [35 36] [40 41 41 41 43 45 46 46 46] [49] 16 : [1 3] [6 6 6 6] [11 12 14 14 15 17 19 20 20 21 21 22] [25 25 27 29 31 32 33] [38 39] [44 45] [49] 16 : [2 4] [7 7 8 10 12 13 15 16] [22 22 24 24] [27 29 31 31 33 34] [37 38 39] [42 43 43 44 45 46 47] 17 : [2 4 5 6 7] [11 11 13 13 14 15 16 17 17 17 19] [29] [34 35 36] [39 39 41 41 41 42 44 46] [49 49] 18 : [3 4 5 7 7] [10 10 12 12 12 14 15 15 17 18] [21] [24 24] [28] [32] [39 40 41 42 43 44 44] [47 47] [50] 16 : [2 4] [7 7 8 8] [11 11] [14 16 17 17 18 19] [22 24 26 26] [30 31 33 34 34 35] [38 38 39] [42 43] [50] 16 : [1 3 4 5] [11 11] [15 15 17 18 19 21 22 23 23 25 27 27 27 27 28 29 30 30] [33 34] [41 41] [45] [48] 17 : [2 2 3 4 6 6 7] [10 10] [13 14 15 16 17 19] [23 25] [28 30 31 32 33 34 36 37 38] [42] [48 49 50] 17 : [2] [7 9 9 9 9 10 10 12] [16 16] [19 21 21 22 24] [27 27 27] [36 36 36 37 39 39 40 40 40 41] [46] 18 : [1] [5 6 6 8] [11 11 12] [19 19 20 21 22 24 26 26] [29 30 31 32 34 35 35] [38] [42] [45] [48 48 49 49] 16 : [2 4 4 6] [11 12 13 13 13] [21 21 21 23] [30 31 31 33 35] [41 41 41 43 45 46 47 48 48 49 49 50] 16 : [2 2] [8 10 12] [15 15 15 15 16 16] [19 20] [23 24] [28 28 29] [32 34 36 36 36 37 39 41] [44 45 47 48] 17 : [3 3] [6] [9 10 11] [17 18] [21 23 23] [27 28 29 29 30 31 31 33] [37 37 39 39 39 40] [43 44] [47 48 49] 17 : [4] [7 9 10 10] [14 14 14] [17] [21] [25 25 27 27 28 30] [33 35 37 37 38 40 41 43 44 45 47 48 49 50] 18 : [3 4 5 6 7] [10 11 12 12 14 15 16 17] [20] [23 24 25 25 26 26] [31] [35] [38 40 41 42] [45 46 47] [50] 17 : [1 3] [8 10] [16 16 18 19 20 20] [23 23] [26] [30 31 33 34 35] [39 39 39 40 41 42 43] [46 46 47 47 49] 18 : [2 4 4 4 4 6 7 8 8 10 10] [13] [16 17] [20 22 23 25 25] [29 29 29] [33] [39 40 42] [48 48 49 49] 16 : [1 1 3 4] [7 8 10 10] [18 18 20 21] [24 25 26 27 29 31 33 33 34 34] [37 37 39] [45 46 48 49 49] 17 : [1] [4 4] [7 9 9 11 12] [15 16 17 17 18 19 21 21 21 22 23] [27 28 30 31] [37 39] [42] [48 49 49 50] 17 : [3 4 6 7 7 8 9 10 10 11 13 14 14] [21 21 23] [26 27] [31 32] [35 36] [39 40 41 41 41] [44 44] [49] 16 : [1] [4 6 6 8 10 12 13 15] [20 20 21 21] [29 29 30] [34 36 36 37 37 38 38 40] [44 45 46 47 47 48] 17 : [3 4 4 6] [12 14 15 16 17] [20 21 22 22 22 23 24 26 26] [29 30 32] [35 37 37 37 38 39 41 42] [48] 19 : [1] [5] [8 9] [14 14 14 16 16 17 17 17 17] [21] [24 24 24] [30] [34 35 36 37 39 40 40] [45 46 46 47 48]  # Mathematica, 67 bytes Length@Flatten[Partition[#,UpTo@2]&/@Split[Sort@#,Abs[#-#2]<3&],1]&  Try in Wolfram sandbox. • Any way we can test? Like the Wolfram thing? Jul 14, 2017 at 13:15 • @LiefdeWen You could Try it online! in Mathics. Mathics doesn't support all the functions of the Wolfram language, but the ones used in this entry are all implemented, so either Mathics is broken or this solution is invalid. Jul 14, 2017 at 14:32 • It works on sandbox.open.wolframcloud.com, so the problem is on Mathics' side – ovs Jul 14, 2017 at 14:34 • @Phoenix don't think Mathics supports UpTo Jul 14, 2017 at 14:39 # K (ngn/k), 31 bytes {#,/0N 2#/:(0,&~t)_t:3>-':x@<x}  Try it online! • x@<x sort the input (ascending) • t:3>-': generate boolean array indicating where the difference between values is less than 3, storing in t • (0,&~t)_t split t on where 0's are present, e.g. 1 1 1 0 1 1 0 1 1 1 => (1 1 1;0 1 1;0 1 1 1) • 0N 2#/: split each of the right-side arguments into length 2 chunks (i.e. valid "pairs" of shoes) • #,/ flatten the chunks and take their count ## Perl, 103 bytes say sub{for(1..$#_+1){$x{$i}++;$i++if$_[$_]-$_[$_-1]>2}@_/2+.5*grep$_%2,values%x}->(sort{$a<=>$b}@ARGV)


Takes list of arguments from command line (as @ARGV), prints to STDOUT by default.

This is an alternative approach, based on the following relationship:

Minimum pairs = ( Population size + # Odd neighbourhoods ) / 2


(See this answer for how neighbourhood is defined)

# Javascript, 67 bytes

a=>(a=a.sort((a,b)=>a-b)).filter((n,i)=>m=!m|n-a[i-1]>2,m=0).length


Example code snippet:

f=
a=>(a=a.sort((a,b)=>a-b)).filter((n,i)=>m=!m|n-a[i-1]>2,m=0).length

v=[[2,4,6,6,8,14],[2,1,3,1,1],[4,1,4,9,1,8,9,1,8,4],[1,2,3,5,7,8,10,12]]
for(k=0;k<4;k++)
console.log(f([${v[k]}])=${f(v[k])})

# J, 29 28 bytes

[:#(([#~_2>-&{.),_:0}])/@/:~


Try it online!

Basic idea:

• /:~ Sort.
• (...)/ Fold from the right, collapsing pairs into the single value infinity _, and appending the new value otherwise.
• [:# Return the length of the result.

Specifically, step 2 works like this:

• _:0}] Update the first element 0} of the right-hand fold argument ] (the list we're "building", the "memo" of the reduce, etc) to infinity _:.
• _2>-&{. When the difference between the left-hand fold argument and the first element of the right-hand fold argument is less than negative 2 _2, append the left-hand argument [#~...,. This condition will hold when either:
• The values are too far apart to wear the same shoe.
• The previous value was already "used up" by a preceding pair. The right argument will always be infinity in this case.

# Jelly, 13 bytes

Ṣ3+þŒpŒɠ€HĊ§Ṃ


Try it online!

# Explatation

Ṣ3+þŒpŒɠ€HĊ§Ṃ   Main monadic link
Ṣ               Sort
3+þ            Add [1,2,3] to each element
Œp          Cartesian product
Œɠ        Run lengths
€         of each sublist
H      Halve all numbers
Ċ     Ceil all numbers
§    Sum each sublist
Ṃ   Minimum