Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
walls = [2,3,4,0,1,3,1,5,4,3,4,0,1,2,0,1,0,2,0,4]
lmax=0;
total=0;
copen=0;
buff=0;
print "\n-----------BEGIN ALG-----------\n"
if walls[0]>walls[1]:
lmax=walls[0];
copen=1;
for i in range(1, len(walls)):
if walls[i]<walls[i-1]:
copen=1;
buff=buff+(lmax-walls[i]);
else:
if walls[i]<lmax:
buff=buff+(lmax-walls[i]);
buff=buff-(copen*(walls[i]-walls[i-1]));
total=total+(copen*(walls[i]-walls[i-1]));
copen=copen+1;
else:
total=total+buff;
buff=0;
copen=1;
lmax=walls[i];
print "step "+str(i)+": total = " +str(total) + " buff = " +str(buff);
print "\nTOTAL = "+str(total);
print "\n-----------END ALG-----------\n"
@flowolf

This comment has been minimized.

Copy link

flowolf commented Nov 4, 2013

Hey!

I've tested it and it's very fast!

but sometimes it miscalculates.
I tested with this array, and came to 50191 with your solution and 50242 with mine.

The benchmark between our two solutions is interesting as well. For an array with length 10000:

Mine runs 0.017299 seconds and yours 0.003123 seconds.

I also get differences for simple cases like:
[landscape] my result / yours
[5, 9, 5, 0, 5, 2, 9, 3, 6, 8, 0, 5, 7, 6, 0, 10, 8, 5, 9, 0] 66 / 65
[2, 9, 9, 5, 10, 9, 3, 1, 10, 7, 8, 9, 9, 4, 7, 10, 1, 4, 1, 9] 58 / 48
[0, 8, 6, 1, 7, 8, 2, 0, 0, 8, 5, 4, 1, 3, 0, 0, 3, 3, 3, 4] 47 / 45
[1, 1, 9, 6, 2, 7, 7, 4, 2, 6, 6, 8, 6, 4, 2, 4, 8, 4, 2, 7] 48 / 30
[10, 7, 5, 9, 10, 7, 9, 5, 2, 6, 0, 5, 0, 1, 6, 6, 2, 0, 9, 1] 77 / 40
[39, 11, 34, 8, 27, 23, 2, 31, 6, 34, 31, 16, 18, 13, 10, 26, 13, 4, 26, 38] 351 / 163

I'm not sure your algorithm is correct.

hth
Florian

@chrisdone

This comment has been minimized.

Copy link

chrisdone commented Nov 13, 2013

walls = [2,5,1,2,3,4,7,7,6] → 10
walls = [6,7,7,4,3,2,1,5,2] → 4

Another broken algorithm that depends on order.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.