# Logic: exam-level questions

If you need help reviewing Logic, take a look at these resources:

We will be using the Logic interpreter, which you can get here. You can run the Logic interpreter from your terminal with:

``python3 logic``

You can load a `.logic` file with

``python3 logic -load file.logic``

Alternatively, you can use the online Logic interpreter

Each question has a "Toggle Solution" button -- click it to reveal that question's solution.

## Code-Writing questions

### Question 1

Write a fact or set of facts for the `interleave` relation, which checks if two given lists will interleave into a third given list. You cannot assume that the lists are of equal length.

``````(fact (interleave ; YOUR CODE HERE

; Tests
logic> (query (interleave (1 2) (3 4) (1 3 2 4)))
Success!
logic> (query (interleave (1 2) (3 4) (1 2 3 4)))
Failed.
logic> (query (interleave (1 2) (3 4 5) ?what))
Success!
what: (1 3 2 4 5)``````
``````(fact (interleave ?lst () ?lst))
(fact (interleave () ?lst ?lst))
(fact (interleave (?a . ?x) (?b . ?y) (?a ?b . ?z))
(interleave ?x ?y ?z))``````

### Question 2

Write a fact or set of facts for the `zip` relation, which checks if two given lists will zip into a third given list (see the tests to get an idea of what "zip" means). You can assume that the lists are of equal length.

``````(fact (zip ; YOUR CODE HERE

; Tests
logic> (query (zip (1 2) (3 4) ((1 3) (2 4))))
Success!
logic> (query (zip (1 2) (3 4) (1 3 2 4)))
Failed.``````
``````(fact (zip () () ()))
(fact (zip (?a . ?x) (?b . ?y) ((?a ?b) . ?z))
(zip ?x ?y ?z))``````

### Question 3

Write a fact or set of facts for the `reverse` relation, which takes two lists and checks if the second list is the reverse of the first. You can assume the `append` relation is already defined.

``````(fact (reverse ; YOUR CODE HERE

; Tests
logic> (query (reverse (1 2 3 4) (4 3 2 1)))
Success!
logic> (query (reverse (1 2 3) (2 1 3)))
Failed.
logic> (query (reverse (4 2 5) ?what))
Success!
what: (5 2 4)``````
``````(fact (reverse () ()))
(fact (reverse (?f . ?rest) ?lst)
(reverse ?rest ?reverse-rest)
(append ?reverse-rest (?f) ?lst))``````

## Logical Trees (courtesy of Sarah Kim)

The following questions were written by Sarah Kim for Summer 2013.

Let's create a series of facts on a tree diagram. The facts are of the following form:

``(fact (tree number entry left right))``

Some examples:

``````(fact (tree tree-1 6 tree-2 tree-3))
(fact (tree tree-2 4 tree-4 tree-5))
(fact (tree tree-3 8 tree-6 tree-7))
(fact (tree tree-4 3 tree-8 none))
(fact (tree tree-5 5 none none))
(fact (tree tree-6 7 none none))

(fact (tree tree-7 11 tree-9 tree-10))
(fact (tree tree-8 2 tree-11 none))
(fact (tree tree-9 9 none tree-12))
(fact (tree tree-10 12 none none))
(fact (tree tree-11 1 none none))
(fact (tree tree-12 10 none none))``````

### Question 4

Write a `find-entry` fact that associates tree number to tree entry.

``````logic> (query (find-entry tree-12 10))
Success!
logic> (query (find-entry tree-2 ?x))
Success!
x: 4
logic> (query (find-entry ?tree 11))
Sucess!
tree: tree-7``````
``````(fact (find-entry ?number ?entry)
(tree ?number ?entry ?left ?right))``````

### Question 5

Write a `check-leaf` fact that checks if a tree is a leaf (no trees in left or right).

``````logic> (query (check-leaf tree-12))
Sucess!
logic> (query (check-leaf tree-4))
Failed.``````
``````(fact (check-leaf ?number)
(tree ?number ?leaf none none))``````

### Question 6

What would Logic print?

``````logic> (query (check-leaf ?x))
______Success!
x: tree-5
x: tree-6
x: tree-10
x: tree-11
x: tree-12``````

### Question 7

Write a `smallest-entry` fact that finds the smallest entry of a tree.
``````logic> (query (smallest-entry tree-2 ?leaf))
Success!
leaf: 1
logic> (query (smallest-entry tree-12 ?leaf))
Success!
leaf: 10
logic> (query (smallest-entry tree-7 ?leaf))
leaf: 9``````
``````(fact (smallest-entry ?number ?entry)
(tree ?number ?entry none ?right))
(fact (smallest-entry ?number ?entry)
(tree ?number ?other-entry ? left ?right)
(smallest-entry ?left ?entry))``````

### Question 8

Write a `find-parent` fact, which finds the parent of a number.

``````logic> (query (find-parent tree-11 ?parent))
Success!
parent: tree-8``````
``````(fact (find-parent ?number ?parent)
(tree ?parent ?entry ?number ?right))
(fact (find-parent ?number ?parent)
(tree ?parent ?entry ?left ?number))``````

### Question 9

Write a `generation` fact, which lists all the members of a tree's family tree.

``````logic> (query (generation tree-11 ?members))
Success!
members: tree-1
members: tree-2
members: tree-4
members: tree-8
members: tree-11``````
``````(fact (generation ?number ?grandfather)
(find-parent ?number ?father)
(generation ?father ?grandfather))
(fact (generation ?number ?number))``````

### Question 10

What would happen if for the `generation` fact, we put the second fact before the first fact?

``logic> (query (generation tree-11 ?members))``
``````Success!
members: tree-11
members: tree-8
members: tree-4
members: tree-2
members: tree-1``````