Ninety-Nine Picat Problems
|
Define predicates and/2, or/2, nand/2, nor/2, xor/2, impl/2
and equ/2 (for logical equivalence) which succeed or fail
according to the result of their respective operations; e.g.
and(A,B) will succeed, if and only if both A and B succeed.
A logical expression in two variables can then be written
in prefix notation, as in the following example:
and(or(A,B),nand(A,B)).
Now, write a predicate table/3 which prints the truth table
of a given logical expression in two variables.
Example:
Picat> truth_table(A,B,$and(A,or(A,B))).
true true true
true fail true
fail true fail
fail fail fail
and(A,B) => call(A), call(B).
or(A,_) ?=> A.
or(_,B) => B.
equ(A,B) => or($and(A,B), $and(not(A),not(B))).
xor(A,B) => not($equ(A,B)).
nor(A,B) => not($or(A,B)).
nand(A,B) => not($and(A,B)).
impl(A,B) => or($not(A),B).
bind(X) ?=> X = true.
bind(X) => X = fail.
truth_table(A,B,Expr) ?=> bind(A), bind(B), eval(A,B,Expr), fail.
truth_table(_,_,_) => true.
eval(A,B,_) ?=> printf("%w %w ", A, B), fail.
eval(_,_,Expr), call(Expr) => writeln(true).
eval(_,_,_) => writeln(fail).
Truth tables for logical expressions (2).
Continue problem 3.01 by using the following operators as
logical connectives:
A #/\ B, A #\/ B, #~A, A #=> B, A #<=> B
This allows to write the logical expression in the more
natural way, as in the example:
A #/\ (A #\/ #~ B).
Example:
Picat> truth_table2(A,B, A #/\ (A #\/ #~ B)).
true true true
true fail true
fail true fail
fail fail fail
import cp.
truth_table2(A,B,Expr) =>
[A,B,Res] :: 0..1,
Res #<=> Expr,
solve_all([A,B,Res]).sort_down() = Table,
foreach ([Va,Vb,Vc] in Table)
printf("%w %w %w\n", truth_value(Va), truth_value(Vb), truth_value(Vc))
end.
truth_value(1) = true.
truth_value(0) = fail.
Truth tables for logical expressions (3).
Generalize problem 3.02 in such a way that the logical
expression may contain any number of logical variables.
Define truth_table/2 in a way that truth_table(List,Expr)
prints the truth table for the expression Expr, which
contains the logical variables enumerated in List.
Example:
Picat> truth_table3([A,B,C], A #/\ (B #\/ C) #<=> A #/\ B #\/ A #/\ C).
true true true true
true true fail true
true fail true true
true fail fail true
fail true true true
fail true fail true
fail fail true true
fail fail fail true
import cp.
truth_table3(List,Expr) =>
List :: 0..1,
Res #<=> Expr,
solve_all(List++[Res]).sort_down() = Table,
foreach (Tuple in Table)
foreach (Val in Tuple)
printf("%w ", cond(Val==0,fail,true))
end,
nl
end.
An n-bit Gray code is a sequence of n-bit strings
constructed according to certain rules. For example,
n = 1: C(1) = ["0","1"].
n = 2: C(2) = ["00","01","11","10"].
n = 3: C(3) = ["000","001","011","010","110","111","101","100"].
Find out the construction rules and write a function gray(N)
that returns the Gray code of N.
Can you apply the method of "result caching" in order to make
the function more efficient, when it is to be used repeatedly?
table
gray(1) = ["0","1"].
gray(N) = G =>
G1 = gray(N-1),
G = [['0'|Code] : Code in G1] ++ [['1'|Code] : Code in reverse(G1)].
Huffman code.
First of all, study a good book on discrete mathematics or
algorithms for a detailed description of Huffman codes, or
consult Wikipedia
We suppose a set of symbols with their frequencies, given
as a list of (S,F) terms. Example:
[(a,45),(b,13),(c,12),(d,16),(e,9),(f,5)].
Our objective is to construct a list (S,C) terms, where
C is the Huffman code word for the symbol S. In our example,
the result could be
[(a,'0'), (b,'101'), (c,'100'), (d,'111'), ...]
Write the function huffman(Fs) that returns the Huffman code
table for the frequency table Fs.
Example:
Picat> C = huffman([(a,45),(b,13),(c,12),(d,16),(e,9),(f,5)]).
huffman(Fs) = Codes =>
Nodes = [$n(F,S) : (S,F) in Fs].sort(),
make_tree(Nodes,Tree),
traverse_tree(Tree,"",Cs,[]),
Codes = sort(Cs).
make_tree([Node],T) => T = Node.
make_tree([N1@n(F1,_),N2@n(F2,_)|Ns],T) =>
F is F1+F2,
Ns1 = Ns.insert_ordered($n(F,s(N1,N2))),
make_tree(Ns1,T).
traverse_tree(n(_,s(Left,Right)),Code,Cs,CsR) =>
traverse_tree(Left,Code++"0",Cs,Cs1),
traverse_tree(Right,Code++"1",Cs1,CsR).
traverse_tree(n(_,A),Code,Cs,CsR) =>
Cs = [(A,Code)|CsR].