• Some users have recently had their accounts hijacked. It seems that the now defunct EVGA forums might have compromised your password there and seems many are using the same PW here. We would suggest you UPDATE YOUR PASSWORD and TURN ON 2FA for your account here to further secure it. None of the compromised accounts had 2FA turned on.
    Once you have enabled 2FA, your account will be updated soon to show a badge, letting other members know that you use 2FA to protect your account. This should be beneficial for everyone that uses FSFT.

Programming Challenge 2004.2

First off... I can't believe I spent the last 8 hours creating new designs for this programming problem....

With that out of the way, I said I had an epiphany, so here are the results:

Version 2.2 (running on my 2.4GHz work machine):
1k x 1k: 0.23s, 4.96 MB
10k x 10k: 70s, 17.1 MB

Version 2.3 (running on my 2.4GHz work machine):
1k x 1k: 0.37s, 4.93 MB
10k x 10k: 55s, 6.2 MB
20k x 20k: 6m 2s, 8.6 MB

2.2 is built for absolute maximum speed. I'm convinced it's very near optimal without going to a lower level language like C or ASM.

2.3 is with the same time saving optimizations as in 2.2, but also includes memory saving optimizations (as can be seen from the numbers). It's still a little rough, but I may touch it up tomorrow.


Tnadrev, since you're also using C#, here is the display code I use...

My version is a command line app, and I use conditional compilation to enable or disable the visual output. This first bit can be put anywhere before the algorithm start. It'll create a new window of the right size and get's it ready for painting.
Code: 
                #if(visual)
                    Form outForm = new Form();
                    outForm.Height = innerSize+27;
                    outForm.Width = innerSize+8;
                    outForm.Show();
                    Graphics draw = Graphics.FromHwnd(outForm.Handle);
                    draw.Clear(Color.White);
                #endif
Then I have the following inside the actual algorithm:
Code: 
                    #if(visual)
                        draw.FillRectangle(Brushes.Black, x, y, 1, 1);
                    #endif

(edit) Oh yea, forgot about the includes:
Code: 
#if(visual)
    using System.Windows.Forms;
    using System.Drawing;
#endif

That's it! Like I said before, it's only a couple lines. Try it out, it's fun to watch :)

(edit) oh, and about your memory size question... The working set is physical memory mapped to the process at the time of the call. If your memory usage changes over the course of the algorithm, Process.PeakWorkingSet() would get the maximum that your app used at any one time. Depending on how yours works, the working set may vary greatly over the life of the process.
 
Originally posted by [MS]

Tnadrev, since you're also using C#, here is the display code I use...
Click to expand...

ya, i just finished my graphical output to work better with large grids

.... very curious to see how you did what you did... i had a method i thought was going to work in my head... that "would" have been that fast, but i could not track the "closed-off" black cells... perhaps if i had done it from the white cell side of things... <sigh>

but i only spent like 3 hours total on this :p
 
Here's the timing/memory usage for mine... I still have a couple things to try to tweak, and I have to write a pretty output function, but it's working fine now.

1k: 37.76s, 6megs memory
2k: 2m 47.98s, 7.3megs memory
10k: 1h, 20m, 19.55s, 17.2megs memory

edit:
tweaked it. recursion + rediculous use of stack= teh slow!:
1k: 14.5 seconds, 4.8Mb
2k: 67 seconds, 5.6Mb
10k: 39m, 4s, 12.8Mb

This is in python, using the psyco JIT compiler to speed it up in both versions.
 
behold my crap code:

takes 1 parameter at the command line, which is the size of the array

foo.py 1000

will run it for a 1k by 1k array.

edit: reduced the amount of memory the edges were taking up by half by removing a useless field from the list. This improved the execution speed slightly too.

Code: 
import sys, random, time, psyco
print time.clock()
psyco.full()

#seedGrid: flips a random first element in the grid.
def seedGrid(grid, x = [0,0]):
    i = 1
    j = 1
    if x[1] == 0:
       y = [[1, len(grid[1]) -1]]
    elif x[1] == len(grid[1]) -1:
       y = [[0, len(grid[1]) -2]]
    else:
       y = [[0,x[1]-1], [x[1]+1,len(grid[1])-1]]
       i =  i + 1
    grid[0][x[0]] = y
    if x[0] == 0:
       y = [[1, len(grid[0]) -1]]
    elif x[0] == len(grid[0]) -1:
       y = [[0, len(grid[0]) -2]]
    else:
       y = [[0,x[0]-1], [x[0]+1,len(grid[0])-1]]
       j = j + 1
    grid[2] = updateEdges(grid[2], x[0], i)
    grid[2] = updateEdges(grid[2], x[1]+len(grid[0]), j)
    grid[1][x[1]] = y
    return grid

#flipPoints: the main loop of the program.  everything important gets
#called from here.
def flipPoints(grid, y):
     w = len(grid[1])
     while y:
#uncomment for output         
#       if w < 80:
#          print 
#          printGrid(grid[0])
#          time.sleep(1)
#          
#       if y % 250000 == 0:
#           print y
#grid[2] contains a tree holding the number of edges in the rows/columns.
#we randomly pick an edge here.  Picking an edge rather than a point will
#automagically weight the points based on the number of flipped points
#around them.
       x = random.randint(0, grid[2][0]-1)
       rowColEdge = getRowColEdge(grid[2], x)
       p = 0
       z = rowColEdge[1]
       x = rowColEdge[0]
       if z >= w:
          z = z - w
          p = 1

#flip a point on an edge
       grid[p][z], i, d = flip(x, grid[p][z], p, w)
       g = 0
       if p:
          g=w
       grid[2] = updateEdges(grid[2],z+g, d)       
       grid[p^1][i], d= addPoint(grid[p^1][i], z, p^1, w)
       g = 0
       if not p:
          g = w
       grid[2] = updateEdges(grid[2],i+g, d)
       y = y - 1
     return grid

def flip(x, grid, p, length):

#voodoo.  clean up later.  The rows and columns are stored as ranges that
#are not set.  this just checks whether the first element in the row is set
#or not, so that we know where the first edge we can add to is. 
    if(grid[0][0] != 0):
       y = 0
    else:
       y = 1
    y = y - 1 - x
    q = y>>1
#pick the left or right edge of the span, and add a flipped element to that edge.
#delete the unflipped range if it's length is 0.
    if y & 1:
       i = grid[q][1]
       grid[q][1] = i - 1
       if i <= grid[q][0]:
           del grid[q]
       elif len(grid) > q + 1:
          if grid[q][1] == grid[q+1][0]:           
             grid[q][1] = grid[q+1][1]
             del grid[q+1]
    else:
       i = grid[q][0]
       grid[q][0] = i + 1
       if i >= grid[q][1]:
           del grid[q]
       elif q > 0:
          if grid[q][0] == grid[q-1][1]:
             grid[q][0] = grid[q-1][0]
             del grid[q-1]
#figure out how many edges are in the row/column.
    if grid == 0 or len(grid) == 0:
       d = 0
    else:
       d = len(grid) * 2
       if grid[0][0] == 0:
          d = d - 1
       if grid[-1][1] == length-1:
          d = d - 1
    return grid, i, d

#addPoint: flip flips a point on an edge.  In the other dimention, this isn't guarunteen,
#so we need a more generic function.
def addPoint(grid, z, p, length):
# check if the row is empty or not.
    if grid != 0:
       w = len(grid) -1
       y = w>>1
#find the unflipped range that the element is in with a binary search,
#and flip the point, splitting or deleting the range if appropriate.
       while True:
          if z < grid[y][0]:
              w = y
              y = y>>1
          elif z > grid[y][1]:
              y = y + ((w-y+1)>>1)
          elif z > grid[y][0] and z < grid[y][1]:
               a = grid[y][1]
               grid[y+1:y+1] = [[z+1, a]]
               grid[y][1] = z-1
               break
          elif z == grid[y][0]:
               grid[y][0] = grid[y][0]+1
               if grid[y][0] > grid[y][1]:
                   del grid[y]
               break
          elif z == grid[y][1]:
               grid[y][1] = grid[y][1]-1
               if grid[y][0] > grid[y][1]:
                   del grid[y]
               break
#add the first element to the row.            
    else:
       if z == 0:
          grid = [[1,length -1]]
       elif z == length -1:
          grid = [[0, length-2]]
       else:
          grid = [[0, z-1],[z+1,length-1]]
#find the number of edges in the row.
    if grid == 0 or len(grid) == 0:
       d = 0
    else:
       d = len(grid) * 2 
       if grid[0][0] == 0:
          d = d - 1
       if grid[-1][1] == length-1:
          d = d - 1

    return grid, d

#constructs the tree that keeps track of the edges.
def makeTree(size):
  t=1
  i = 0
  while t < size:
      t= t<<1
  eTree = []
  t = t << 1
  while i < t -1:
          eTree.append(0)
          i = i + 1
  return eTree

#what it says.
def printGrid(grid):
   y = len(grid)
   for x in grid:
       printRow(x, y)

def printRow(x, y):
   if x == 0:
      print '.'*y
   elif len(x) == 0:
      print '*'*y
   else:
      l =  ''
      t = 0
      for z in x:
        l = l+'*'*(z[0]-t)
        l = l+'.'*(z[1]-z[0]+1)
        t = z[1]+1
      l = l+'*'*(y-t)
      print l
   
#update the number of edges in the grid.
def updateEdges(eTree, endElement, newEdges):
   i = len(eTree)//2
   j = 0
   oldEdges = eTree[i + endElement] 
   while i:
      eTree[i + endElement] = eTree[i + endElement] - oldEdges + newEdges
      i = i >> 1
      endElement = endElement >> 1
   eTree[i + endElement] = eTree[i + endElement] - oldEdges + newEdges
   return eTree

#get a row or column, and edge.
def getRowColEdge(eTree, x):
    h = 0
    i = 0
    j = len(eTree)//2
    while i < j:
       i = (i<<1)|1
       h = h<<1
       if x >= eTree[i+h]:
          x = x - eTree[i+h] 
          h = h | 1
    return x-eTree[i+h],h     


y = int(sys.argv[1])
random.seed(time.time())
gridv = [0]*y
gridh = [0]*y
eTree = makeTree(y*2)
grid = [gridv, gridh, eTree]
x = [random.randint(0,y-1), random.randint(0,y-1)]
grid = seedGrid(grid, x)
y = y*y-1 

grid =flipPoints(grid, y)
print time.clock()
 
Well, I really wish I could compete with your guys code, but damn if mine isn't even close to your guys.

Code: 
C:\Programming>eden 10 10
It took 187 iterations to complete this.
Program started at:   Mon Mar 01 18:38:19 2004
Program completed at: Mon Mar 01 18:38:19 2004

C:\Programming>eden 30 30
It took 1789 iterations to complete this.
Program started at:   Mon Mar 01 18:38:30 2004
Program completed at: Mon Mar 01 18:38:30 2004

C:\Programming>eden 50 50
It took 4986 iterations to complete this.
Program started at:   Mon Mar 01 18:38:36 2004
Program completed at: Mon Mar 01 18:38:36 2004

C:\Programming>eden 70 70
It took 9787 iterations to complete this.
Program started at:   Mon Mar 01 18:38:42 2004
Program completed at: Mon Mar 01 18:38:42 2004

C:\Programming>eden 100 100
It took 19975 iterations to complete this.
Program started at:   Mon Mar 01 18:38:46 2004
Program completed at: Mon Mar 01 18:38:47 2004

C:\Programming>eden 1000 1000

C:\Programming>eden 500 500
It took 499981 iterations to complete this.
Program started at:   Mon Mar 01 18:39:00 2004
Program completed at: Mon Mar 01 18:40:46 2004

C:\Programming>eden 999 999

C:\Programming>eden 750 750
It took 1124995 iterations to complete this.
Program started at:   Mon Mar 01 18:43:22 2004
Program completed at: Mon Mar 01 18:49:31 2004

If you see, my program crashes on 999 x 999, and 1000 x 1000. It appears the threshhold is at 786 x 786 for mine running under Windows. Any idea why?

My number of iterations is how often my program goes through the main loop of: picking a random point, picking a random surrounding point, and then adding it to the graph. Looking at the number of iterations, does it look outrageous?

I'll probably re-look at my algorithm, but I've already increased it's speed incredibly from my previous version (100x100 took forever). The only improvement I made over my previous version was removing a point from the list of possible random points, if it checks all adjoining spaces and has no luck.

However, I still have A LONG way to go before I get to where you guys are. Not to mention I have to figure out why it crashes with large grids.





edit:

Well, I have a good idea why my program crashes. Keeping a vector< pair<int,int> > for every occupied point with 1000x1000 grid would be somewhere around the realms of 16 GB of memory. But I'm probably wrong, how do you guys measure memory usage?
 
how much memory is your program using? How much do you have free on your system? open up task manager and watch the performance and processes tabs. CPU should be stuck at nearly 100%, but see if you're running out of memory. If you're dynamically allocating and de-allocating memory, are you sure you're not leaking some(alot)? A couple of the people here have said that their programs are using 100+ megs for a 1k grid, yours wouldn't have too use much more per element to run most PCs out of memory.

Anyway, half the point of exercises like this, especially for people who are just learning, is figuring out how not to do things. So if you come up with what you think is an embarrassingly bad implementation, post it anyway.

I'm measuring it by watching the python process in window's task manager. Python doesn't seem to have a process memory usage tool for windows (there is one for unix, which I'm not on... :( )
 
Originally posted by Cverick

Well, I have a good idea why my program crashes. Keeping a vector< pair<int,int> > for every occupied point with 1000x1000 grid would be somewhere around the realms of 16 GB of memory. But I'm probably wrong, how do you guys measure memory usage?
Click to expand...

assuming 4 byte ints, it'd only need 8MB for the data. There'd be some overhead for the vector, but not 16 GB worth.
 
Yeah sorry, I wasn't thinking. I meant to say 8GB, but even still I screwed up because I skipped over kilobytes when I was trying to calculate how much that would be in engineering notation. ;p

It also appears that memory isn't an issue with my program, because it always frees the memory if it realizes that it does not have to check the point anymore.

My program finished with 1000x1000 though.

Code: 
C:\Programming>eden 1000 1000
It took 1999992 iterations to complete this.
Program started at:   Mon Mar 01 19:14:16 2004
Program completed at: Mon Mar 01 19:29:09 2004

I still have to work on my algorithm though. I have a new idea that should reduce the time to a reasonable time though; instead of remember every occupied spot, should probably just remember every point that is up for consideration for overtaking (mwhaha), and then update that list, instead of remember every point that is occupied, then calculating a random one of those, then calculating a random point around it.

I'm having a lot of fun doing this. Maybe one day I'll be able to compete with you guys. I hope this is a never-ending event. 8)
 
I'm working on a java solution. Unless I have an epiphany similar to [MS]'s, I think my code is about as fast as I can get it to be... there are probably some minor tweaks that I can do.

Here are my current times:
100: .05s
1000: 2.3s
10000: still running ;)

*Edit: This is on a dual amd mp 2000+. My program runs in a single thread, but it gets one of the cpus more or less to itself while it's running.

I haven't optimized for memory usage at all - it's not atrocious, but it isn't great either. It currently varies between n^2 and 2(n^2) bytes of memory... including the JVM, it uses about 115 megs on average for n=10000. After I get it going faster, I'm definitely going to look into trimming its memory requirements.
 
Anyone come up with a solution using 1 bit to represent each square? That was going to be the solution I was going to attempt... eg. a single 4 byte int can represent the state of 32 squares. I just don't have the desire to impliment it.
 
My 10k grid took about 30 minutes. Not great, but not horrible. No epiphanies in sight, though.

Twister - I thought about doing that. I'm a little worried that the extra calculations would slow the algorithm down... granted, they're all pretty trivial, but when you perform something trivial 100 million times (as in the case of the 10k grid), it could add up. I dunno - for memory-starved situations, it would definitely help, as it would cut the memory requirement by a factor of 8.
 
well i can't wait to see what everybody's got. i've only been able to make a minor improvement. now 100 takes 2-3 seconds on my computer. i don't have the time atm to do anything else with it, midterms and all. spring break is coming up though.
 
Originally posted by synergist-x
My 10k grid took about 30 minutes. Not great, but not horrible. No epiphanies in sight, though.

Twister - I thought about doing that. I'm a little worried that the extra calculations would slow the algorithm down... granted, they're all pretty trivial, but when you perform something trivial 100 million times (as in the case of the 10k grid), it could add up. I dunno - for memory-starved situations, it would definitely help, as it would cut the memory requirement by a factor of 8.
Click to expand...

But it would still be n^2 for memory. It'd definately help for some people, but I'm not storing individual elements, and I seriously doubt MS is either. Read LJ & MS's posts earlier in the thread, and follow some of their suggestions (or mine) to reduce memory requirements, and you'll probably get a better return, especially for larger grids.

of course, they're also more complex to implement, but that's the idea, is to try new things.
 
since you guys have beaten my times hands down, here is my C# code:

you can also download the compiled version...
http://lscs.servehttp.com/h/aggregate.exe (internet explorer users might have to right-click save as)
my program is kind of fun because its all graphical...

(note if you want it to run to completion, instead stopping after a number of loops, put zero in the loops box.

this is not the best code, but i completed it in about 3 hours


edit: linked for length
http://lscs.servehttp.com/h/aggregate.txt
 
Originally posted by Tnadrev
since you guys have beaten my times hands down, here is my C# code:

you can also download the compiled version...
http://lscs.servehttp.com/h/aggregate.exe (internet explorer users might have to right-click save as)
my program is kind of fun because its all graphical...
[/url]
Click to expand...

Can't get it to run. Are there any dlls or something that I need? I'm using windows XP.

"The application failed to initialize properly (0xc0000135). Click on OK to terminate the application."
 
Well.... My final numbers (2.4Ghz workstation)...

I ported my C# version over to C++, and put in all the memory optimizations I could...

Version 3.0:
1k x 1k: 0.34s s, 0.88
10k x 10k: 46.5 s, 1.95 mb

For reference, my most tweaked out C# version it was based on (2.3.1):
1k x 1k: 0.36s, 4.96 mb
10k x 10k: 42s, ~8 mb

While the C# version was faster, the C++ version gave me more control over memory, and I didn't have the 3-4mb overhead of the runtime.

On the other hand, I could get the C# version to compile down to 4KB is size while the C++ version is ~48KB in size.
 
Originally posted by FuzzyDonkey
Can't get it to run. Are there any dlls or something that I need? I'm using windows XP.

"The application failed to initialize properly (0xc0000135). Click on OK to terminate the application."
Click to expand...

do you have the .net framework installed?
 
did a bit more editing, i got
n; time (s); ~mem (MB)
100; 1.046; 5.8
200; 6.031; 5.9
500; 107.891; 7.1

mem was just by watching the java process in the task manager. i noted whatever the peak was.

a definate improvement but nothing compared to you guys.
 
Originally posted by FuzzyDonkey
No, that'd probably be the problem :)
Click to expand...

unfortunatly you need the either .net framework or the mono-runtime to run any .net apps...
 
I've trimmed it to <10s for 1k, and 45s for 2k, mostly by realizing that I've been an idiot, and was returning data that was passed by reference.

I've stopped working on this now, someone post another challenge please. :) This one was fun, btw, tim.

Code: 
import sys, random, time, psyco
print time.clock()
psyco.full()

#seedGrid: flips a random first element in the grid.
def seedGrid(grid, x = [0,0]):
    i = 1
    j = 1
    if x[1] == 0:
       y = [[1, len(grid[1]) -1]]
    elif x[1] == len(grid[1]) -1:
       y = [[0, len(grid[1]) -2]]
    else:
       y = [[0,x[1]-1], [x[1]+1,len(grid[1])-1]]
       i =  i + 1
    grid[0][x[0]] = y
    if x[0] == 0:
       y = [[1, len(grid[0]) -1]]
    elif x[0] == len(grid[0]) -1:
       y = [[0, len(grid[0]) -2]]
    else:
       y = [[0,x[0]-1], [x[0]+1,len(grid[0])-1]]
       j = j + 1

    updateEdges(grid[2], x[0], i, len(grid[2])//2)
    updateEdges(grid[2], x[1]+len(grid[0]), j, len(grid[2])//2)
    grid[1][x[1]] = y
    return grid

#flipPoints: the main loop of the program.  everything important gets
#called from here.
def flipPoints(grid, y):
     length = len(grid[2])//2
     w = len(grid[1])
     while y:
#uncomment for output         
#       if w < 80:
#          print 
#          printGrid(grid[0])
#          time.sleep(1)
#          
#       if y % 250000 == 0:
#           print y
#grid[2] contains a tree holding the number of edges in the rows/columns.
#we randomly pick an edge here.  Picking an edge rather than a point will
#automagically weight the points based on the number of flipped points
#around them.
       x = random.randint(0, grid[2][0]-1)
       x,z = getRowColEdge(grid[2], x, length)
       if z >= w:
          z = z - w
          p = 1
          r = 0
          g = w
          h = 0
       else:
          p = 0  
          r = 1
          g = 0
          h = w
          
#flip a point on an edge
       i, d = flip(x, grid[p][z], p, w)
       updateEdges(grid[2],z+g, d, length)
       d= addPoint(grid[r], i, z, r, w)
       updateEdges(grid[2],i+h, d, length)
       y = y - 1
     return grid

def flip(y, grid, p, length):

#voodoo.  clean up later.  The rows and columns are stored as ranges that
#are not set.  this just checks whether the first element in the row is set
#or not, so that we know where the first edge we can add to is. 
    if(grid[0][0] != 0):
       y = y - 1
    q = y>>1
#pick the left or right edge of the span, and add a flipped element to that edge.
#delete the unflipped range if it's length is 0.
    if y & 1:
       i = grid[q][1]
       grid[q][1] = i - 1
       if i <= grid[q][0]:
           del grid[q]
       elif len(grid) > q + 1:
          if grid[q][1] == grid[q+1][0]:           
             grid[q+1][0] = grid[q][0]
             del grid[q]
    else:
       i = grid[q][0]
       grid[q][0] = i + 1
       if i >= grid[q][1]:
           del grid[q]
       elif q > 0:
          if grid[q][0] == grid[q-1][1]:
             grid[q-1][1] = grid[q][1]
             del grid[q]
#figure out how many edges are in the row/column.
    if grid == 0 or len(grid) == 0:
       d = 0
    else:
       d = len(grid) * 2
       if grid[0][0] == 0:
          d = d - 1
       if grid[-1][1] == length-1:
          d = d - 1
    return i, d

#addPoint: flip flips a point on an edge.  In the other dimention, this isn't guarunteen,
#so we need a more generic function.
def addPoint(grid, i, z, p, length):
# check if the row is empty or not.
    if grid[i] != 0:
       w = len(grid[i]) -1
       y = w>>1
#find the unflipped range that the element is in with a binary search,
#and flip the point, splitting or deleting the range if appropriate.
       while True:
          if z < grid[i][y][0]:
              w = y
              y = y>>1
          elif z > grid[i][y][1]:
              y = y + ((w-y+1)>>1)
          else:
             if z == grid[i][y][0]:
               grid[i][y][0] = grid[i][y][0]+1
             elif z == grid[i][y][1]:
               grid[i][y][1] = grid[i][y][1]-1
             else:
               a = grid[i][y][1]
               grid[i][y+1:y+1] = [[z+1, a]]
               grid[i][y][1] = z-1
               break
             if grid[i][y][0] > grid[i][y][1]:
                del grid[i][y]
             break
#add the first element to the row.            
    else:
       if z == 0:
          grid[i] = [[1,length -1]]
       elif z == length -1:
          grid[i] = [[0, length-2]]
       else:
          grid[i] = [[0, z-1],[z+1,length-1]]
#find the number of edges in the row.
    length2 = len(grid[i]) 
    if length2 == 0:
       d = 0
    else:
       d = length2 * 2 
       if grid[i][0][0] == 0:
          d = d - 1
       if grid[i][-1][1] == length-1:
          d = d - 1
    return  d

#constructs the tree that keeps track of the edges.
def makeTree(size):
  t=1
  i = 0
  while t < size:
      t= t<<1
  eTree = []
  t = t << 1
  while i < t -1:
          eTree.append(0)
          i = i + 1
  return eTree

#what it says.
def printGrid(grid):
   y = len(grid)
   for x in grid:
       printRow(x, y)

def printRow(x, y):
   if x == 0:
      print '.'*y
   elif len(x) == 0:
      print '*'*y
   else:
      l =  ''
      t = 0
      for z in x:
        l = l+'*'*(z[0]-t)
        l = l+'.'*(z[1]-z[0]+1)
        t = z[1]+1
      l = l+'*'*(y-t)
      print l
   
#update the number of edges in the grid.
def updateEdges(eTree, endElement, newEdges, i):
   index = i + endElement
   newEdges = newEdges - eTree[index]
   while i:
      eTree[index] = eTree[index] + newEdges
      i = i >> 1
      endElement = endElement >> 1
      index = i + endElement

   eTree[index] = eTree[index] + newEdges


#get a row or column, and edge.
def getRowColEdge(eTree, x, length):
    h = 0
    i = 0
    while i < length:
       i = (i<<1)|1
       h = h<<1
       if x >= eTree[i + h]:
          x = x - eTree[i + h] 
          h = h | 1
    return eTree[i+h]-x,h     

def foo():
   y = int(sys.argv[1])
   random.seed(time.time())
   gridv = [0]*y
   gridh = [0]*y
   eTree = makeTree(y*2)
   grid = [gridv, gridh, eTree]
   x = [random.randint(0,y-1), random.randint(0,y-1)]
   grid = seedGrid(grid, x)
   y = y*y-1 

   grid =flipPoints(grid, y)
   print time.clock()
foo()
 
i'm gonna go ahead and close the contest, that is to say, the time for making the program is done, it's time to submit source code. the thread has grown quite nicely. please submit a link to your source code (or post it if it's not too long). just make sure it's obvious what language it's in. i'll do my best to compile them but i am rather limited as i mentioned in the first post. even if i can't compile it, feel free to post it. i suppose you can post executable files but they probably won't be counted as if i had the source code and was able to compile it, this is more for those who have programs i wouldn't be able to compile, i'd still like to see it in action.

i don't have much experience grading things so if you're so inclined, feel free to comment on other's programs (especially mine ;)), but don't just say it's bad or anything like that.

i'll say that all entries should be in by friday/saturday 3/5-3/6. i believe there's been enough time to finish up.

(i'll post mine in a minute, have to put it in my www directory and add comments)
 
my solutions
aggregate
aggregate2
aggregateapplet

the first one is my initial attemp, only slightly modified, from before i posted the contest so i could get an idea of what it was about

the second one i added a vector to keep track of points that had neighbors so it didn't have to scan the entire array

the third one was my attempt at creating an applet to demonstrate it. it seems to work in the standalone applet viewer but doesn't work in a browser. i simply don't know enough about applets (i mean i hardly know anything) to make it work properly from the applet side of things. the underlying aggregate code is from my first attemp
 
OK.... I've got a bit to go over, but I'll leave most of it as linked info...

Everything from this post is from the full write up here, which contains 24 pages of problem analysis, solution explanations, and source code.


There's all sorts of info in the link... including pseudocode like the following (check file for explanation):
Code: 
Select a random grid node
For each adjacent node {
	Add the adjacent node to the ArrayList of border elements
	Add state information for the adjacent node to the HashTable 
to indicate selected node is flipped
}
While (ArrayList of border nodes is not empty){
	Pick a random node from the ArrayList of border nodes
	For each adjacent node {
		Add the adjacent node to the ArrayList of border elements
		Add state information for the adjacent node to the HashTable to indicate selected node is flipped
	}
	Remove the selected node from the ArrayList of border nodes
}


There's explanation of the sudden breakthrough in versions 2.2 and 2.3:
Code: 
int[] borderNodeArray
and
Code: 
            if (bitBlocks[g]==0)
                bitGrid[g] = new BitArray(bitsPerBlock, true);
            bitGrid[g][gi] = false;
            bitBlocks[g]++;
the two things that improved the performance of my code by two orders of magnitude :). Fun stuff...

There's even some nice bitwise math...
Code: 
                g = ((gridNode&sizeMask)>>blockWidthBits) + ((gridNode>>sizePbb)<<sizeMbw);
                gi = (gridNode&BlockLowMask) +  (((gridNode>>sizeBits)&BlockLowMask)<<blockWidthBits);
...horrible logic statements...
Code: 
if (bitBlocks[g+GridWidthInBlocks] == 0 || bitBlocks[g+GridWidthInBlocks] != bitsPerBlock && bitGrid[g+GridWidthInBlocks][gi&BlockLowMask])
... and even some fun with C...
Code: 
unsigned short *bitBlocks = new unsigned short[MIN_BLOCK_SHORT( actualGridWidthInBlocks * GridWidthInBlocks)];
ZeroMemory(bitBlocks, sizeof(short) * MIN_BLOCK_SHORT( actualGridWidthInBlocks * GridWidthInBlocks));
BitArray **bitGrid = (BitArray**)calloc(MIN_BLOCK_INT( actualGridWidthInBlocks * GridWidthInBlocks), sizeof(SIZE_T));
... looks yummy huh? :).


Anyway, the full source code is there for version 2.3.1 (final C# version), and it only requires that you have the framework to compile it ("csc.exe /d:cmdline,rand <filename>", or optionally with "/d:cmdline,rand,output,visual" if you want to watch it draw).

The last C version (3.0.1) is also there but isn't to be taken lightly. It can be compiled with VC2002\VC2003 to a native or managed executable. Compiling to native gives no output during execution, compiling to managed enables visual output using the same winform code that the C# version uses. Because it bypasses certain sections of the C runtime library for memory management (tracking the memory itself), the platform APIs would have to be changed to compile on a different platform.

I won't post execubable unless requested. It's bad security practice to download and run random binaries.

The below info comes from the summary area of the linked file. Each of the versions listed below is described in the link.

The algorithm goes over all 10 billion nodes, using only 32 million bytes :)
Code: 
Summary of timings (2.4Ghz unless specified, all C# except v3.x ):
version			1k x 1k		10k x 10k	100k x 100k
1.0 (p3-500)		27s
2.0			10s		~4h
2.1.3	(AMD 1700+)	7s		~2h 36m
2.2			0.23s		70s
2.3			0.37s		55s
2.3.1			0.28s		43s
3.0			0.24s		42s
3.0.1			0.24s		44s		[b]3h 14m 56s[/b]

Summary of Memory (in MB):
version			1k x 1k		10k x 10k	100k x 100k
1.0 			>10
2.0			7.14		100
2.1.3			6.1		99
2.2			4.96		17.1
2.3			4.93		6.2
2.3.1			4.86		6.13
3.0			0.79		1.93
3.0.1			0.81		2.20		~32
A couple points of interest...
Since versions 2.3.1 and 3.0 are pretty much the same algorithmically and implementation wise (with the exception that one is higher level).

The execution times are almost identical.
The C# version has ~4.1 MB of runtime overhead.

The C# version compiles down to a 6KB executable (actually, 4096 bytes if I remove resources)
The C++ version compiled down to about 50KB

And how did they scale up? From 1K to 10K:
Code: 
2.3.1 (C#)	+43s		+1.27MB
3.0 (C++)	+42s		+1.14MB

C++ slightly edges out C# in how it scales.
That said, the C# version was much easier\quicker to write and debug, and it cleans up after itself. I only point this out because some still believe performance on managed code can’t compare with that of optimized C\C++. :) Ok... I’ll get down off the soap box before someone throws a tomato...


edit: updated the link
 
Originally posted by [MS]
OK.... I've got a bit to go over, but I'll leave most of it as linked info...

Everything from this post is from the full write up here, which contains 24 pages of problem analysis, solution explanations, and source code.
Click to expand...

Dude, you put WAY too much time into this. :)

The algorithm goes over all 10 billion nodes, using only 32 million bytes
Click to expand...

Cool. Mine would probably come in at ~ 60-80, but I'm not eager to run it long enough to find out (since it'd take a couple days). I'll probably implement the same algorithm I used in C, just to see if it's python that's slowing it down. I don't think it is (not by that much, anyway), but I am curious.

That said, the C# version was much easier\quicker to write and debug, and it cleans up after itself. I only point this out because some still believe performance on managed code can’t compare with that of optimized C\C++. Ok... I’ll get down off the soap box before someone throws a tomato...
Click to expand...

<hides tomato behind back> who, me? :) C++ (and, apparently, C#, though I have no experience with it) performance has usually been hampered by poor design (I know! we'll add another layer of abstraction... what, it didn't help? add another!) more than by the languages themselves. That said, there are limited cases where you do need the 2-3% of performance that you can gain.

I can't complain about this much though, considering what I wrote my submission in. :)
 
Originally posted by FuzzyDonkey
<hides tomato behind back> who, me? :) C++ (and, apparently, C#, though I have no experience with it) performance has usually been hampered by poor design (I know! we'll add another layer of abstraction... what, it didn't help? add another!) more than by the languages themselves. That said, there are limited cases where you do need the 2-3% of performance that you can gain.

I can't complain about this much though, considering what I wrote my submission in. :)
Click to expand...

actually the amazing thing here is that C# (well, when compiled to a .net assembly) is managed, using the CLR... which is kind of like the jvm (but obviously a little better in the performance arena, along with some other major differences... but conceptually its a similar thing) and provides things like code access security, and garbage collection...
 
So considering that everyone is (nearly?) done, any suggestions for the next one? Personally, I'd like to get away from just "do this the fastest, with the least memory" (no, not because MS kicked my ass :) ), and more towards making things that are just neat, or possibly useful. And I promise not to use 50 1 letter variable names next time. :) The reason I'd like to get away from what the last two challenges were like is to use/learn more python modules, which I'm bad at doing unless I have some sort of motivation to do so. Something with a gui requirement (but not JUST a gui) would be nice.
 
I've got a suggestion (although I wouldn't have time to complete or run such a challenge at the moment) - a Rubik's cube simulator and solver. The premise :

Take a Rubik's cube in a solved state. Perform 100 random operations on it, then WITHOUT HOLDING THE RANDOM MOVES IN MEMORY, solve the puzzle in the least number of moves. The average of 3 attempts will be considered the program's final score (too much lookahead will render that attempt null and void, or will count as an attempt in itself).

The winner will be decided solely on the basis of the average score. Real-world speed is not an issue. Should two programs score exactly the same, a subjective view would be taken on the style and intelligence of the code.
 
sounds like recursive backtracking. i did one for a knight's tour. that is, back in cs 1 i looked at a cs 2 assignment and checked it out.
 
Well, even though I didn't get a chance to participate like I had hoped, I'm still pleased to see that there was such interest in the Programming Challenge. When I posted 2004.1 I never expected that it would continue like this, and I'm really glad that I was wrong!

As an aside... I just realized that Gentoo stole my numbering scheme. :mad: ;)
 
As for the next challeng: In keeping with the spirit of the contest, and assuming tim follows the idea from the last one, it would be the "winner" of this contest that picks the next one.

Of course, I do like :LJ:'s suggestion, even if I don't have a blasted clue on how to do it!
 
Yeah, carl, i know the feeling. I'd really like to participate more, but things are so crazy at the moment that I don't have time to think about dinner, much less something like this that requires real thought. So, I'm just settling for being an active lurker at the moment.

Incidentally, I think my suggestion could be a little complex for a lot of people, so maybe it could be more than a 1 month offer....?

I think it's fantastic that this challenge thing has got the response - 2nd month and already 70+ replies!
 
Originally posted by :LJ:
Yeah, carl, i know the feeling. I'd really like to participate more, but things are so crazy at the moment that I don't have time to think about dinner, much less something like this that requires real thought. So, I'm just settling for being an active lurker at the moment.

Incidentally, I think my suggestion could be a little complex for a lot of people, so maybe it could be more than a 1 month offer....?
Click to expand...

I don't think there needs to be a fixed time limit. If anyone is participating and needs a bit more time, just post to say so. People could always ask for help if they hit a big snag too. Your comments earlier in the thread probably gave some people ideas that they wouldn't otherwise have thought of, but I don't see anyone complaining about it.
 
Originally posted by FuzzyDonkey
I don't think there needs to be a fixed time limit. If anyone is participating and needs a bit more time, just post to say so. People could always ask for help if they hit a big snag too. Your comments earlier in the thread probably gave some people ideas that they wouldn't otherwise have thought of, but I don't see anyone complaining about it.
Click to expand...

As long as I'm useful to somebody ;) I just figured that since we were numbering the challenges by month, there was an implied 1-month limit. But you're right, there's no reason they shouldn't run on a bit (but we do need to set a deadline at some point).

And I think that discussion is part and parcel of the whole thing - this isn't an exam, after all. Personally, I like Stallman's model of the caring 'n' sharing development community, so that's the approach I take.
 
Originally posted by FuzzyDonkey
Dude, you put WAY too much time into this. :)
Click to expand...

What can I say… I like to program :)
I do much of the product performance monitoring for my team, and it’s fun to get back to basics instead of theorizing about a product is didn’t design, using various metrics. It’s also educational since knowing the relative performance of some of the BCLs can actually help me with my job.

The write up was just for anyone that’s interested in programming, to help give ideas that people could use in future challenges. The main lesson is that it’s invaluable to know the strengths and weaknesses of various data structures. Once you know that, you can focus more on what should be tracked, rather than spending time trying to figure out how to do it.

Note that none of my tries were valid (given the system to be used to compile), it was mainly just to have some fun and see if I could beat my previous best. A game only a true computer geek could love... :)


Cool. Mine would probably come in at ~ 60-80, but I'm not eager to run it long enough to find out (since it'd take a couple days). I'll probably implement the same algorithm I used in C, just to see if it's python that's slowing it down. I don't think it is (not by that much, anyway), but I am curious.
Click to expand...

At a glance, it looks like you’re breaking the grid area into linear blocks. I tried this at one point but the nodes per block must be reduced drastically in order to prevent excessive memory usage. Using a 64x64 block means that for a given border element, we’re tracking 32 points to either side of the border (on average), and the block count is nodes/4096. Using a 1x256 block would track (on average) 64 points to either side and have a block count of nodes/256.

<hides tomato behind back> who, me? :) C++ (and, apparently, C#, though I have no experience with it) performance has usually been hampered by poor design (I know! we'll add another layer of abstraction... what, it didn't help? add another!) more than by the languages themselves. That said, there are limited cases where you do need the 2-3% of performance that you can gain.

I can't complain about this much though, considering what I wrote my submission in. :)
Click to expand...

Quite true…
 
Originally posted by [MS]

Note that none of my tries were valid (given the system to be used to compile), it was mainly just to have some fun and see if I could beat my previous best. A game only a true computer geek could love... :)
Click to expand...


Yea, I'm in the same boat on that one. I think someone may win just because they have the only valid entry. :)

At a glance, it looks like you’re breaking the grid area into linear blocks. I tried this at one point but the nodes per block must be reduced drastically in order to prevent excessive memory usage. Using a 64x64 block means that for a given border element, we’re tracking 32 points to either side of the border (on average), and the block count is nodes/4096. Using a 1x256 block would track (on average) 64 points to either side and have a block count of nodes/256.
Click to expand...

In practice, there are normally 5.5-8 nodes per block for large blocks (I tried several runs between 1k to 10k, 1k had the best and worst performance, higher numbers appear to approach 6 nodes per block. This assumes the blob starts in the center, if it started in a corner, there'd be 4.5-7 nodes per block). Worst case if far higher, roughly 1/3n nodes per block, where n is the length of the block. If Python would actually free nodes when they were deleted (which might hamper performance considerably, I'm not sure), instead of doing it every hour or so, real world memory performance would be much better. If the problem were different, so that we just had to insert points randomly throughout the grid, rather than next to a random flipped point, memory performance of this algorithm and data structure would be horrendous.

I'd kill for a good, easy to use memory profiler for python.

Where my program really gets into trouble is speed, not memory usage. Since I have to search for every edge after I select it, and update the binary tree after the grid is updated, performance decreases for large grids.
 
Originally posted by :LJ:
I just figured that since we were numbering the challenges by month, there was an implied 1-month limit. But you're right, there's no reason they shouldn't run on a bit (but we do need to set a deadline at some point).
Click to expand...
i thought the number just meant the number challenge of 2004. this was the second challenge. i haven't used gentoo (yet ;)) so i'm not familiar with their numbering scheme if they do it by yyyy.m, just a coincidence i suppose :)
 
Originally posted by tim
i thought the number just meant the number challenge of 2004. this was the second challenge. i haven't used gentoo (yet ;)) so i'm not familiar with their numbering scheme if they do it by yyyy.m, just a coincidence i suppose :)
Click to expand...

Yes, you are correct. I numbered not by month, but by ordinality. Mine was the first challenge; yours is the second.

I think mine had a one-week timeframe anyhow.
 
just a heads up, i'll be delayed in doing anything because it's become necessary to do a fresh install on my compter :( :(
 
You must log in or register to reply here.
Back
Top