Interesting puzzle

[ja...@ioctl.org]

I've been slightly distracted from a mini-project (an ML compiler*) this
weekend by this:

http://www.mit.edu/~puzzle/2013/coinheist.com/rubik/a_regular_crossword/grid.pdf

It can be best viewed as a constraint-satisfaction problem; each "row" of
the honeycomb is accepted by the regular expression** at its end.

I think trying to come at this problem from an FP perspective is quite a
good exercise. Not only does it force you to consider how to best
represent various finite state machines as functional data structures***
(and maybe refresh some very rusty automata theory), but actually
expressing search heuristics is also a practical challenge. (This might be
the first time I've ever considered using continuations nontrivially as
being the simplest way to approach the expression of the solution to a
problem.)

* I'm having more trouble with the front-end than I have with the guts of
this; although I think I now understand Haskell's readS (remember that
from the dojo?) and how monadic parsers work.

** using the term loosely; a couple of expressions include backreferences

*** I haven't picked a single good approach for this yet

PS. How one might go about constructing such a puzzle as this in the first
place is currently an astonishing mystery; I'm hoping that working on the
forward version will shed some light on the - apparently much trickier -
backwards one.

--
jan grant http://ioctl.org/jan/
"My army boots contain everything not in them." - Russell's pair o' Docs.

[Arwyn]

Hi Jan,

Wow. That one is going to keep me awake nights.

I have been pondering a similar constraint satisfaction puzzle but on a square grid and without the full regex.

One motivation was to try out some logic/constraint programming packages in Haskell.

Originally, I was looking for something like core.logic but this might require something more explicitly constraint-based.

Speaking of which, have you seen this?:

http://www-ps.informatik.uni-kiel.de/currywiki/

Looking forward to discussing this when next we meet.

Cheers,

Arwyn

[ja...@ioctl.org]

On Mon, 11 Feb 2013, Arwyn wrote:

> Hi Jan,
>
> Wow. That one is going to keep me awake nights.

I had all sorts of plans for approaching solutions by increasingly clever
approximations of state paths through a natching NFA; it turns out to be
less difficult than that :-/

The main problem I'm stumbling on now (translating my solution from
functional python into an actual functional language) is a persistent data
structure for modelling the hex grid that lets me share as much state as
possible whilst "updating" a row with a new set of conclusions.

> I have been pondering a similar constraint satisfaction puzzle but on a
> square grid and without the full regex.

Is this the nonogram? http://en.wikipedia.org/wiki/Nonogram

I wrote a very naive solver for these as an experiment in computational
steering for batch-processing tasks. That was mostly stymied because it
turned out that a million jobs was a lot for a Condor system back then :-)
I've been meaning to revisit this problem in light of smarter approaches
to constraint propagation.

> One motivation was to try out some logic/constraint programming packages in
> Haskell.
> Originally, I was looking for something like core.logic but this might
> require something more explicitly constraint-based.

> Looking forward to discussing this when next we meet.

Yeah, I could really do with some motivation (a reading group or
something) to kick me into getting to the bottom of these kinds of
constraint systems. I'm looking forward to it!

> Speaking of which, have you seen this?:
> http://www-ps.informatik.uni-kiel.de/currywiki/

Never looked closely at it, but you've rekindled my motivation to explore
it.

Cheers,
jan

--
Update your address books: ja...@ioctl.org http://ioctl.org/jan/
Theoremhood is positively decidable.
It just takes time at least exponential in the length of the proof.

[Arwyn]

> Is this the nonogram?

The very same!

Regarding data structures, I can only wish you luck.

On a square grid I can use the built-in Array that does the sharing for me.

You might take a look at how that was implemented for inspiration.

Can't wait to hear how your solution works!

Cheers,

Arwyn