Problem 212

[pjt33]

The value I get for the sum of the volumes of the first 100 cuboids is less than the hint value given for the sum of their union, so I must have a bug in my lagged Fibonacci generator. However, I can't see anything which looks wrong, and it produces the first two cuboids correctly. Could someone please post C₁₀₀ for comparison? I make it {(6055,553,2105),(339,66,283)}.

[jaap]

The value I get for the sum of the volumes of the first 100 cuboids is less than the hint value given for the sum of their union, so I must have a bug in my lagged Fibonacci generator. However, I can't see anything which looks wrong, and it produces the first two cuboids correctly. Could someone please post C₁₀₀ for comparison? I make it {(6055,553,2105),(339,66,283)}.

Here are what I think are 99-101:
1119 3181 374 232 297 121
8487 1033 5529 307 337 46
6088 4299 4383 44 34 129

[daniel.is.fischer]

I agree with jaap.
Do you get
*Lagged> cube 20
[2323,1925,7281,154,87,30]
and
*Lagged> cube 24
[312,6798,2104,138,325,67]
?
In other words, I suspect overflow.

[pjt33]

Daniel, you're spot on about the overflow. Thanks, both of you.

[DNS]

A method I design is sloooow. For 100 cuboids time is about 0.5 min... Can somebody confirm n=1579 V=13022800300 ?

[Georg]

Can somebody confirm n=1579 V=13022800300 ?

Confirmed.

[DNS]

Thank you, Georg!
My way is not wrong

[stijn263]

My way is not wrong

Just a bit slow

I don't know what programming language you are using, but my experience with C++ is that sometimes a significant speed boost can be gained by using a compiler that performs optimisations. I've seen programs I made run up to 10 times faster by allowing the optimisations.. Recursive algorithms are the best target

[DNS]

Thanks, stijn263, for the idea.
I use C++ 5.02 from Borland, my PC is Duron 1.4, 512Mb.
As I note, when __int64 type is used, program runs ~10 times slower in comparision with long type. But long type is short ( ) for preserv a result.
Sometimes I use Ruby, but it is 10 times more slow than C++ with __int64

[JamieCamardelle]

For problem 212, combined volume of cuboids, I wrote code that works great for some test sets of cuboids I built. It uses a generalized DeMoivre’s theorem. Even though my test sets are complex, with many different configurations of overlap between cuboids, and the code captures the overlaps and adds or subtracts intersecting volumes as appropriate, it doesn’t capture any overlap between the first 100 cuboids generated for the problem.
I must assume there is some overlap between at least two cuboids in the first 100, otherwise the combined volume of the cuboids would be 776975023 instead of 723581599 given in the problem explanation.
If someone could please tell me the positions of at least two cuboids that overlap among the first 100, I can debug and hopefully settle the issue and solve the problem.
I really appreciate anyone's help.
PS - I assume my cuboid generator is correct since my first two cuboids match the ones given in the problem explanation.

[stijn263]

Actually, I get 726218359 without taking the overlapping in account..

There's an intersection with origin at (9872,3710,7557) between cuboids 58 and 67 (zero based indices).

Also, you could still have an integer overflow problem, despite the fact that your first two cuboids are correct..

[Tommy137]

What do you get for S₅₅?

[JamieCamardelle]

Thanks for your help. Maybe I have the integer overflow problem.
With indices starting at 1, I have: C[[58]]={{4223, 2059, 4343}, {349, 205, 175}},
C[[67]]={{4223, 2353, 7199}, {251, 229, 190}}
I guess that your C[[58]], C[[67]] is my C[[59]], C[[68]].
I have: C[[59]]={{8799, 3953, 3807}, {202, 256, 70}}, C[[68]]={{4583, 3639, 9663}, {305, 119, 67}}
If my results don't match yours, I'll guess it is a problem with my cuboid list.

[JamieCamardelle]

What do you get for S₅₅?

I get s[55]=764463

I get C[[55]]={{5903, 857, 9503}, {164, 336, 63}}

[Tommy137]

What do you get for S₅₅?

I get s[55]=764463

I get C[[55]]={{5903, 857, 9503}, {164, 336, 63}}

s[55] is correct, but your cuboid-values for 55, 59 and 68 aren't...

[stijn263]

Some additional values for comparison can be found here

[JamieCamardelle]

Thanks for the help. I was able to figure out that the problem was in my cuboid list, and not in my volume computing algorithm. My mistake was dumber than I thought - not integer overflow, but incorrectly computing all sk for k > 55.

[sivakd]

Should the wording

x_(0) ≤ X ≤ x_(0)+dx, y_(0) ≤ Y ≤ y_(0)+dy and z_(0) ≤ Z ≤ z_(0)+dz

have been

x_(0) ≤ X < x_(0)+dx, y_(0) ≤ Y < y_(0)+dy and z_(0) ≤ Z < z_(0)+dz

for this problem? Otherwise, how can the volume be dx*dy*dz?

Say, {(0,0,0),(1,1,1)} would have a volume of 8 with the former definition and 1 with the later. Isn't it?

Anyway, I solved this problem, but wasted a lot of time on this and only by looking at the non-overlap volume in the above post I figured out what I was doing wrong as per the expected definition of the problem.

[hk]

Should the wording

x_(0) ≤ X ≤ x_(0)+dx, y_(0) ≤ Y ≤ y_(0)+dy and z_(0) ≤ Z ≤ z_(0)+dz

have been

x_(0) ≤ X < x_(0)+dx, y_(0) ≤ Y < y_(0)+dy and z_(0) ≤ Z < z_(0)+dz

for this problem? Otherwise, how can the volume be dx*dy*dz?

Say, {(0,0,0),(1,1,1)} would have a volume of 8 with the former definition and 1 with the later. Isn't it?

{(0,0,0),(1,1,1)} and x_(0) ≤ X ≤ x_(0)+dx, y_(0) ≤ Y ≤ y_(0)+dy and z_(0) ≤ Z ≤ z_(0)+dz

represents a cube with side 1 with all its surfaces.

{(0,0,0),(1,1,1)} and x_(0) ≤ X < x_(0)+dx, y_(0) ≤ Y < y_(0)+dy and z_(0) ≤ Z < z_(0)+dz
represents a cube with side 1 with three of its 6 surfaces.
Both have volume 1.

[Lord_Farin]

You may want to notice that the volume of a cuboid is not the same as the amount of lattice points contained in it. That is what led to your confusion, I believe. Since planes have volume zero in 3D, it does not matter if we include the boundary of the cuboid or not: the volume stays the same.