[Haskell-cafe] Learning list filtering using puzzles

[Karthick Gururaj]

Hi all,

I'm very new to Haskell, having started earlier this week. This is my
second attempt after two years :) Currently, I can do simple list
processing/recursion/functions. I'm using GHC on Ubuntu.

I decided to use puzzles as a way to explore list filtering. For
example, while "normal" solution for solving a quadratic is to compute
the solution algebraically, I tried:

solvequad :: Int -> Int -> Int -> [Int]
solvequad a b c = [x | x <- [1..10000], a*x*x + b*x + c == 0]

This works well, of course assuming the roots are in the given integer range.

Next, to solve the puzzle: "A stone weighing 40 kg falls from a
certain height and is split into four pieces. With the help of these
four pieces, one can weigh any quantity from one kg to 40 kg by using
these in a scale (both plates of the scale can be used for placing any
stone pieces at a time). Find the weight of each piece."

I tried:
solvepuzzle = [(a,b,c,d) | a <- [1..40], b <- [a..40], c <- [b..40], d
<- [c..40], a+b+c+d == 40, sort [p*a + q*b + r*c + s*d | p <-
[-1,0,1], q <- [-1,0,1], r <- [-1,0,1], s <- [-1,0,1], p*a+q*b+r*c+s*d
> 0] == [1..40]]

It works, but I'm not too happy with the last constraint..

Is there a better way to express: "..one can weigh any quantity from
1kg to 40 kgs.." ?

A more interesting candidate - considering the previous ones can be
also solved with a language like C easily: consider the well know
honestans/swindle-cats puzzle: "there are two gate keepers guarding
two doors - one that leads to hell and the other to heaven. One of
these keepers always speaks the truth and the other always lies (and
will only answer questions that permit a "yes" or "no" for answer). We
don't know who is the honest one. If allowed to ask one question to
one of the keepers, what would you ask to find out which is the gate
to heaven?"

I'm trying to see how to formulate this in a way Haskell can lead me
to a solution.. This is where I'm at now (in "psedo" Haskell code).

--- Oracle knows answers to all questions and will answer truthfully
oracle :: Question -> Bool
-- Ignoring the definition for now

--- invOracle knows answers to all questions but will always lie
invOracle :: Question -> Bool
invOracle x = not (oracle x)

As far as the answer we are looking for, the truth val of "does the
first door lead to heaven?" is what we want. I represent this Question
as 'q'.

So in my notation:
   keeper1 q - ask the question to keeper 1
   oracle q  - ask oracle the question
   (not . oracle) q  - ask oracle the question, and then negate it
   (keeper1 . keeper2) q - Ask keeper 1, "Suppose I ask keeper 2 the
question 'q', what would he say?"
  .. etc

Suppose there is a way to generate "all possible questions" that can
be asked to the two gate-keepers.. a generator function (say "gen")
that takes three parameters: keeper1, keeper2 and q and returns a list
of questions (like the examples above).

The solution(s) to the puzzle is then (something like..):
[x | keeper1 <- [oracle, invOracle], keeper2 <- [oracle, invOracle],
keeper1 /= keeper2, x <- gen keeper1 keeper2 q, x q == oracle q]

The answer I know is "not (keeper1 (keeper2 q))". Thinking through the
puzzle now, I realized even "keeper1 (keeper1 q)" can be an answer.

How would I go about defining such a generator function? I'm not
looking for a detailed solution, but hints what I can look up/refer.
Any other comments on the approach above would be gratefully received
:)

Cheers,
Karthick