Can ANTLR4 solve packing problems using parsing?

[Dennis Ferron]

(The project/problem I give below is real; using ANTLR4 to solve it is whimsical.  I thought it might be fun to think about if it could be done or that we might learn something by determining that it can't.  I hope this kind of post is not unwelcome.)

I have a cut list for a welding project.  I want to know the optimal way to order lengths of steel stock (4x4x0.25 square tube) that balances several concerns:

1. minimal waste (cost per foot is expensive)
2. no single piece ordered is too heavy to lift (5' is 60#)
   
3. simple instructions (since I have to order over the phone)

For example, I might order five 5' lengths.  When I get them I will cut a 54" piece out of one, and a 20" and 21" piece out of another, etc.  I could waste less by cutting "54+20+21" all from one 8' length instead of two 5', but I don't know if I can lift 8' of 4x4 tube and balance it on the saw.

There are about a dozen pieces to cut (all different), and a complication is some of the ends have 45 degree angles, so they can be packed closer if orientation is taken into account.  (However just solving the rectangle packing problem would be a simpler first step.)

There's many ways I could approach this, but since I was already using ANTLR4 for an actual parsing problem, it got me wondering whether ANTLR4 could solve this physical problem using parsing?  Obviously with code behind anything could be done, but I'm curious how far one could get with no or minimal additional code - just a grammar.

The basic idea is I'd turn my cut list into a grammar, and my proposed selection of stock lengths into a text document.  The text document might have, e.g., one "x" for every inch of stock, with each separate length on a separate line.  The grammar rules would consume some number of x's per cut list piece; an extra rule to consume a variable number of unused extra x's at the end of a line would even tell me how much waste there was.

One potential issue I see is I don't know how to write a grammar that says that any of 12 piece lengths can be matched, but each of the 12 unique pieces must be used exactly once per document.