24
\$\begingroup\$

Write a function or program which takes as input a set of distinct, non-negative integers \$\{x_1, \ldots, x_n\}\$ and outputs the smallest gap between any two values in the set, i.e. \$\min_{i\neq j}|x_i-x_j|\$.

Scoring

This is not code golf. Your score is the smallest gap of the set of code points of characters in your code (highest score wins). In other words: convert your code to integer code points (using ASCII or whatever code page is standard for your language); remove duplicates; use that as input to your program; the output is your score.

For instance, if your code is min(alldifferences(input)), to get your score convert m->109, i->105, n->110, (->40, ... and your score will be 1, since the codepoints for m and n are only 1 apart.

You may assume that the input contains at least 2 distinct values; behaviour is undefined otherwise. Your code must include at least two distinct characters.

If your encoding is ASCII, you can use this online R code to verify your score.

Test cases

Input         | Output
0 1 2 3 4     | 1
2 4 8 16 32   | 2
1             | undefined
3 14 159 2653 | 11
4 6 8 9 12 14 | 1
3 14 2        | 1

Default rules for input/output apply. In particular, since the input is a set, you may assume any structure for the input.

\$\endgroup\$
  • 1
    \$\begingroup\$ Something that I just understood: we remove duplicates when scoring our code, but we get distinct integers when it’s normal inputs. So we don’t have to remove duplicates ourselves in the code, right? \$\endgroup\$ – Fatalize Dec 9 '19 at 9:32
  • \$\begingroup\$ @Fatalize That's correct: the input is made of distinct integers. \$\endgroup\$ – Robin Ryder Dec 9 '19 at 9:38
  • 1
    \$\begingroup\$ Suggested test case: [3,14,2]. Output should be 1, right? \$\endgroup\$ – Fatalize Dec 9 '19 at 9:38
  • \$\begingroup\$ @Fatalize Yes. Edited in. \$\endgroup\$ – Robin Ryder Dec 9 '19 at 9:39
  • 1
    \$\begingroup\$ Where a language has its own codepage, can we opt to use UTF-8? Or do we have to use the language-specific codepage? \$\endgroup\$ – Nick Kennedy Dec 9 '19 at 17:06

13 Answers 13

11
\$\begingroup\$

05AB1E, score: 22 49 69 (5 4 bytes)

ê¥êн

Uses the 05AB1E encoding, where the bytes have the codepoints [234,165,234,14] (ê¥ are 69 apart).

+27 score by porting @Arnauld's approach of sorting.
+20 score (and even -1 byte at the same time) thanks to @Grimmy.

Try it online or verify all test cases.

Explanation:

ê     # Sort and uniquify the (implicit) input-list (in ascending order)
 ¥    # Get the deltas of this sorted list
  ê   # Sort and uniquify this again
   н  # Pop this list and push its first item
      # (which is output implicitly as result)
\$\endgroup\$
  • 3
    \$\begingroup\$ ê¥êн scores 69. \$\endgroup\$ – Grimmy Dec 9 '19 at 12:55
  • \$\begingroup\$ @Grimmy, isn't 7 (172-165)? \$\endgroup\$ – Nahuel Fouilleul Dec 9 '19 at 13:06
  • \$\begingroup\$ @NahuelFouilleul No. \$\endgroup\$ – Grimmy Dec 9 '19 at 13:08
  • \$\begingroup\$ @Grimmy Very nice, not only do you increase the score, but it also saves a byte if this were a code-golf challenge. Thanks! \$\endgroup\$ – Kevin Cruijssen Dec 9 '19 at 13:18
4
\$\begingroup\$

Brachylog, Score = 12

⊇ᶠl₂ˢ-ˢȧˢ⌋

Try it online!

The minimum gap is 12, between and , and also between and ˢ (see the code page).

Explanation

⊇ᶠ             Find all subsets of the input
  l₂ˢ          Only keep those that have a length of 2
     -ˢ        Compute the difference of each subset
       ȧˢ      Compute the absolute value of each difference 
         ⌋     Output is the smallest one
\$\endgroup\$
4
\$\begingroup\$

Charcoal, 13 bytes, score 3

I⌊Eθ⌊ΦEθ↔⁻ιλλ

Try it online! Link is to verbose version of code and takes the code's own code points as input. Explanation:

   θ            Input array
  E             Map over elements
       θ        Input array
      E         Map over elements
          ι     Outer element
           λ    Inner element
        ↔⁻      Take the difference
     Φ      λ   Filter out zero values
 ⌊  ⌊           Take the minimum of the minima
I               Cast to string for implicit print

Charcoal's loop variables are implicit but fortunately Map consumes two variables and even more fortunately there is no variable j so there is actually a minimum difference of 3.

\$\endgroup\$
4
\$\begingroup\$

Jelly, 5 bytes, score = 24

This is most probably sub-optimal. Uses Jelly code page.

ṢIṢ1ị

Try it online! (with the code points of the source code)

Commented

ṢIṢ1ị  - a monadic link taking a list, e.g. [183, 73, 49, 216]
Ṣ      - sort in ascending order -> [49, 73, 183, 216]
 I     - get increments -> [24, 110, 33]
  Ṣ    - sort in ascending order -> [24, 33, 110]
   1ị  - extract the first element -> 24
\$\endgroup\$
4
\$\begingroup\$

MathGolf, score = 35

ê│╓

Try it online!

Uses MathGolf's codepage along with this simple Python script.

ê    Take user input as array of integers
 │   Take differences
  ╓  Find minimum
\$\endgroup\$
3
\$\begingroup\$

Gaia, 3 bytes, score = 36

ȯọ⌋

Try it online!

Uses the Gaia codepage. ȯọ are 36 apart.

\$\endgroup\$
3
\$\begingroup\$

Jelly, score 53

’ÞIṂ

Try it online!

The code page is here. The code points are 253 20 73 179 which has minimal difference of 73-20=53 as may be seen in this self-evaluation.

How?

      ’ÞIṂ - Link: list of numbers, L     e.g. [253, 20, 73, 179]
 20:   Þ   - sort L by:
253:  ’    -   decrement                       [20, 73, 179, 253]
 73:    I  - incremental differences           [53, 106, 74]
179:     Ṃ - minimum                           53
\$\endgroup\$
  • \$\begingroup\$ Why does the Jelly wiki say that Þ is outer product/table and you say it's sort by? \$\endgroup\$ – Neil Dec 9 '19 at 22:49
  • \$\begingroup\$ Because there are two thorns in the code-page: 20 (Þ) = sort by key function; and 31 (þ) = outer product. \$\endgroup\$ – Jonathan Allan Dec 9 '19 at 22:55
  • \$\begingroup\$ Ah, sorry, I didn't realise that my search was case insensitive... \$\endgroup\$ – Neil Dec 10 '19 at 1:18
2
\$\begingroup\$

Japt -g, 6 bytes, score: 43

n¹än¹n

Try it (includes codepoints test case)

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

Jelly, 12 bytes, score = 35

ạ€`«/Ƈ€«/€«/

Try it online!

A monadic link taking a list of (optionally distinct) integers as its argument and returning the smallest gap. Generates an outer table of absolute differences between the inputs, filters out zero differences, finds the smallest in each row and then the smallest of those values. TIO link has a footer to translate the code into numeric codepoints within Jelly codepage (technically each is +1, but there is no effect on differences between pairs).

Pairwise differences shown here

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

Runic Enchantments, Score 1 (79 bytes)

D?)0]li[0y̤<<<<<<<<
Ro"/{~D-{:ii"6Xkq";$~\"akq"/~{R{0[il]0)?/:}S-:}}:{)?"E͍$;

Try it online!

(Note that due to the way input is coerced to the most appropriate type and we want decimal value 49 not decimal value 1 for such bytes; this applies to the newline, 0, 6 (etc), as well as the injection of all the spaces).

There's a few reasons I can't score higher. In decreasing order of troublesomeness.

  1. @ and ? are adjacent (? is required for conditionals, @ is one of two terminators)
  2. : and ; are adjacent (: is required to duplicate the top of the stack for non-destructive comparisons, ; is the other terminator)
  3. < and ; are adjacent
  4. > and ? are adjacent (using other entry points possible, but we're already score-limited, v is best option as ^ and ] are adjacent)
  5. D and E are adjacent (replacing D with / or \ or not using Eval possible)
  6. l and k are adjacent (l is required to read all input, k is required to inject a newline and entry point into the evaluated code; Eval not strictly needed)
  7. } and ~ are adjacent (pop-discarding an arbitrary value without corrupting the stack is difficult otherwise, [] does work, but limits score to 2, assuming we could overcome the other points, 0*+ also works, but + and * are adjacent)
  8. o and q limit score to 2
  9. [ and ] limit score to 2 (but not strictly necessary, just simplifies the input reading process, but lril1- is still score limited to 3 on its own plus r and q are adjacent as well as 0 and 1)
  10. l and o limit score to 3
  11. pre-processing the code and injecting troublesome bytes with reflection necessitates a minimum of 2 of 1234567890, all of which are going to cause low score limits.
\$\endgroup\$
2
\$\begingroup\$

MATL, Score 16

SdS9z)

Try it online!

For anything up to SdS) I could get a score of 17, but generating a 1 for indexing (because X< is too close to S) bumped the score down to 16.

Let's see if any ASCII-based language beats this...

\$\endgroup\$
  • \$\begingroup\$ @Giuseppe Oh I didn't notice the input is a set, not a list. That'll probably help a lot. \$\endgroup\$ – Sanchises Dec 10 '19 at 17:37
2
\$\begingroup\$

R, 47 bytes, score = 2

`-`=`mi\x6E`;`~`=diff;`?`=`s\x63\x61\x6E`;-~?""

Try it online!


The input is assumed to be unique and sorted ascending.

Verify the score here

\$\endgroup\$
  • \$\begingroup\$ Well done for the first answer with score >1 in a verbose language! \$\endgroup\$ – Robin Ryder Dec 20 '19 at 13:14
0
\$\begingroup\$

C++, score : 1, bytes : 132

#include <cmath>
int f(int* a,int c){int m=abs(a[0]-a[1]),i,j,d;for(i=-1;++i<c;)for(j=i;++j<c;)m=(d=abs(a[i]-a[j]))<m?d:m;return m;}

The very need of the abs function kills my score, and any other C++ answer's.
It's actually return.

Try it online!

\$\endgroup\$
  • 1
    \$\begingroup\$ () being 1 apart also kills any C++ answers (in fact, very many practical languages will have a score of 1 due to this). \$\endgroup\$ – 79037662 Dec 11 '19 at 15:23
  • \$\begingroup\$ @79037662 Aww man \$\endgroup\$ – Varad Mahashabde Dec 11 '19 at 19:36
  • \$\begingroup\$ @VaradMahashabde I'm sorry - I was commenting on the other person's comment. I wasn't making a suggestion to you. I didn't mean to cause any confusion. I've deleted my comment so that I don't confuse anyone else. \$\endgroup\$ – Jerry Jeremiah Dec 19 '19 at 20:41
  • \$\begingroup\$ But return is usually unnecessary, as gcc produces a warning and then effectively returns the variable that was mentioned the last, and seems to return m here. \$\endgroup\$ – my pronoun is monicareinstate Dec 20 '19 at 13:53
  • \$\begingroup\$ @mypronounismonicareinstate It would matter if this was code golf, but as @79037662 said, () kills any dreams right away. Also that is UB AF, and I don't like it when there is even a remote chance of a kitten beam being shot into space or a space beam being shot into a kitten :-) \$\endgroup\$ – Varad Mahashabde Dec 21 '19 at 18:02

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.