Programming Challenge 2004.2

[tim_m]

i was going to look at the first challenge for reference but it seems to have been pruned or i just can't find it.....

anyway, here's the new challenge. it's pretty much based on this page

Simulate a simple model of aggregation on a 2D grid: start with a single black cell, and at each step fill in a random white neighbor of a randomly selected existing black cell.

Here's how it works. Have a 2D grid of black and white cells (1s and 0s). Start with a single black cell. At each step, select at random an existing black cell that has at least one white neighbor. Then select a neighboring white cell at random, and make it black. (By neighbor we mean a cell above, below, left or right--not diagonal.)

also, all cells are white to start out (it says it somewhere on that page but it's kinda obscure)

to adapt it to be more generalized, not mathmatica,

• you don't necessarily have to have a 2 dimensional array. whatever method you think will work. a 2d array may be the easiest to work with or not, just depends how you feel i suppose
• you need to be able to choose how many cells to create, like what size to make a 2d array
• you need to randomly pick a starting cell
• you need to be able to aggregate the cells untill they are all black
• it would be helpful to have an option to print a representation of the cells at each iteration
• it would be good to be able to choose to only do a certain number of iterations. then when you show the array, you can see the pattern of growth

i'm not exactly sure what i'll be judging on.
possible list in no particular order

• possibly speed, but that might vary to much between programming languages.
• efficiency - not so much speed, but does the code do what it does in the best way
• definately style

an illustration of what should happen where # is the number of times it's aggregated (. is white and + is black):

    0           1           2
 . . . .     . . . .     . . . .
 . + . .     . + + .     . + + .
 . . . .     . . . .     . + . .
 . . . .     . . . .     . . . .

    3           4           5
 . . . .     . . . .     . . . .
 . + + .     . + + .     . + + +
 . + . .     + + . .     + + . .
 . + . .     . + . .     . + . .

    6           7           8
 . . . .     . . . .     . . . .
 . + + +     . + + +     . + + +
 + + . .     + + + .     + + + .
 + + . .     + + . .     + + + .
And so on...

on a larger scale, a pattern like the following might emerge after a lot of iterations but before all the white cells are gone

 . . . . . . . . . . . . . . .
 . . . . . . . . . . . . . . .
 . . . . . . . . . . . . . . .
 . . . . . . . . . . . . . . .
 . . . . . . . . . + + + + . .
 . . . . . . . . + + + + + + .
 . . . . . . . + + + + + + . .
 . . . . . . . + + + + + + . +
 . . . . + + + + + + + + + + +
 . . . . + . + + + + + + + + +
 . . . . . . + + + + + + + + .
 . . . . . . + + + + + + + + +
 . . . . . . + + + + + + + . .
 . . . . . . . + . + + + + + .
 . . . . . . . . . + + . . . .

or

 . . . . . . . . . . . . . . .
 . . . . . . . . + + + + . . .
 . . . . . . . . + + + . . . .
 . . . . . . + + + + + . . . .
 . . . . + + + + + + + + + . .
 . . . + + + + + + + + + + . .
 . . . + + + + + + + + + + + .
 . . . . + + + + + + + + + + .
 . . . . . + + + + + + + + + .
 . . . . . + + + + + + + + . .
 . . . . . . . + + + + . . . .
 . . . . . . . . + + + . . . .
 . . . . . . . . . . . . . . .
 . . . . . . . . . . . . . . .
 . . . . . . . . . . . . . . .

i already made a command line program to do this mainly so i understood the challenge before describing it to everybody and it also helped me illustrate it above. also, i'm working on making a java applet to better represent this (but this is my first real applet, i have something that looks good in the standalone applet viewer but it's messed up in a browser)

i'll be testing these out on my college's computer science department server so i should be able to accept anything in java, c, c++, ada, and possibly pascal [and perl and php], i may need help compiling ada and pascal programs. sorry, that's all that's installed on the server. if i end up comparing times, they'll all have to be run on the same computer (can't do it on mine because cygwin screwed up the gcc compiler on my computer)

i'm sure there will be changes made as necessary but for now, here we go. also, no specific deadline. as always, be sure to ask questions. i'll clarify as best i can. [i'll try to denote edits in brackets]

...sorry i couldn't post this sooner.

 

[carl67lp]

Cool! This should be a lot of fun. I'm glad to see you posted the new challenge. I hope this can be an at least monthly event.

Question: I was planning on doing this challenge (and all future challenges) in Perl. Most servers have it. Is that acceptable?

 

[:LJ:]

Nice one Tim - this one's a little more challenging that the last.

Question is, can anyone come up with an n-dimensional version? Or get away from using the random functions? I've got a couple of ideas on the n-dimensional thang, but I think this one's going to take a bit more thinking about that the previous challenge.

My only criticism would be that it will produce more interesting results if it were based on rules as well as the random factor - thus producing a semi-chaotic system with generally reproducible results. Or perhaps base it on fractal patterns.

Just some suggestions really - if anyone objects to me posting ideas, let me know and I'll scrub this post (don't want to affect the competition....).

Good luck everyone!

 

[carl67lp]

Originally posted by :LJ:
Nice one Tim - this one's a little more challenging that the last.

It is indeed more challenging. But you have to start easy to get interest building.

 

[:LJ:]

Originally posted by carl67lp
It is indeed more challenging. But you have to start easy to get interest building.

It wasn't a criticism of your challenge - the challenge in yours was to make it quick and minimise the amount of extraneous components. In this one, I think the challenge is more a case of style and logical thinking.

 

[carl67lp]

Originally posted by :LJ:
It wasn't a criticism of your challenge - the challenge in yours was to make it quick and minimise the amount of extraneous components. In this one, I think the challenge is more a case of style and logical thinking.

Oh, I know it wasn't a criticism. I much prefer style and logical thinking anyhow, so I'm eager to start on this challenge.

 

[FuzzyDonkey]

Not that I'd do it this way, but could we get points for lack of style (or perverted sense of style?), like the IOCCC?

 

[:LJ:]

Well, we did a lot of work on n-dimensional calculations when I was at university, so I'm going to work on a generic solution. I'm just not sure how to go about constructing an n-dimensional representation (logical and graphical) of the structure in the languages I'm good with (VB and Java). I can also pretty much guarantee that it's going to be an absolute memory hog. And it probably won't be particularly speedy for > 4 dimensions.

 

[tim_m]

Originally posted by carl67lp
Cool! This should be a lot of fun. I'm glad to see you posted the new challenge. I hope this can be an at least monthly event.

Question: I was planning on doing this challenge (and all future challenges) in Perl. Most servers have it. Is that acceptable?

that's fine too, i was only thinking about languages i would need to compile, i just forgot about perl. i guess one could also write a cli php version too

 

[tim_m]

Originally posted by FuzzyDonkey
Not that I'd do it this way, but could we get points for lack of style (or perverted sense of style?), like the IOCCC?

maybe if one provided a 'normal' and obfuscated version of the code. but i think i'd have a hard time going through the obfuscated version

link if you don't know (like i didn't) or don't want to search
http://www.ioccc.org/

 

[FuzzyDonkey]

I'm doing it in python. I don't care if it gets evaluated or not, I'm just doing it for kicks anyway.

 

[tim_m]

Originally posted by :LJ:
Question is, can anyone come up with an n-dimensional version? Or get away from using the random functions?
....
My only criticism would be that it will produce more interesting results if it were based on rules as well as the random factor - thus producing a semi-chaotic system with generally reproducible results. Or perhaps base it on fractal patterns.
....
Just some suggestions really - if anyone objects to me posting ideas, let me know and I'll scrub this post (don't want to affect the competition....).

making it 3d shouldn't be that hard to implement, but graphically representing it is way beyond my knowledge at this point. any dimension > 3 is probably beyond me as well at this point

i also don't know how to use a 'standard' random factor. although i'd love to find out, especially about using fractals.

suggestions are fine, they can make us think more, but for now, i won't change the rules. i think using something like fractals is beyond many 'average' programmers' skills (including me )

 

[:LJ:]

Originally posted by tim
suggestions are fine, they can make us think more, but for now, i won't change the rules. i think using something like fractals is beyond many 'average' programmers' skills (including me )

I wasn't after changing the rules - my assumption was that the more fancy (I mean this as functional complication, if there is such a thing) the solution, the better chance there was of winning.

 

[FuzzyDonkey]

Originally posted by tim
making it 3d shouldn't be that hard to implement, but graphically representing it is way beyond my knowledge at this point. any dimension > 3 is probably beyond me as well at this point

making *this* n-dimentional isn't that hard (displaying it is), but like LJ said, finding a computer to run any it on for any significant number of dimensions, for grid size bigger than 1, would be.

 

[:LJ:]

Out of curiosity, how big is the test grid going to be (roughly)? It'll have a bearing on the coding, because (for Java in particular), and arbitrarily large grid (say, 100k square) would cause major memory problems when points are stored as objects, so it'd make more sense to hold the grid itself in memory and refer to it as a whole.

 

[tim_m]

Originally posted by :LJ:
Out of curiosity, how big is the test grid going to be (roughly)? It'll have a bearing on the coding, because (for Java in particular), and arbitrarily large grid (say, 100k square) would cause major memory problems when points are stored as objects, so it'd make more sense to hold the grid itself in memory and refer to it as a whole.

did you mean 100k by 100k?

...i have no idea how big the test size would be! first, i don't want to have to wait an unreasonable amount of time to test each and 2nd, i don't want it to take so long that PuTTY times out from it's connection to the server. a run of my program of a 200x200 grid takes about 64 seconds, i got that by just running "date; java Aggregate ...; date" from my command prompt. i couldn't imagine how long a 100k x 100k grid would take. first, i don't know how fast the server is exactly, i think it's a 1ghz p3. also, it takes a mere 24 seconds on my computer, p4 3.15ghz, and i also don't really know how efficient my way is, that is to say, i don't know if there's some super duper class in java i could be using instead of a plain 2d array

 

[FuzzyDonkey]

ok, I just spent 2 hours trying to figure out what had gone wrong with a recursive function I wrote, only to discover that Python's copy by reference had really bitten me in the ass. "No you (&*#^$*, I only change one!"

I'm an idiot.

 

[FuzzyDonkey]

Originally posted by tim
did you mean 100k by 100k?

I'd challenge anyone here to find an implementation that wouldn't bog down with that size grid on a normal PC, without compressing the grid within your program. I assume he meant just a bigass grid.

 

[[MS]]

Well, my first try is in C#, so it may not be valid since this wasn't in the set of languages. I'll still post source when the competition is over though. The compiled program comes out to ~6KB.

Here are some of the times, taken on a P3-500 (to be exact, a OptiPlex GX1 500MTbr+ running xpsp1 /w v1.0.3705). The last few are averages, since the times for different runs start to vary more with a larger array. 2000x2000 was only run once, since it takes so long.

<snip>

The timings were taken in program, in the following fashion:

        static void Main(string[] args) {
            DateTime start = DateTime.Now;
            Method1(2000);
            Console.WriteLine(new TimeSpan(DateTime.Now.Ticks - start.Ticks).ToString());
            Console.WriteLine(Environment.WorkingSet/(1024*1024.0));
        }

Of course, I now realize there's a couple inefficient parts to the algorithm I used. I know it's possible for someone to beat the above times...

...who's it going to be?

It's obvious mine isn't going to be one to make the 100,000x100,000 challenge. The way I figure it, this machine could complete that matrix in ~500 hours, but only if it had close to 100GB or ram... Not going to happen...

edit: I discovered that the algorithm didn't give the correct preferential treatment to white spaces with a certain number of bordering black spaces (which is inferred by the inital description). I've removed the timings...

A new version (2.0) was made which is simpler, does give the correct preferences , uses less memory , but is slightly slower . A couple sample timings on a 2.4 GHz:
1000x1000........ ~10 seconds....~7.14 MB
10000x10000.... ~4 hours....~100.1 MB

The good news is that it's *possible*do 100k x 100k now, without running out of memory. Bad news is that it would still require a server with 10GB, and would take ~240 days using this method .

 

[HorsePunchKid]

Sorry, I don't have time to add anything particularly relevant. I did do some diffusion-limited aggregation simulations in Java a while ago. I maintain a tiny project page for it, though it's severely out of date. Here's the site, a shot of an example aggregate (with four particle sources, line segments for particles, tangential initial velocities for the particles, and an inverse-square attractor in the center), and part of the blurb I wrote about it:

Aggregate was initially intended to be a simulation of diffusion limited aggregation. Essentially, you release sticky particles into a container and let them take random walks until they stick to something. Clusters form that have predictable properties. This started out as something like that, but then the particles acquired momenta, and the clustering points became massive. So I had a little space with massive bodies wandering around with random perturbations, sticking to things and whatnot. Anyway, the goal was to generate pretty pictures, and I believe I have accomplished that.

My app would be massively slow and inefficient for a simulation on the scale of a 100k by 100k grid. Might be fun to try sometime, though...

 

[:LJ:]

OK, guys, I'm not going to be able to participate in this one - I'm moving house soon, and I'm bloody busy at work. However, I've had a few ideas which may be able to speed up the large grids :

1) Work out how much memory you've got to play with (this has to be dynamic, I'm afraid), then split the grid up into smaller portions which will fit in memory several at a time, then assign a thread to work on each. When you're done, write them to disk and carry on working on the next lot.

2) If you're using an object to represent each point, then work on the "on" points until you've occupied half of the points in the grid (or portion of the grid, if you're doing 1 as well). Once you're done, start running an inverse algorithm which works on the "off" points - that way, you never need to hold any more than half of the grid in working memory (my logic may be off here).

3) This one only works if you're planning on holding the entire grid in memory. For any given generation, only a small portion of the grid may be occupied at any given time because we're only starting with a single point. Therefore, for generation 2 (assuming generation 0 to be the first point), the potentially occupied grid would be 3x3, regardless of the target size.

4) Work out when an area is totally filled, and discard that area when you're working - a follow-on to this is to work out where the boundary is and only work on that (remembering that a group og "off" points can be surrounded, so this needs including in such a boundary).

Personally, I'd say that a combination of these strategies would be best - option 4 will work well in conjunction with option 3 when you've got a totally filled area and for arbitrarily small grids or at the start of the cycle (I'm not sure how well it would work with enclosed "off" areas - depends on how efficient your boundary scanning is). Once these options start to run out of memory, switch to a combination of 1 and 2 to start actively managing your memory.

Just some thoughts.

 

[:LJ:]

And another thought - what if you had one thread (or group of threads) doing all the work, and another thread constantly monitoring the state of the array and maintaining a shared array of hints and optimisations that the worker threads could examine to determine the smartest area to work on next?

 

[FuzzyDonkey]

Originally posted by :LJ:

2) If you're using an object to represent each point, then work on the "on" points until you've occupied half of the points in the grid (or portion of the grid, if you're doing 1 as well). Once you're done, start running an inverse algorithm which works on the "off" points - that way, you never need to hold any more than half of the grid in working memory (my logic may be off here).

I'm thinking you could get bigger gains by not storing every point as an object.

 

[FuzzyDonkey]

Originally posted by :LJ:
3) This one only works if you're planning on holding the entire grid in memory. For any given generation, only a small portion of the grid may be occupied at any given time because we're only starting with a single point. Therefore, for generation 2 (assuming generation 0 to be the first point), the potentially occupied grid would be 3x3, regardless of the target size.

I've been thinking about it, and given the algorithm, the grid will be very compressable in the vast majority of cases, especially if you do what MS is doing, and weighing the chances of a point being flipped based on the number of already flipped bits surrounding it. a 100k x 100k grid could probably fit in a few megs of ram in most cases (I haven't done calculations on this, this is all in my head, so I may be wrong). If you store the rows and columns as ranges of elements that are flipped or unflipped, rather than storing all of the elements individually, you also get quick boundary detection for free. Basically, a variation on a sparse matrix, but don't even store the elements that are populated, only the ranges of elements that are. Adding weight to unflipped bits like MS is doing is more difficult this way, though.

 

[tim_m]

well it would seem my initial attempt was dismally unoptimized. or could it be because it's java vs a 'really' compiled program, i somehow doubt it would make it run too much slower. at least it visualizes the problem enough to show what it is. but i'll try to make it faster. for as good as i may seem to those around me, i'm still comparitively a beginner at programming, or at least there's a whole lot of stuff i don't know

 

[[MS]]

Having written two versions, I'll offer some hints and insights....

Originally posted by FuzzyDonkey
I've been thinking about it, and given the algorithm, the grid will be very compressible in the vast majority of cases, especially if you do what MS is doing, and weighing the chances of a point being flipped based on the number of already flipped bits surrounding it.

Be very careful here. Compression is the art of trading CPU time for memory space. Be sure that you don't go too far to one side or another.

Also the weighted of chances based on surrounding values is a requirement if you read the first post closely. We can't treat each possible space as equally probable, this was what my first version did, and while it was faster, I removed the results because they didn't meet the requirements to the letter.

a 100k x 100k grid could probably fit in a few megs of ram in most cases (I haven't done calculations on this, this is all in my head, so I may be wrong). If you store the rows and columns as ranges of elements that are flipped or unclipped, rather than storing all of the elements individually, you also get quick boundary detection for free.

A 100K grid is 10 billion elements.
It sounds like you’re describing some variation of run length encoding. Could work, though it's not something I'm an expert at, so I didn't try anything that difficult.

Basically, a variation on a sparse matrix, but don't even store the elements that are populated, only the ranges of elements that are. Adding weight to unflipped bits like MS is doing is more difficult this way, though. [/B]

Note that the weighted probabilities is a requirement
Else, my first implementation would have been valid.

Originally posted by :LJ:
1) Work out how much memory you've got to play with (this has to be dynamic, I'm afraid), then split the grid up into smaller portions which will fit in memory several at a time, then assign a thread to work on each. When you're done, write them to disk and carry on working on the next lot.

While I haven't tried it, I think the main difficulty of using threads are:
- since each new point is picked at random, the grid section you'll need to access is also random, you can't work one "only" a certain section at a time.
- operations must be atomic. Since each operation in the algorithm required depends on the previous operation, for all intents and purposes, each operation must be complete before starting the next. So what if gained by the other thread?

I'm not saying there's not gain. I'm just saying it be hard to get any gain, and the gain will be minimal.

If we're aloud to go outside the rules, by picking up a new point before finishing execution on the other point for instance, then there is much more to be gained by going multithread.

2) If you're using an object to represent each point, then work on the "on" points until you've occupied half of the points in the grid (or portion of the grid, if you're doing 1 as well). Once you're done, start running an inverse algorithm which works on the "off" points - that way, you never need to hold any more than half of the grid in working memory (my logic may be off here).

While that is one simplification, there has to be others ...

3) This one only works if you're planning on holding the entire grid in memory. For any given generation, only a small portion of the grid may be occupied at any given time because we're only starting with a single point. Therefore, for generation 2 (assuming generation 0 to be the first point), the potentially occupied grid would be 3x3, regardless of the target size.

If you are randomly accessing parts of array it'll be difficult, but not impossible to find a way to cache that data off to disk in an intelligent manner. Unless you're going for 10k x 10k or larger, things should fit in memory just fine, and touching the disk on a regular basis would be a massive hit to perf.

3) This one only works if you're planning on holding the entire grid in memory. For any given generation, only a small portion of the grid may be occupied at any given time because we're only starting with a single point. Therefore, for generation 2 (assuming generation 0 to be the first point), the potentially occupied grid would be 3x3, regardless of the target size.

This could be quite possible, all depends on the implementation probably. It'd require some amount of tuning to make it run well probably.

4) Work out when an area is totally filled, and discard that area when you're working - a follow-on to this is to work out where the boundary is and only work on that (remembering that a group og "off" points can be surrounded, so this needs including in such a boundary).

That shows promise... But the big question is how?

 

[Mr_Superstar]

I just spent a little time writing this in Scheme. I know it's not on the list, but it was a nice challenge. My code's not pretty, but it gets the job done. If anyone wants it, I'll send it to them. Also, I wrote this for "Petite Chez Scheme" which you can download at www.scheme.com (it's the free version).

 

[FuzzyDonkey]

Originally posted by [MS]
Be very careful here. Compression is the art of trading CPU time for memory space. Be sure that you don't go too far to one side or another.

Also the weighted of chances based on surrounding values is a requirement if you read the first post closely. We can't treat each possible space as equally probable, this was what my first version did, and while it was faster, I removed the results because they didn't meet the requirements to the letter.

Yes, but for large grids, swapping to disk could be much worse. Anyway, this is a fun little exersize, not a production app, so we SHOULD try potentially retarded crap here. I'd KISS if this were for something important, rather than waste time doing things that may not save time or memory. After years of doing it in school and at work, I don't mind embarrassing myself completely with laughably bad implementations once in a while though.

A 100K grid is 10 billion elements.
It sounds like you’re describing some variation of run length encoding. Could work, though it's not something I'm an expert at, so I didn't try anything that difficult.

That's the word I was looking for. With weighted probabilites, the flipped elements should tend to form large blobs, with relatively few thin arms reaching out from them. Which should be very easy to compress to very small size, but not be rediculously slow. My estimate of a few megs may be off by an order of magnitude or so, too, but at worst the 100k grid should still be able to fit into ram on any PC that's at all recent.

Note that the weighted probabilities is a requirement
Else, my first implementation would have been valid.

Yea, that's the gotcha. It's more than a bit of a pain to do.
I haven't started writing yet (I aborted my first attempt, see an earlier post), but I suspect that my intended method of weighing the probabilities might be objectionable to some people. Then again, I'm only doing these things to learn Python better, so I don't really care if I get DQ'd or not.

 

[jen4950]

OH!

This could get cool-



Here's an idea for the geniuses-

Have it output a realtime image (video? details..) of the propogation pattern, and age.

And Age??

Assign a color to each element versus timestep..

So say you have a 1024x768 array, you'd have a standard image, and 786k time and color steps- hell, 4086x4087- 16.7 million colors! Assign a pixel to an array value-


that could get wicked cool!

 

[[MS]]

Originally posted by jen4950
OH!

This could get cool-



Here's an idea for the geniuses-

Have it output a realtime image (video? details..) of the propogation pattern, and age.

And Age??

Just for kicks and giggles I added real time drawing to a winform (pretty trivial, just a couple lines of code), and I'd have to say it's pretty cool to watch it. It's just the basic black, but it's just interesting to watch the leading edge and all the little spikes that come out before being enveloped by the "blob".

It's a bad idea to encourage people to run executables from the web, so I won't post the executable here, and since the contest is still going, I won't post the source yet.

 

[:LJ:]

Hehe MS, I was only posting a bunch of unfinished thoughts. Presumably with the last one, you'd write the position and size of the filled area out to a file so it's not held in memory. Detection shouldn't be a problem - just set a threshold on the number of filled points next to each other before it can be considered a "filled area". How you discard it would depend mainly on the result you want to achieve - either set it to "ignore" for computational speed, or store it somewhere else for memory efficiency.

Having thought about it, I like the idea of the boundary method best - particularly since it will scale well to n-dimensions (the boundary will be a surface of (n-1) dimensions, which simplifies the operation considerably). A pity I don't have time to do it....

 

[GRT]

I have an c++ implementation that probably could use some tweaking.

For size = 1000, it completes in 6-7 seconds on my Athlon 1800+ and uses about 6.3MB of memory(if kde system guard can be trusted)

For size = 10000, I haven't let it complete but it uses about 395MB of memory. The problem is my Node objects use 4 bytes each because they have a short and a bool in them. Is there any way that I can get a smaller number than a short? It only needs to hold the numbers 0-4 so 4 unsigned bits should do it for the 5 possibilities. That would knock my Node objects down to 1 byte each and make the memory situation much better.

Also, how is everyone else estimating memory usage? I am just looking in KDE system guard while my program is running to see what it jumps to. Is there a better way?

edit: ok, I figured out how to get rid of the short all together. I now complete 1000x1000 in 6-8 seconds and uses just over 3MB of memory. I'm about to run 10000 but it only uses 100MB of memory now.

edit #2: ok, it finished the 10000x10000 one finally. It took 2 hr and 13 minutes but I'm going to work on it some more and run it while i'm sleeping to see if I can speed it up a little.

 

[[MS]]

To get some comparable numbers, I ran my C# version (with drawing disabled) on my brother's Athlon 1700+....

Version 2.1.3:
1k x 1k: 6-7s, ~6.1MB
10k x 10k: 2.6h, ~99MB

This is the same as the one from my previous posting, but with a "fall through" method which gave about 30-40% increase in speed, and marginal improvment in memory.


Edit1: I just had and epiphany....
It'll have to wait till I get to work though....

 

[Tnadrev]

hmm, with my current method, my biggest problem is outputting the grid!

lol

 

[FuzzyDonkey]

Originally posted by Tnadrev
hmm, with my current method, my biggest problem is outputting the grid!

lol

yes. I'm also getting annoying with parts of Python. I've got mine written (except for a pretty output function), but there are still a couple of bugs I haven't tracked down.

On the plus size, I have a good understanding of Python's list type now.

 

[Tnadrev]

Originally posted by FuzzyDonkey
yes. I'm also getting annoying with parts of Python. I've got mine written (except for a pretty output function), but there are still a couple of bugs I haven't tracked down.

On the plus size, I have a good understanding of Python's list type now.

its the mathematics behind my method that makes it hard to output...

when i finish, i will share

i have not done much with python...

my solution is in C#, not sure if it will be accepted, but i wanted to try nonetheless

hmm... i had to change it around... i now store the whole thing, i thought it was avoidable, but alas, one aspect doesn't work

 

[Tnadrev]

Originally posted by [MS]

edit: I discovered that the algorithm didn't give the correct preferential treatment to white spaces with a certain number of bordering black spaces (which is inferred by the inital description). I've removed the timings...

preferential treatment? it says choose a random black square with a neighboring white square...

so would infer that it must be completly random (or as random as a computer can be) with no optimizing "fill" strategies

 

[Tnadrev]

my C# version takes around 6-7 seconds for 1000
and around 45-46 seconds for 2000

will leave it on 10,000 tonight

not sure if what i am using is measuring the memory used correctly... (i am using the same code MS posted...

on 1000 i get ~17.5 mB, on 2000 i get about the same...

i currently have a display mechanism... but it uses a dynamic array of "labels" which seem to take a long time to generate... so anything above say... 80 wide is too much for the display engine to handle... but at least i can see it work in real time at 80x80..

i should probably go to system.drawing... but meh... not worth it... unless you guys want it...


Edit: this is on a Athlon XP 1700+

edit:
1 hour, 20 minutes for 10,000x10,000 grid using 121.75 mB ram

note: this is a winforms app... so at least a few meg of that are from controls...

 

[[MS]]

Originally posted by Tnadrev
preferential treatment? it says choose a random black square with a neighboring white square...

Yup.

So, given two white cells (A & B) that are bordering black where cell "A" has a single black neighbor and "B" has three.

Cell "B" is three times as likely to be the randomly chosen cell for that round. The reason is that we're not choosing a random white cell, but rather a random black one, and then selecting a white neighbor.

That's what I meant. So if you were tracking white cells, for instance, you couldn't just pick a random one (from the ones with black neighbors), different ones would have different probabilities.


Hope that explains what I meant by the statement.

 

[Tnadrev]

Originally posted by [MS]
Yup.

So, given two white cells (A & B) that are bordering black where cell "A" has a single black neighbor and "B" has three.

Cell "B" is three times as likely to be the randomly chosen cell for that round. The reason is that we're not choosing a random white cell, but rather a random black one, and then selecting a white neighbor.

That's what I meant. So if you were tracking white cells, for instance, you couldn't just pick a random one (from the ones with black neighbors), different ones would have different probabilities.


Hope that explains what I meant by the statement.

ahh, yes... i track the black cells so i had it that way in my head

sorry!