6
\$\begingroup\$

Task

You have a row of numbered boxes, with some filled with items and some empty. Your job is to output the number of boxes from the first to the last box, inclusive, minus the number of boxes of the largest gap between two filled boxes.

Rules

Your program should handle up to 1000 boxes. Score = size of program in bytes. -50 if you don't use a built-in sorting functionality. -150 if you program in assembly :D All cases will have at least one gap.

Input is a list of n-th boxes that are filled. Standard loop-holes aren't allowed.

Sample Input

9, 5, 4, 2

Functions with a list as input are fine.

Sample Output

5

This is the number of boxes between the 2nd and 9th box, inclusive, subtracted by the number of boxes of the gap between the 5th and 9th box (8 - 3 = 5)

\$\endgroup\$
  • \$\begingroup\$ @MartinBüttner I've edited it so hopefully it's clearer. \$\endgroup\$ – qwr Oct 1 '14 at 21:45
  • \$\begingroup\$ @MartinBüttner Functions are okay. \$\endgroup\$ – qwr Oct 1 '14 at 21:50
  • 2
    \$\begingroup\$ Can I assume input to be like [9 5 4 2] ? \$\endgroup\$ – Optimizer Oct 1 '14 at 21:58
  • \$\begingroup\$ 1. Are the box numbers always in descending order? At least one answer seems to assume this. 2. Will the box numbers always be positive integers? \$\endgroup\$ – Dennis Oct 2 '14 at 2:41
  • 1
    \$\begingroup\$ @Dennis No, and the boxes are numbered starting from 1. \$\endgroup\$ – qwr Oct 2 '14 at 3:02
5
\$\begingroup\$

CJam, -19 -22 -23 (27 bytes - 50 bonus)

Vq~_:+,\&_(+]z{~-~:Xe>}/X+z

Try it online.

Example run

$ cjam box-gap.cjam <<< '[9 5 4 2]'; echo
5

How it works

V                              " V := 0                                          ";
 q~                            " Q := eval(input))                               ";
   _:+,                        " S := range(sum(Q))                              ";
       \&                      " T := S ∩ T          # Preserves the order of S. ";
         _(+                   " U := T[1:] + [T[0]]                             ";
            ]z                 " Z := zip(T, U)                                  ";
              {       }/       " for (X,Y) ∊ Z:                                  ";
               :-~:Me>         "   V := max(V, M := ~(X - Y))                    ";
                        M+z    " R := abs(V + M)                                 ";
\$\endgroup\$
5
\$\begingroup\$

CJam, -8 (43 42 bytes - 50 bonus)

l~:A{e>}*A{e<}*-)A{_A\-f{-z}{e<}*}%{e>}*(-

Using tips by @Dennis!

Try it online here

Input is like:

[9 5 4 2]
\$\endgroup\$
  • \$\begingroup\$ The bug with folding e< and e> is really annoying, isn't it? ;) \$\endgroup\$ – Martin Ender Oct 1 '14 at 21:59
  • \$\begingroup\$ Yeah, 9 extra characters :( \$\endgroup\$ – Optimizer Oct 1 '14 at 22:00
  • \$\begingroup\$ You can use f{-z} instead of \f-{z}%. (I was going to suggest :z, but that doesn't seem to work either.) \$\endgroup\$ – Dennis Oct 2 '14 at 5:04
  • \$\begingroup\$ Yeah, too many non : supported operations :( \$\endgroup\$ – Optimizer Oct 2 '14 at 5:07
  • \$\begingroup\$ Sadly. You don't need the \ before f. \$\endgroup\$ – Dennis Oct 2 '14 at 5:10
4
\$\begingroup\$

Mathematica, 44 bytes

f=Max@#-Min@#-Max[RotateLeft[l=Sort@#]-l]+2&

Defines a function that takes one argument in form of a list {9, 5, 4, 2}.

\$\endgroup\$
  • \$\begingroup\$ Wow, you're fast. What does purpose does RotateLeft have? \$\endgroup\$ – qwr Oct 1 '14 at 21:51
  • 2
    \$\begingroup\$ @qwr Well, it rotates the array to the left ^^. So {2,4,5,9} becomes {4,5,9,2}. Subtracting the original (sorted) list, gives me all gaps (plus one), i.e. {2,1,4,-7}. The last element is of course useless, but since it's always negative it doesn't matter for Max. \$\endgroup\$ – Martin Ender Oct 1 '14 at 21:53
0
\$\begingroup\$

APL (Dyalog 14) (34 - 50 = -16)

{⎕ML←3⋄(1+V-⌊/⍵)-⌈/≢¨⊂⍨~⍵∊⍨⍳V←⌈/⍵}

This is a function that takes a list.

Or, for the same amount of characters:

⎕ML←3⋄(1+V-⌊/B)-⌈/≢¨⊂⍨~B∊⍨⍳V←⌈/B←⎕

This reads the list from the keyboard.

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

Python 2 - 54 (117104-50)

x=input()
M=max(x)-min(x)+1
X=['1']*M
for i in x:X[i-min(x)]='0'
print M-len(max("".join(X).split('0')))

A program that pretends that the buckets are real, then awkwardly splits them into groups. Takes input like 9,5,4,2.

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