piles of cannonballs

[Fusion_power]

Lol cheese, agree that doing without WHILE, UNTIL, etc. is difficult. But remember that the commodore 64 only had one looping structure in its basic routines, that was the FOR statement.

It is difficult to get used to modifying an index inside a loop. But once you figure out the tricks, it is a very powerful tool.

I always had a problem with instructors who told me to:

Never write self modifying code.
Never use the NOT command, people just don't understand it.
Never modify loop indexes inside the loop.

There are some problems that are almost impossible to solve without using self modifying code. Still, I have to give this one the respect it deserves, its generally a no-no.

Twice in my life I have encountered a coding problem where the only possible solution was using NOT.

Loop indexes are just variables that may automatically increment. The variable itself should be treated just like any other variable.


I try to always keep in mind the consequences of any code I write especially if someone else tries to understand it. As you may guess, I write some very unusual programs!

[kwstone]

Hey, if was difficult to write, it should be difficult to understand. Comments are for wimps.

[c00ler]

I used very stupid Delphi program and record is
6590687693369780+952833181691720=7543520875061500 balls
(sides are 340690,178808 and 356375 balls)
Who can beat it?

P.S. And who can prove that it has infinetely many solutions?

[Maybeso]

c00ler,

Did you use an algorithm similar to the one above? If not, could you describe/post it? And did you find all the solutions less than your record?

I used a different method, it is currently at
30394 = 18633 + 27853 or
4680100641580 = 1078368074245 + 3601732567335

It is checking 10 values of n per second, and I haven't seen much slowdown as n grows.

The basic that I use has a hybrid structure:
FOR A = 1 TO 100 UNTIL (B > 15)
NEXT A
which exits if B > 15 before A = 101. But it only checks between loops.

My algorithm is as follows, 'converted' from pascal:[code:1]stack = record
n,t,p : bigint;
end
stack1 = (2,3,4); // pyramid # ~= base of stack4.
stack4 = (2,3,3); // pyramid # I'm checking; p = sum of base + k levels.
repeat
with stack4 { n++; t += n; p = t; }
stack3 = stack4; // starts = base of 4, adds levels until n <= stack2
while (stack1.p < stack3.t) with stack1 { n++; t += n; p += t; }
stack2 = stack1; // starts = 1, inc(n) until >= 4.
while (stack2.n < stack3.n) and (stack2.p != stack3.p) {
while(stack2.p < stack3.p) with stack2 { n++; t += n; p += t; }
while(stack3.p < stack2.p) with stack3 { t -= n; p += t; n--;}
}
if (stack2.p == stack3.p) myprint(stack4.n,' = ',stack2.n,' + ', stack3.n);
if keypressed then done = true;
until done;[/code:1]
Cheesehead, you wondered earlier why I was interested in the triangular numbers that make up the tetrahedral number. With my method, I don't need to calculate Tetra(n) to check it. I start with
s = Triangle(n) {the number of balls in the base} at one end, and
t = Tetra(a) ~= s {the stack with the closest number of balls} at the other.

Then I inc(a) and/or dec(n), s += Triangle(n) {adding rows to s}
until t = s or a passes n.

my program has checked another 10000 n while I wrote this.
;)

[c00ler]

I've found all the solutions less than record.
Program that founds all solutions less than nmax:
1) generate array (a[n]=n*(n+1)*(n+2)/6 for n=1..nmax)
2) for i:=1 to nmax do for j:=1 to i-1 do //i-size of the biggest pile, j- size of the middle pile
begin
y:=a[i]-a[j]; number of balls in the smallest pile
l:=1;
r:=nmax;

while r>l+1 do // this loop searches y in array a[n]
begin
m:=(l+r) div 2
if a[m]>=y then r:=m else l:=m;
end;

if a[r]=y then ...;//output piles of sizes i,j,r and number of balls a[i],a[j],a[r]

end;

[Fusion_power]

The most interesting part about this thread is that there are 4 different programs each of which takes a radically different approach to solving the same basic problem. The interesting part is that none of us has a truly optimum solution, I can point out flaws with each method. The one that works best with small numbers is COOler's, the one that works best regardless of number size is mine (the last one, not the first) but it is slow since it has to re-calculate values in each iteration, Maybeso's works well overall but does too many comparisons of values that can't possibly match.

I think I'll try to come up with another really good problem that can be solved by coding, this has been fun!

Fusion

[Maybeso]

One version of mine generated the list of a[n], but separated them out mod 10 -- I'd noticed that n(n+1)(n+2)/6 == 0,1,4 mod 5, and wanted to break my search into smaller pieces.
Then it looked only in pairs of mod lists that added up to the right mod.

But I got a stack overflow for a rather low value of n. Also it was an early version, and I think I looked at every member of a given list, so it wasn't that much faster. Although the 0 mod 10 list was 5 times the rest combined, so it did the others really fast.

Perhaps if the mod 10 idea was combined with c00lers binary search . . .
But splitting up a binary search doesn't improve it . . .

Ok, one last note, then I'll wait for the next puzzle. I looked for numbers that showed up on both sides of the equation and combined them:[code:1] 58 = 30 + 20 + 54
175 = 34 + 118 + 154
3143 = 219 + 515 + 3138
644 = 399 + 434 + 495
702 = 272 + 324 + 663
6040 = 608 + 754 + 6034
8379 = 4115 + 6152 + 6586
35826 = 19151 + 26148 + 27624[/code:1]There were a few numbers which showed up several times on the right, I'm not sure what could be done with those.

I was trying to find a relationship that would let me prove there are infinite solutions, but I don't see any patterns.

[c00ler]

Originally Posted by Maybeso

I used a different method, it is currently at
30394 = 18633 + 27853 or
4680100641580 = 1078368074245 + 3601732567335

It is checking 10 values of n per second, and I haven't seen much slowdown as n grows.

My new program checks 10 values per second at sizes of piles 1000000+ 8)

I'll try to do it faster and then I'll post it.

[tom11784]

Hi all. I'm new to this forum, but when I saw this I noticed one major improvement on the Z-loop

Originally Posted by Fusion_power

100 CLS
110 W = 500
120 FOR X = 3 TO W
130 A = (X * (X + 1) * (X + 2) / 6)
140 FOR Y = X TO (2 * W)
150 B = (Y * (Y + 1) * (Y + 2) / 6)
160 D = A + B
165 T = INT(1.3 * Y) + 9
170 FOR Z = Y TO T STEP 7
180 V = Z + 7
190 C = (V * (V + 1) * (V + 2) / 6)
200 IF C >= D THEN U = Z: Z = T
210 NEXT Z
220 FOR Z = U TO V
230 C = (Z * (Z + 1) * (Z + 2) / 6)
240 IF (D = C) THEN PRINT A, B, C
250 IF (C > D) THEN Z = V
260 NEXT Z
270 NEXT Y
280 NEXT X
290 END

The reason we can replace the 3*W by INT(1.3*Y) + 9 is that since we have that X<=Y, A+B is at most 2*B, such that
2B = 2*(Y)*(Y+1)*(Y+2)/6 = ( 2Y^3 + 6Y^2 + 4Y )/6.

Also, not that if we test 1.3*Y into the formula for a tetrahedron, we have T(1.3Y) = (1.3Y)*(1.3Y+1)*(1.3Y+2)/6 = ( 2.197Y^3 + 5.07Y^2 + 2.6W )/6, which is greater for all Y>6, but has a maximum difference from T(Y)+T(Y) of ~7.97 at Y=~3.775 so we add the +9 since we truncate the INT(1.3*Y).

Whoever wrote that this program ran in 45 seconds, can you let me know just how much time this shaved off? (hoping it gets it to <40)

[tom11784]

Also, the main programming thing at my school is C++, so anyone know how to get it to store a variable with more than 52 bits of precision (double-precision) since that seems to be around where the record currently lies.

[ColdFury]

Also, the main programming thing at my school is C++, so anyone know how to get it to store a variable with more than 52 bits of precision (double-precision) since that seems to be around where the record currently lies.

You're going to need a bignum library to work that. Try www.swox.com/gmp for one.