[Question]
  [
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 [code-golf](/questions/tagged/code-golf "show questions tagged 'code-golf'"), 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
```
  
[Answer]
## [Husk](https://github.com/barbuz/Husk), ~~15~~ 14 bytes
```
Γ0(→₀?tI↑<+3)O
```
Uses the greedy algorithm: sort and pair from the left.
[Try it online!](https://tio.run/##yygtzv6vkHti/aOmxtzM8kPb/p@bbKDxqG3So6YG@xLPR20TbbSNNf3///9vpGCiYAaEFgqGJlxGCoYKxkBsyGUCJE0ULIGkBZQ04TJUMALKmiqYgxQbKBgaAQA "Husk – 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.
```
[Answer]
# [Python 2](https://docs.python.org/2/), 49 bytes
```
f=lambda a:a>[a.sort()]and-~f(a[[3+a.pop(0)]>a:])
```
[Try it online!](https://tio.run/##XYzBCsIwEETvfoXHDa6lSROtBfsjIYeVEhQ0CTUXL/56XMGDCcsMzCzz0itfY1Cl@POdHpeFtjTRbKl7xjWDcBSW/dsDWTvsqEsxQS/cTJMTJa23kMGDVajxwDei1E6Izd9D4sCSVau50XhiH39eryQqXhk8foE9StUwTZVNQ1dNZhrn8gE "Python 2 – Try It Online")
Based on [Leaky Nun's recursive solution](https://codegolf.stackexchange.com/a/132372/20260).
---
**[Python 2](https://docs.python.org/2/), 59 bytes**
```
p=c=0
for x in sorted(input()):c+=x>p;p=(x>p)*(x+2)
print c
```
[Try it online!](https://tio.run/##LUtLDsIgEN1zCsIK2lkUBEUNXsR0hRi7gQligqfHaWIm7zd5D7/tVbIZqacohBgYYljYs1Te@Zb5u9SWHnLL@GlSqUucQ7/hFYMkUZPss1EM65Ybj4P2kxt3AxaOdB60XRlFDQeCJm9JLZyJ/Z/3hgZDDQenfbKANvRz4Ncf "Python 2 – 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.
[Answer]
# [05AB1E](https://github.com/Adriandmen/05AB1E), 13 bytes
Uses the approach OP described in the comments.
```
{¥3‹J0¡€gÌ2÷O
```
[Try it online!](https://tio.run/##MzBNTDJM/f@/@tBS40cNO70MDi181LQm/XCP0eHt/v//RxvqKBjpKBjrKJjqKJjrKFjoKBgaALFRLAA "05AB1E – 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
```
[Answer]
# [Python 3](https://docs.python.org/3/), ~~69~~ ~~66~~ 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!](https://tio.run/##VYwxDsIwDEV3TtExFi6qmwAlgpNEGYxKBFJJqpCFhasHV2Kgsv4b3tf3/C73FHWt4TLx8zpyw5YdWd69Ui4KPMex/QQlbrvAt@w6f9ZgPaTcTLeoGOqcH7GooFyPBg9yA5LxAJu/glBLaGWNGIMn4fDjekXYy2qPx@Vhh9RLW78 "Python 3 – Try It Online")
[Answer]
# [Jelly](https://github.com/DennisMitchell/jelly), ~~20~~ 18 bytes
```
ṢLµIḢ<3+2⁸ṫß‘µLỊ$?
```
[Try it online!](https://tio.run/##y0rNyan8///hzkU@h7Z6PtyxyMZY2@hR446HO1cfnv@oYcahrT4Pd3ep2P8/3P6oac3//9FGOiY6ZkBooWNoEqsD5BrqGAOxIZBtAqRNdCyBpAWUBKkw1DECqjDVMQdpMdAxNIoFAA "Jelly – Try It Online")
Fork of my [Python answer](https://codegolf.stackexchange.com/a/132372/48934).
[Answer]
## C#, ~~111~~ ~~108~~ ~~137~~ 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;}
```
[Answer]
## 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]
```
[Answer]
# Mathematica, 67 bytes
```
Length@Flatten[Partition[#,UpTo@2]&/@Split[Sort@#,Abs[#-#2]<3&],1]&
```
Try in [Wolfram sandbox](https://sandbox.open.wolframcloud.com "Wolfram sandbox").
[Answer]
# [K (ngn/k)](https://bitbucket.org/ngn/k), 31 bytes
```
{#,/0N 2#/:(0,&~t)_t:3>-':x@<x}
```
[Try it online!](https://tio.run/##y9bNS8/7/z/NqlpZR9/AT8FIWd9Kw0BHra5EM77EythOV92qwsGmovZ/mrqGkYKJghkQWigYmlgbKRgqGAOxobUJkDRRsASSFlDSxNpQwQgoa6pgDlJsoGBopPkfAA "K (ngn/k) – 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
[Answer]
## 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](https://codegolf.stackexchange.com/a/132505/2771) for how *neighbourhood* is defined)
[Answer]
# 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])}`)
```
[Answer]
# [J](http://jsoftware.com/), 29 28 bytes
```
[:#(([#~_2>-&{.),_:0}])/@/:~
```
[Try it online!](https://tio.run/##TYxPC4JAEMXvfopHQrmku85qVhtGf6BTdOiqISKFdMiQbpVf3ab0EMN7M/yY967tQI4uiA1GcOHDsDyJ7XG/axNjO05iN5leesOnFG5m/PdJqJUyTSusw0Zifase5blGfr/XVV6U5kdtj2zpO2z6NVapWMiMVq52gqUnVJqaxrLORVkhRIwLNO@IZwYKOx70nPgiUAejH@RfYs3ZZ72H/2XEsQATTL91Pki3Hw "J – 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.
[Answer]
# [Jelly](https://github.com/DennisMitchell/jelly), 13 bytes
```
Ṣ3+þŒpŒɠ€HĊ§Ṃ
```
[Try it online!](https://tio.run/##y0rNyan8///hzkXG2of3HZ1UcHTSyQWPmtZ4HOk6tPzhzqb/h9uBvP//o7mijXRMdMyA0ELH0CRWB8Q31DEGYkMQxwTIMNGxBJIWUBKsxlDHCKjGVMccpMtAx9AIKBgLAA "Jelly – 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
```
]