Coverage for moptipyapps/binpacking2d/instgen/inst

1"""

2A decoder for 2D BPP instances.

4The goal of developing this decoding procedure is that we need a deterministic

5mapping of some easy-to-process data structure to an instance of the

6two-dimensional bin packing problem. The instance produced by the mapping

7should use a pre-defined bin width, bin height, and number of items. It should

8also have a pre-defined lower bound for the number of bins required and it

9must be ensured that this lower bound can also be reached, i.e., that at least

10one solution exists that can indeed pack all items into this number of bins.

12As source data structure to be mapped, we choose the real vectors of a fixed

13length (discussed later on).

15The idea is that we take the bin width, bin height, and lower bound of the

16number of bins (let's call it `lb`) from a template instance. We also take

17the number items (let's call it `n`) from that instance.

19Now we begin with `lb` items, each of which exactly of the size and dimensions

20of a bin. At the end, we want to have `n` items. To get there, in each step of

21our decoding, we split one existing item into two items. This means that each

22step will create one additional item for the instance (while making one

23existing item smaller). This, in turn, means that we have to do `n - lb`

24decoding steps, as we start with `lb` items and, after `n - lb` steps, will

25have `lb + n - lb = n` items.

27So far so good.

28But how do we split?

30Each split that we want to perform be defined by four features:

321. the index of the item that we are going to split,

332. whether we split it horizontally or vertically,

343. where we are going to split it,

354. and how to continue if the proposed split is not possible, e.g., because

36 it would lead to a zero-width or zero-height item.

38Now we can encode this in two real numbers `selector` and `cutter` from the

39interval `[-1,1]`.

41First, we multiply the absolute value of the `selector` with the current

42number of items that we have. This is initially `2`, will then be `3` in the

43next iteration, then `4`, and so on.

44Converted to an int, the result of this multiplication gives us the index of

45the item to split.

47Then, if `cutter >= 0`, we will cut the item horizontally. Otherwise, i.e., if

48`cutter < 0`, we cut vertically.

49Where to cut is then decided by multiplying the absolute value of `cutter`

50with the length of the item in the selected cutting dimension.

52If that is not possible, we move to the next item and try again.

53If `selector < 0`, we move towards smaller indices and wrap after `0`.

54Otherwise, we move towards higher indices and wrap at the end of the item

55list.

56If we arrive back at the first object, this means that the split was not

57possible for any of the existing items.

58We now rotate the split by 90°, i.e., if we tried horizontal splits, we now

59try vertical ones and vice versa.

61It is easy to see that it must always be possible to split at least one item

62in at least one direction. Since we took the bin dimensions and numbers of

63items from an existing instance of the benchmark set, it must be possible to

64divide the bins into `n` items in one way or another. Therefore, the loop

65will eventually terminate and yield the right amount of items.

67This means that with `2 * (n - lb)` floating point numbers, we can describe an

68instance whose result is a perfect packing, without any wasted space.

70Now the benchmark instances are not just instances that can only be solved by

71perfect packings. Instead, they have some wasted space.

73We now want to add some wasted space to our instance. So far, our items occupy

74exactly `lb * bin_width * bin_height` space units. We can cut at most

75`bin_width * bin_height - 1` of these units without changing the required bins

76of the packing: We would end up with `(lb - 1) * bin_width * bin_height + 1`

77space units required by our items, which is `1` too large to fit into `lb - 1`

78bins.

80So we just do the same thing again:

81We again use two real numbers to describe each split.

82Like before, we loop through these numbers, pick the object to split, and

83compute where to split it. Just now we throw away the piece that was cut off.

84(Of course, we compute the split positions such that we never dip under the

85area requirement discussed above).

87This allows us to use additional real variables to define how the space should

88be reduced. `2 * (n - lb)` variables, we get instances requiring perfect

89packing. With every additional pair of variables, we cut some more space.

90If we would use `2 * (n - lb) + 10` variables, then we would try to select

91five items from which we can cut off a bit. This number of additional

92variables can be chosen by the user.

94Finally, we merge all items that have the same dimension into groups, as is

95the case in some of the original instances. We then shuffle these groups

96randomly, to give the instances a bit of a more unordered texture.

97The random shuffling is seeded with the binary representation of the input

98vectors.

100In the end, we have translated a real vector to a two-dimensional bin packing

101instance. Hurray.

102

103>>> space = InstanceSpace(Instance.from_resource("a04"))

104>>> print(f"{space.inst_name!r} with {space.n_different_items}/"

105... f"{space.n_items} items with area {space.total_item_area} "

106... f"in {space.min_bins} bins of "

107... f"size {space.bin_width}*{space.bin_height}.")

108'a04n' with 2/16 items with area 7305688 in 3 bins of size 2750*1220.

109

110>>> decoder = InstanceDecoder(space)

111>>> import numpy as np

112>>> x = np.array([ 0.0, 0.2, -0.1, 0.3, 0.5, -0.6, -0.7, 0.9,

113... 0.0, 0.2, -0.1, 0.3, 0.5, -0.6, -0.7, 0.9,

114... 0.0, 0.2, -0.1, 0.3, 0.5, -0.6, -0.7, 0.9,

115... 0.0, 0.2, ])

116>>> y = space.create()

117>>> decoder.decode(x, y)

118>>> space.validate(y)

119>>> res: Instance = y[0]

120>>> print(f"{res.name!r} with {res.n_different_items}/"

121... f"{res.n_items} items with area {res.total_item_area} "

122... f"in {res.lower_bound_bins} bins of "

123... f"size {res.bin_width}*{res.bin_height}.")

124'a04n' with 15/16 items with area 10065000 in 3 bins of size 2750*1220.

125

126>>> print(space.to_str(y))

127a04n;15;2750;1220;1101,1098;2750,244;2750,98;1101,171;1649,171;2750,976;\

128441,122;1649,122;2750,10;2750,1,2;2750,3;1649,1098;2750,878;2750,58;660,122

129

130

131>>> x = np.array([ 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0,

132... 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0,

133... 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0,

134... 0.0, 0.0, ])

135>>> y = space.create()

136>>> decoder.decode(x, y)

137>>> space.validate(y)

138>>> res: Instance = y[0]

139>>> print(f"{res.name!r} with {res.n_different_items}/"

140... f"{res.n_items} items with area {res.total_item_area} "

141... f"in {res.lower_bound_bins} bins of "

142... f"size {res.bin_width}*{res.bin_height}.")

143'a04n' with 3/16 items with area 10065000 in 3 bins of size 2750*1220.

144

145>>> print(space.to_str(y))

146a04n;3;2750;1220;2750,1216,2;2750,1,13;2750,1215

147

148>>> from math import nextafter

149>>> a1 = nextafter(1.0, -10)

150>>> x = np.array([ a1, a1, a1, a1, a1, a1, a1, a1,

151... a1, a1, a1, a1, a1, a1, a1, a1,

152... a1, a1, a1, a1, a1, a1, a1, a1,

153... a1, a1, ])

154>>> y = space.create()

155>>> decoder.decode(x, y)

156>>> space.validate(y)

157>>> res: Instance = y[0]

158>>> print(f"{res.name!r} with {res.n_different_items}/"

159... f"{res.n_items} items with area {res.total_item_area} "

160... f"in {res.lower_bound_bins} bins of "

161... f"size {res.bin_width}*{res.bin_height}.")

162'a04n' with 4/16 items with area 10065000 in 3 bins of size 2750*1220.

163

164>>> print(space.to_str(y))

165a04n;4;2750;1220;2750,1208;2750,1219;2750,1220;2750,1,13

166

167>>> from math import nextafter

168>>> a1 = nextafter(-1.0, 10)

169>>> x = np.array([ a1, a1, a1, a1, a1, a1, a1, a1,

170... a1, a1, a1, a1, a1, a1, a1, a1,

171... a1, a1, a1, a1, a1, a1, a1, a1,

172... a1, a1, ])

173>>> y = space.create()

174>>> decoder.decode(x, y)

175>>> space.validate(y)

176>>> res: Instance = y[0]

177>>> print(f"{res.name!r} with {res.n_different_items}/"

178... f"{res.n_items} items with area {res.total_item_area} "

179... f"in {res.lower_bound_bins} bins of "

180... f"size {res.bin_width}*{res.bin_height}.")

181'a04n' with 5/16 items with area 10065000 in 3 bins of size 2750*1220.

182

183>>> print(space.to_str(y))

184a04n;5;2750;1220;2750,1220;2730,1220;2748,1220;1,1220,4;2,1220,9

185

186>>> from math import nextafter

187>>> a1 = nextafter(-1.0, 10)

188>>> x = np.array([ a1, a1, a1, a1, a1, a1, a1, a1,

189... a1, a1, a1, a1, a1, a1, a1, a1,

190... a1, a1, a1, a1, a1, a1, a1, a1,

191... a1, a1, 0.3, 0.7 ])

192>>> y = space.create()

193>>> decoder.decode(x, y)

194>>> space.validate(y)

195>>> res: Instance = y[0]

196>>> print(f"{res.name!r} with {res.n_different_items}/"

197... f"{res.n_items} items with area {res.total_item_area} "

198... f"in {res.lower_bound_bins} bins of "

199... f"size {res.bin_width}*{res.bin_height}.")

200'a04n' with 6/16 items with area 10064146 in 3 bins of size 2750*1220.

201

202>>> print(space.to_str(y))

203a04n;6;2750;1220;2,1220,9;1,1220,3;2748,1220;1,366;2750,1220;2730,1220

204

205>>> from math import nextafter

206>>> a1 = nextafter(-1.0, 10)

207>>> x = np.array([ a1, a1, a1, a1, a1, a1, a1, a1,

208... a1, a1, a1, a1, a1, a1, a1, a1,

209... a1, a1, a1, a1, a1, a1, a1, a1,

210... a1, a1, 0.3, 0.7, -0.2, -0.3,

211... 0.5, -0.3])

212>>> y = space.create()

213>>> decoder.decode(x, y)

214>>> space.validate(y)

215>>> res: Instance = y[0]

216>>> print(f"{res.name!r} with {res.n_different_items}/"

217... f"{res.n_items} items with area {res.total_item_area} "

218... f"in {res.lower_bound_bins} bins of "

219... f"size {res.bin_width}*{res.bin_height}.")

220'a04n' with 6/16 items with area 10061706 in 3 bins of size 2750*1220.

221

222>>> print(space.to_str(y))

223a04n;6;2750;1220;2,1220,7;2750,1220;2730,1220;1,1220,5;1,366;2748,1220

224

225

226>>> x = np.array([ 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0,

227... 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0,

228... 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0,

229... 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0,

230... 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0,

231... 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0,

232... 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0,

233... 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0,

234... 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0,

235... 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0,

236... 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0,

237... 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0,

238... 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0,

239... 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0,

240... 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0,

241... 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0,

242... 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0,

243... -1.0, -1.0, -1.0, -1.0, -1.0, -1.0, -1.0, -1.0,

244... -1.0, -1.0, -1.0, -1.0, -1.0, -1.0, -1.0, -1.0,

245... -1.0, -1.0, -1.0, -1.0, -1.0, -1.0, -1.0, -1.0,

246... -1.0, -1.0, -1.0, -1.0, -1.0, -1.0, -1.0, -1.0,

247... -1.0, -1.0, -1.0, -1.0, -1.0, -1.0, -1.0, -1.0,

248... -1.0, -1.0, -1.0, -1.0, -1.0, -1.0, -1.0, -1.0,

249... -1.0, -1.0, -1.0, -1.0, -1.0, -1.0, -1.0, -1.0,

250... -1.0, -1.0, -1.0, -1.0, -1.0, -1.0, -1.0, -1.0,

251... -1.0, -1.0, -1.0, -1.0, -1.0, -1.0, -1.0, -1.0,

252... -1.0, -1.0, -1.0, -1.0, -1.0, -1.0, -1.0, -1.0,

253... -1.0, -1.0, -1.0, -1.0, -1.0, -1.0, -1.0, -1.0,

254... -1.0, -1.0, -1.0, -1.0, -1.0, -1.0, -1.0, -1.0,

255... -1.0, -1.0, -1.0, -1.0, -1.0, -1.0, -1.0, -1.0,

256... 0.0, 0.0, ])

257>>> y = space.create()

258>>> decoder.decode(x, y)

259>>> space.validate(y)

260>>> res: Instance = y[0]

261>>> print(f"{res.name!r} with {res.n_different_items}/"

262... f"{res.n_items} items with area {res.total_item_area} "

263... f"in {res.lower_bound_bins} bins of "

264... f"size {res.bin_width}*{res.bin_height}.")

265'a04n' with 5/16 items with area 9910948 in 3 bins of size 2750*1220.

266

267>>> print(space.to_str(y))

268a04n;5;2750;1220;2698,1;2750,1,12;2750,1216;2750,1215;2750,1160

269"""

270from math import isfinite

271from typing import Final

272

273import numpy as np

274from moptipy.api.encoding import Encoding

275from numpy.random import default_rng

276from pycommons.types import check_int_range, type_error

277

278from moptipyapps.binpacking2d.instance import Instance

279from moptipyapps.binpacking2d.instgen.instance_space import InstanceSpace

280

281

282class InstanceDecoder(Encoding):

283 """Decode a string of `n` real values in `[0,1]` to an instance."""

284

285 def __init__(self, space: InstanceSpace) -> None:

286 """

287 Create the instance decoder.

288

289 :param space: the instance description and space

290 """

291 super().__init__()

292 if not isinstance(space, InstanceSpace):

293 raise type_error(space, "space", InstanceSpace)

294 #: the instance description

295 self.space: Final[InstanceSpace] = space

296

297 def get_x_dim(self, slack: float | int = 0) -> int:

298 """

299 Get the minimum dimension that a real vector must have.

300

301 :param slack: a parameter denoting the amount of slack for reducing

302 the item size

303 :return: the minimum dimension

304 """

305 if not isinstance(slack, float | int):

306 raise type_error(slack, "slack", (float, int))

307 if (not isfinite(slack)) or (slack < 0):

308 raise ValueError(f"slack={slack} is invalid")

309 base: Final[int] = check_int_range(

310 self.space.n_items - self.space.min_bins, "base", 1, 1_000_000)

311 added: Final[int] = int(slack * base + 0.5)

312 if (added < 0) or (added > 1_000_000):

313 raise ValueError(f"invalid result {added} based "

314 f"on slack={slack} and base={base}")

315 return 2 * (base + added)

316

317 def decode(self, x: np.ndarray, y: list[Instance]) -> None:

318 """

319 Decode the real-valued array to a 2D BPP instance.

320

321 :param x: an array with values in [-1, 1]

322 :param y: the instance receiver

323 """

324 # We start by using the prescribed number of bins as items.

325 # There will be n_bins items, each of which has exactly the size of a

326 # bin. Therefore, we know that all items fit exactly into n_bins bins.

327 bin_width: Final[int] = self.space.bin_width

328 bin_height: Final[int] = self.space.bin_height

329 n_bins: Final[int] = self.space.min_bins

330 items: list[list[int]] = [

331 [bin_width, bin_height] for _ in range(n_bins)]

332

333 # Now we need to make n_items - n_bins cuts. Each cut will divide one

334 # item into two items. Therefore, each cut yields exactly one new

335 # item. Therefore, after n_items - n_bins cuts we get n_items - n_bins

336 # new items. Since we start with n_bins items, this means that we get

337 # n_items - n_bins + n_bins items at the end, which are exactly

338 # n_items.

339 #

340 # Each cut cuts an item into two items along either the horizontal or

341 # vertical dimension. If we would put the two new, smaller items back

342 # together, they would exactly result in the item that we just cut.

343 # Therefore, they do fit into the same area and their area sum is also

344 # the same. Therefore, the overall area and the overall number of

345 # required bins will also stay the same.

346 x_idx: int = 0

347 for cur_n_items in range(n_bins, self.space.n_items):

348 # In each iteration of this loop, we perform one cut.

349 # This means, that we add exactly one item to the item list.

350 # Our counter variable `cur_n_items`, which starts at `n_bins`

351 # and iterates until just before the target number of items

352 # `self.desc.n_items` represents the current number of items

353 # in our list `items`.

354 # It thus always holds that `cur_n_items == len(items)`.

355

356 # Each cut is described by four properties:

357 # 1. The index of the item that we want to cut.

358 # 2. The direction (horizontal or vertical) into which we cut.

359 # 3. The location where we will cut along this dimension.

360 # 4. The direction into which we will search for the next item

361 # if the current item cannot be cut this way.

362 # These four properties are encoded in two real numbers `selector`

363 # and `cutter` from `[-1, 1]`.

364

365 # The first number is `sel`. It encodes (1) and (4).

366 # First, we multiply `selector` with `cur_n_items` and take this

367 # modulo `cur_n_items`. This gives us a value `t` with

368 # `-cur_n_items < t < cur_n_items`. By adding `cur_n_items`

369 # and repeating the modulo division, we get

370 # `0 <= sel_i < cur_n_items`.

371 # `sel_i` is the index of the item that we want to cut.

372 selector: float = x[x_idx]

373 x_idx += 1

374

375 sel_i: int = ((int(cur_n_items * selector) % cur_n_items)

376 + cur_n_items) % cur_n_items

377 orig_sel_i: int = sel_i # the original selection index.

378

379 # Now, it may not be possible to cut this item.

380 # The idea is that if we cannot cut the item, we simply try to cut

381 # the next item.

382 # The next item could be the one at the next-higher index or the

383 # one at the next lower index.

384 # If `selector < 0.0`, then we will next try the item at the next

385 # lower index. If `selector >= 0.0`, we will move to the next

386 # higher index.

387 # Of course, we will wrap our search when reaching either end of

388 # the list.

389 #

390 # If we arrive back at `orig_sel_i`, then we have tried to cut

391 # each item in the list in the prescribed cutting direction,

392 # however none could be cut.

393 # In this case, we will change the cutting direction.

394 #

395 # It must be possible to cut at least one item in at least one

396 # direction, or otherwise the problem would not be solvable.

397 # Therefore, we know that this way, trying all items in all

398 # directions in the worst case, we will definitely succeed.

399 sel_dir: int = -1 if selector < 0.0 else 1

400

401 # `cutter` tells us where to cut and in which direction.

402 # If `cutter >= 0`, then we will cut horizontally and

403 # if `cutter < 0`, we cut vertically.

404 # Each item is described by list `[width, height]`, so cutting

405 # horizontally means picking a vertical height coordinate and

406 # cutting horizontally along it. This means that for horizontal

407 # cuts, the `cut_dimension` should be `1` and for vertical cuts,

408 # it must be `0`.

409 cutter: float = x[x_idx]

410 x_idx += 1

411 cut_dimension: int = 1 if cutter >= 0.0 else 0

412

413 while True:

414 cur_item: list[int] = items[sel_i] # Get the item to cut.

415

416 item_size_in_dim: int = cur_item[cut_dimension]

417

418 # We define the `cut_modulus` as the modulus for the cutting

419 # operation. We will definitely get a value for `cut_position`

420 # such that `0 < cut_position <= cut_modulus`. This means that

421 # we will get `0 < cut_position < item_size_in_dim`.

422 # Therefore, if `cut_modulus > 1`, then we know that there

423 # definitely is a `cut_position` at which we can cut the

424 # current item and obtain two new items that have both

425 # non-zero width and height.

426 cut_modulus: int = item_size_in_dim - 1

427 if cut_modulus > 0: # Otherwise, we cannot cut the item.

428 cut_position: int = (((int(

429 cut_modulus * cutter) % cut_modulus) + cut_modulus)

430 % cut_modulus) + 1

431

432 if 0 < cut_position < item_size_in_dim: # Sanity check...

433 # Now we perform the actual cut.

434 # The original item now gets `cut_position` as the

435 # size in the `cut_dimension`, the other one gets

436 # `item_size_in_dim - cut_position`. Therefore, the

437 # overall size remains the same.

438 cur_item[cut_dimension] = cut_position

439 cur_item = cur_item.copy()

440 cur_item[cut_dimension] = (

441 item_size_in_dim - cut_position)

442 items.append(cur_item)

443 break # we cut one item and can stop

444

445 sel_i = ((((sel_i + sel_dir) % cur_n_items) + cur_n_items)

446 % cur_n_items)

447 if sel_i == orig_sel_i:

448 cut_dimension = 1 - cut_dimension

449

450 # At this stage, our instance can only be solved with a perfect

451 # packing. The items need to be placed perfectly together and they

452 # will cover the complete `current_area`.

453 bin_area: Final[int] = bin_width * bin_height

454 current_area: int = n_bins * bin_area

455

456 # However, requiring a perfect packing may add hardness to the problem

457 # that does not exist in the original problem.

458 # We now want to touch some of the items and make them a bit smaller.

459 # However, we must never make them smaller as

460 # `current_area - bin_area`, because then we could create a situation

461 # where less than `n_bins` bins are required.

462 # Also, we never want to slide under the `total_item_area` prescribed

463 # by the original problem. If the original problem prescribed a

464 # perfect packing, then we will create a perfect packing.

465 min_area: Final[int] = current_area - bin_area + 1

466

467 # If and only if the input array still has information left and if we

468 # still have area that we can cut, then let's continue.

469 # We will keep cutting items, but this time, we throw away the piece

470 # that we cut instead of adding it as item. Of course, we never cut

471 # more than what we are permitted to.

472 max_x_idx: Final[int] = len(x)

473 cur_n_items = list.__len__(items)

474 while (x_idx < max_x_idx) and (current_area > min_area):

475 # We perform the same selection and cutting choice.

476 selector = x[x_idx]

477 x_idx += 1

478 sel_i = ((int(cur_n_items * selector) % cur_n_items)

479 + cur_n_items) % cur_n_items

480 orig_sel_i = sel_i # the original selection index.

481 sel_dir = -1 if selector < 0.0 else 1

482 cutter = x[x_idx]

483 x_idx += 1

484 cut_dimension = 1 if cutter >= 0.0 else 0

485

486 # We have selected the item and got the cutter value, too.

487 # Now we try to perform the cut. If we cannot cut, we try

488 # the next item. If we could not cut any item along the

489 # cut dimension, we switch the cut dimension.

490 # However, we may fail to cut anything (which means that

491 # we arrive at `step == 2`). In this case, we just skip

492 # this cut.

493 step: int = 0

494 while step < 2: # This time, we may actually fail to cut.

495 cur_item = items[sel_i] # Get the item to cut.

496

497 item_size_in_dim = cur_item[cut_dimension]

498 item_size_in_other_dim: int = cur_item[1 - cut_dimension]

499 # This time, the `cut_modulus` is also limited by the area

500 # that we can actually cut. This is `current_area - min_area`.

501 # Now each cut along the `cut_dimension` will cost us

502 # `item_size_in_other_dim` area units.

503 cut_modulus = min(

504 (current_area - min_area) // item_size_in_other_dim,

505 item_size_in_dim) - 1

506 if cut_modulus > 0:

507 cut_position = (((int(

508 cut_modulus * cutter) % cut_modulus) + cut_modulus)

509 % cut_modulus) + 1

510

511 if 0 < cut_position < item_size_in_dim:

512 # We cut away cut_position and do not add the area at

513 # the end.

514 cur_item[cut_dimension] = \

515 item_size_in_dim - cut_position

516 break # we cut one item and can stop

517

518 sel_i = ((((sel_i + sel_dir) % cur_n_items) + cur_n_items)

519 % cur_n_items)

520 if sel_i == orig_sel_i:

521 cut_dimension = 1 - cut_dimension

522 step += 1 # If we tried everything, this enforces a stop.

523

524 # Finally, we sort the items in order to merge items of the

525 # same dimension.

526 items.sort()

527 lo: int = 0

528 n_items: int = list.__len__(items)

529 while lo < n_items:

530 # For each item in the list, we try to find all items of the same

531 # dimension. Since the list is sorted, these items must all be

532 # located together.

533 hi: int = lo

534 cur_item = items[lo]

535 while (hi < n_items) and (items[hi] == cur_item):

536 hi += 1

537 cur_item.append(hi - lo) # We now have the item multiplicity.

538 # We delete all items with the same dimension (which must come

539 # directly afterward).

540 hi -= 1

541 while lo < hi:

542 del items[hi]

543 hi -= 1

544 n_items -= 1

545 lo += 1 # Move to the next item

546

547 # Now all items are sorted. This may or may not be a problem:

548 # Some heuristics may either benefit or suffer if the item list

549 # has a pre-defined structure. Therefore, we want to try to at least

550 # somewhat remove the order and make the item list order more random.

551 default_rng(int.from_bytes(x.tobytes())).shuffle(items)

552

553 # And now we can fill in the result as the output of our encoding.

554 res: Instance = Instance( # Generate the instance

555 self.space.inst_name, bin_width, bin_height, items)

556 if list.__len__(y) > 0: # If the destination has length > 0...

557 y[0] = res # ...store the instance at index 0,

558 else: # otherwise

559 y.append(res) # add the instance to it.

Coverage for moptipyapps / binpacking2d / instgen / inst_decoding.py: 94%

103 statements