Zugg Software :: View topic

Wanderer Joined: 08 Feb 2001 Posts: 89 Location: USA

Ok.. I'm still working on that potion mixing problem I brought up before. At this point, I need a "function" that will increment my combination string.

Supposing that the maximum number of components was 4, the first few combos would look like this:

01: 1
02: 2
03: 3
04: 4
05: 10
06: 11
07: 12
08: 13
09: 20
10: 21
11: 22

Essentially, in this example, the n-th combination is the n-th integer in base 4+1 whose digit sum <= 4.

I want an algorithm that will generate this numbers for base 7+1 whose digit sum <= 7.

Ideally I would like a function that will generate the next combo from a given combo. For example, 10: "21" -> 11: "22" without having to do the previous calculations.

If there's a quick way to generate combo(n) without iterating through the first n-1, then that would be good, too.

Any insights as to how to accomplish this in zScript?

Wil

Wil Hunt

P.S. If I need to just translate the number n to base n+1, and manually ignore the numbers whose digit sums are too high, I can do that. So if the algorithm is greatly complicated by that requirement, we can lose it. :)

GURU Joined: 15 Jun 2001 Posts: 654 Location: USA

Invasion of the WoTMUD players, it seems :P

I didn't see your other topic here until just now... I have a finished script that tries out recipes at breakneck speeds. For now, though, it's Brown Ajah only. I can describe a bit of how it works, though.

Instead of attacking the problem with a number of up to 20 digits representing the numbers of each herb in the recipe, I instead numbered the herbs from one to 20 and then created a combination (with replacement) of whatever length I desired of the numbers 1 to 20.

For example, if we limit it to 4 possible herbs and choose them three at a time, we get the combinations:

1 1 1
1 1 2
1 1 3
1 1 4
1 2 2
1 2 3
1 2 4
1 3 3
1 3 4
1 4 4
2 2 2
2 2 3
2 2 4
2 3 3
2 3 4
2 4 4
3 3 3
3 3 4
3 4 4
4 4 4

It is relatively simple to generate one combination given the previous one (and not especially difficult to derive a formula to instantly arrive at a specific one instead of iterating) and it just so happens that if you consider only the first digit or the first two digits and test those when they change, you can efficiently test all herb combinations of length one and two as you go along.

Note that regardless of what method you use, with n herbs taken r at a time, there are Cr(n, r) = C(n + r - 1, r) = (n + r - 1)!/(r!*(n - 1)!) combinations with replacement.

So for 20 herbs taken 7 at time, we have 657800 combinations. When you figure that you also want to check out the recipes of all lengths less than 7 as well, you bring the total to 888029.

Since it's not really possible to bring it below 4 seconds testing per recipe, this means about 3552116 seconds. Or 52901 minutes. Or 987 hours.

Or approximately 41 days, 2 hours, 41 minutes and 56 seconds of actual play time. You could be in it for the long haul...

- Charbal

GURU Joined: 15 Jun 2001 Posts: 654 Location: USA

Also, note that if you are testing up to r ingredients at a time and you have exactly r + 1 of each ingredient in a pack, ingredient k can can always be found in position (k-1)*(r+1)+1. The reason I say that you must have at least r + 1 of a item is that if you only have r, you run the risk of taking all of that item out of your pack and losing its position. When you put it back it becomes herb number 1 and could disrupt the script.

Note that the changes from one combination to the next are really only made at one side of my data structure (as well as yours). Couple this with the fact that with few exceptions (which lexigraphical order circumvents) if you reference by herb, put herb flask;take herb flask will end up doing nothing so containers in WoTMUD can be thought of as LIFO (last in, first out). This lends well to the concept of a stack that you can "push" ingredients onto and then "pop" off of, attempting to mix at each iteration.

- Charbal

Wanderer Joined: 08 Feb 2001 Posts: 89 Location: USA

Yeah, we discussed that on the mud. One of the things I'm hoping to do, though (as I mentioned in our mud conversation), is to allow for a bit more flexibility.

That's why I'm doing my combination recipe as I am. Further, I'm a lot closer to getting the herb accession routines down. I'm simply mimicing the pseudo lifo mechanisms in my "herb inventory" routines. That way, my script always knows what's where.

The problem I'm having at the moment, however, (I'm sure there will be many more to come...), is the generation of the digits. The method that I would usually use is recursive which does not work well with zScript and the lack of local variables. I was hoping someone else could help my addled brain by providng a simple script to provide those combination strings.

In all, however, I think our approaches are very similar. Do to my characters lack of resources, however (she's neither Brown Ajah or Wisdom clan), I'm forced to make my script much more flexible. For example, I need to allow for combinations that I simply do not yet have the ingredients to test. I need to make a note of that and come back to it later.

To deal with this, I figured I'd use a list of recipe blocks. Each recipe block has two recipes, a start recipe and an end recipe. For example, my first block will be:

1: 1
1: 1
Failed

The left-hand side is the recipe index, the right-hand side is the recipe combination. Though I'm considering getting rid of the combination altogether once I get an algorithm for generating it from the recipe index. Modulus arithmetic should be my savior there... In any case, this allows me to group results into blocks that have the same result. Since I expect untestables to be grouped together and successes to be rare, my overall disk usage for storing results should be quite low.

1 -> 5 : failure
6 -> 6 : success
7->200 : failure
201 -> 250 : untested
251 -> 271 : failure

etc.

Anything that is not already in a block is considered unknown/untested.

So... what I need/am working on is this:

1) algorithm for generating recipes from index

2) routines for updating knowledge base (set of recipe blocks with results) with new results.

3) routines for accessing a particular herb from an arbitrary herb container

I'm getting closer, but any help would be greatly appreciated.

Wil

Wil Hunt

P.S. My old Tower girl wanted to be a brown.. before I didn't play her enough and she got deleted. :( That count? ;)

GURU Joined: 10 Oct 2000 Posts: 4379 Location: USA

Here is a function to get the next number in the sequence:
#FUNC nextcomb {%exec("#VAR total 0;#LOOP 1,%len(%1) {#ADD total %copy(%1, %i, 1)};#IF (@total > %2) {#VAR num -1} {#VARIABLE num %1;#ADD num 1;#VAR total 0;#LOOP 1,%len(@num) {#ADD total %copy(@num, %i, 1)};#WHILE (@total > %2) {#ADD num 1;#VAR total 0;#LOOP 1,%len(@num) {#ADD total %copy(@num, %i, 1)}}};@num;#UNVAR num;#GAG;#UNVAR total;#GAG")}

Usage:
@nextcomb(num, base)

where num is the previous number in the sequence to the one returned and base is the number base to use for the sequence.

Examples:
#SH @nextcomb(11, 4)
#SH @nextcomb(22, 4)
#SH @nextcomb(34, 7)

shows:
12
30
40

Notes:

The function returns -1 when num is not part of the sequence for the specified number base.

The function may cause your MUD output to be "jumpy", especially when the next number in the sequence is much bigger than the current one. If you don't mind some extra variables hanging around, you can solve this by deleting all of the #UNVAR's and #GAG's.

The function is very messy and it could be a lot neater if a separate function to calculate the sum of the digits of a number is written. However, when I tried to do this, it did not work correctly because zMUD seems to execute the contents of the inner %exec's of nested %exec's in addition to returning the result.

By the way, %exec is really cool and full of possibilities.

I had not even thought about using it this way until Charbal suggested it in a recent post.

Kjata

Wanderer Joined: 08 Feb 2001 Posts: 89 Location: USA

Thanks, Kjata.

Thank you so much for putting that together. The only problem I had with it is speed. The time between 400 and 1000 (then next valid number) took 10 seconds or so on my PIII 733 512MB RAM. I can only imagine how bad it will be when I get to 40000000000 and need to skip to 100000000000.

It seems that there should be a short cut. Since any number with a 4 will be a 4 followed by some number of zeroes, the next valid number will be 1 followed by one more zero. Essentially if the digits to the left of a certain index sum our max, we should skip past all the number increments on the right to the next valid one.

1300000000000

since 1 + 3 is 4, our magic number, we ignore all the zeroes on the right. Then we can skip directly to 2000000000000.

Without some optimization procedure, this function will simply bog down since we have as many as 20 digits to deal with and 7 max ingredients.

Any ideas on that?

Wil

Wil Hunt

P.S. On a detail note, the second paramter is base-1 not base.

The sequence:

0,1,2,3,4,10,11,12,13,14,20, ...

is a base 5 sequence, not base four. But that's not relavent to the algorithm at hand.

Wanderer Joined: 08 Feb 2001 Posts: 89 Location: USA

Just a little data... I reran the number generator out until it reached 10000 (base 5). I got much better results when the variable inspection window was not open, but the results still look exponential:

Starting with a number of 0. Each call was framed by a %secs system call to provide the timing. The big jumps were from 4 and 0's to the next 1 and 0's. I've snipped the rest of the steps out to illustrate the exponential increase.




Next number: 1 (20 ms)


Next number: 4 (20 ms)


Next number: 10 (41 ms)


Next number: 40 (70 ms)


Next number: 100 (371 ms)


Next number: 400 (681 ms)


Next number: 1000 (4437 ms)


Next number: 4000 (7851 ms)


Next number: 10000 (51554 ms)

notice that the skip to 1 and 0's is on the order of magnitude of 10^digits ms. That's fine for small numbers but when we hit 20 digit long numbers.. ;)

10^20 ms is like 100 million billion seconds.

I'll try to digest your algorithm and find some optimizations, but in the mean time I'll put this out as a challenge to you guys. :)

I think the key is, as suggested above, cheating ahead when the sum of the current digits is maxsum. Then we need to figure out which digit(s) to decrease and then increase digits.

Any thoughts?

Wil

Wil Hunt

GURU Joined: 15 Jun 2001 Posts: 654 Location: USA

quote:

Yeah, we discussed that on the mud. One of the things I'm hoping to do, though (as I mentioned in our mud conversation), is to allow for a bit more flexibility.

[stare] Didn't know that was you :P

In any case, we need to make an algorithm for you...

It is easy to see that this problem is equivalent to having 20 distinguishable boxes in which you must place 7 or less indistinguishable balls.

So I attacked that problem and derived an algorithm to turn a number into its corresponding combination (and vice versa) in this lexigraphical ordering without generating all the previous ones.

It's Visual Basic but it demonstrates the algorithm :P




Public Function Comb(ByVal n As Long, ByVal r As Long) As Long


'Large operands may cause an overflow.


    Dim temp As Long, A As Long





    temp = 1


    For A = 0 To r - 1


        temp = temp * (n - A) / (A + 1)


    Next


    Comb = temp


End Function





Public Function Cr(ByVal n As Long, ByVal r As Long) As Long


    Cr = Comb(n + r - 1, r)


End Function





Public Function NumToCombR(ByVal n As Long, ByVal r As Long, ByVal x As Long) As String


    'Inputs: number of digits left to fill (n), number of available digits left (r), combination number (x).


    Dim p As Long, q As Long, A As Long


    If n < 1 Or x < 0 Or r < 0 Then


        NumToCombR = "": Exit Function


    End If


    If n = 1 Then


        NumToCombR = Str$(x)


        Exit Function


    End If


    p = 0


    q = 0


    For A = 0 To r


        p = p + Cr(n, r - A)


        If x < p Then NumToCombR = Str$(A) & NumToCombR(n - 1, r - A, x - q): Exit Function


        q = p


    Next


    NumToCombR = ""


End Function





Public Function CombRToNum(Combination As String, ByVal r As Long) As Long


    Dim temp As Long


    Dim Combo() As String


    Dim A As Long, B As Long


    Combo = Split(Trim$(Combination), " ")


    temp = 0


    For A = LBound(Combo) To UBound(Combo)


        For B = 1 To CLng(Combo(A))


            temp = temp + Cr(UBound(Combo) - A + 1, r)


            r = r - 1


        Next


    Next


    CombRToNum = temp


End Function

You'd be able to get better times than those posted above by using an algorithm similar to the preceding to convert from combination to number, add 1, then convert back to combination. If you want to keep something like your method, I'd recommend using an array to store the values.

I could give example code for something that would use this to take the execution time down to marginal levels if you need it. In any case, you'll need to do something since once you hit 20 digits, you won't be able to use integers since 20 decimal digits can exceed the maximum unsigned integer expressible with 64 bits (and zMUD's integers are signed 32 bit integers so it fails even sooner... at 10 digits).

Also, there are several ways you can use local variables in zMUD. The easiest would be to use VBScript or JScript and to let them handle the details.

Another way would be to emulate it yourself... make a variable called @Stack and then whenever you enter your recursive routine, use %push to put whatever variables whose contents you wish to save into this stack variable. For example,
#VAR Stack %push(@VarToSave, @Stack).
And then when you are done with the procedure, %pop your saved values in the reverse order back into the variables you got them from.

Also, on the %exec thing, I can't take credit for that... I didn't think of using it until Zugg suggested it to someone in the beta forum who wanted a way to do a loop inside a function.

- Charbal

Wanderer Joined: 08 Feb 2001 Posts: 89 Location: USA

Ok, I think my brain is slowly (but surely) getting somewhere now. I'm still a little muddled, so I'll try to work my way through my understanding of what you're doing. Please make sure that I'm not making any stupid misinterpretations. With any luck, by the time I'm done writing this post, I'll have something resembling a clue. :)

The first function is just a combinatorial function n choose r:




Public Function Comb(ByVal n As Long, ByVal r As Long) As Long


'Large operands may cause an overflow.


    Dim temp As Long, A As Long


    temp = 1


    For A = 0 To r - 1


        temp = temp * (n - A) / (A + 1)


    Next


    Comb = temp


End Function

And given this problems combinatorial nature, that doesn't surprise me. The next function, however, I'm not really sure what this will give us. Hopefully I'll understand this later...




Public Function Cr(ByVal n As Long, ByVal r As Long) As Long


    Cr = Comb(n + r - 1, r)


End Function

Obvious this returns (n+r-1)Choose(r), but I don't see the use of this yet...

This bring us to the first function with "meat." Given that...




sheath sword


draw dagger


butcher corpse


eat meat


sheath dagger


draw sword

(Sorry about the bad WOTMud joke...)




Public Function NumToCombR(ByVal n As Long, ByVal r As Long, ByVal x As Long) As String


    'Inputs: number of digits left to fill (n), number of available digits left (r),


    'combination number (x).

This is where I'm already lost... I don't think I really understand the meaning of the parameters.




    Dim p As Long, q As Long, A As Long


    If n < 1 Or x < 0 Or r < 0 Then


        NumToCombR = "": Exit Function


    End If

So after defining the variables, we're checking for conditions that will cause problems. This If block is just a sanity check then. If "insane" values are passed in, we return
an empty string.




    If n = 1 Then


        NumToCombR = Str$(x)


        Exit Function


    End If

If sane values are passed in and n is passed in as 1, then function returns the number x as a string, right?




    p = 0


    q = 0


    For A = 0 To r


        p = p + Cr(n, r - A)


        If x < p Then NumToCombR = Str$(A) & NumToCombR(n - 1, r - A, x - q): Exit Function


        q = p


    Next

Clearly this is the recursive meat of the function though I'm having trouble understanding it at all much less putting it into words. We have temporary variables p, q and A... all initialized to zero. p is somehow summing some set of combinations, though I'm not seeing the meaning of these combinations. This sum is done until p is greater than x which allows us to make the recursive call with NumToCombR.




    NumToCombR = ""


End Function

This shouldn't ever be reached. Presumably you're setting this to satisfy validation checks or insane possibilities.

I won't even start in on the next one until I get this cleared up. I'm a lot further along in understanding the algorithmm, but it's simply been too long since I've done any programming beyond GUI stuff. I think I can get there, but it'll take time. :)

Thanks again for your patience.

Take care,

Wil

Wil Hunt

GURU Joined: 15 Jun 2001 Posts: 654 Location: USA

quote:
And given this problems combinatorial nature, that doesn't surprise me. The next function, however, I'm not really sure what this will give us. Hopefully I'll understand this later...

Public Function Cr(ByVal n As Long, ByVal r As Long) As Long
Cr = Comb(n + r - 1, r)
End Function

Obvious this returns (n+r-1)Choose(r), but I don't see the use of this yet...

This function exists to count combinations with replacement. Replacement basically means that we can use an element more than once (once it is taken out of the bag of elements, it is put back in so it can be taken out again).

quote:




Public Function NumToCombR(ByVal n As Long, ByVal r As Long, ByVal x As Long) As String


    'Inputs: number of digits left to fill (n), number of available digits left (r),


    'combination number (x).

This is where I'm already lost... I don't think I really understand the meaning of the parameters.

n is the number of positions in your number that have yet to be filled (so you'll pass in 20). r is the maximum number of herbs that may be distributed among these n positions (so you'll pass in 7). x is the combination number, in the range 0 to
Cr(n, r) + Cr(n, r - 1) + Cr(n, r - 2) + ... + Cr(n, 1) + Cr(n, 0) - 1
(this number is merely the number of ways to use exactly r herbs plus the number of ways to use exactly r - 1 herbs plus ... plus the number of ways to use exactly one herb plus the number of ways to use no herbs. It is pretty clear that this is one less than the number of ways to pick at most r items with replacement from n items (one less since it is zero-based).

quote:

Dim p As Long, q As Long, A As Long
If n < 1 Or x < 0 Or r < 0 Then
NumToCombR = "": Exit Function
End If

So after defining the variables, we're checking for conditions that will cause problems. This If block is just a sanity check then. If "insane" values are passed in, we return
an empty string.

Yep.

quote:

If n = 1 Then
NumToCombR = Str$(x)
Exit Function
End If

If sane values are passed in and n is passed in as 1, then function returns the number x as a string, right?

That's correct. If n = 1, then we are dealing with the last digit of the combination. So the x value (the combination number) directly determines what the value should be here.

quote:

p = 0
q = 0
For A = 0 To r
p = p + Cr(n, r - A)
If x < p Then NumToCombR = Str$(A) & NumToCombR(n - 1, r - A, x - q): Exit Function
q = p
Next

Clearly this is the recursive meat of the function though I'm having trouble understanding it at all much less putting it into words. We have temporary variables p, q and A... all initialized to zero. p is somehow summing some set of combinations, though I'm not seeing the meaning of these combinations. This sum is done until p is greater than x which allows us to make the recursive call with NumToCombR.

p and q are set up such that q lags behind p and p is the first combination number greater than q whose combination representation differs from q's in the first digit. In other words, since q starts at zero, it's combination representation is exactly n zeroes so the first digit is a zero. p's combination representation then starts with a 1 and any number less than p does not have a combination representation starting with 1. So if x < p, then it is clear that x's combination representation does not start with 1. So it starts with 0 and the recursion considers the n - 1 remaining digits with however many herbs remain available for alottment at appropriate combination number.

This is repeated until a range of q and p is found that contains x.

quote:

NumToCombR = ""
End Function

This shouldn't ever be reached. Presumably you're setting this to satisfy validation checks or insane possibilities.

Indeed, it shouldn't be reached... but if x is greater than the allowable values, it could be reached. This makes sure that if you increment past the last permutation, you get an empty string.

- Charbal

GURU Joined: 10 Oct 2000 Posts: 4379 Location: USA

Just in case, here's the function modified to be more intelligent and quickly find out the next number in the sequence:
#FUNC nextcomb {%exec( "#VARIABLE total 0;#LOOP 1,%len( %1) {#ADD total %copy( %1, %i, 1)};#IF (@total > %2) {#VARIABLE num -1} {#VARIABLE num %1;#VARIABLE changed 0;#LOOP %len( @num),1 {#VARIABLE total 0;#LOOP 1,%i {#ADD total %copy( @num, %i, 1)};#IF (!@changed and (@total < 4)) {#VARIABLE num %concat( %left( @num, %i - 1), %eval(%copy( @num, %i, 1) + 1), %repeat( 0, %len( @num) - %i));#VARIABLE changed 1}};#UNVAR changed;#GAG;#IF (@num = %1) {#VARIABLE num %concat( 1, %repeat( 0, %len( @num)))}};@num;#UNVAR num;#GAG;#UNVAR total;#GAG")}

Kjata

Wanderer Joined: 08 Feb 2001 Posts: 89 Location: USA

Wonderful, Kjata! That's great!

Thanks again,

Wil

Wil Hunt