domingo, 15 de noviembre de 2020

Programming with Constraints

I've been following https://www.hillelwayne.com/ for some time and there's always something valuable to take to your daily life from each one of his posts.

Highest level is queuing theory and TLA+ stuff. But the couple of articles that touched home the most are his J lang article and the decision table patterns (and its intro from long time ago). 

He uses productivity tools that reasonate a lot with my way of tooling. AutoHotKey, editors, minilanguages and, Constraint Propagation Systems.

On CPS, he talks about MiniZinc and OR-Tools. For me, Oz/Mozart rang a bell (from CPM book), and cl:screamer. I don't know if Z3 overlaps with it, but worth mentioning too.

Now onto my usage/takeaway of this: I used screamer to create a magic-square some time ago, and last week I was thinking if I could use screamer, Prolog, or PiLog to solve the coin change problem.

Well, as just today, I read about this MiniZinc tool and when this watching the MiniZinc videos, it was clear that yes, it should be possible, and it might be worth to try the coin change there. Here's what I came with (using screamer):



I haven't figured out how to do the performance analysis of this, but I suspect it will be less efficient than the usual manual way, because the only 'fitness' function is v=, but it's a complete hit-or-miss. once the current factors add up to an already bigger num than out target, this algorithm will keep trying "what if I add one coin of 1cent?", "and what about 2?".  

IIRC, in CPM, there are some explanations of smarter CPS, but I'm not sure if they apply here, as there is only a single 'cut', which is the final objective function.

No hay comentarios: