FWIW, I've found that companies outside the valley, particularly those that don't see software as their primary product, are more interested in work samples than puzzle solutions.

Try broadening your search to things like aerospace and medical technology companies.