FAQ

Hi, I'm trying to enumerate all the combinations from rolling a dice
repeatedly, with an arbitrary number of rolls.

http://play.golang.org/p/LBhxle3WM_

[...]

Oddly, if I add a 5th roll, the last element starts iterating again (next to
last element is still broken).

I've studied on it for a while and can't figure it out. I must be misusing
slices somehow, but I'm not seeing it. Two questions:

a) what the heck is wrong here?
append(oldseries, die) may refer to the same piece of memory as oldseries.
Then the loop of dice may actually mutate a single array instead of
producing slices.
b) I bet there is a nicer way to permute a slice against another slice than
all this new/old/series/combined stuff. Please show me the way.
I prefer this way of doing: http://play.golang.org/p/IzaqT9y8q1
I think it is also more memory-efficient if you need to generate a lot
of dice rolls.

Rémy.

--

## Search Discussions

•  at Oct 10, 2012 at 9:56 pm ⇧
Hi, I'm trying to enumerate all the combinations from rolling a dice
repeatedly, with an arbitrary number of rolls.

http://play.golang.org/p/LBhxle3WM_

In the example I'm using a 3 sided die. So rolling once gets you 3
possibilities [1, 2, 3], rolling twice gets you 9 [[1, 1], [1, 2], [1, 3],
[2, 1] etc], three rolls would have 27 combinations, etc.

I'm keeping track of these results as a slice of slices, where each
iteration (roll) permutes the original set of slices against each dice
possibility. Even if this is not the optimal way to solve this problem, I'd
like to understand the bug and get it to work.

Something is wrong with my logic. If we simulate 4 rolls, something goes
wrong on the fourth roll, and the final element is not iterating the way it
should, instead it's always the last value:

newseries: [[1 1 1 3] [1 1 1 3] [1 1 1 3]]
newseries: [[1 1 2 3] [1 1 2 3] [1 1 2 3]]

should be

newseries: [[1 1 1 1] [1 1 1 2] [1 1 1 3]]
newseries: [[1 1 2 1] [1 1 2 2] [1 1 2 3]]

Oddly, if I add a 5th roll, the last element starts iterating again (next
to last element is still broken).

I've studied on it for a while and can't figure it out. I must be misusing
slices somehow, but I'm not seeing it. Two questions:

a) what the heck is wrong here?
b) I bet there is a nicer way to permute a slice against another slice than
all this new/old/series/combined stuff. Please show me the way.

--
•  at Oct 10, 2012 at 11:34 pm ⇧

On Wed, Oct 10, 2012 at 4:21 PM, Rémy Oudompheng wrote:

http://play.golang.org/p/LBhxle3WM_
a) what the heck is wrong here?
append(oldseries, die) may refer to the same piece of memory as oldseries.
Then the loop of dice may actually mutate a single array instead of
producing slices.
I tried making the append to oldseries an explicit temporary variable
and watching what happened.

http://play.golang.org/p/z0MCwq45EZ

The append to newseries is behaving wrongly:

extendold: [1 1 1 1] //correct
partial newseries: [[1 1 1 1]]
extendold: [1 1 1 2] //correct
partial newseries: [[1 1 1 2] [1 1 1 2]] // ?!?! wrong, we
append *and* modify earlier element?
extendold: [1 1 1 3] //correct
partial newseries: [[1 1 1 3] [1 1 1 3] [1 1 1 3]] // also wrong
newseries: [[1 1 1 3] [1 1 1 3] [1 1 1 3]]

You were saying the append might mutate the array, here it seems to be
both appending, and mutating the previous element, in the same step.

I don't understand why "newseries = append(newseries, extendold)" is
doing this.

I guess all 3 references in newseries are really to the same extendold
slice? Which is only the newest version of extendold--even though
extendold is being reallocated each time? Clearly this is not
happening every time, most of the permutations work correctly.

Can you show me the correct way to do this append so the reference is
not reused (if that is in fact what is happening)? Mostly I am
concerned with understanding what I am doing wrong here so I don't get
bitten by something similar in the future. This behavior is thoroughly
confusing and surprising to me.
b) I bet there is a nicer way to permute a slice against another slice than
all this new/old/series/combined stuff. Please show me the way.
I prefer this way of doing: http://play.golang.org/p/IzaqT9y8q1
I think it is also more memory-efficient if you need to generate a lot
of dice rolls.
That is nicer and cleaner (and accurate!). I'll take some time and digest it.

Thanks for the help Remy.

--
•  at Oct 10, 2012 at 11:11 pm ⇧

You were saying the append might mutate the array, here it seems to be
both appending, and mutating the previous element, in the same step.

I don't understand why "newseries = append(newseries, extendold)" is
doing this.
It happens whenever the capacity of newseries is large enough.
I guess all 3 references in newseries are really to the same extendold
slice? Which is only the newest version of extendold--even though
extendold is being reallocated each time? Clearly this is not
happening every time, most of the permutations work correctly.
The capacity grow in unspecified ways. At some time you can append one
element but the reallocation makes the capacity grow by more than 1.
Can you show me the correct way to do this append so the reference is
not reused (if that is in fact what is happening)?
It's essentially not possible. You would need to create a full copy
each time, which is very inefficient.
b) I bet there is a nicer way to permute a slice against another slice than
all this new/old/series/combined stuff. Please show me the way.
I prefer this way of doing: http://play.golang.org/p/IzaqT9y8q1
I think it is also more memory-efficient if you need to generate a lot
of dice rolls.
That is nicer and cleaner (and accurate!). I'll take some time and digest it.

Thanks for the help Remy.
Rémy.

--
•  at Oct 11, 2012 at 12:58 am ⇧

On Wed, Oct 10, 2012 at 6:11 PM, Rémy Oudompheng wrote:
Can you show me the correct way to do this append so the reference is
not reused (if that is in fact what is happening)?
It's essentially not possible. You would need to create a full copy
each time, which is very inefficient.
Ugh. Well, that, at least, helps me understand my error.

Am I right then that my mistake was fundamentally this: modifying a
reference type, and then using the modified version as if it were a
new allocation separate from the earlier version?

To go further: even though it seemed to be working most of the time,
this was basically a fluke having to do with the way space for slices
is extended?

--
•  at Oct 11, 2012 at 6:18 am ⇧
Perhaps if you had sent the cap on the initial assignment to a large number you could have checked if it was in fact because of capacity allocation?
Looks like you fixed the original so I can't test.

--
•  at Oct 11, 2012 at 11:42 pm ⇧

On Thu, Oct 11, 2012 at 1:18 AM, Rory McGuire wrote:
Perhaps if you had sent the cap on the initial assignment to a large number you could have checked if it was in fact because of capacity allocation?
That's a good idea. The answer is no, apparently not:

http://play.golang.org/p/yVkWW56YYJ

I set the initial cap to 64 for all of the slices. I expected this
would result in more reuse of old references, and thus more strange
behavior, but it acts the same as the original.

At this point I am more confused by the first few iterations
generating the correct results, than by the later ones being "wrong".
Looks like you fixed the original so I can't test.
It's still there and still broken.

http://play.golang.org/p/LBhxle3WM_

Note that the strange behavior doesn't show up until the fourth "roll".

Although Remy recommended against it for efficiency reasons, you can
patch the original so it works by using copy():

http://play.golang.org/p/lCacHUyxlm

--
•  at Oct 11, 2012 at 10:04 pm ⇧

On 11 Oct 2012 11:49 PM, "Matt Conrad" wrote:
On Thu, Oct 11, 2012 at 1:18 AM, Rory McGuire wrote:
Perhaps if you had sent the cap on the initial assignment to a large
number you could have checked if it was in fact because of capacity
allocation?
That's a good idea. The answer is no, apparently not:

http://play.golang.org/p/yVkWW56YYJ
Weird would have that appending checks cap not len. I suppose they didn't
want append to clobber data if the slice was from a larger array that had
important data after the slice.

--
•  at Oct 11, 2012 at 10:07 pm ⇧

On Thu, Oct 11, 2012 at 1:18 AM, Rory McGuire wrote:
Perhaps if you had sent the cap on the initial assignment to a large number you could have checked if it was in fact because of capacity allocation?
That's a good idea. The answer is no, apparently not:

http://play.golang.org/p/yVkWW56YYJ

I set the initial cap to 64 for all of the slices. I expected this
would result in more reuse of old references, and thus more strange
behavior, but it acts the same as the original.

At this point I am more confused by the first few iterations
generating the correct results, than by the later ones being "wrong".
Here is a version that indeed does what you may have intended:

http://play.golang.org/p/aq_GqYzMJ-

Rémy.

--

## Related Discussions

Discussion Overview
 group golang-nuts categories go posted Oct 10, '12 at 9:49p active Oct 11, '12 at 11:42p posts 9 users 3 website golang.org

### 3 users in discussion

Content

People

Support

Translate

site design / logo © 2022 Grokbase