Took you long enough, I saw you browsing this topic quite some time ago. ;)
Getting 30 seconds out of that should be easy. Delay is 28 seconds, a 7 minute movie shouldn'd have more than like 18 seconds human delay. Then I saw at least 20 unnecessary steps in that execution, another 4 seconds. That's half of it without changing the route at all.
hehe, I was playing this game & checking other forums, also later I played chess at FICS... Anyway, finally got to beat level 5-1 & took me around 4'40 (yikes, that was slow) I though on some improvements for my strat, but as I saw your video, you already were ahead of me & made them...
15 levels to go (for me)...
Edited: Hey Gorash, I just trashed your 9-1 record by almost 3 minutes, I didn't checked your video, but I think you just played once if I'm not mistaken ;)
9-1? I'll see to that in a minute.
First things first: Bad Warp. Beating my 5-2 and not telling me! The result is the all the same though, it's mine again.
EDIT: About 9-1 goroh:
Yes that was a first time completion. And your route is not half bad, I tried beating it for half an hour, no chance.
My original route was left side first and then unravelling the right side from below. It feels faster, and I'm sure there has to be a clue in it, but I still have about 30 steps more than you. I think I just need some sleep.
As for 5-1:
4:40 isn't a bad time. My first optimised version had a time around that. After that the battle with Warp started about that level. I'm still not entirely happy with the last 5 boxes in the right, but this is the fastest route to date. If you find something, let us know. :)
About 9-1 goroh:
Yes that was a first time completion. And your route is not half bad, I tried beating it for half an hour, no chance.
My original route was left side first and then unravelling the right side from below. It feels faster, and I'm sure there has to be a clue in it, but I still have about 30 steps more than you. I think I just need some sleep.
As for 5-1:
4:40 isn't a bad time. My first optimised version had a time around that. After that the battle with Warp started about that level. I'm still not entirely happy with the last 5 boxes in the right, but this is the fastest route to date. If you find something, let us know. :)
Well, for level 9-1 I had to played it a few times because I always missed something, so ideas came while re-starting that level. Still I made a couple of minor mistakes IIRC...
As for level 5-1, my brother deleted the cookies, so bye bye to all my times :(. That level cost me a lot & only beat it once, so it'll take me some tries to get it again, hope not to many...
BTW, I took your 12-3 record. Dunno if my strat is faster, but I think it looks nicer :)
PS: Hey Warp, I just recuperated my 11-1 record. BTW, the strat I used can be optimised by about 3.6 secs...
As for level 5-1, my brother deleted the cookies, so bye bye to all my times :(. That level cost me a lot & only beat it once, so it'll take me some tries to get it again, hope not to many...
Yeah, well... in that case just forge it into place.
The cookie syntax isn't that complicated to recreate, and if you give yourself a completion time of 10 minutes it won't ask you to submit new records all the time.
I lost my cookie three times now. And now I keep a backup file with the particular lines for each level from the cookie, so in case I lose it again I can just recreate it.
12-3 huh? Oh dear, all my precious records...
EDIT: D'oh, what a complicated route. It's too hot in here for me to think that one up now. I'll look into it this afternoon...
Hehe, I found a better path & took warp's 3-5 record. With all the lag I had, it can be improved by around 2.5 secs. So I bet warp will want to recuperate it ASAP :P
BTW Bisqwit, have you tried more levels for Bisqbot? Maybe it can tackle level 3-3 by now, don't you think?
Edited: Now I took level 4-3. Not sure of my strat was better, but I guess Warp didn't played again when the turn lag was removed...
Have you tried throwing away the caching of blunder situations and computing them again everytime?
That would reduce complexity of the game space by at least one order of magnitude for some levels, although extending the time of computation a lot...
You could also merge walking and push/kicking into one cycle, reducing the intermediate situations that need to be saved.
Another idea I see from your tech description would be only saving the last (best) move (10 bit for desciption of the starting position of kick/push, other 6 bit for length of pushing, 0=kick, implies that peter has moved there from last position) and the framecounter after the situation, and then reconstructing the movie after the puzzle is solved. Would save a little memory.
Is it possible to get a glimpse on the source? :)
About 3-5: Ouch, what a simple change... *bangs-head-to-table*
Have you tried throwing away the caching of blunder situations and computing them again everytime?
In the beginning, some cache is created of blunder situations, and that cache takes relatively very little memory compared to the amount of iterations (and thus, memory) it saves.
> You could also merge walking and push/kicking into one cycle, reducing the intermediate situations that need to be saved.
Already done.
> Another idea I see from your tech description
Which, is very outdated.
> would be only saving the last (best) move (10 bit for desciption
> of the starting position of kick/push, other 6 bit for length of pushing,
> 0=kick, implies that peter has moved there from last position) and
> the framecounter after the situation, and then reconstructing the
> movie after the puzzle is solved. Would save a little memory.
The problem is that there still needs to be a container that can answer the question "has this situation been tested before?" and also "if the situation was tested before, did we reach the situation now faster than we did back then?".
Therefore, all the game states need to be saved.
Otherwise you can't know whether you're progressing at all, or if you're just pushing the same boxes back and forth.
The storage for those situations is currently a very effecient implementation of a radix tree. The level itself is compressed as an arbitrary-precision integer that is mathematically composed of the positions of the player and the boxes, with a coordinate system that only allows valid non-blunder positions.
A state of the level 3-2, for example, where there are 10 boxes + player, takes only 8 bytes.
In 3-2 you see, there are 70 possible locations on floor for the player to reside in, and 46 possible locations for boxes. But since two boxes can't be placed in same coordinate, the number of possible locations for boxes is actually 36 when considering the other boxes too. For the blunder checker, +1 is added to allow boxes to be removed from the field.
Thus, the state of the level 3-2 is stored in ceil(log2(70*37^10)/8) bytes, that is, 8 bytes.
> Is it possible to get a glimpse on the source? :)
Due to the possibility that someone might abuse it, I'm keeping it closed. Of course, someone might still create a similar effort, but from my experience, I think that's rather unlikely.
But ok, I will offer a glimpse :)
> would be only saving the last (best) move (10 bit for desciption
> of the starting position of kick/push, other 6 bit for length of pushing,
> 0=kick, implies that peter has moved there from last position) and
> the framecounter after the situation, and then reconstructing the
> movie after the puzzle is solved. Would save a little memory.
The problem is that there still needs to be a container that can answer the question "has this situation been tested before?" and also "if the situation was tested before, did we reach the situation now faster than we did back then?".
Therefore, all the game states need to be saved.
Otherwise you can't know whether you're progressing at all, or if you're just pushing the same boxes back and forth.
Er, clarification of the idea:
What if your map uses compressed situations as keys (as now?) and saves the last move plus the overall framecount of that solution as values.
Pseudocode after you built the list of situations s' that can be generated from a situation s by /walk*(kick|push*)/:
for each situation s' do
m := moves needed from s -> s'
compute framecount(s') := framecount(s) + framecount(m)
lookup s' in the map of situations
if s' exists then
if framecount(map(s')) > framecount(s') then
map(s') = {m , framecount(s')} // replace with better solution
fi
else
map(s') = {m , framecount(s')} // initial entry
fi
od
After you found the goal solution you can work your way backwards, by identifying the situations that could have leaded to this situation, looking them up and checking if the framecount matches.
A state of the level 3-2, for example, where there are 10 boxes + player, takes only 8 bytes.
In 3-2 you see, there are 70 possible locations on floor for the player to reside in, and 46 possible locations for boxes. But since two boxes can't be placed in same coordinate, the number of possible locations for boxes is actually 36 when considering the other boxes too. For the blunder checker, +1 is added to allow boxes to be removed from the field.
Thus, the state of the level 3-2 is stored in ceil(log2(70*37^10)/8) bytes, that is, 8 bytes.
Hmm, my personal calculation says:
10 boxes disregarding order in 46 places are binom(46,10) possibilities. Since this will be a compressed representation you can check for blunders before it, so no need to include blunder stuff. In each of these situations Peter may be in 70-10 positions on the field, so the upper bound for the length of optimal coding is ceil[ld(binom(46,10)*(70-10)/8)] = 5 bytes. Finding a number to represent each situation is also possible (requires you to build a cache of (block# x position) --> initial coding, the coding can then be gotten by adding up the cached values).
Due to the possibility that someone might abuse it, I'm keeping it closed. Of course, someone might still create a similar effort, but from my experience, I think that's rather unlikely.
Oh, I think that too, or else I'd just have started a solver myself :D. I also don't want to lessen your efforts, if I read that glimpse correctly the actual stuff is a lot more. No Perl one-liner this time.
(and if I wrote total bull, don't hesitate to explain why)
What if your map uses compressed situations as keys (as now?) and saves the last move plus the overall framecount of that solution as values.
You are trying to optimize wrong issue.
The size taken by the list of attempted moves is not an issue. The current program uses generally 5-6 bytes per move (including the link to the previous move). At worst it has taken about 600 MB of memory, even if the unworthy moves are never deallocated. This memory is currently taken from a temporary file, so it's really not an issue at all. At any given moment, it only reserves at most 2 MB of the program's address space.
This wasn't the situation when I wrote the technical explanation though.
I'm also doing the same treatment (temporary file with portions mmapped and munmapped on fly) for the TODO-list of board positions. The size of that list may approach 4 GB, but it is not an issue: an address space of 16 TB may be used for them, if only the disk space allows it. They are stored in a disk-backed ring buffer.
> Hmm, my personal calculation says:
10 boxes disregarding order in 46 places are binom(46,10) possibilities.
I am not familiar with this "binom()" expression you use, and I don't know how to convert it into an integer.
And I certainly don't know how to form an integer from those 10 block positions according to this binom() rule.
I think you might be right however.
In Finnish lottery, there are 7 numbers chosen from the 1..39 range. According to Wikipedia, the number of possible combinations is 15380937. According to my formula, it would be 34359738368 ((39-7)^7).
I don't understand where the difference comes from.
With Google, I found that the formula (for lottery) is 39! / (7! * (39-7)!), but I still don't understand.
[Edit 2]: Okay, now I do. My coordinate system _allows_ expressing the same board configuration with different numbers (different order of blocks), even though the game can never generate more than one of them. (The block position list is always in a coordinate-sorted order.)
In other words, my coordinate system stores the delta between each two coordinates (and the first coordinate position), and the maximum theoretical sum of those delta values is greater than the actual maximum possible sum of the delta values.
So now I need a new method of enumerating the board configurations.
The current algorithm is here:
function GetCompactData returns bigint
{
bigint result;
result = PlayerCoordinateTranslation(playerpos);
int last = BlockCoordinateTranslation(blockpos[1]);
result *= PlayerCoordinateLimit;
result += last;
int limit = (BlockCoordinateLimit - NumBlocks);
for(int blockno = 2 to NumBlocks)
{
int coord = BlockCoordinateTranslation(blockpos[blockno]);
result *= limit;
result += coord-last-1;
last=coord;
}
return result;
}
Where PlayerCoordinateTranslation is a static table of that maps real player coordinates into those "allowed player coordinates", and PlayerCoordinateLimit is the number of those "allowed player coordinates",
and Block* are respectively the same for blocks.
> In each of these situations Peter may be in 70-10 positions on the field
Now that you mention it, in fact, Peter may be in 41 different positions as most, because he's always either in the beginning location or facing one of the boxes from some direction.
The intermediate walking positions are not seen by the solution finder except when calculating how many steps are there from point A to point B (for the cost).
But this difference only saves 0.1 bytes. :)
([Edit]: In 2-2, there are 49 points of floor. 49 points where Peter can stand. But there are 13 blocks. If using the method explained above, Peter has 13*4+1=53 different points. However, such space-cramped levels are rare.)
> if I read that glimpse correctly the actual stuff is a lot more.
Yes, that particular code are the template functions which are responsible of loading/generating&saving maps of dead N block position combinations (where N is an integer template parameter).
What if your map uses compressed situations as keys (as now?) and saves the last move plus the overall framecount of that solution as values.
You are trying to optimize wrong issue.
The size taken by the list of attempted moves is not an issue. The current program uses generally 5-6 bytes per move (including the link to the previous move). At worst it has taken about 600 MB of memory, even if the unworthy moves are never deallocated. This memory is currently taken from a temporary file, so it's really not an issue at all. At any given moment, it only reserves at most 2 MB of the program's address space.
This wasn't the situation when I wrote the technical explanation though.
I'm also doing the same treatment (temporary file with portions mmapped and munmapped on fly) for the TODO-list of board positions. The size of that list may approach 4 GB, but it is not an issue: an address space of 16 TB may be used for them, if only the disk space allows it. They are stored in a disk-backed ring buffer.
At this point I lose because I don't know the internals of your program, but the idea was to store nothing else than this one map. It is enough to restore the movie afterwards. Ignore this part if it makes no sense.
[ ... ]
So now I need a new method of enumerating the board configurations.
Since you figured out the binomial coefficent you might as well use them. The abbreviation binom derives from the Latex command for the vertical alignment of the variables \binom{n}{k}... sorry to confuse you.
How about this:
Assume you already have enumerated playerpositions and non-blunder blockpositions and have translation functions.
Let us make a field of 4 block positions with 2 block in them as example:
I'll represent it as an array containing x's where a box is, and . where a space is.
The number of all combinations is binom(4,2) = 4!/2!(4-2)! = 6 as you've found out:
[xx..] [x.x.] [x..x] [.xx.] [.x.x] [..xx]
These are sorted in a way, that those with boxes on the left are sorted first.
Now using the above formular lets count some of the subsets:
- If the first position is taken by a box, then the rest of the array is filled with 3 out of 1 = binom(3,1) = 3 positions before the first box is altered.
If you generalise that, it follows:
If a the n-th box if on position m, The pattern up to that will stay the same for binom(4-m, 2-n) positions.
And if you then go a step further and make the number of block-places and the number of blocks variable:
For box n out of N on place m out of M, the number of combinations of the rest of the boxes is binom(M-m, N-n).
The number of a combination of boxes can then be computed by adding up the possible combinations of each position where no box (position m) is if there had been the next box (box n+1).
A few examples from above?
(Note: This depends on the agreement that 0! = 1 and that invalid binomials compute to 0, a common agreement for these purposes)
M and N are constant for the analysis of one puzzle, so all you have to do is cache the values of binom(M-m, N-n) at the start of the analysis, which is in O-space(M²), and while computing you can just sum them up to get your optimal coding.
Errr, I hope that was understandable...
To get peters position into it, just multiply the box-number with the number of positions peter may have and add his position.
> In each of these situations Peter may be in 70-10 positions on the field
Now that you mention it, in fact, Peter may be in 41 different positions as most, because he's always either in the beginning location or facing one of the boxes from some direction.
The intermediate walking positions are not seen by the solution finder except when calculating how many steps are there from point A to point B (for the cost).
But this difference only saves 0.1 bytes. :)
([Edit]: In 2-2, there are 49 points of floor. 49 points where Peter can stand. But there are 13 blocks. If using the method explained above, Peter has 13*4+1=53 different points. However, such space-cramped levels are rare.)
Not that it matters, but couldn't peter stand a little bit away from a box after kicking?
I have to say that you lost me on the explanation of enumerating board positions.
As you already know, I need a method to convert an array of block positions (which are assumed to be sorted in ascending order) into an integer.
I'll try to analyze your post better when I'm better awake.
> Not that it matters, but couldn't peter stand a little bit away from a box after kicking?
Yes, I think this point invalidates my idea. The shape of the level immediately after kicking is indeed stored to the radixtree, and thus the optimization on Peter's position can't be taken. However, your idea to eliminate the coordinates that coincide with boxes' locations still applies.
I have to say that you lost me on the explanation of enumerating board positions.
As you already know, I need a method to convert an array of block positions (which are assumed to be sorted in ascending order) into an integer.
I'll try to analyze your post better when I'm better awake.
*Sigh* I feared so...
I tried to intercept you in your irc chan, but you were already off.
I'll try tomorrow again. I really want to see more perfect solutions. :P
In that case, would you like to try writing out the Sum3() function to this test program?
It should be generalized enough so that the number of blocks (and number of coordinates) can be later tuned at compile time (but not runtime) without touching the source code.
#include <cstdio>
#include <set>
#include <iostream>
#include <algorithm>
/* Calculates the C(N,k) function. */
unsigned Choo(unsigned N,unsigned K)
{
unsigned long long nom=1, denom=1;
std::cout << "C("<<N<<","<<K<<")=";
while(K > 0)
{
nom *= N--;
denom *= K--;
/* Use euclidean GCD algorithm to simplify nom/denom */
/* In order to make integer overflows unlikely.
* They still do happen easily though.
*/
unsigned long long gcd = std::min(nom,denom), util=std::max(nom,denom);
for(;;)
{
unsigned long long tmp = util % gcd;
if(!tmp)break;
util = gcd;
gcd = tmp;
}
nom /= gcd;
denom /= gcd;
}
std::cout << nom/denom <<" (nom="<<nom<<",denom="<<denom<<")\n";
return nom/denom;
}
/* Introducing three methods of converting an array
* of 4 elements in range 0-99 into a single unique integer.
*/
/* Easiest method. Output value range: 100^4. */
unsigned Sum1(unsigned Buf[4])
{
unsigned result=0;
for(unsigned a=0; a<4; ++a)
{
result *= 100;
result += Buf[a];
}
return result;
}
/* Sum2 is Sum1 altered to take advantage of the assumption
* that the input values are (1) ordered and that (2) same
* value will not appear twice.
* Output value range: (100-4)^4
*/
unsigned Sum2(unsigned Buf[4])
{
unsigned result=0;
unsigned last = Buf[0];
result += last;
unsigned limit = 100-4;
for(unsigned a=1; a<4; ++a)
{
unsigned coord = Buf[a];
result *= limit;
result += coord-last-1;
last=coord;
}
return result;
}
/* Sum3 should, in theory, output values in range C(100,4),
* that match the same uniqueness rule as Sum1 and Sum2
* already do. But somehow we're not there yet. This is a FIXME.
*/
unsigned Sum3(unsigned Buf[4])
{
unsigned result=0, scale=0, begin=0;
for(unsigned a=0; a<4; ++a)
{
result *= Buf[a]-scale;
result += Buf[a]-begin;
scale = begin;
begin = Buf[a]+1;
}
result *= 100-scale;
return result;
}
int main(void)
{
Choo(100,4); /* Outputs 3921225, which is the value of "100 choose 4". */
/* This loop verifies that the functions work as supposed to.
* Tests performed:
*
* - Verify that all Sum() functions match the same rules of uniqueness
* - Verify that Sum3() won't create values greater or equal to C(100,4).
*/
std::set<unsigned> set1,set2,set3;
for(unsigned a=0; a<1000000; ++a)
{
Retry:
unsigned Buf[4];
Buf[0] = rand()%100;
Buf[1] = rand()%100;
Buf[2] = rand()%100;
Buf[3] = rand()%100;
std::sort(Buf,Buf+4);
if(Buf[0]==Buf[1]
|| Buf[1]==Buf[2]
|| Buf[2]==Buf[3]) goto Retry;
unsigned s1 = Sum1(Buf);
unsigned s2 = Sum2(Buf);
unsigned s3 = Sum3(Buf);
bool f1 = set1.find(s1) != set1.end();
bool f2 = set2.find(s2) != set2.end();
bool f3 = set3.find(s3) != set3.end();
std::printf("%2u-%2u-%2u-%2u: s1=%u,s2=%u,s3=%u f1=%s,f2=%s,f3=%s\n",
Buf[0],Buf[1],Buf[2],Buf[3],
s1,s2,s3,
f1?"true":"false",
f2?"true":"false",
f3?"true":"false"
);
if(f1 != f2
|| f1 != f3
|| s3 >= 3921225)
{
abort();
}
set1.insert(s1);
set2.insert(s2);
set3.insert(s3);
}
return 0;
}
Pff... pretending to go sleeping but coding...
This is your function commented and readable (and I hope at least somewhat understandable)
/* Sum3 should, in theory, output values in range C(100,4),
* that match the same uniqueness rule as Sum1 and Sum2
* already do. But somehow we're not there yet. This is a FIXME.
*/
unsigned Sum3(unsigned Buf[4])
{
// change these to compile time later
unsigned B = 4; // block count
unsigned P = 100; // position count
unsigned bufi = 0, // index in buffer
result = 0; // result
// iterate through block positions
for (unsigned bp=0; bp<P; ++bp)
{
// if the current position is used by a block,
// use next one. if the current one was the last one
// return the result up to that point since it will not
// further increase
if (Buf[bufi] == bp)
{
bufi++;
if (bufi == B)
return result;
continue;
} else
{
// if not, add the number of combinations
// the rest of the field COULD have with
// a box at this position.
// We have B-bufi-1 boxes left.
// We have P-bp-1 positions left.
result += Choo(P-bp-1, B-bufi-1);
}
}
}
and in plain version, slightly compressed and altered for common case first:
unsigned Sum3(unsigned Buf[4])
{
unsigned B = 4; // block count
unsigned P = 100; // position count
unsigned i = 0, result = 0;
for (unsigned bp=0; bp<P; ++bp)
if (Buf[i] != bp)
result += Choo(P-bp-1, B-i-1);
else {
if (++i != B)
continue;
return result;
}
}
A few things:
- You want to disable your debug echos in Choo or you'll get spammed.
- I was too lazy to lookup the compile time syntax...
- Since all those Choos take some time one should cache them at compile time, either manually or by abusing templates, then the Sum3 will be constant in time for constant positions. Unfortunately I'm rather bad at advanced C++...
I just noticed this topic so I'm a little behind current affairs, only up to level 5-1, but very fun so far.
I have only noticed two bad/annoying things, sorry if they are mentioned as I didn't read pages 4-9:
When you kick a box pressing a direction interrupts this, this is really annoying if you are trying to go fast.
When I press space bar to undo, for some reason some of the time instead of undo it just restarts the level. This basically just makes be careful because I can never rely on an undo.
I am using the browser Camino which is like firefox for mac. Safari didn't work.
The optimal solver program is interesting, I am tempted to try and write my own, but it looks like yours is pretty good already so I might just be wasting my time.
When you kick a box pressing a direction interrupts this, this is really annoying if you are trying to go fast.
As I have already saíd several times, it's a question of whether we want to compete on who has the most skill on playing this game requiring reflexes and good timing and finding the optimal path for a level, or do we want to compete simply on who can find the optimal path first.
Certainly if kicks were uninterruptible then the whole competition in this game would be who is the first to complete a level (with an optimal path). Since uninterruptible kicks would make it more or less trivial to get the optimal time, that would kill all competition (unless someone can find a better path). Only the longest levels would have some competition (because long runs are more prone to errors and to path optimization). Shorter levels would just be immediately sealed by the first one who gets to play them. In the latters it would thus not be a question of skill, but more a question of timezone (ie. who is awake at the time the change to the kick routine is made). Is that really what we want?
The optimal solver program is interesting, I am tempted to try and write my own, but it looks like yours is pretty good already so I might just be wasting my time.
The solver requires quite advanced data containers (in terms of efficiency, both speedwise and especially memorywise) and algorithms. You can try if you want... :P
Gorash, can you make a version that iterates over B instead of iterating over P?
Edit: And another thing...
Your function gives the same result, 2185700, for both 18-23-45-59 and 18-23-45-96.
My C() function is now this:
/* Calculates the C(N,k) function. */
unsigned long long Choo(unsigned N,unsigned K)
{
if(K == 0) return 0;
// std::cout << "C("<<N<<","<<K<<")=";
unsigned long long Result = N;
if(K > 1)
{
if(N <= K) return 0;
Result = Result * Choo(N-1,K-1) / K;
}
// std::cout << Result << "\n";
return Result;
}
And Sum3 is:
unsigned Sum3(unsigned Buf[4])
{
unsigned B = 4; // block count
unsigned P = 100; // position count
unsigned i = 0, result = 0;
for (unsigned bp=0; bp<P && i<B; ++bp)
if (Buf[i] == bp)
++i;
else
result += Choo(P-bp-1, B-i-1);
return result;
}
As I have already saíd several times, it's a question of whether we want to compete on who has the most skill on playing this game requiring reflexes and good timing and finding the optimal path for a level, or do we want to compete simply on who can find the optimal path first.
Complaints are useless without suggested improvement, so here's both:
To me it makes more sense to base it more on who can figure out the optimal path first. As it is now, if you are good at kicking all you have to do to steal a record is beat some level using the worst path in the world then you can look how the record holder does it then you can just copy it exactly but kick slightly better. Then whoever figured out the smart path gets no credit. So like you said it is a question of timing versus thinking, but I choose thinking.
Besides I would consider this a fault in the controls, its not intuitive and why would you ever want to cancel a kick? Good games have good controls, you do not see Link canceling his sword swing if you move too soon. If this were the case, probably none of us would have ever heard the world Zelda. I am just a big believer in good controls, I feel the challenge should come from the design of the levels and monsters and stuff not from the controller.
It probably should stay the way it is though, since this has been here a while and people have spent good time optimizing with these controls it would be terribly mean to void all their work. Perhaps in the high scores, list who discovered currently known theoretical fastest path first? Theoretical fastest time for a path can be calculated pretty easily right?
Gorash, can you make a version that iterates over B instead of iterating over P?
Edit: And another thing...
Your function gives the same result, 2185700, for both 18-23-45-59 and 18-23-45-96.
unsigned Sum3(unsigned Buf[4])
{
unsigned B = 4; // block count
unsigned P = 100; // position count
unsigned i = 0, result = 0;
for (unsigned bp=0; bp<P && i<B; ++bp)
(Buf[i++]!=bp)?result+=Choo(P-bp-1, B-(--i)-1):0;
return result;
}
As for iterating over B, no I can't... I thought I'd have found an algorithm to do that yesterday, but it doesn't work like I want, so you have to stick with the long version for now.
Your Choo function is broken then...
I replaced your original function with the new one, and I get the same error.
I haven't got infinite time atm, so I'll see if I can find a fast implementation of binomials this evening.
Your Choo function is broken then...
I replaced your original function with the new one, and I get the same error.
You are right. Okay then, I'll try using this!
Edit: Apparently, it's the "if(K==0 || N<K) return 0;" rule which breaks it. Hmhm.
Edit 2: Right, because it should have been "if(K==0) return 1;".
Edit 3: It works, and is in use, and using the mpz_bin_uiui function of GMP, it isn't very slow either
Let's see what kind of effect it has. :)
If you still want it, I found a way to compute it by iterating through the boxes:
unsigned Sum3(unsigned Buf[4])
{
unsigned B = 4; // block count
unsigned P = 100; // position count
unsigned result = 0; int lBuf = -1;
for (int i=0; i<B; i++) {
result += C(P-lBuf-1, B-i) - C(P-Buf[i], B-i);
lBuf = Buf[i];
}
return result;
}
where C(n,k) is the binom function of your choice
The general idea was that the first one generates lines in the Pascal's triangle, which can be summed up by exploiting the properties of binmials.
It doesn't like one of your functions, but since you're using a library function now it should be fine.
