April 13, 2011

The Right Tool for the Job

I remember a time when my father was looking to buy a reciprocating saw for something he was working on around the house.  As he already owned at least five other saws, I questioned why he wanted to buy another.  Couldn't he use one of his other ones?  He replied that this particular type of saw would allow him to finish his work faster and with a better cut.  So yes, he could use one of his other saws, but a reciprocating saw is the better one for the job. 

So where am I going with this?  Well, Alan Skorkin has an interesting blog post on the Dropbox programming challenges and his use of dynamic programming to solve one of problems.  This was certainly interesting, but while I was reading his summary of the problem, I immediately began thinking that this was right in Prolog's wheelhouse.

The problem is essentially the subset sum problem: given a set of integers, is there a non-empty subset whose sum is exactly zero?  Now, with your typical imperative language, once you understand the nature of the problem, you go about specifying the exact steps needed to solve it.  But with a declarative language like Prolog, you describe what the application should solve, providing context, facts, and inferences about the problem, but you don't actually have to solve it.  Prolog does the heavy lifting.

With the subset sum problem, I knew what needed to be accomplished, but I wasn't immediately sure of an algorithm to do it.  With Prolog, though, I didn't need to do know an algorithm.  I merely needed to describe the nature of the problem, which was actually easy.  So the solution to the subset sum problem in Prolog is:

subset_sum(List, Subset, Sum) :-
sublist(Subset, List), sum_list(Subset, Sum).

That's it, folks.  Pretty sweet, eh?  You're basically telling Prolog that a solution is valid if all of the members of the Subset list are in the full List, and the sum of the members in Subset equals Sum.  With this in place, Prolog will go about finding possible solutions to the problem.

| ?- sum_subset([802, 421, 143, -302, 137, 316, 150, -611, -466, -42, -195, -295], Subset, 0).

Subset = [] ? a

Subset = [316,150,-466]

(4 ms) no

Or if I want to find all subsets from a list that total 11:

| ?- sum_subset([7, 8, -4, -2, 3, 9, 12, 5], Subset, 11).

Subset = [-4,3,12] ? a

Subset = [-4,-2,12,5]

Subset = [-4,-2,3,9,5]

Subset = [8,3]

Subset = [8,-2,5]

Subset = [8,-4,-2,9]

Subset = [7,-4,3,5]

Subset = [7,8,-4]


This is a great example of using polyglot programming to leverage the right language to solve a particular problem.  Prolog excels at problems like the above one, so I was able to implement a solution much faster than I would have in any other language.  But for other problems, Prolog would be a horrible choice.  Thus understanding various languages and the kinds of situations where they are best utilized can lead to faster, simpler, and better solutions than just relying on a single general purpose language.  It's all about using the right tool for the job.

No comments:

Post a Comment