One of my favorite pieces of code I've written is a 150 line Python script I made to solve a really ugly text processing problem. I have tried to use it as a code sample when talking to potential employers, but it backfires because it makes the original problem look so simple that they wonder why I bothered to send it.
If it's any consolation, Peter Norvig's Sudoku solver seems so readable on the surface that I've fallen into the trap of thinking it looks easy, or that I fully get it. :)
Maybe you should try a reverse interview process. Send them the original problem, ask them to have one of their top developers solve it, and then compare solutions.
I once wrote a custom report generator that could pair basically arbitrary input formats (pluggable, I think by the time I was done I'd written importers for CSV, fixed width, and JSON data) and output custom PDF output, with fully-user definable formatting/elements - using XML "templates" just because I didn't want to write a custom parser. Included loops, if statements, etc, and some pretty fancy output features (e.g. output N records per page, with custom sorting, headers/footers/etc). Used ReportLab for the PDF generation. Whole thing was under 1k lines of Python 2.
