28
\$\begingroup\$

Your input is a list/sequence/vector/array of 5-255 positive integers, not necessarily unique. You may assume whatever input format is most suitable, and that each integer (as well as the quantity of integers) is chosen uniformly at random from the range 5-255.

The goal is to output the same list, in the same (or equivalent) format, but sorted into increasing (nondecreasing) order. A common early exercise in learning a language. Submissions to include:

  1. An answer which works correctly and achieves the goal; and

  2. A second answer which contains an annoying bug. Between 1% and 10% of the time, the output needs to be a list in the correct format and containing the correct elements, but in the wrong order (any order except correctly sorted). The rest of the time, the program must work correctly and achieve the goal.

The two answers must have Levenshtein distance one; that is, we can get one from the other by deleting one byte, or adding one byte, or changing one byte.

Scoring as usual in code-golf (based on the shorter of your two answers), with usual loopholes forbidden.

10% bonus (decrease to score) if the annoying bug is input-independent, i.e. using the same input again doesn't reproduce the bug (except between 1% and 10% of the time).

\$\endgroup\$
  • 9
    \$\begingroup\$ Welcome to PPCG! I suggest removing the bonus, it’s not really good practice. \$\endgroup\$ – Mr. Xcoder Nov 4 '17 at 5:50
  • 2
    \$\begingroup\$ It's unclear what is the probability of each possible input length. \$\endgroup\$ – user202729 Nov 4 '17 at 7:32
  • 12
    \$\begingroup\$ Should the spec between 1% and 10% of the time be fulfilled for each input or just overall for the set of possible inputs? For some inputs like [5,5,5] it's impossible to produce the wrong order \$\endgroup\$ – Luis Mendo Nov 4 '17 at 11:19
  • 4
    \$\begingroup\$ There's a subtlety regarding our default IO formats. If our code defines a function, is it OK if it has some chance of defining the function consistently buggy, as opposed to defining a function that has some chance of being buggy? \$\endgroup\$ – xnor Nov 4 '17 at 12:08
  • 1
    \$\begingroup\$ @VadimPonomarenko On this site people are allowed to provide functions as well as full programs. xnor is asking whether it is allowed to have a function that, 1% to 10% of the time when created, is a buggy function that will always have a bug. Keeping to the letter of your question the answer's probably no, but it would be more fun if it was yes. \$\endgroup\$ – wizzwizz4 Nov 4 '17 at 15:05

23 Answers 23

9
\$\begingroup\$

Python 3, 36 bytes

Bug-free version, 37 bytes

lambda l:sorted(l,reverse=l[-9:]==[])

Try it online!

Annoying version, 36 bytes

lambda l:sorted(l,reverse=l[9:]==[])

Try it online!

This depends on the input and therefore does not qualify for the bonus.
It has a probability of around 2% to fail. It fails when the input length is lower then 10.

Combined with LyricLy's answer this gets 34 bytes:

lambda l:sorted(l)[::l[9:]>[]or 1]
lambda l:sorted(l)[::l[9:]>[]or-1]
\$\endgroup\$
  • \$\begingroup\$ I don't think you need the space in the bug-free version. \$\endgroup\$ – wizzwizz4 Nov 4 '17 at 15:07
  • \$\begingroup\$ @wizzwizz4 without the space or1 will get interpreted as an variable name and raises a syntax error. \$\endgroup\$ – ovs Nov 4 '17 at 15:13
9
\$\begingroup\$

05AB1E, 5*0.9 = 4.5 bytes

Working solution

{TLΩi

Try it online!

Explanation

{      # sort input
 TL    # push the range [1 ... 10]
   Ω   # pick a random number in the range
    i  # if true (equal to 1), do nothing

Solution containing the bug

Gives the wrong solution 10% of the time (independent on input).

{TLΩiR

Try it online!

Explanation

Same as the working solution, except it reverses the list if the number picked is true.

\$\endgroup\$
  • \$\begingroup\$ Seriously what the hey. Output isn't even of the right cardinality. \$\endgroup\$ – Joshua Nov 5 '17 at 3:40
  • \$\begingroup\$ @Joshua What do you mean? \$\endgroup\$ – Erik the Outgolfer Nov 5 '17 at 8:16
  • \$\begingroup\$ Try it online shows it outputting a list of lists. \$\endgroup\$ – Joshua Nov 5 '17 at 14:41
  • 4
    \$\begingroup\$ @Joshua The TiO link includes a header 100F and a footer }, that help us visualize the result of the function called on the input multiple times. This shows us that the working solution always returns correct results, whilst the bugged one has flawed output . \$\endgroup\$ – Mr. Xcoder Nov 5 '17 at 15:04
  • \$\begingroup\$ Please, someone, explain the algorithm. Soon I will accept the top-ranked submission (or one of the top-ranked submissions). I can't accept any solution which I can't understand. \$\endgroup\$ – Vadim Ponomarenko Nov 7 '17 at 15:20
7
\$\begingroup\$

Jelly, 7 * (100% - 10%) = 6.3 bytes

Ṣ¹⁵X:¤¡

Try it online!

Buggy version:

ṢẊ⁵X:¤¡

Try it online!

In both links, there's a test harness that will run the code 100 times, each time with the list you give as the argument, and then return the results.

The probability of each input length is:

0.1 - 0.1/(length!)

So for length 1 there's a 0% probability, for length 2 5%, for length 3 8.83̅%, for length 4 9.583̅% etc. until length ∞ which has a 10% probability.

\$\endgroup\$
  • \$\begingroup\$ Should be 0.1 - 0.1/(length!). \$\endgroup\$ – user202729 Nov 4 '17 at 9:23
  • \$\begingroup\$ @user202729 sure \$\endgroup\$ – Erik the Outgolfer Nov 4 '17 at 9:26
  • \$\begingroup\$ Ṣ⁵X’¤¡ and Ṣ⁵X¤¡ should works too: buggy version return the list unsorted <10% of the time, and given that the input is chosen uniformly random, it should work, save 2 bytes. \$\endgroup\$ – user202729 Nov 4 '17 at 9:28
  • \$\begingroup\$ If you don't like that solution you can obviously just delete the ¹ to save 1 byte (the rule count number of byte = the shorter one) ; also there is an extraneous combining overline after the second 6 in 6.6̅%. \$\endgroup\$ – user202729 Nov 4 '17 at 9:29
  • \$\begingroup\$ @user202729 Unfortunately then it won't be input-independent anymore, and no I can't "just remove the ¹" because then it wouldn't sort at all 10% of the time. \$\endgroup\$ – Erik the Outgolfer Nov 4 '17 at 9:34
6
\$\begingroup\$

Python 3, score 58 57 - 10% = 51.3

Saved a byte thanks to ovs.

Bug-free version, 57 bytes

lambda m:sorted(m)[::random()>.1or 1]
from random import*

Try it online!

Bugged version, 57 bytes

lambda m:sorted(m)[::random()>.1or-1]
from random import*

Try it online!

I decided to try a solution that uses the bonus. It doesn't beat the other Python answer, but I had fun thinking it up.

\$\endgroup\$
5
\$\begingroup\$

C, 71*0.9 = 63.9 bytes

Bug-free:

c(int*a,int*b){return*a-*b;}f(a,n)int*a;{if(rand()%1<9)qsort(a,n,4,c);}

Try it online!

Buggy:

c(int*a,int*b){return*a-*b;}f(a,n)int*a;{if(rand()%10<9)qsort(a,n,4,c);}

Try it online!

\$\endgroup\$
  • \$\begingroup\$ +1 for %1 (oh come on 6 more to go you gotta be kidding me) \$\endgroup\$ – Joshua Nov 5 '17 at 3:42
4
\$\begingroup\$

Groovy, 31 bytes

Bugged solution:

{a->a.sort()[a[9]?0..-1:-1..0]}

Working solution:

{a->a.sort()[a[0]?0..-1:-1..0]}

The Groovy subscript operator (the getAt method) returns null for lists if the index is bigger than the size. So if there's a ninth element it'll stay the same as the sorted list, but if not (1.99203187% chance) it'll be reversed. However there will always be a first element because the list's size is always bigger than or equal to 5. So the 0 in a[0] could be swapped with 1, 2, 3 or 4.

\$\endgroup\$
  • 1
    \$\begingroup\$ Welcome to the site and nice first post! \$\endgroup\$ – caird coinheringaahing Nov 5 '17 at 15:08
3
\$\begingroup\$

Wolfram Language (Mathematica), 29 bytes

This is 26.1 bytes with the bonus, but I'm not entirely sure I earn the bonus; on already-sorted input, both versions always produce sorted output.

Bug-free version (29 bytes)

If[RandomReal[]<0.,#,Sort@#]&

Try it online!

Annoying version (30 bytes)

If[RandomReal[]<0.1,#,Sort@#]&

Try it online!

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

PHP, 70 bytes

Bug-free version, 70 bytes

<?unset($argv[0]);((rand(1,9)?"":r).sort)($argv);echo join(" ",$argv);

Try it online!

Bugged version, 70 bytes

<?unset($argv[0]);((rand(0,9)?"":r).sort)($argv);echo join(" ",$argv);

Try it online!

The bugged version sorts in reverse order 10% of the time (based on a random number generator).

\$\endgroup\$
  • \$\begingroup\$ no need for the tag with -r (-2 bytes). join by underscore; that should be equivalent (-2 bytes). use asort instead of sort (-1 byte). \$\endgroup\$ – Titus Nov 4 '17 at 10:30
  • \$\begingroup\$ ... or use the whole word instead of prefix (or not): unset($argv[0]);(rand(1,9)?sort:rsort)($argv);echo join(_,$argv); (also 65 bytes) \$\endgroup\$ – Titus Nov 4 '17 at 16:13
3
\$\begingroup\$

Python 2, 26 bytes

Buggy:

lambda l:l[9:]and l.sort()

Try it online!

Outputs by modifying the input list. Sorts the list only if its length is at least 10. The non-buggy version replaces the 9 with a 0 to always sort.

Working:

lambda l:l[0:]and l.sort()

Try it online!

We can modify the function to return the list at the cost of 4 bytes, for 30 bytes total:

lambda l:l[9:]and l.sort()or l

Try it online!


25 bytes with some stretches of the rules:

[list,sorted][id(0)%17>0]

Try it online!

Outputs a function literal that either sorts or is the identity, using id(0) as a random source. Change > to >= to fix, or 0 to ~0.

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

Husk, 6 bytes

Buggy version:

?OIV¦9

Try it online!

Correct version:

?OIVK9

Try it online!

Explanation

These programs are completely deterministic. In fact, Husk has currently no support at all for random numbers.

?  V    If any element
    ¦9  is divisible by 9 (in buggy version),
    K9  is truthy when replaced by 9 (in correct version),
 O      sort the list,
  I     otherwise return it unchanged.

I claim that the output of the buggy program is not sorted with a probability between 1% and 2%. Denote by N = 251 the number of possible values of the elements. The probability that a random list of length L contains no multiples of 9 is ((N-K)/N)^L, where K is the number of values divisible by 9 (in our case K = 28). The total probability is the average of this for 5 ≤ L ≤ 255, which is about 1.98%. Some of these lists are false positives, since they are already sorted. The probability of a random list of length L to be sorted is at most ((N+N*(N-1)/2)/N^2)^⌊L/2⌋: if we break the list into chunks of length 2, each of the ⌊L/2⌋ chunks must be sorted. The total probability of a list being sorted is bounded by the average of the above for 5 ≤ L ≤ 255, which is about 0.30%. Thus the probability of the function returning a non-sorted list is between 1.67% and 1.98%.

\$\endgroup\$
  • \$\begingroup\$ divisible by 9 gives approx 11% chance of failure. and not sorting doesn´t guarantee that the list is unsorted. \$\endgroup\$ – Titus Nov 4 '17 at 17:18
  • 1
    \$\begingroup\$ @Titus I address this in the analysis. Failure to sort occurs only if the list contains no elements that are divisible by 9. The probability of this is about 1.98%. And it's true that if the list is already sorted, doing nothing will also give a sorted list. However, the probability of the list being already sorted is at most 0.30%, which is low enough that the total probability of outputting an unsorted list is above 1%. \$\endgroup\$ – Zgarb Nov 4 '17 at 17:23
  • \$\begingroup\$ true ... and the input being sorted doesn´t change the bug. \$\endgroup\$ – Titus Nov 4 '17 at 18:27
  • \$\begingroup\$ Could you maybe use ↓9 instead of V¦9, and shorten it to just 9 for the correct version? This would make it always fail on short inputs and always work correcly on longer ones, but since the input length follows a random distribution it should still be a valid answer \$\endgroup\$ – Leo Nov 6 '17 at 2:59
3
\$\begingroup\$

Bash, 26 bytes

Correct version

s=n
sort -${s:RANDOM%20<0}

Try it online! or check the probabilities.

Bugged version

s=n
sort -${s:RANDOM%20<1}

Try it online! or check the probabilities.

Takes input as newline-separated numbers. Uses the builtin variable RANDOM, which always returns a (pseudo)random number in the range 0 - 32767. Using %20 results in about a 5% failure rate (thanks @Titus for clarifying issues with %10).

This randomness means the failure rate is independent of the input, but this does require that the input array includes at least one number with more than one digit, because the failure output is sorted lexicographically.

Alternate version, 27 bytes

((RANDOM+20))||cat&&sort -n

Bugged version replaces the + with a %. Try it online or try it bugged.

\$\endgroup\$
  • \$\begingroup\$ penny picking: %10 has a higher chance of returning 0 to 7 than 8 or 9, so the chance for failure is above 10% ;) \$\endgroup\$ – Titus Nov 4 '17 at 17:17
  • \$\begingroup\$ @Titus Thanks, I forgot about that fact. Updated to use %20 like your answer does. \$\endgroup\$ – Justin Mariner Nov 4 '17 at 17:34
3
\$\begingroup\$

Pyth, score 8 * 0.9 = 7.2

First snippet (correct one):

h.uSNT.S

Try it here!

Second snippet (bugged one):

O.uSNT.S

Try it here!

Saved two bytes (and 1.8 score) thanks to isaacg!

\$\endgroup\$
  • \$\begingroup\$ I think 9 rather than 10 new copies would be fine. The possibility of .S returning the input unchanged means that in those (rare) cases, our chances of getting the wrong answer drop from 10% to 0% - so on average, it's still in the right range. Of course, 10 copies are fine too. \$\endgroup\$ – Misha Lavrov Nov 4 '17 at 6:32
  • \$\begingroup\$ @MishaLavrov I have made a mistake in my explanation, now addressed. I said .S might also return the input itself (which wouldn't be a problem), but I meant .S might also return the sorted list. \$\endgroup\$ – Mr. Xcoder Nov 4 '17 at 6:37
  • \$\begingroup\$ Right, that's what I meant too. \$\endgroup\$ – Misha Lavrov Nov 4 '17 at 6:37
  • \$\begingroup\$ Same idea, but shorter: O.uSNT.S \$\endgroup\$ – isaacg Nov 4 '17 at 23:18
2
\$\begingroup\$

JavaScript (ES6), 24 bytes

Bug-free version (at least for integers in the range 0-2147483647, so anything in the given range):

a=>a.sort((a,b)=>a-b>>0)

Buggy version:

a=>a.sort((a,b)=>a-b>>1)

Depends on a) the engine's sorting algorithm and b) the input list containing two values in the wrong order that differ by 1. (If the probability of that turns out to be too low then the 1 can be increased, but by the time you get to 8 it simply won't sort anything in the range 5-255.)

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

PHP, 62 bytes

inspired by Jo´s solution (and I just noticed: it´s a port of Justin Mariner´s):

working (sorts ascending):

unset($argv[0]);(r[rand()+20].sort)($argv);echo join(_,$argv);

buggy (approx. 5% chance of descending sort):

unset($argv[0]);(r[rand()%20].sort)($argv);echo join(_,$argv);

Run with -nr

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

Pushy, 9 bytes - 10% = 8.1

Bugged Solution:

g0TUn?};_

Try it online!

Working Solution:

g1TUn?};_

Try it online!

The bugged code does the following:

g0TUn?};_

g          \ Sort the stack correctly
 0TU       \ Generate random(0, 10)
    n? ;   \ If this is zero:
      }    \    Cyclically shift the stack right once
        _  \ Print the result

The fixed code simply changes 0 to 1. As random(1, 10) will never be 0, the if statement will never be executed.

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

MATL, 7*0.9 = 6.3 6*0.9 = 5.4 bytes

Buggy version:

Gr.9<?S

Try it online!

Explanation:

G        % Grab input
 r       % Push a random number between 0 and 1
  .9     % Push 0.9
    <    % Check if the random number is smaller than 0.9
     ?   % If true
      S  % Sort input
         % Implicit output

Bug-free version:

Gr9<?S

Try it online!

Explanation:

G       % Grab input
 r      % Push a random number between 0 and 1
  9     % Push 9
   <    % Check if the random number is smaller than 9 (always true)
    ?   % If true
     S  % Sort the input
        % Implicit output     
\$\endgroup\$
1
\$\begingroup\$

Jq 1.5, 42 bytes

Buggy

sort|if length%13<=0then reverse else. end

Working (delete the =)

sort|if length%13<0then reverse else. end

Assuming line lengths are uniform in range [5,255] about 7% will trigger the bug

Try it online!

\$\endgroup\$
1
\$\begingroup\$

J, 22.5 bytes (25 bytes - 10%)

with bug:

[:]`(1&A.)@.(0.1>?@0:)/:~

without bug:

[:]`(0&A.)@.(0.1>?@0:)/:~

Try it online!

\$\endgroup\$
1
\$\begingroup\$

R, 30*.9 = 27 bytes

(buggy)

function(l)sort(l,runif(1)<.1)

Try it online!

(not buggy)

function(l)sort(l,runif(1)<.0)

The buggy version sorts in decreasing=T 10% of the time, sampling from a uniform(0,1) distribution. The un-buggy version is always decreasing=F

\$\endgroup\$
1
\$\begingroup\$

Röda, 42 bytes - 10% = 37.8

Bug-free:

{sort key={|i|currentTime|[_%20//19*0+i]}}

Buggy:

{sort key={|i|currentTime|[_%20//19*i+i]}}

Try it online!

This uses the currentTime function to create random numbers. It seems that their distribution varies a little between machines. The ratio 20//19 can be adjusted to get different results for no byte penalty (unless it is smaller than 99//98).

\$\endgroup\$
1
\$\begingroup\$

Octave, 36*0.9 = 32.4 bytes

Buggy version:

@(x)sort(x)(shift(1:end,+(rand<.1)))

Try it online!

Bug-free version:

@(x)sort(x)(shift(1:end,+(rand<.0)))

Try it online!

This sorts the vector, then shifts all numbers one to the right if a random number is less than 0.1.

\$\endgroup\$
  • \$\begingroup\$ Yes, you're of course right :) Thanks :) \$\endgroup\$ – Stewie Griffin Nov 7 '17 at 14:42
1
\$\begingroup\$

Java 8, 45 34.2 (50 38 - 10%) bytes

Normal version:

a->{if(Math.random()>0.)a.sort(null);}

Explanation:

Try it here.

a->{                    // Method with ArrayList<Integer> parameter and no return-type
  if(Math.random()>0.)  //  If the random 0-1 double is larger than 0:
    a.sort(null);       //   Sort the input-List
}                       // End of method

Bugged version (51 39 bytes):

a->{if(Math.random()>0.1)a.sort(null);}

LD of 1: 1 added.

Explanation:

Try it here.

a->{                     // Method with ArrayList<Integer> parameter and no return-type
  if(Math.random()>0.1)  //  If the random 0-1 double is larger than 0.1:
    a.sort(null);        //   Sort the input-List
}                        // End of method
\$\endgroup\$
0
\$\begingroup\$

JavaScript, 25*0.9=22.5

new Date%25?x:x.sort()

input x

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