Discussion on:

My first IronRuby application

... you're finally taking the Ruby plunge. Can't say that I'd find Visual Studio all that helpful, though. I use Ruby from the command line on all platforms quite happily.

The new site really messed up your code formatting, so much so that I'm having trouble reading it. I guess I'll copy/paste and reformat in vim.

Just for s & g, let me see how code gets formatted in a comment with pre and code tags:


def calculate (iteration, low, high, currentsum, output)
if (iteration == 1)
low.upto(high) do |value|
newsum = currentsum + value
output[newsum] += 1
end
else
low.upto(high) do |value|
calculate(iteration - 1, low, high, currentsum + value, output)
end
end
return output
end

diceInput = ARGV[0].to_i
lowInput = ARGV[1].to_i
highInput = ARGV[2].to_i

if (diceInput 1)
puts "You must use at least one dice."
return
end


initResults = Hash.new

(lowInput * diceInput).upto(highInput * diceInput) do |value|
initResults[value] = 0
end

results = calculate(diceInput, lowInput, highInput, 0, initResults)

results.each do |result|
puts "#{result}"
end
~

oddly, it preserved some of my indentation, but not all.

... runs off the edge. It needs to:

* Maintain all spacing, indents, etc.
* Use a fixed width font
* Wrap at the edge
* Put the content in a box or other mechanism to set it apart

J.Ja

CSS floating elements in the article (i.e., text-inset ads) chew up code formatting too. I'm not sure there's anything that can be done about that without taking those elements out of the article, though -- and I really doubt TR/CBSi will do that, even for the Programming column where it is desperately needed.

As we discussed in email, of course, this doesn't precisely solve my problem. It visibly slows down at seven six-sided dice, and gets exponentially slower for higher numbers of dice. Still, it's at least faster than my original, and less prone to blowing up. I've taken a break for a few days on the matter of getting the "right" algorithm worked out. I got a little burned out after my failures to make the Pascal's Triangle approach work for me. I'll probably revisit it in a while, though.

edit: I don't know if I'll ever be back to this discussion. The complete lack of reasonable facility for keeping up with discussions in the new interface is making it difficult for me to keep up with discussions.

On my laptop with 1024x768 resolution, useless crap eats up half the screen, even with "Collapse" selected to collapse the upper banner. The fonts are way too huge -- zooming out to 80% of original size makes the regular text about right, but headers and such are still way too big. Time to brush up on Greasemonkey.

#!/usr/bin/ruby
def vwnd(value,dice)
if value 1
return 0
elsif dice==1 && value 6
return 0
else
return vwnd(value-1,dice-1)+vwnd(value-2,dice-1)+vwnd(value-3,dice-1)+vwnd(value-4,dice-1) +vwnd(value-5,dice-1) +vwnd(value-6,dice-1)
end
end

for value in 5...31
print value, " with 5 dice: ", vwnd(value,5), "\n"
end

It's not very generalized, but that's basically just paperwork. Swap out some of those hard-coded values with expressions or variables from input and you've got a generalized program.

Unfortunately, it's only "pretty fast" up to about five six-sided dice. With larger dice or, worse, with more dice of whatever size, it starts getting pretty slow -- basically at the exact same time Justin's version starts getting too slow.

I hacked around with some Pascal's Triangle stuff for a bit, and that was blazing fast -- but I haven't come up with a pattern to describe the probability curve's divergence from the progression of values in a diagonal "row" in Pascal's Triangle that is generalized across different numbers of dice yet. Part of the reason I haven't figured it out is that I gave up on it in favor of trying to make a living, but I plan to return to the problem in earnest at some point.

Yeah, you are right: it is fast only up to 12 12-sided dice. After that, it takes up to one minute or more. Do you mind dropping here your "Pascal Triangle-based code" so I can compare speed?
Also, note that by the symmetry of the results, one can cut computation time and resources by a half!
This is how my last version looks:

#!/usr/bin/ruby

idice=ARGV[0].to_i
isides=ARGV[1].to_i

def vwnd(value,dice,sides)
if value 1
return 0
elsif dice==1 && value sides
return 0
else
collect=0
for step in 1...sides+1
collect=collect+vwnd(value-step,dice-1,sides)
end
return collect
end
end

for value in idice...idice+(idice*isides-idice)/2+1
stuff = vwnd(value,idice,isides)
print value, " and ", idice*isides-value+idice, " with ", isides, "-sided ", idice, " dice: ", stuff, "\n"
end

Cutting computation time in half should buy you about one more increment -- from 12 dice to 13 dice, for instance.

I don't have a small code snippet to share for solving this problem with the Pascal's Triangle approach. As I mentioned, I have not actually gotten the Pascal's Triangle approach to work properly yet, because the series of numbers in a given diagonal of the triangle is a progression and not a curve. I've actually used Pascal's Triangle in several different variants, each of them falling short of solving the whole problem.

What has to be done is to select a specific diagonal, get all the numbers from that diagonal starting at a specified depth and ending at a specified (greater) depth in the triangle, modify all the values according to a generalized function starting with the value that is die_faces+1 into the selected series to produce the needed curve, then mirror it to get the descending half of the curve. The part of that I'm missing is the generalized function that modifies part of the series to produce the needed curve.

For demonstration's sake, though, this is a simplistic Pascal's Triangle class:

class PascTri
include Enumerable

def initialize(rownum)
@triangle = PascTri.build_triangle(rownum)
end

attr_reader :triangle

def self.build_row(rownum)
([nil] * rownum).inject([1]) do |n,row|
row = next_row n
end
end

def self.diagonal(rownum, depth)
diagonal_list = Array.new
0.upto(depth) do |d|
diagonal_list.push build_row(rownum+d)[d]
end
diagonal_list
end

def self.build_triangle(rownum)
triangle = Array.new
(0..rownum).each do |num|
triangle.push self.build_row(num)
end
triangle
end

private

def self.next_row(rownum)
([0] + rownum).zip(rownum + [0]).collect do |left,right|
left + right
end
end
end

ptri = PascTri.new 7


The PascTri instance stored at ptri then contains the numbers of Pascal's Triangle up to a depth of seven (+1) rows in the form of an array of arrays. It would look like this:

[1]
[1, 1]
[1, 2, 1]
[1, 3, 3, 1]
[1, 4, 6, 4, 1]
[1, 5, 10, 10, 5, 1]
[1, 6, 15, 20, 15, 6, 1]
[1, 7, 21, 35, 35, 21, 7, 1]


I have a couple other implementations of a Pascal's Triangle class lying around here, too. I don't think this was my most recent toy implementation -- but it should serve as an example of the increased speed of this approach to generating a series of numbers over one that actually does a one-by-one increment so that the 35s in that triangle would each take 35 operations, all to themselves.

In fact, generating the first thirty rows of Pascal's Triangle is effectively instant, whereas generating only the first fifteen numbers using your code or Justin's can take effectively forever.

at least for this problem. Thanks for the implementation of the Pascal Triangle, though

The weird thing about it is that, until you get past the number of results equal to the number of faces on a single die, a diagonal series from Pascal's Triangle will perfectly match the number of permutations that will produce each of those results. It really feels like there should be some kind of generalized function that can be used to adjust numbers to match the curve. Unfortunately, after writing a program that worked for up to three dice, I realized that though I thought I had been on to something it simply didn't work for four dice.

. . . and it would be wonderful if it worked, because that version worked in what appeared to be constant time (effectively instantly) for any number of virtual dice up to 100.

Please reveal how you got TR to format code! Thanks.

use the <pre> environment, and copy-paste your code inside. TR will do the formatting for ya.

... it also makes longer lines disappear. With the larger font size, you are getting roughly 100 characters per line, hardly enough, especially for an OO language. It might work for Ruby or Python, but imagine what C# will look like...

J.Ja

Frankly, the only reasonable answer to display on the page with such narrow content constraints is horizontal scroll bars. You don't want wrapping if you can avoid it, and you don't want lines cut off if you can avoid it. Luckily, horizontal scroll bars solve both problems. It only takes one line of CSS.

That was one of the first no-no's we learned right away - both in ASM and C! Sure, you could make it go fast, but self-modifying code was a nightmare to understand and debug. The language may have changed, but the issue hasn't. BAD practice...

And sorry, J, but this IS a trivial application. The sum of the pips will be in the range (# of dice) x ((# of pips per die) * (# of dice)). A simple reentrant function that calls itself successively, returning intermediate results for fewer dice as you build toward the end result. It just keeps calling itself until the number of dice is 1. It evaluates with iteration for each die up to the maximum number of pips. Then it returns a result back for the next die. When you've run out of dice, the result is the final result.

"That was one of the first no-no's we learned right away - both in ASM and C! Sure, you could make it go fast, but self-modifying code was a nightmare to understand and debug. The language may have changed, but the issue hasn't. BAD practice..."

I agree... for C and ASM. For languages like Ruby, Perl, Lisp, this is not only much less of a bad practice, but in many cases, encourages or even required.

"The sum of the pips will be in the range (# of dice) x ((# of pips per die) * (# of dice))."

Yes.

"A simple reentrant function that calls itself successively, returning intermediate results for fewer dice as you build toward the end result. It just keeps calling itself until the number of dice is 1. It evaluates with iteration for each die up to the maximum number of pips. Then it returns a result back for the next die. When you've run out of dice, the result is the final result."

Funny, this is exactly what my code does. Did you look at it?

The problem is, my code works fine, in terms of producing *correct* results. But it takes FOREVER at large numbers (say, 100 100 sided dice). So it's not a good solution, it's an accurate brute force approach. There is either a more elegant brute force approach, or there is a better algorithm to use.

J.Ja

#!/usr/bin/ruby

dice = ARGV[0].to_i
sides= ARGV[1].to_i

def printarray(array)
array.cycle(1) {|x| print x," "}
puts
end

def sumarray(array)
array.inject(0) {|su,item| su+item}
end

def mda(width,height)
return Array.new(width) {Array.new(height) {0}}
end

def helper(size,stack,step)
if step==1
return stack
else
a=mda(size,size+stack.length-1)
for k in 0...size
a[k][k...stack.length+k]=stack
end
b=a.transpose
return helper(size,Array.new(size+stack.length-1) {|x| sumarray(b[x])},step-1)
end
end

def function(n,size)
origen=Array.new(size) {1}
if n==1
return origen
else
return helper(size,origen,n)
end
end

printarray(function(dice,sides))

Great work! That is blazingly fast. It does, however, use a ton of RAM... well over 1 GB on my system (IronRuby, your mileage may vary). My recursive version uses practically none, once I moved the data array to be a global variable.

J.Ja

I'll let y'all experts figure out how to reduce the memory usage, and polish the style and all that jazz. I am writing a post in my blog explaining the solution strategy. I am sure you can get to a nicer code with the ideas from there.

I'd like to see that strategy write-up when you're done with it. It does not seem to me to be as quick as you seem to think.

I rewrote it slightly to make it a bit more understandable to me. I don't see anything in the changes I made (mostly changes in variable names, though I did replace a for loop and a cycle(1) message with each iterators) that should affect performance overmuch, unless a for loop is significantly faster than an each iterator for some reason. Using the time utility, though, it shows just over eleven minutes to complete a run for one hundred dice with one hundred sides each. Maybe you're using a much faster computer than me, but I'd hate to see what happens if I double the number of virtual dice.

Before I started writing this, I started the time utility to time the run of the unmodified version. It's still going.

edit: The unmodified version finished its run, and took about twelve and a half minutes.

I figured out how to rewrite the same algorithm without using matrices at all. It will only take two functions to handle simple 1-d arrays of integers, which eventually also makes the code "a little" faster. My ruby skills are not too good, though (I just learned ruby for this problem!) mind helping me out figuring out how to do it? This is a first attempt
#!/usr/bin/ruby

dice = ARGV[0].to_i
sides= ARGV[1].to_i
original_permutation=Array.new(sides) {1}

# helper adds to the array "target" n shifted
# versions of the array "pattern", for n=size
# see blancosilva.wordpress.com/puzzles/unusual-dice/
def helper(pattern,target,step,size)
if step==1
return target
else
target+=[0]
pattern.each_index{ |x| target[x+1-step+size] += pattern[x] }
return helper(pattern,target,step-1,size)
end
end

def get_permutations(dice,sides,ary)
if dice==1
return ary
else
return get_permutations(dice-1, sides, helper(ary, ary, sides, sides))
end
end

get_permutations(dice,sides,original_permutation)

hey, and gratz on todays good news.

blancosilva.wordpress.com/puzzles/unusual-dice/

Mind sending us your code? You can drop it as a comment in that other blog, if it makes sharing simpler. Also, a quick question about one of your previous comments: What do you mean with "the series of numbers in a given diagonal of the triangle is a progression and not a curve"?

I suspect you're replying to me, though in the TR interface (as of today, at least) your reply appears out of place.

What code do you mean -- the minor rewrite of your code that I did? If so, I might post it at blogstrapping instead, where this entire exercise actually started.

What I mean by "the series of numbers in a given diagonal of the triangle is a progression and not a curve" is that numbers increase at an easily predictable rate, infinitely growing, where what's needed for the dice roll probabilities is a bell curve. My earlier point was that the progression and the curve are identical until it reaches the point where the rate of increase starts angling toward deceleration, but a generalized function for calculating the rate of deceleration relative to the rate of progression escapes me so far.

Yes, please by all means, post *your* code anywhere; I don't need a re-write of mine with those minor changes. How long does it take for yours to do a 50 50, for example? Quit stalling, or we are going to start thinking that you don't have any code, dude. I hate doing somebody else's homework.

And your explanation gets more and more confusing; but I am intrigued: bell curve... really? Let us start from scratch again: what is for you a "given diagonal of the Pascal Triangle"?

Evidently, my first attempt at a response to you was deemed too abrasive, and has been deleted. I'll try again:

I have no idea what you're talking about. You made vague, hand-wavy statements about wanting to see my code, divested of any placement within the context of discussion. I made the only code I thought you might mean at that point -- my minimal reorganizing of your code for readability -- available in a blogstrapping essay, Fast Die Roll Permutations Still Elusive. Now you're acting like I'm an idiot and a bad person for thinking that's what you meant.

I find your attitude offensive.

Try rephrasing so that you do not come off like a corrupt politician trying to cast all blame for your own failings on someone else, and maybe I'll discuss the matter with you. Otherwise, I want nothing to do with you and your offensive, accusatory behavior. Go away.

... Ruby's Matrix class: http://www.ensta.fr/~diam/ruby/online/ruby-doc-stdlib/libdoc/matrix/rdoc/classes/Matrix.html

Don't know if it will speed things up at all, but it might make the code more clear.

The code seems singularly written to be unclear, using variable names like "array". Introducing another class will not help much.

[[ Edit: this is supposed to be in response to 'oldbaritone' -- is there a way of moving a reply under the initial post? If not, I apologize, still getting used to the new interface... ]]

Unless I'm missing something rather Basic (that's a pun... get it? ) there's no self-modifying code either in the existing example or could (easily) be derived from the eval() scenarios given by the author.

Self-modifying code (by the definition I've always understood it) needs to modify the original program memory, Perl's eval() doesn't modify program memory. Depending on the underlying operating system, it may even start a thread of its own.

I have written self-modifying code in 6800/6809 assembler, several flavors of Basic, and in packed Basic09; the last example was a *lot* more work than it was worth. (I did it just to see if it could be done -- Possible? Yes. Useful? Not particularly. ) In some instances - especially where memory is at a premium, I can see where it may be considered a viable programming practice. However, in today's computing environment (GBytes of RAM, etc.) I'm not sure I could ever imagine an actual need for it -- most languages nowadays would require such voodoo to make it happen that I don't see where it could be considered useful, let alone readable.

Nowadays, in some instances self-modifying code may not even be possible - some processors implement memory protection where program memory may be read-only once the process starts. [[ Don't quote me on the specifics of this, I haven't done a ton of research on it. ]] Wading through memory / allocation areas on Intel processors is also something I wouldn't call "fun"...

Laterz!