P81 · Packing and covering · Classic · Applied frontier · Hard

Irregular strip nesting · GARDEYN9 · 47 pieces, all different

Given the strip height H, a set of piece polygons and how many copies of each are demanded, place every piece in the strip so that the largest x-coordinate over all vertices — the occupied length L — is as small as possible. Pieces may only be translated and turned about their own origin by 0°, 90°, 180° or 270°; they may touch but their interiors may not overlap, and none may leave the strip.

InstanceGARDEYN9 · 47 pieces, all different

ObjectiveMinimize occupied length

Formal definition

ContainerThe closed region {x ≥ 0, 0 ≤ y ≤ H}; a piece may touch the boundary. H is fixed per case: 20000 for GARDEYN1, 10000 for GARDEYN2, 44 for GARDEYN9
SubmissionOne placement per copy of a piece: its type, its turn and its shift. The piece polygons (concave and asymmetric allowed), the demands and the strip height are frozen by the case; a submission changes no vertex, count or shape
MovesEach copy is turned about its own origin by 0°, 90°, 180° or 270°, then shifted by (x, y). No reflection, scaling or free angle
No overlapNo two copies have intersecting interiors: touching along an edge or at a vertex is allowed; containment or any positive-area overlap is not
Exact verificationCoordinates are decimal strings of at most 24 places, scaled by 10²⁴ to integers, and the four right-angle turns keep them integers. Every polygon is triangulated exactly and every triangle pair is tested by separating axes with BigInt cross products; equal projection endpoints are contact, not overlap. No floating point and no ε
ScoreThe largest x-coordinate over all placed vertices, L, exact to 24 places; smaller is better. The source file's container length is not the score, and a claimed score is ignored
ObjectiveMinimise L over all legal placements

Open the full editor ↗

VERIFIED CONSTRUCTIONoccupied length 65.770

Getting a feel for it

Why these three cases

The GARDEYN family comes from real garment-cutting and direct-to-film print jobs: concave, asymmetric outlines with few repeats. GARDEYN1 is 10 types, 5 copies each; GARDEYN2 is 50 pieces, all different; GARDEYN9 is 47 different print motifs in a strip only 44 high. Each case is complete on its own, and an answer for one says nothing about another.

Quarter turns only

Nesting solvers in the literature usually allow continuous rotation, but continuous angles carry trigonometry into the coordinates and cannot be verified exactly. Here only 0°, 90°, 180° and 270° are allowed, every coordinate stays rational, and the verifier decides contact and overlap with no tolerance at all. It also means this problem is not directly comparable with published results that allow free rotation.

Where the frontier is

There is no external record. The Sparrow repository publishes its own layouts (lengths 16181.169, 47382.125 and 65.792223), each of which verifies exactly under this problem's rules; starting from them, a short exact compaction here brought the three cases to 16177.649, 47319.670679 and 65.769735999999999, shipped as baselines bylined MinMax Arena. None of these is a proof of optimality or a literature record; the editor can load Sparrow's layouts and the weaker 20-second starting layouts for comparison.

Source

Where the data comes from

The instance geometry and the reference layouts come from the Sparrow repository (Jeroen Gardeyn, Greet Vanden Berghe and Tony Wauters, KU Leuven; MIT) at revision 649d4c78, with the original decimal coordinates kept free of floating-point truncation; each case's input hashes and source links can be downloaded from the editor.

Source

Current leader

65.769735999999999

occupied length

Answer sourceMinMax Arena

Solution methodMinMax Arena offline search

Challenge this record ↗Submit a proof / idea ↓Share a proof or idea in the discussion. Accepted contributions can earn proof points.

Record holder's solver noteNo solver note yet (expand)＋

The record holder has not shared a solver note yet.

ANSWER FORMAT

How to write your answer

The strip {x ≥ 0, 0 ≤ y ≤ H}: H is the material's width, drawn vertically, and the material runs on to the right without end. Each piece is a polygon given by its own decimal vertices, and may be concave.

Submit {schemaVersion: "1", problemKey: "V09", instanceId, placements}, where instanceId is the id in the case's instance file (v09-gardeyn2-v1, say). placements has one entry {typeId, rotation, x, y} per copy of a piece: typeId names the piece type, rotation is 0, 90, 180 or 270, and x, y are decimal strings (at most 24 fractional digits, absolute value at most 1000000) — the piece is turned about its own origin, then shifted. Each type must occur exactly as many times as demanded; the order of the array does not matter. The piece shapes, the strip height and the demands can be downloaded from the editor; they are not part of the answer.

The current leader's answer

{
  "instanceId": "v09-gardeyn9-v1",
  "placements": [
    {
      "rotation": 270,
      "typeId": "t0",
      "x": "49.536922",
      "y": "43.833246"
    },
    {
      "rotation": 0,
      "typeId": "t1",
      "x": "53.310434",
      "y": "14.081869"
    },
    {
      "rotation": 180,
      "typeId": "t10",
      "x": "57.936388",
      "y": "22.015273"
    },
    {
      "rotation": 180,
      "typeId": "t11",
      "x": "47.73577",
      "y": "42.487798"
    },
    {
      "rotation": 270,
      "typeId": "t12",
      "x": "64.106534",
      "y": "8.857996"
    },
    {
      "rotation": 90,
      "typeId": "t13",
      "x": "65.303802",
      "y": "26.59188"
    },
    {
      "rotation": 0,
      "typeId": "t14",
      "x": "41.079309",
      "y": "42.308482"
    },
    {
      "rotation": 0,
      "typeId": "t15",
      "x": "14.254236",
      "y": "17.697975"
    },
    {
      "rotation": 180,
      "typeId": "t16",
      "x": "33.633194",
      "y": "32.989586"
    },
    {
      "rotation": 180,
      "typeId": "t17",
      "x": "49.140784",
      "y": "35.675826"
    },
    {
      "rotation": 90,
      "typeId": "t18",
      "x": "29.769226",
      "y": "32.632156"
    },
    {
      "rotation": 0,
      "typeId": "t19",
      "x": "0.12339478",
      "y": "14.889212"
    },
    {
      "rotation": 180,
      "typeId": "t2",
      "x": "19.762715",
      "y": "18.880486"
    },
    {
      "rotation": 90,
      "typeId": "t20",
      "x": "10.523917",
      "y": "27.146084"
    },
    {
      "rotation": 0,
      "typeId": "t21",
      "x": "39.447822",
      "y": "36.31345"
    },
    {
      "rotation": 90,
      "typeId": "t22",
      "x": "66.171911",
      "y": "20.259862"
    },
    {
      "rotation": 90,
      "typeId": "t23",
      "x": "28.976716",
      "y": "0.12277269"
    },
    {
      "rotation": 180,
      "typeId": "t24",
      "x": "65.552142",
      "y": "43.86438"
    },
    {
      "rotation": 270,
      "typeId": "t25",
      "x": "0.12577166",
      "y": "33.646435"
    },
    {
      "rotation": 90,
      "typeId": "t26",
      "x": "54.330047",
      "y": "30.869584"
    },
    {
      "rotation": 0,
      "typeId": "t27",
      "x": "12.173116",
      "y": "0.13359737"
    },
    {
      "rotation": 90,
      "typeId": "t28",
      "x": "54.360727",
      "y": "28.909076"
    },
    {
      "rotation": 270,
      "typeId": "t29",
      "x": "5.3599937",
      "y": "34.622522"
    },
    {
      "rotation": 270,
      "typeId": "t3",
      "x": "9.216326",
      "y": "43.865227"
    },
    {
      "rotation": 0,
      "typeId": "t30",
      "x": "40.429454",
      "y": "0.20132125"
    },
    {
      "rotation": 0,
      "typeId": "t31",
      "x": "28.346242",
      "y": "-0.68400956"
    },
    {
      "rotation": 0,
      "typeId": "t32",
      "x": "48.649913",
      "y": "13.506231"
    },
    {
      "rotation": 180,
      "typeId": "t33",
      "x": "44.865562",
      "y": "28.06545"
    },
    {
      "rotation": 270,
      "typeId": "t34",
      "x": "21.966038",
      "y": "21.293765"
    },
    {
      "rotation": 90,
      "typeId": "t35",
      "x": "30.963012",
      "y": "36.3955"
    },
    {
      "rotation": 180,
      "typeId": "t36",
      "x": "42.062806",
      "y": "36.838852"
    },
    {
      "rotation": 0,
      "typeId": "t37",
      "x": "10.737913",
      "y": "18.830784"
    },
    {
      "rotation": 270,
      "typeId": "t38",
      "x": "48.396311",
      "y": "14.067703"
    },
    {
      "rotation": 270,
      "typeId": "t39",
      "x": "54.141184",
      "y": "40.519108"
    },
    {
      "rotation": 90,
      "typeId": "t4",
      "x": "55.626939",
      "y": "26.912271"
    },
    {
      "rotation": 270,
      "typeId": "t40",
      "x": "40.972948",
      "y": "19.10906"
    },
    {
      "rotation": 0,
      "typeId": "t41",
      "x": "56.640816",
      "y": "13.829794"
    },
    {
      "rotation": 90,
      "typeId": "t42",
      "x": "40.960554",
      "y": "9.410119"
    },
    {
      "rotation": 270,
      "typeId": "t43",
      "x": "0.13183697",
      "y": "43.873856"
    },
    {
      "rotation": 180,
      "typeId": "t44",
      "x": "33.085811",
      "y": "28.146021"
    },
    {
      "rotation": 180,
      "typeId": "t45",
      "x": "56.082034",
      "y": "29.164982"
    },
    {
      "rotation": 180,
      "typeId": "t46",
      "x": "12.161658",
      "y": "14.632311"
    },
    {
      "rotation": 270,
      "typeId": "t5",
      "x": "20.385334",
      "y": "35.515647"
    },
    {
      "rotation": 180,
      "typeId": "t6",
      "x": "39.206991",
      "y": "43.874355"
    },
    {
      "rotation": 90,
      "typeId": "t7",
      "x": "41.167263",
      "y": "7.9403256"
    },
    {
      "rotation": 0,
      "typeId": "t8",
      "x": "17.961679",
      "y": "11.781264"
    },
    {
      "rotation": 180,
      "typeId": "t9",
      "x": "22.18915",
      "y": "18.891047"
    }
  ],
  "problemKey": "V09",
  "schemaVersion": "1"
}

Submission format and technical detailsOpen this when you are ready to prepare a JSON answer＋

Instance parameters

{
  "case": "gardeyn9"
}

The current leader's answer

{
  "instanceId": "v09-gardeyn9-v1",
  "placements": [
    {
      "rotation": 270,
      "typeId": "t0",
      "x": "49.536922",
      "y": "43.833246"
    },
    {
      "rotation": 0,
      "typeId": "t1",
      "x": "53.310434",
      "y": "14.081869"
    },
    {
      "rotation": 180,
      "typeId": "t10",
      "x": "57.936388",
      "y": "22.015273"
    },
    {
      "rotation": 180,
      "typeId": "t11",
      "x": "47.73577",
      "y": "42.487798"
    },
    {
      "rotation": 270,
      "typeId": "t12",
      "x": "64.106534",
      "y": "8.857996"
    },
    {
      "rotation": 90,
      "typeId": "t13",
      "x": "65.303802",
      "y": "26.59188"
    },
    {
      "rotation": 0,
      "typeId": "t14",
      "x": "41.079309",
      "y": "42.308482"
    },
    {
      "rotation": 0,
      "typeId": "t15",
      "x": "14.254236",
      "y": "17.697975"
    },
    {
      "rotation": 180,
      "typeId": "t16",
      "x": "33.633194",
      "y": "32.989586"
    },
    {
      "rotation": 180,
      "typeId": "t17",
      "x": "49.140784",
      "y": "35.675826"
    },
    {
      "rotation": 90,
      "typeId": "t18",
      "x": "29.769226",
      "y": "32.632156"
    },
    {
      "rotation": 0,
      "typeId": "t19",
      "x": "0.12339478",
      "y": "14.889212"
    },
    {
      "rotation": 180,
      "typeId": "t2",
      "x": "19.762715",
      "y": "18.880486"
    },
    {
      "rotation": 90,
      "typeId": "t20",
      "x": "10.523917",
      "y": "27.146084"
    },
    {
      "rotation": 0,
      "typeId": "t21",
      "x": "39.447822",
      "y": "36.31345"
    },
    {
      "rotation": 90,
      "typeId": "t22",
      "x": "66.171911",
      "y": "20.259862"
    },
    {
      "rotation": 90,
      "typeId": "t23",
      "x": "28.976716",
      "y": "0.12277269"
    },
    {
      "rotation": 180,
      "typeId": "t24",
      "x": "65.552142",
      "y": "43.86438"
    },
    {
      "rotation": 270,
      "typeId": "t25",
      "x": "0.12577166",
      "y": "33.646435"
    },
    {
      "rotation": 90,
      "typeId": "t26",
      "x": "54.330047",
      "y": "30.869584"
    },
    {
      "rotation": 0,
      "typeId": "t27",
      "x": "12.173116",
      "y": "0.13359737"
    },
    {
      "rotation": 90,
      "typeId": "t28",
      "x": "54.360727",
      "y": "28.909076"
    },
    {
      "rotation": 270,
      "typeId": "t29",
      "x": "5.3599937",
      "y": "34.622522"
    },
    {
      "rotation": 270,
      "typeId": "t3",
      "x": "9.216326",
      "y": "43.865227"
    },
    {
      "rotation": 0,
      "typeId": "t30",
      "x": "40.429454",
      "y": "0.20132125"
    },
    {
      "rotation": 0,
      "typeId": "t31",
      "x": "28.346242",
      "y": "-0.68400956"
    },
    {
      "rotation": 0,
      "typeId": "t32",
      "x": "48.649913",
      "y": "13.506231"
    },
    {
      "rotation": 180,
      "typeId": "t33",
      "x": "44.865562",
      "y": "28.06545"
    },
    {
      "rotation": 270,
      "typeId": "t34",
      "x": "21.966038",
      "y": "21.293765"
    },
    {
      "rotation": 90,
      "typeId": "t35",
      "x": "30.963012",
      "y": "36.3955"
    },
    {
      "rotation": 180,
      "typeId": "t36",
      "x": "42.062806",
      "y": "36.838852"
    },
    {
      "rotation": 0,
      "typeId": "t37",
      "x": "10.737913",
      "y": "18.830784"
    },
    {
      "rotation": 270,
      "typeId": "t38",
      "x": "48.396311",
      "y": "14.067703"
    },
    {
      "rotation": 270,
      "typeId": "t39",
      "x": "54.141184",
      "y": "40.519108"
    },
    {
      "rotation": 90,
      "typeId": "t4",
      "x": "55.626939",
      "y": "26.912271"
    },
    {
      "rotation": 270,
      "typeId": "t40",
      "x": "40.972948",
      "y": "19.10906"
    },
    {
      "rotation": 0,
      "typeId": "t41",
      "x": "56.640816",
      "y": "13.829794"
    },
    {
      "rotation": 90,
      "typeId": "t42",
      "x": "40.960554",
      "y": "9.410119"
    },
    {
      "rotation": 270,
      "typeId": "t43",
      "x": "0.13183697",
      "y": "43.873856"
    },
    {
      "rotation": 180,
      "typeId": "t44",
      "x": "33.085811",
      "y": "28.146021"
    },
    {
      "rotation": 180,
      "typeId": "t45",
      "x": "56.082034",
      "y": "29.164982"
    },
    {
      "rotation": 180,
      "typeId": "t46",
      "x": "12.161658",
      "y": "14.632311"
    },
    {
      "rotation": 270,
      "typeId": "t5",
      "x": "20.385334",
      "y": "35.515647"
    },
    {
      "rotation": 180,
      "typeId": "t6",
      "x": "39.206991",
      "y": "43.874355"
    },
    {
      "rotation": 90,
      "typeId": "t7",
      "x": "41.167263",
      "y": "7.9403256"
    },
    {
      "rotation": 0,
      "typeId": "t8",
      "x": "17.961679",
      "y": "11.781264"
    },
    {
      "rotation": 180,
      "typeId": "t9",
      "x": "22.18915",
      "y": "18.891047"
    }
  ],
  "problemKey": "V09",
  "schemaVersion": "1"
}

DISCUSSION

Discussion

Talk strategy, share methods, ask why you are stuck. Every signed-in user can post. Posts carry your public byline, the same name your records use; the #number after it is the account's signup ordinal, so a name cannot be worn by someone else. New posts appear after an automated review.

问题大草NUE_13#310 replies54m ago