Shoes for seahorses

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, 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 1

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.

Answer 2

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.

Answer 3

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

Answer 4

Python 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!

Answer 5

Jelly, 20 18 bytes

ṢLµIḢ<3+2⁸ṫß‘µLỊ$?

Try it online!

Fork of my Python answer.

Answer 6

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 7

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 8

Mathematica, 67 bytes

Length@Flatten[Partition[#,UpTo@2]&/@Split[Sort@#,Abs[#-#2]<3&],1]&

Try in Wolfram sandbox.

Answer 9

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

Answer 10

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)

Answer 11

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 12

J, ²⁹ 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.

Answer 13

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