30
\$\begingroup\$

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
\$\endgroup\$
  • \$\begingroup\$ 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) \$\endgroup\$ – rigged Jul 14 '17 at 6:12
  • 1
    \$\begingroup\$ I don't see how it can be done trivially... \$\endgroup\$ – Leaky Nun Jul 14 '17 at 6:13
  • 5
    \$\begingroup\$ @bushdid911 I suppose I can't explain how Jelly works in a comment \$\endgroup\$ – Leaky Nun Jul 14 '17 at 6:31
  • 1
    \$\begingroup\$ @CodyGray You can have a size 3 pair, which covers 2 and 4. \$\endgroup\$ – Zgarb Jul 14 '17 at 8:07
  • 2
    \$\begingroup\$ Potential Title edit: Sea-horseshoes \$\endgroup\$ – CraigR8806 Jul 14 '17 at 11:43

10 Answers 10

5
\$\begingroup\$

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
\$\endgroup\$
8
\$\begingroup\$

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.
\$\endgroup\$
  • \$\begingroup\$ All these people using their own languages makes me want to create my own. First I have to come up with a name :P \$\endgroup\$ – rigged Jul 14 '17 at 21:22
5
\$\begingroup\$

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!

\$\endgroup\$
  • \$\begingroup\$ I think you can do a.sort(). \$\endgroup\$ – xnor Jul 14 '17 at 6:45
  • \$\begingroup\$ @xnor done, thanks. \$\endgroup\$ – Leaky Nun Jul 14 '17 at 6:46
  • \$\begingroup\$ 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) \$\endgroup\$ – xnor Jul 14 '17 at 7:14
  • \$\begingroup\$ or[]<a to save 3 bytes \$\endgroup\$ – Felipe Nardi Batista Jul 17 '17 at 12:16
4
\$\begingroup\$

Jelly, 20 18 bytes

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

Try it online!

Fork of my Python answer.

\$\endgroup\$
  • \$\begingroup\$ -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µḊ?) \$\endgroup\$ – Erik the Outgolfer Jul 14 '17 at 9:58
  • \$\begingroup\$ But you didn't sort anywhere... \$\endgroup\$ – Leaky Nun Jul 14 '17 at 10:04
  • \$\begingroup\$ 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. \$\endgroup\$ – Erik the Outgolfer Jul 14 '17 at 10:07
  • \$\begingroup\$ 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. \$\endgroup\$ – rigged Jul 14 '17 at 15:40
  • \$\begingroup\$ @bushdid911 They both work. Could you demonstrate? \$\endgroup\$ – Leaky Nun Jul 14 '17 at 17:06
4
\$\begingroup\$

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.

\$\endgroup\$
2
\$\begingroup\$

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;}
\$\endgroup\$
  • \$\begingroup\$ Comments are not for extended discussion; this conversation has been moved to chat. \$\endgroup\$ – Dennis Jul 14 '17 at 18:16
  • \$\begingroup\$ Thank you for keeping the progression through the answers - that's just as interesting as the final answer. \$\endgroup\$ – Criggie Jul 16 '17 at 7:36
2
\$\begingroup\$

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]
\$\endgroup\$
1
\$\begingroup\$

Mathematica, 67 bytes

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

Try in Wolfram sandbox.

\$\endgroup\$
  • \$\begingroup\$ Any way we can test? Like the Wolfram thing? \$\endgroup\$ – LiefdeWen Jul 14 '17 at 13:15
  • \$\begingroup\$ @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. \$\endgroup\$ – Pavel Jul 14 '17 at 14:32
  • \$\begingroup\$ It works on sandbox.open.wolframcloud.com, so the problem is on Mathics' side \$\endgroup\$ – ovs Jul 14 '17 at 14:34
  • 1
    \$\begingroup\$ @Phoenix don't think Mathics supports UpTo \$\endgroup\$ – martin Jul 14 '17 at 14:39
0
\$\begingroup\$

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)

\$\endgroup\$
0
\$\begingroup\$

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])}`)

\$\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.