Cut positioning error in pseudo code

[JamesBremner]

Line 1.17 records the position of a vertical cut.

I think the line should be

pos[i,j,k] = p[ t ]

Here is a simple instance to test this

1
3 1 1
1 1 1
item1cube_bin3x1x1

The output from this is

DP3UK
read problem item1cube_bin3x1x1
length points ( total 3 ) 1 2 3
width points ( total 1 ) 1
height  points ( total 1 ) 1
Most valuable item in ( 1 1 1 ) has value 1
Most valuable item in ( 2 1 1 ) has value 1
Most valuable item in ( 3 1 1 ) has value 1
vertical cut 1 0 0 1 x=0 t=0 1<1+1
vertical cut 2 0 0 1 x=0 t=1 1<1+2
item type 0 value 1 at 1 1 1
item type 0 value 1 at 2 1 1
item type 0 value 1 at 3 1 1
3 items, total value 3

Vertical cuts at 1
Depth cuts at
Horizontal cuts at

This clearly wrong: two cuts are found but they are both positioned at the same location!

The detailed debug output shows the problem and the solution

vertical cut 1 0 0 1 x=0 t=0 1<1+1
vertical cut 2 0 0 1 x=0 t=1 1<1+2

Making the change to pos[i,j,k] = p[ t ] gives this output

DP3UK
read problem item1cube_bin3x1x1
length points ( total 3 ) 1 2 3
width points ( total 1 ) 1
height  points ( total 1 ) 1
Most valuable item in ( 1 1 1 ) has value 1
Most valuable item in ( 2 1 1 ) has value 1
Most valuable item in ( 3 1 1 ) has value 1
vertical cut 1 0 0 1 x=0 t=0 1<1+1
vertical cut 2 0 0 1 x=0 t=1 1<1+2
item type 0 value 1 at 1 1 1
item type 0 value 1 at 2 1 1
item type 0 value 1 at 3 1 1
3 items, total value 3

Vertical cuts at 1 2
Depth cuts at
Horizontal cuts at

Analogour errors are present in the pseudo code for depth and horizontal cut positions.

[Cashewfly]

Excellent catch of this of this error - I'm glad and impressed that you were able to work out what was actually needed!

[JamesBremner]

Working well now.

DP3SUK
read problem item4cube_bin13cube
length points ( total 3 ) 4 8 12
width points ( total 3 ) 4 8 12
height  points ( total 3 ) 4 8 12
Most valuable item in ( 4 4 4 ) has value 64
Most valuable item in ( 4 4 8 ) has value 64
Most valuable item in ( 4 4 12 ) has value 64
Most valuable item in ( 4 8 4 ) has value 64
Most valuable item in ( 4 8 8 ) has value 64
Most valuable item in ( 4 8 12 ) has value 64
Most valuable item in ( 4 12 4 ) has value 64
Most valuable item in ( 4 12 8 ) has value 64
Most valuable item in ( 4 12 12 ) has value 64
Most valuable item in ( 8 4 4 ) has value 64
Most valuable item in ( 8 4 8 ) has value 64
Most valuable item in ( 8 4 12 ) has value 64
Most valuable item in ( 8 8 4 ) has value 64
Most valuable item in ( 8 8 8 ) has value 64
Most valuable item in ( 8 8 12 ) has value 64
Most valuable item in ( 8 12 4 ) has value 64
Most valuable item in ( 8 12 8 ) has value 64
Most valuable item in ( 8 12 12 ) has value 64
Most valuable item in ( 12 4 4 ) has value 64
Most valuable item in ( 12 4 8 ) has value 64
Most valuable item in ( 12 4 12 ) has value 64
Most valuable item in ( 12 8 4 ) has value 64
Most valuable item in ( 12 8 8 ) has value 64
Most valuable item in ( 12 8 12 ) has value 64
Most valuable item in ( 12 12 4 ) has value 64
Most valuable item in ( 12 12 8 ) has value 64
Most valuable item in ( 12 12 12 ) has value 64
======= STAGE 1============
depth cut 0 1 0 64 0 0 64<64+64
depth cut 0 1 1 64 0 0 64<64+64
depth cut 0 1 2 64 0 0 64<64+64
depth cut 0 2 0 64 0 1 64<64+0
depth cut 0 2 1 64 0 1 64<64+0
depth cut 0 2 2 64 0 1 64<64+0
depth cut 1 1 0 64 0 0 64<128+128
depth cut 1 1 1 64 0 0 64<128+128
depth cut 1 1 2 64 0 0 64<128+128
depth cut 1 2 0 64 0 1 64<128+64
depth cut 1 2 1 64 0 1 64<128+64
depth cut 1 2 2 64 0 1 64<128+64
depth cut 2 1 0 64 0 0 64<128+128
depth cut 2 1 1 64 0 0 64<128+128
depth cut 2 1 2 64 0 0 64<128+128
depth cut 2 2 0 64 0 1 64<128+128
depth cut 2 2 1 64 0 1 64<128+128
depth cut 2 2 2 64 0 1 64<128+128
======= STAGE 2============
horizontal cut 0 0 1 64 0 0 64<64+64
horizontal cut 0 0 2 64 0 1 64<64+0
horizontal cut 0 1 1 128 0 0 128<128+128
horizontal cut 0 1 2 128 0 1 128<128+0
horizontal cut 0 2 1 128 0 0 128<128+128
horizontal cut 0 2 2 128 0 1 128<128+0
horizontal cut 1 0 1 64 0 0 64<128+128
horizontal cut 1 0 2 64 0 1 64<192+64
horizontal cut 1 1 1 128 0 0 128<256+256
horizontal cut 1 1 2 128 0 1 128<384+128
horizontal cut 1 2 1 128 0 0 128<256+256
horizontal cut 1 2 2 128 0 1 128<384+128
horizontal cut 2 0 1 64 0 0 64<128+128
horizontal cut 2 0 2 64 0 1 64<192+192
horizontal cut 2 1 1 128 0 0 128<256+256
horizontal cut 2 1 2 128 0 1 128<384+384
horizontal cut 2 2 1 128 0 0 128<256+256
horizontal cut 2 2 2 128 0 1 128<384+384
item type 0 value 64 at 4 4 4
item type 0 value 64 at 4 4 8
item type 0 value 64 at 4 4 12
item type 0 value 64 at 4 8 4
item type 0 value 64 at 4 8 8
item type 0 value 64 at 4 8 12
item type 0 value 64 at 4 12 4
item type 0 value 64 at 4 12 8
item type 0 value 64 at 4 12 12
item type 0 value 64 at 8 4 4
item type 0 value 64 at 8 4 8
item type 0 value 64 at 8 4 12
item type 0 value 64 at 8 8 4
item type 0 value 64 at 8 8 8
item type 0 value 64 at 8 8 12
item type 0 value 64 at 8 12 4
item type 0 value 64 at 8 12 8
item type 0 value 64 at 8 12 12
item type 0 value 64 at 12 4 4
item type 0 value 64 at 12 4 8
item type 0 value 64 at 12 4 12
item type 0 value 64 at 12 8 4
item type 0 value 64 at 12 8 8
item type 0 value 64 at 12 8 12
item type 0 value 64 at 12 12 4
item type 0 value 64 at 12 12 8
item type 0 value 64 at 12 12 12
27 items, total value 1728

Stage 1 Cuts 18
Stage 1 Depth cuts at 4 8

Stage 2 Cuts 18
Stage 2 Horizontal cuts at 4 8

[JamesBremner]

Since this algorithm is unbounded ( creates as many duplicate orders as will fit and permits some order to be ignored ) we will not be using it for timer allocation. So closing this issue.