Prepare to... die?

Question

Background

One source of ennui in tabletop role-playing games is dealing with rolls involving many dice. Casting a Disintegration spell may be instantaneous, but rolling and adding together 40 dice certainly isn't!

A number of suggestions for handling this are discussed at rpg.stackexchange.com. Some of them, however, such as using a roller program or averaging dice, take away some of the fun and sense of control from the players. Others, such as rolling 4 dice and multiplying the total by 10, make the results far more swingy (while averaging dice acts in the opposite direction).

This question concerns a method of reducing the number of dice rolls without changing either the average result (mean) or its swinginess (variance).

Notation and math

In this question, we'll use the following notation to represent dice rolls:

• ndk (e.g. 40d6) refers to the sum of n rolls of a k-sided die.
• ndk*c (e.g. 4d6*10) describes multiplying the result by a constant c.
• We can also add rolls (e.g. 4d6*10 + 40d6) and constants (e.g. 4d6 + 10).

For a single die roll, we can show that:

• Mean: E[1dk] = (k+1)/2
• Variance: Var(1dk) = (k-1)(k+1)/12

Using the basic properties of mean and variance, we can furthermore infer that:

• Mean: E[mdk*a + ndl*b + c] = a.m.E[1dk] + b.n.[1dl] + c
• Variance: Var(mdk*a + ndl*b + c] = a².m.Var(1dk) + b².n.Var(1dl)

Task

Given three integers n, k and r, your program should output a way of approximating ndk in at most r rolls, with the following constraints:

• The solution should have the same mean and variance as ndk.
• The solution should contain the largest possible number of rolls less than or equal to r, as more rolls produces a smoother distribution.
• You should restrict your solutions to only using k-sided dice, unless you're aiming for the Bonus (see below).
• If there is no solution (as r is too small), the program should output the string "I AM A SEXY SHOELESS GOD OF WAR!".
• The parameters are passed in as a single space-separated string.
• You may assume that 1 ≤ n ≤ 100, 1 ≤ r ≤ n and that k is one of 4, 6, 8, 10, 12 and 20 (the standard dice used in tabletops).
• The output should be in the format described in Notation (e.g. 4d6*10+5), with optional spaces around +s but nowhere else. Unit multipliers are also optional: both 4d6*1 and 4d6 are valid.

You may write a program or function, taking input via STDIN (or closest alternative), command-line argument or function argument. Results should be printed to STDOUT (or closest alternative) or returned as a string.

Examples

>> "10 6 10"
10d6
>> "10 6 4"
2d6*2+2d6+14
>> "10 6 3"
1d6*3+1d6+21
>> "10 6 2"
1d6*3+1d6+21
>> "10 6 1"
I AM A SEXY SHOELESS GOD OF WAR!

Scoring

Shortest code wins. Standard rules apply.

Bonus

-33% (rounded down before subtraction) if your program also return solutions that include valid dice other than k (where the valid values, as mentioned above, are 4, 6, 8, 10, 12 and 20). If you choose to do so, then you should always return such solutions when appropriate, and handle solutions that use multiple types of die. Example:

>> "7 4 3"
3d6+7

Answer 1

GolfScript (163 143 133 bytes)

~@:^\?,{^base 0-}%{0\{.*+}/^=},.{{,}$-1=..&{[[1$[1$]/,(3$@]'d*+'1/]zip}%^@{-}/@)*.2/\1&'.5'*}{];'I AM A SEXY SHOELESS GOD OF WAR!'}if

Online demo

When not mixing types of dice, the problem reduces to expressing n as a sum of no more than r squares, and k is irrelevant except for the calculation of the constant at the end. The bulk of this answer is the bookkeeping required to express the result in the desired format: the actual calculation is ^\?,{^base}%{0\{.*+}/^=}, to find the multiplication factors a, b, etc.; and ^@{-}/@)*.2/ to calculate the constant.

Dissection

~                # Stack: n k r
@:^\?,{          # Store n in ^, and for 0 to n**r
  ^base 0-       #   convert to base n and remove 0s.
}%               # Stack: k [arrays of up to r values from 1 to n-1]
{0\{.*+}/^=},    # Filter them to arrays whose sum of squares is n,
                 #   i.e. to multipliers which have the right variance
.{               # If any multiplier array passes the filter...
  {,}$-1=        #   Pick one with the greater number of rolls
                 #   Stack: k [multipliers]
  ..&{           #   Map each distinct multiplier a...
    [[           #     Gather in nested array for later zip
      1$[1$]/,(  #       Split a copy of the multipliers around a to count the as
                 #       Let's denote that count as m
                 #       Stack: k [multipliers] a [ [ m
      3$@        #       Copy k and rotate the a inside the nested array
     ]           #       Stack: k [multipliers] [ [m k a]
      'd*+'1/    #       Push an array ['d' '*' '+'] and close nested array
    ]zip         #       Giving [[m 'd'] [k '*'] [a '+']]
                 #       which will be printed as mdk*a+
  }%             #   Stack: k [multipliers] [string representations of dice]
  ^@{-}/@)*      #   Compute (n - sum(multipliers)) * (k + 1)
                 #   That's twice the constant we need to add to fix the mean
  .2/\1&'.5'*    #   And convert it to a renderable form, including .5 if needed
}{               # Otherwise clear the stack and push the error message
  ];'I AM A SEXY SHOELESS GOD OF WAR!'
}if

Answer 2

Python, 487 461 452 - 33% = 303 bytes

Since nobody else has done so, here is a solution that handles different types of dice. Like the other solution, it generates a range of possible solutions and filters them down. It uses the fact that (k+1)(k-1) = k^2-1 and two semi-loopholes in the spec (oops!): the lack of ban on printing the redundant form 0dk*a (which saves all of 5 bytes!), and the lack of running time restriction (it gets slow fairly quickly, though does run all the examples given).

from itertools import*
N,K,R=map(int,input().split())
S=lambda l:sum([x[0]for x in l])
s=[x for x in product(*[[(n,k,a)for n in range(N*(K**2-1)/((k**2-1)*a**2)+1)]for a in range(1,N+1)for k in[4,6,8,10,12,20]if a**2<=N])if sum([n*(k**2-1)*a**2 for n,k,a in x])==N*K**2-N and S(x)<=R]
if s:s=max(s,key=S);print"+".join(["%sd%s*%s"%x for x in s]+[str(int(N*(K+1)/2.-sum([n*a*(k+1)/2.for n,k,a in s])))])
else:print"I AM A SEXY SHOELESS GOD OF WAR!"

For prettier output add if x[0] after "%sd%s*%s"%x for x in s:

>> "7 4 3"
3d6+7
>> "10 6 3"
1d6*1+1d8*1+1d8*2+18
>> "10 6 2"
1d6*1+1d6*3+21
>> "10 6 1"
I AM A SEXY SHOELESS GOD OF WAR!