31
\$\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\$
15
  • \$\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
  • 6
    \$\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

13 Answers 13

6
\$\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\$
1
  • 1
    \$\begingroup\$ The returns 3 for 2 4 6 6 8 14. \$\endgroup\$ – Jonah Feb 21 at 23:00
9
\$\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\$
1
  • \$\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
7
\$\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\$
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\$
4
  • \$\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\$
7
  • \$\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
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\$
2
  • \$\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\$
4
  • \$\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
1
\$\begingroup\$

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

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

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