### Programming Problem Set: 99 Problems Chapter 3

December 9, 2015 | Labs | No Comments

Ninety-nine Problems is generalized version to famous P-99: Ninety-Nine Prolog Problems collection used for teaching programming. The problems initially set for prolog but later many solutions come from various programming language. The purpose of this problem is to give us opportunity to practice our skills in logic programming. The goal is to find the most elegant solution of the given problem. Efficiency is important, but logical clarity is even more crucial.

The problem set are divided into seven categories / chapters: Lists, Arithmetic, Logic and Codes, Binary Trees, Multiway Trees, Graphs, and Miscellaneous.

In this chapter you will be only given a problem set. The solution might come however it would be on different page.

This chapter will cover about **Logic and Codes**. The problems in this chapter served as continuation of previous problems, therefore the numbering will start from the last problem.

#### 40. Truth tables for logical expression

Define 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. Now, write a predicate table/3 which prints the truth table of a given logical expression in two variables. Example: table_p( A, B, xor(A,B) ) -> true true false true false true false true true false false false

#### 41. Truth tables for logical expressions (2)

Continue problem 40 by defining and/2, or/2, etc as being operators. This allows to write the logical expression in the more natural way, as in the example: A and (A or not B). Define operator precedence as usual; i.e. as in C. Example: table2_p( A, B, A and (A or not B) ) -> true true true true false true false true false false false false

#### 41. Truth tables for logical expressions (2)

Generalize problem 41 in such a way that the logical expression may contain any number of logical variables. Define table/2 in a way that table(List,Expr) prints the truth table for the expression Expr, which contains the logical variables enumerated in List. The index is started from 1. Example: table3_p( [A,B,C], A and (B or C) equ A and B or A and C) -> <tt>true true true true true true false true true false true true true fail false true false true true true false true false true false false true true false false false true

#### 43. Gray code

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 predicate with the following specification: % gray(N,C) :- C is the N-bit Gray code Can you apply the method of "result caching" in order to make the predicate more efficient, when it is to be used repeatedly?

#### 44. 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 fr(S,F) terms. Example: [fr(a,45),fr(b,13),fr(c,12),fr(d,16),fr(e,9),fr(f,5)]. Our objective is to construct a list hc(S,C) terms, where C is the Huffman code word for the symbol S. In our example, the result could be Hs = [hc(a,'0'), hc(b,'101'), hc(c,'100'), hc(d,'111'), hc(e,'1101'), hc(f,'1100')] [hc(a,'01'),...etc.]. Example: huffman_p(Fs,Hs) -> Hs is the Huffman code table for the frequency table Fs

## Solution:

- Haskell
- Lisp
- Prolog
- Python