35
\$\begingroup\$

About the Series

I will be running a little series of code-golf challenges revolving around the theme of randomness. This will basically be a 9-Hole Golf Course, but spread out over several questions. You may participate in any challenge individually as if it was a normal question.

However, I will maintain a leaderboard across all challenges. The series will run over 9 challenges (for now), one posted every few days. Every user who participates in all 9 challenges is eligible for winning the entire series. Their overall score is the sum of their shortest submissions on each challenge (so if you answer a challenge twice, only the better answer one is counted towards the score). If anyone holds the top spot on this overall leaderboard for 28 days I will award them a bounty of 500 rep.

Although I have a bunch of ideas lined up for the series, the future challenges are not set in stone yet. If you have any suggestions, please let me know on the relevant sandbox post.

Hole 1: Shuffle an Array

The first task is pretty simple: given a non-empty array of integers, shuffle it randomly. There are a few rules though:

  • Every possible permutation must be returned with the same probability (so the shuffle should have a uniform distribution). You can check if your algorithm is uniform/unbiased by implementing it in JavaScript on Will it Shuffle, which will produce a matrix of the biases - the result should look as uniform as their built-ins Fisher-Yates or sort (random order).
  • You must not use any built-in or 3rd-party method to shuffle the array or generate a random permutation (or enumerate all permutations). In particular, the only built-in random function you may use is getting a single random number at a time. You may assume that any built-in random number method runs in O(1) and is perfectly uniform over the requested interval (in a mathematical sense - you may ignore details of floating-point representation here). If your language lets you obtain a list of m random numbers at once, you may use this facility, provided the m numbers are independent of each other, and you count it as O(m).
  • Your implementation must not exceed a time complexity of O(N), where N is the size of the array to be shuffled. For instance, you cannot "sort by random numbers".
  • You may either shuffle the array in place, or create a new array (in which case the old array may be modified however you like).

You may write a full program or a function and take input via STDIN, command-line argument, function argument or prompt and produce output via return value or by printing to STDOUT (or closest alternative). If you write a function that shuffles the array in place, you don't need to return it of course (provided your language lets you access the modified array after the function returns).

Input and output may be in any convenient list or string format, but must support arbitrary integers in the range -231 ≤ x < 231. In principle, your code should work for arrays up to length 231, although this doesn't necessarily have to fit in your memory or complete within a reasonable amount of time. (I just don't want to see arbitrary size limits to hardcode loops or something.)

This is code golf, so the shortest submission (in bytes) wins.

Leaderboard

The following snippet will generate a leaderboard across all challenges of the series.

To make sure that your answers show up, please start every answer with a headline, using the following Markdown template:

# Language Name, N bytes

where N is the size of your submission. If you improve your score, you can keep old scores in the headline, by striking them through. For instance:

# Ruby, <s>104</s> <s>101</s> 96 bytes

(The language is not currently shown, but the snippet does require and parse it, and I may add a by-language leaderboard in the future.)

/* Configuration */

var QUESTION_IDs = [45302, 45447, 46991, 49394, 51222, 66319, 89621, 120472]; // Obtain this from the url
// It will be like http://XYZ.stackexchange.com/questions/QUESTION_ID/... on any question page
var ANSWER_FILTER = "!.FjwQBrX2KXuFkv6p2lChi_RjzM19";

/* App */

var answers = [], page = 1, currentQ = -1;

function answersUrl(index) {
  return "https://api.stackexchange.com/2.2/questions/" +  QUESTION_IDs.join(";") + "/answers?page=" + index + "&pagesize=100&order=desc&sort=creation&site=codegolf&filter=" + ANSWER_FILTER;
}


function getAnswers() {
  $.ajax({
    url: answersUrl(page++),
    method: "get",
    dataType: "jsonp",
    crossDomain: true,
    success: function (data) {
      answers.push.apply(answers, data.items);
      if (data.has_more) getAnswers();
      else process();
    }
  });
}

getAnswers();

var SIZE_REG = /\d+(?=[^\d&]*(?:&lt;(?:s&gt;((?!&gt;).)*&lt;\/s&gt;|((?!&gt;).)+&gt;)[^\d&]*)*$)/;
var NUMBER_REG = /\d+/;
var LANGUAGE_REG = /^#*\s*([^\n,]+)(?=,)/;//

function shouldHaveHeading(a) {
  var pass = false;
  var lines = a.body_markdown.split("\n");
  try {
    pass |= /^#/.test(a.body_markdown);
    pass |= ["-", "="]
              .indexOf(lines[1][0]) > -1;
    pass &= LANGUAGE_REG.test(a.body_markdown);
  } catch (ex) {}
  return pass;
}

function shouldHaveScore(a) {
  var pass = false;
  try {
    pass |= SIZE_REG.test(a.body_markdown.split("\n")[0]);
  } catch (ex) {}
  if (!pass) console.log(a);
  return pass;
}

function getAuthorName(a) {
  return a.owner.display_name;
}

function getAuthorId(a) {
  return a.owner.user_id;
}

function process() {
  answers = answers.filter(shouldHaveScore)
                   .filter(shouldHaveHeading);
  answers.sort(function (a, b) {
    var aB = +(a.body_markdown.split("\n")[0].match(SIZE_REG) || [Infinity])[0],
        bB = +(b.body_markdown.split("\n")[0].match(SIZE_REG) || [Infinity])[0];
    return aB - bB
  });

  var users = {};
  answers.forEach(function (a) {
    var headline = a.body_markdown.split("\n")[0];
    var question = QUESTION_IDs.indexOf(a.question_id);
    var size = parseInt((headline.match(SIZE_REG)||[0])[0]);
    var language = headline.match(LANGUAGE_REG)[1];
    var user = getAuthorName(a);
    var userId = getAuthorId(a);
    if (!users[userId]) users[userId] = {name: user, nAnswer: 0, answers: []};
    if (!users[userId].answers[question]) {
      users[userId].answers[question] = {size: Infinity};
      users[userId].nAnswer++;
    }
    if (users[userId].answers[question].size > size) {
      users[userId].answers[question] = {size: size, link: a.share_link}
    }
  });
  
  
  var sortedUsers = [];
  for (var userId in users)
    if (users.hasOwnProperty(userId)) {
      var user = users[userId];
      user.score = 0;
      user.completedAll = true;
      for (var i = 0; i < QUESTION_IDs.length; ++i) {
        if (user.answers[i])
          user.score += user.answers[i].size;
        else
          user.completedAll = false;
      }
      sortedUsers.push(user);
    }  
  
  sortedUsers.sort(function (a, b) {
    if (a.nAnswer > b.nAnswer) return -1;
    if (b.nAnswer > a.nAnswer) return 1;
    return a.score - b.score;
  });
  
  var place = 1;
  for (var i = 0; i < sortedUsers.length; ++i) {
    var user = sortedUsers[i];
    var row = '<tr><td>'+ place++ +'.</td><td>'+user.name+'</td>';
    for (var j = 0; j < QUESTION_IDs.length; ++j) {
      var answer = user.answers[j];
      if (answer)
        row += '<td><a href="'+answer.link+'">'+answer.size+'</a></td>';
      else
        row += '<td class="missing"></td>';
    }
    row += '<td></td>';
    if (user.completedAll)
      row += '<td class="total">'+user.score+'</td>';
    else
      row += '<td class="total missing">'+user.score+'</td>';
    row += '</tr>';
    $("#users").append(row);
  }
}
body { text-align: left !important}

#leaderboard {
  width: 500px; 
}

#answer-list {
  padding: 10px;
  width: 290px;
  float: left;
}

#language-list {
  padding: 10px;
  width: 290px;
  float: left;
}

table thead {
  font-weight: bold;
}

table td {
  padding: 5px;
}

td.total {
  font-weight: bold;
  text-align: right;
}

td.missing {
  background: #bbbbbb;
}
<script src="https://ajax.googleapis.com/ajax/libs/jquery/2.1.1/jquery.min.js"></script>
<link rel="stylesheet" type="text/css" href="//cdn.sstatic.net/codegolf/all.css?v=83c949450c8b">
<div id="leaderboard">
  <h2>Leaderboard</h2>
  <p>
    Missing scores are shown as grey cells. A grey total indicates that the user has not participated in all challenges and is not eligible for the overall victory yet.
  </p>
  <table class="_user-list">
    <thead>
      <tr><td></td><td>User</td>
        <td><a href="https://codegolf.stackexchange.com/q/45302/8478">#1</a></td>
        <td><a href="https://codegolf.stackexchange.com/q/45447/8478">#2</a></td>
        <td><a href="https://codegolf.stackexchange.com/q/46991/8478">#3</a></td>
        <td><a href="https://codegolf.stackexchange.com/q/49394/8478">#4</a></td>
        <td><a href="https://codegolf.stackexchange.com/q/51222/8478">#5</a></td>
        <td><a href="https://codegolf.stackexchange.com/q/66319/8478">#6</a></td>
        <td><a href="https://codegolf.stackexchange.com/q/89621/8478">#7</a></td>
        <td><a href="https://codegolf.stackexchange.com/q/120472/8478">#8</a></td>
        <td></td><td>Total</td>
      </tr>
    </thead>
    <tbody id="users">

    </tbody>
  </table>
</div>
<table style="display: none">
  <tbody id="answer-template">
    <tr><td>{{NAME}}</td><td>{{LANGUAGE}}</td><td>{{SIZE}}</td><td><a href="{{LINK}}">Link</a></td></tr>
  </tbody>
</table>
<table style="display: none">
  <tbody id="language-template">
    <tr><td>{{LANGUAGE}}</td><td>{{NAME}}</td><td>{{SIZE}}</td><td><a href="{{LINK}}">Link</a></td></tr>
  </tbody>
</table>

\$\endgroup\$
  • 7
    \$\begingroup\$ I am disappointed that we are not allowed to be "clever" and use library functions other than "get a random number". Do we want to look at yet another 69 implementations of Fisher-Yates shuffling? Please consider removing this rule in future tasks. Also, why a limit on time complexity? Please consider relaxing it to at least O(n^2); I also think someone might find an especially golfed implementation if you allow O(n!). \$\endgroup\$ – anatolyg Feb 3 '15 at 20:58
  • 7
    \$\begingroup\$ @anatolyg Removing the restrictions amounts to every answer being either sortby(random) (the reason for the time restriction) or simply .shuffle() (the reason for the built-ins restriction), which I think is a lot less clever than having to implement Fisher-Yates or some other approach. \$\endgroup\$ – Martin Ender Feb 3 '15 at 21:03
  • 1
    \$\begingroup\$ If shuffling in place, does a function have to return the array, or is it enough that it is modified? Can I write a function for shuffle(array) instead of newArray=shuffle(array)? \$\endgroup\$ – Geobits Feb 4 '15 at 2:30
  • 1
    \$\begingroup\$ @Bakuriu Claiming that you can sort in linear time if the numbers are fixed is a bit like claiming you can do anything in O(1) if the input sizes are fixed. Also the relevant restriction is fixed-size arrays, not fixed-size integers - because the array size determines how large you need your random numbers to be. Anyway, the limitation on time complexity are of course for the general algorithm you implement, whereas the limits on input sizes are in place so you don't have to use arbitrary-precision integers if your language doesn't use them out of the box. \$\endgroup\$ – Martin Ender Feb 4 '15 at 9:48
  • 2
    \$\begingroup\$ Why is Adám's solution coming up as 43319 bytes when it's actually 14? \$\endgroup\$ – boboquack May 14 '17 at 0:10

35 Answers 35

1
2
1
\$\begingroup\$

PowerShell, 39 27 bytes

-4 bytes thanks to @mazzy

$args-split','|sort{random}

Accepts input as commandline arguments, and outputs as an array.

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

Jolf, 46 bytes

Invalid, since language postdates question. Is otherwise a perfectly valid answer. Try it ici!

v'nlKW«n)v'HC*mrhntv'S.Kn$K[n]=K[H];K[H]=S$}K

Explanation

v'nlKW«n)v'HC*mrhntv'S.Kn$K[n]=K[H];K[H]=S$}K
                                              implicit: K = input array
v'n                                           set n to
   lK                                           the length of K
     W«n)                                     while(--n){
         v'H                                    set H to
            C     t                               the integer part of
             *mr                                  Math.random() times
                hn                                  n+1
                   v'S                          set S to
                      .Kn                         the nth member of K
                         $K[n]=K[H];K[H]=S$     eval as javascript (perform swap)
                                           }  }
                                            K K
                                              implicit: print K

This runs in O(n) time, I believe, as n is strictly decreasing.

I used this as the basis for the code

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

Julia 0.6, 56 bytes

!a=for i=length(a):-1:1;j=rand(1:i);a[[i,j]]=a[[j,i]]end

Try it online!

Fisher-Yates.

a[[i,j]]=a[[j,i]] is slightly shorter than a[i],a[j]=a[j],a[i].

rand(1:i) samples from the range 1:i.

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

SmileBASIC, 56 bytes

Fisher-Yates algorithm of course.

DEF S A
FOR I=1-LEN(A)TO-1SWAP A[-I],A[RND(1-I)]NEXT
END

Downwards FOR loops are expensive (STEP -1), so instead you can just negate the start/end values, which only adds 1 extra character. This is the code if FOR implicitly went backwards when the end value is lower than the start:

DEF S A
FOR I=LEN(A)-1TO 1SWAP A[I],A[RND(I+1)]NEXT '1 character less
END
\$\endgroup\$
-1
\$\begingroup\$

VBA/Basic, 96

Someday I will find a good challenge for vba or basic, but not today

Fisher-Yates

Sub s(o(), n)
For i = 0 To n
r = Int(Rnd() * (n + 1))
x = o(r)
o(r) = o(i)
o(i) = x
Next
End Sub
\$\endgroup\$
  • \$\begingroup\$ This is biased. It's what Will it Shuffle calls "swap (i <-> random)". You can turn it into actual Fisher-Yates by replacing n + 1 with i + though. \$\endgroup\$ – Martin Ender Feb 4 '15 at 15:30
  • \$\begingroup\$ ty, but damm then I need to add 'step -1' \$\endgroup\$ – dwana Feb 4 '15 at 15:48
  • \$\begingroup\$ Sorry, I don't know what you mean. \$\endgroup\$ – Martin Ender Feb 4 '15 at 15:49
1
2

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.