Iterated Dice Rolling

Question

Given an input n where 3 <= n <= 25, perform the following steps, starting with a single n-sided die (faces in the range [1, n], inclusive):

1. Print the result of rolling the current n-sided dice in play, in the form kdn: X (where X is the result and k is the number of dice in play).
2. If X is greater than or equal to n/2 times the number of dice in play, add a die. Else, remove a die.
3. If the number of dice in play is equal to 0 or n, stop. Else, go to step 1.

Example runs (note that the output in parentheses is for explanation and is not required):

6-sided:

1d6: 4 (avg: 3.0, add)
2d6: 6 (avg: 6.0, add)
3d6: 9 (avg: 9.0, add)
4d6: 16 (avg: 12.0, add)
5d6: 13 (avg: 15.0, remove)
4d6: 9 (avg: 12.0, remove)
3d6: 5 (avg: 9.0, remove)
2d6: 7 (avg: 6.0, add)
3d6: 11 (avg: 9.0, add)
4d6: 14 (avg: 12.0, add)
5d6: 17 (avg: 15.0, add)

9-sided:

1d9: 7 (avg: 4.5, add)
2d9: 14 (avg: 9.0, add)
3d9: 18 (avg: 13.5, add)
4d9: 18 (avg: 18.0, add)
5d9: 28 (avg: 22.5, add)
6d9: 26 (avg: 27.0, remove)
5d9: 28 (avg: 22.5, add)
6d9: 34 (avg: 27.0, add)
7d9: 33 (avg: 31.5, add)
8d9: 30 (avg: 36.0, remove)
7d9: 29 (avg: 31.5, remove)
6d9: 35 (avg: 27.0, add)
7d9: 32 (avg: 31.5, add)
8d9: 42 (avg: 36.0, add)

Rules

• Outputs must be exactly in the format kdn: X, with newlines separating each roll
• You must actually simulate rolling multiple dice; simply returning a random integer in the range [1, n] (inclusive) multiplied by the number of dice currently in play is not allowed, as that does not accurately simulate rolling multiple dice.
• Standard loopholes are forbidden
• This is code-golf, so the shortest answer in bytes wins

Leaderboard

The Stack Snippet at the bottom of this post generates the leaderboard from the answers a) as a list of shortest solution per language and b) as an overall leaderboard.

To make sure that your answer shows up, please start your 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

If there you want to include multiple numbers in your header (e.g. because your score is the sum of two files or you want to list interpreter flag penalties separately), make sure that the actual score is the last number in the header:

## Perl, 43 + 2 (-p flag) = 45 bytes

You can also make the language name a link which will then show up in the snippet:

## [><>](http://esolangs.org/wiki/Fish), 121 bytes

<style>body { text-align: left !important} #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; }</style><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="language-list"> <h2>Shortest Solution by Language</h2> <table class="language-list"> <thead> <tr><td>Language</td><td>User</td><td>Score</td></tr> </thead> <tbody id="languages"> </tbody> </table> </div> <div id="answer-list"> <h2>Leaderboard</h2> <table class="answer-list"> <thead> <tr><td></td><td>Author</td><td>Language</td><td>Size</td></tr> </thead> <tbody id="answers"> </tbody> </table> </div> <table style="display: none"> <tbody id="answer-template"> <tr><td>{{PLACE}}</td><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><script>var QUESTION_ID = 65904; var ANSWER_FILTER = "!t)IWYnsLAZle2tQ3KqrVveCRJfxcRLe"; var COMMENT_FILTER = "!)Q2B_A2kjfAiU78X(md6BoYk"; var OVERRIDE_USER = 45941; var answers = [], answers_hash, answer_ids, answer_page = 1, more_answers = true, comment_page; function answersUrl(index) { return "https://api.stackexchange.com/2.2/questions/" + QUESTION_ID + "/answers?page=" + index + "&pagesize=100&order=desc&sort=creation&site=codegolf&filter=" + ANSWER_FILTER; } function commentUrl(index, answers) { return "https://api.stackexchange.com/2.2/answers/" + answers.join(';') + "/comments?page=" + index + "&pagesize=100&order=desc&sort=creation&site=codegolf&filter=" + COMMENT_FILTER; } function getAnswers() { jQuery.ajax({ url: answersUrl(answer_page++), method: "get", dataType: "jsonp", crossDomain: true, success: function (data) { answers.push.apply(answers, data.items); answers_hash = []; answer_ids = []; data.items.forEach(function(a) { a.comments = []; var id = +a.share_link.match(/\d+/); answer_ids.push(id); answers_hash[id] = a; }); if (!data.has_more) more_answers = false; comment_page = 1; getComments(); } }); } function getComments() { jQuery.ajax({ url: commentUrl(comment_page++, answer_ids), method: "get", dataType: "jsonp", crossDomain: true, success: function (data) { data.items.forEach(function(c) { if (c.owner.user_id === OVERRIDE_USER) answers_hash[c.post_id].comments.push(c); }); if (data.has_more) getComments(); else if (more_answers) getAnswers(); else process(); } }); } getAnswers(); var SCORE_REG = /<h\d>\s*([^\n,<]*(?:<(?:[^\n>]*>[^\n<]*<\/[^\n>]*>)[^\n,<]*)*),.*?(\d+)(?=[^\n\d<>]*(?:<(?:s>[^\n<>]*<\/s>|[^\n<>]+>)[^\n\d<>]*)*<\/h\d>)/; var OVERRIDE_REG = /^Override\s*header:\s*/i; function getAuthorName(a) { return a.owner.display_name; } function process() { var valid = []; answers.forEach(function(a) { var body = a.body; a.comments.forEach(function(c) { if(OVERRIDE_REG.test(c.body)) body = '<h1>' + c.body.replace(OVERRIDE_REG, '') + '</h1>'; }); var match = body.match(SCORE_REG); if (match) valid.push({ user: getAuthorName(a), size: +match[2], language: match[1], link: a.share_link, }); else console.log(body); }); valid.sort(function (a, b) { var aB = a.size, bB = b.size; return aB - bB }); var languages = {}; var place = 1; var lastSize = null; var lastPlace = 1; valid.forEach(function (a) { if (a.size != lastSize) lastPlace = place; lastSize = a.size; ++place; var answer = jQuery("#answer-template").html(); answer = answer.replace("{{PLACE}}", lastPlace + ".") .replace("{{NAME}}", a.user) .replace("{{LANGUAGE}}", a.language) .replace("{{SIZE}}", a.size) .replace("{{LINK}}", a.link); answer = jQuery(answer); jQuery("#answers").append(answer); var lang = a.language; lang = jQuery('<a>'+lang+'</a>').text(); languages[lang] = languages[lang] || {lang: a.language, lang_raw: lang.toLowerCase(), user: a.user, size: a.size, link: a.link}; }); var langs = []; for (var lang in languages) if (languages.hasOwnProperty(lang)) langs.push(languages[lang]); langs.sort(function (a, b) { if (a.lang_raw > b.lang_raw) return 1; if (a.lang_raw < b.lang_raw) return -1; return 0; }); for (var i = 0; i < langs.length; ++i) { var language = jQuery("#language-template").html(); var lang = langs[i]; language = language.replace("{{LANGUAGE}}", lang.lang) .replace("{{NAME}}", lang.user) .replace("{{SIZE}}", lang.size) .replace("{{LINK}}", lang.link); language = jQuery(language); jQuery("#languages").append(language); } }</script>

Answer 1

Pyth, 37 bytes

J1W%JQs[J\dQ\:dKsmhOQJ)=J+WgK*JcQ2tJ2

Try it online.

Answer 2

Mathematica, 95 89 80 characters

For[k=1,0<k<#,If[Print[k,d,#,": ",x=Tr[{1,#}~RandomInteger~k]];x<k/2#,k--,k++]]&

Ungolfed

For[
  k = 1,
  0 < k < #,
  If[
    Print[k, d, #, ": ", x = Tr[{1, #}~RandomInteger~k]];
    x < k/2 #,
    k--,
    k++
  ]
] &

Answer 3

PHP, 164 121 112 113 109 bytes

Final version, I promise. Improved using Titus' suggestion:

function d($x,$y){for($i=$y;$i--;)$r+=rand(1,$x);echo$y."d$x: $r\n";$y+=$r/$y>$x/2?:-1;$y<$x&&$y?d($x,$y):0;}

---

EDIT: Added an extra byte for formatting. Forgot there's an IF in there that, thanks to dropping the "add/sub" text, could have been a ternary operator:

function d($x,$y){for($i=$y;$i--;)$r+=rand(1,$x);echo$y."d$x: $r\n";$r/$y>$x/2?$y++:$y--;if($y<$x&&$y)d($x,$y);}

Output now looks like:

1d6: 5
2d6: 11
3d6: 8
2d6: 11
3d6: 7
2d6: 4
1d6: 5

---

EDIT: Thanks to @Manatwork, saved me a lot! New and imrpoved version:

function d($x,$y){for($i=$y;$i--;)$r+=rand(1,$x);echo$y."d$x=$r\n";if($r/$y>$x/2)$y++;else$y--;if($y<$x&&$y){d($x,$y);}}

---

Previous entry:

function d($x,$y){for($i=0;$i<$y;$i++)($r+=rand(1,$x));$s=$y."d$x=$r, ";if($r/$y>$x/2){$y++;$s.="add";}else{$y--;$s.="sub";}echo $s."\n";if($y<$x&&$y>0){d($x,$y);}}`

Rolls separate dies, outputs this:

1d6=6, add
2d6=7, add
3d6=11, add
4d6=14, add
5d6=15, sub
4d6=15, add
5d6=18, add

And it's called thusly: d(6, 1);

Is displaying the Add and Sub suffix mandatory? This is unclear from your question.

Answer 4

Python 3, 125

Saved 3 bytes thanks to DSM.

def x(d):
 import random;c=1
 while 0<c<d:r=sum(map(random.randint,[1]*c,[d]*c));print('%id%i: %i'%(c,d,r));c+=2*(r>=d*c/2)-1

Pretty simple, rolls a bunch of dice and checks the average. Nothing too fancy here yet.
It needs to be called with an int. So, x(6) will produce something like this:

1d6: 5
2d6: 10
3d6: 8
2d6: 7
3d6: 11
4d6: 8
3d6: 13
4d6: 19
5d6: 13
4d6: 15
5d6: 22

.

Answer 5

JavaScript (ES6), 97 102 106 112 bytes

Thanks @user81655 and @Jupotter for saving me a few bytes.

f=n=>{for(k=1;k%n;console.log(k+`d${n}: `+x),k+=x<k*n/2?-1:1)for(x=i=k;i--;)x+=Math.random()*n|0}

// 102 bytes:
f=n=>{for(k=1;k%n;console.log(k+`d${n}: `+x),k+=x<k*n/2?-1:1)for(x=i=0;++i<=k;)x+=1+Math.random()*n|0}

// Previous attempt, 112 bytes
f=n=>{k=1;while(k&&k!=n){for(x=i=0;i++<=k;)x+=1+~~(Math.random()*n);console.log(k+`d${n}: `+x);k+=x<k*n/2?-1:1}}

Demo

This only works in ES6 compliant browsers (at the moment that includes Firefox and Edge, possibly with Chrome and Opera with experimental JavaScript features enabled):

f=n=>{for(k=1;k%n;console.log(k+`d${n}: `+x),k+=x<k*n/2?-1:1)for(x=i=k;i--;)x+=Math.random()*n|0}

// Snippet stuff
console.log = x => {
  document.getElementById('O').innerHTML += x + `<br>`;
}

document.getElementById('F').addEventListener('submit', e => {
  document.getElementById('O').innerHTML = ``
  f(document.getElementById('I').valueAsNumber)
})

<form id=F action=# method=get>
  <label>
    Number of faces: 
    <input type=number min=3 max=25 value=9 required id=I>
  </label>
  <button>Play</button>
  
  <div>
    <output id=O></output>
  </div>
</form>

Answer 6

CJam, 45 bytes

ri:M;{X__{Mmr+}*[X'dM':S5$N]o_+XM*<_+(-:XM%}g

Try it online.

Implements the spec pretty literally (including the mathematically incorrect "mean roll" formula). As expected, porting the original GolfScript program below to CJam saved a bunch of bytes due to shorter built-in command names (mr, o and g instead of rand, puts and do).

GolfScript, 51 bytes

~:&;{1..{&rand+}*[1"d"&": "4$]puts.+1&*<.+(-:1&%}do

Here's my original GolfScript entry. Notable golfing tricks include using the number 1 as a conveniently pre-initialized variable to store the current number of dice to to be rolled. (The CJam version instead uses X, which CJam initializes to the value 1.)

---

Ps. Seeing the title, I originally wanted to answer this in AnyDice. But it turns out to be a horrible choice for this challenge, and I don't think it's even technically possible to use it to implement this spec as given.

The problem is that AnyDice is a domain-specific language for writing deterministic programs to calculate dice rolling statistics. While inspecting the possible outcomes of a roll and doing conditional rolls based on them is possible via recursion, there's no way to generate any actual randomness. So while you could simulate this sequence of dice rolls in AnyDice, all you can get as output is statistics on things like, say, the number of rolls until the process ends, or the distribution of results at a given step.

All that said, here's the closest I could get in AnyDice:

N: 6
K: 1
function: clip X:n { result: X * (X < N) }
function: adjust X:n { result: [clip X + ((XdN)*2 >= X*N)*2-1] * (X > 0) }
loop I over {1..20} {
  output K named "dice in roll [I]"
  output KdN named "outcome of roll [I]"
  K: [adjust K]
}

This isn't particularly golfed code, since that seemed like an exercise in futility. Standard brace language golfing tricks, like shortening function names and eliminating unnecessary whitespace, should exhaust most of the golfing potential anyway.

The key trick used here is that, when you call a function expecting a number (as indicated by the :n in the function definition) in AnyDice, and pass it a die (i.e. a probability distribution) instead, AnyDice automatically evaluates the function for all possible values of the die, and combines the results into a new die.

Here's a screenshot of the output (in bar chart format) for the first three rolls:

(Note that the "0" column in each graph indicates the probability that the iteration stopped, due to the number of dice hitting either 0 or N, before the current roll. This happens to be a convenient way to represent the stopping condition, since of course rolling 0dN always yields 0.)

Answer 7

R, 103 Bytes

A fairly straight forward implementation. Dice rolls are done by sum(sample(n,i)).

i=1;n=scan();while(i&i<=n){cat(i,'d',n,': ',s<-sum(sample(n,i)),'\n',sep='');i=ifelse(s<i*n/2,i-1,i+1)}

Test run

> i=1;n=scan();while(i&i<=n){cat(i,'d',n,': ',s<-sum(sample(n,i)),'\n',sep='');i=ifelse(s<i*n/2,i-1,i+1)}
1: 9
2: 
Read 1 item
1d9: 9
2d9: 14
3d9: 10
2d9: 14
3d9: 9
2d9: 9
3d9: 12
2d9: 7
1d9: 9
2d9: 11
3d9: 17
4d9: 18
5d9: 25
6d9: 29
7d9: 33
8d9: 43
9d9: 45
> 

Answer 8

CoffeeScript, 106 99 bytes

f=(n,k=1)->(x=k;x+=Math.random()*n|0for[k..0];console.log k+"d#{n}: "+x;k+=x<k*n/2&&-1||1)while k%n

# Previous attempt, 106 bytes
f=(n,k=1)->(x=i=0;x+=1+Math.random()*n//1while++i<=k;console.log k+"d#{n}: "+x;k+=x<k*n/2&&-1||1)while k%n

Ungolfed

f = (n, k = 1) ->
 (x = k
 x += 1 + Math.random() * n | 0 for [k..0]
 console.log k + "d#{n}: " + x
 k += x < k * n / 2 && -1 || 1
 ) while k % n

Answer 9

Julia, 77 bytes

n->(N=1;while 0<N<n k=sum(rand(1:n,N));print(N,"d$n: $k
");N+=1-2(2k<N*n)end)

Most of this should be self-explanatory - an actual newline is being used in the print string rather than using println to save a byte. rand(1:n,N) produces N random integers between 1 and n.

Answer 10

Ruby, 93 90 82 characters

->n{d=s=2
puts"#{d}d#{n}: #{s=eval'+rand(n)+1'*d}"while(d+=s<d*n/2.0?-1:1)>0&&d<n}

Sample run:

2.1.5 :001 > -->n{d=s=2;puts"#{d}d#{n}: #{s=eval'+rand(n)+1'*d}"while(d+=s<d*n/2.0?-1:1)>0&&d<n}[6]
1d6: 5
2d6: 10
3d6: 6
2d6: 5
1d6: 5
2d6: 8
3d6: 15
4d6: 18
5d6: 22

Answer 11

PHP, 104 bytes

for($n=$argv[$k=1];$k&&$k<$n;print$k."d$n: $x\n",$k-=$x<$n*$k/2?:-1)for($x=$i=0;$i++<$k;)$x+=rand(1,$n);

Run with php -r '<code>' <N>

breakdown

for($n=$argv[$k=1];     // import input, init number of dice
    $k&&$k<$n;          // while 0<$k<$n
    print$k."d$n: $x\n",    // 2. print results
    $k-=$x<$n*$k/2?:-1      // 3. remove or add a die
)
    for($x=$i=0;$i++<$k;)   // 1. roll dice separately
        $x+=rand(1,$n);         // sum up results

Answer 12

QBIC, 83 bytes

:c=a{e=0[1,q|e=e+_rq,a|]?!q$+@d|!+a$+@:|+!e$~e<c/2|q=q-1\q=q+1]c=q*a~q=a|_X]~q=0|_X

Explanation:

q                    Tracks the number of dice (is implicitly 1 at the start)
:                    Takes input from a CMD line parameter
[1,q|e=e+_rq,a|]     Rolls the dice separately
?!q$+@d|!+a$+@:|+!e$ Prints the roll result (requires an unfortunate amount of casting...)
~e<c/2|q=q-1\q=q+1]  Checks whether to increase or decrease
~q=a|_X]~q=0|_X      Tests the amount of dice and quits on either boundary.

Answer 13

Python 3, 131 bytes

def f(n):
    import random;k=1
    while 0<k<n:
        r=sum([random.randint(1,n)for _ in range(k)]);print(f'{k}d{n}: {r}');k+=2*(r>=k*n/2)-1

Try it online!

Explanation:

def f(n): # function header, doesn't need to use int(input())
    import random;k=1 # initialize, can't use import* to save bytes
    while 0<k<n: # while k is in between 0 and n:
        r=sum([random.randint(1,n)for _ in range(k)]); # roll k dice and add them up
                                                      print(f'{k}d{n}: {r}'); # print to console, concatenation would take up even more bytes
                                                                             k+=2*(r>=k*n/2)-1 # add dice if r is >= to k*n/2, else remove dice