Week 48

Exercise Monday (28.11.2011)

1) A program that uses "," for conjunction and ";" for disjunction can always be written only using "," for conjunction. Discuss how to transform a clause with a right-hand side that is an arbitrary Boolean expression using "," and ";" step by step to a number of clauses that yield the same behaviour.

Apply your transformation to the following clause:

f(X,Y) :- X =:= 0, Y = 0; X > 0, (X > 1, X1 is X-1, X2 is X-2, f(X1,Y1), f(X2,Y2), Y is Y1+Y2; X =:= 1, Y is 1).

Simplify the resulting clauses. What does f actually compute?

2) Read Section 2.8 (Input/Output) in the lecture notes. Follow the example both with user interactions and with files.

Write a program that asks the user for a query until the user inputs stop. and executes each query. The user should then be informed whether the query succeeded or not.

3) Read Section 2.9 (Constraint Programming) in the lecture notes. Follow the SEND+MORE=MONEY example.

Then apply constraint programming to find a 3x3 magic square. Here, a nxn magic square is a field where each cell has a different number from 1 to nxn, but all rows and columns have the same sum.

Find a more magic square by adding constraints for the diagonals.

How can you change your logic program such that it can find magic squares of any given size?

Exercise Tuesday (29.11.2011)

1) The previous exercise and the fifth lecture lecture showed how to use constraint programming to solve non-trivial search problems. Constraint programming consists of two phases. In the first phase, a given problem description is translated into constraints. In the second phase, the constraint solver looks for an assignment of the constraint variables such that all constraints are satisfied. In the examples so far, the first phase was performed manually, i.e., by the programmer. Given for example the SEND+MORE=MONEY problem, the programmer came up with the corresponding constraints. In this exercise, you will learn how to write a program that generates constraints from a given problem description. The numbers 1-26 have been randomly assigned to the 26 letters of the alphabet. As input, we are given a list of equations each consisting of a word (represented by a list of variables) and a value representing the sum of the numbers corresponding to these letters. A possible input is:

[[B,A,L,L,E,T]=45, [G,L,E,E]=66, [P,O,L,K,A]=59, [S,O,N,G]=61,
[C,E,L,L,O]=43, [J,A,Z,Z]=58, [Q,U,A,R,T,E,T]=50, [S,O,P,R,A,N,O]=82,
[C,O,N,C,E,R,T]=74, [L,Y,R,E]=47, [S,A,X,O,P,H,O,N,E]=134, [T,H,E,M,E]=72,
[F,L,U,T,E]=30, [O,B,O,E]=53, [S,C,A,L,E]=51, [V,I,O,L,I,N]=100,
[F,U,G,U,E]=50, [O,P,E,R,A]=65, [S,O,L,O]=37, [W,A,L,T,Z]=34].

Consider for example [L,Y,R,E]=47. The numbers for the letters could for example be 5,9,20 and 13 (or any other combination that add up to 47). The problem is to find the value of each letter such that all the equations are satisfied at the same time.

Discuss how to write a Prolog program that generates the constraints for an arbitrary list of equations. Implement the program and test it with at least the equations given before.

Lecture Thursday (01.12.2011)

The seventh lecture will continue with the introduction to Haskell.

Topics

types, parametric polymorphism, type declarations

Reading

Lecture Notes in Blackboard (Course Documents)

Exercise Friday (02.12.2011)

2) Let xs and ys be lists of integers and let x and y be integers. The function ++ concatenates two lists. For example, we have [1,2,3] ++ [4,5] = [1,2,3,4,5]. Which of the following equations between lists are right and which are not? Give reasons for your answers.

• [x] = x
• x:xs = [x ++ xs]
• x:xs = [x,xs]
• x:y:[] = [x:y]
• xs ++ ys = [xs,ys]
• xs:[] = [xs ++ []]
• ys:x = ys ++ [x]
• x:xs:ys = (x:xs) ++ ys
• [x] : [] = [x] ++ []
• xs ++ [] = xs
• (x : ys) ++ zs = x : (ys ++ zs)

2) Implement the following functions in Haskell. Make sure these work correct on natural numbers and lists of natural numbers. You may use the pre-defined functions if ... then ... else ..., +, and >. You may not use other pre-defined functions such as *, sum, < etc.

• times :: Int -> Int -> Int
  The expression times x y computes the product of x and y. For example, the expression times 3 4 evaluates to 12.
• intsum :: [Int] -> Int
  The expression intsum xs computes the sum of all elements in xs. For example, the expression sum [3,4] evaluates to 7.
• squareroot :: Int -> Int
  The expression squareroot x computes the rounded-off square root of x. For example, the expression squareroot 24 evaluates to 4 while the expression squareroot 25 evaluates to 5.
• sumroot :: [Int] -> Int
  The expression sumroot xs computes the sum of the rounded-off square roots of all elements in xs. For example, the expression sumroot [24,16] evaluates to 8.