tag:blogger.com,1999:blog-334469232020-02-28T19:46:59.759-08:00p.brcpbrchttp://www.blogger.com/profile/08886303380215934723noreply@blogger.comBlogger69125tag:blogger.com,1999:blog-33446923.post-74690508309763043322016-11-27T02:06:00.002-08:002016-11-27T05:20:52.530-08:0099 Clojure Problems – 64: Binary Tree Layout (1)"Given a binary tree as defined before being either a vector of the form [v l r] or nil.
As a preparation for drawing the tree, a layout algorithm is required to
determine the position of each node in a rectangular grid. In this
layout strategy, the position of a node v is obtained by the
following two rules:
x(v) is equal to the position of the node v in the inorder
y(v) is equal topbrchttp://www.blogger.com/profile/08886303380215934723noreply@blogger.com0tag:blogger.com,1999:blog-33446923.post-13571083595181571452016-05-28T04:41:00.001-07:002016-05-28T04:41:30.730-07:0099 Clojure Problems – 63: Construct a Complete Binary Tree
"A complete binary tree with height H is defined as follows: The levels 1,2,3,...,H-1 contain the maximum number of nodes (i.e 2(i-1) at the level i, note that we start counting the levels from 1 at the root). In level H, which may contain less than the maximum possible number of nodes, all the nodes are 'left-adjusted'. This means that in a levelorder tree traversal all internal nodes come pbrchttp://www.blogger.com/profile/08886303380215934723noreply@blogger.com0tag:blogger.com,1999:blog-33446923.post-52729356384330544632016-03-20T03:55:00.003-07:002016-03-20T03:57:27.758-07:0099 Clojure Problems – 62B: Collect the Nodes at a Given Level in a List."A node of a binary tree is at level N if the path from the root to the
node has length N-1. The root node is at level 1. Write a method
at-level to collect all nodes at a given level in a list."
(deftest p62b-at-level
(is (= '(b c) (at-level '[a [b nil nil] [c [d nil nil] [e nil nil]]] 2))))
The basic idea for the solution was to see the tree as a list of nodes and to realise that the pbrchttp://www.blogger.com/profile/08886303380215934723noreply@blogger.com0tag:blogger.com,1999:blog-33446923.post-46658407534053492942016-03-08T11:09:00.001-08:002016-03-08T11:09:05.583-08:0099 Clojure Problems – 61A: Collect the Leaves of a Binary Tree in a List
"61A (*) Collect the leaves of a binary tree in a list.
A leaf is a node with no successors. Write a method leaves to
collect them in a list."
(deftest p61a-leaves
(is (= '(b d e) (leaves '[a [b nil nil] [c [d nil nil] [e nil nil]]]))))
A variation on the previous exercise. Solution.
Read more about this series.pbrchttp://www.blogger.com/profile/08886303380215934723noreply@blogger.com0tag:blogger.com,1999:blog-33446923.post-28260504657476132152016-03-02T22:09:00.000-08:002016-03-02T22:09:03.149-08:0099 Clojure Problems – 62: Collect the Internal Nodes of Binary Tree in a List"An internal node of a binary tree has either one or two non-empty successors. Write a method internals to collect them in a list."
(deftest p62-internals
(is (= '(a c) (internals '[a [b nil nil] [c [d nil nil] [e nil nil]]]))))
I used the same idea as in the two previous exercises: walk the tree and filter, just filtering for branch nodes this time. Again using a predicate I wrote earlier.pbrchttp://www.blogger.com/profile/08886303380215934723noreply@blogger.com0tag:blogger.com,1999:blog-33446923.post-47680885915145939772016-02-21T13:06:00.002-08:002016-03-02T22:07:02.833-08:0099 Clojure Problems – 61: Count the Leaves of a Binary Tree.
"A leaf is a node with no successors. Write a method leaf-count to count them."
(deftest p61-count-leaves
(is (= (leaf-count '[x [x [x nil nil] nil] [x nil nil]]) 2)))
I simply walked the tree and counted all the leaves. Both functions, for detecting leaves and walking the tree, existed from previous exercises. See the solution on Github.
Read more about this series.
pbrchttp://www.blogger.com/profile/08886303380215934723noreply@blogger.com0tag:blogger.com,1999:blog-33446923.post-38722664759522894482016-02-17T12:04:00.002-08:002016-02-17T12:54:49.564-08:0099 Clojure Problems – 60 (alternative solution): Construct Height-balanced Binary Trees with a Given Number of Nodes.
This post describes an alternative solution to problem 60 based on logic programming. Check out my previous post for a functional Clojure solution.
The original 99 problems were compiled to teach Prolog. Clojure's core.logic implements a minimal logic DSL called miniKanren using Clojure as the host language. In this post I reimplement the solution to problem 60 based on core.logic. If you pbrchttp://www.blogger.com/profile/08886303380215934723noreply@blogger.com0tag:blogger.com,1999:blog-33446923.post-40754943599936047952016-01-16T11:07:00.002-08:002016-01-17T02:59:47.091-08:0099 Clojure Problems – 60: Construct Height-balanced Binary Trees with a Given Number of Nodes.
"Construct height-balanced binary trees with a given number of nodes.
Consider a height-balanced binary tree of height H. What is the
maximum number of nodes it can contain? Clearly, MaxN = 2H - 1.
However, what is the minimum number MinN? This question is more
difficult. Try to find a recursive statement and turn it into a
function min-hbal-nodes that takes a height and returns MinNpbrchttp://www.blogger.com/profile/08886303380215934723noreply@blogger.com0tag:blogger.com,1999:blog-33446923.post-278067106646068082015-06-11T12:40:00.000-07:002016-01-16T10:48:01.430-08:0099 Clojure Problems – 59: Construct Height-Balanced Binary Trees
"In a height-balanced binary tree, the following property holds for every node: The height of its left subtree and the height of its right subtree are almost equal, which means their difference is not greater than one.
Write a method to construct height-balanced binary trees for a given height with a supplied value for the nodes. The function should generate all solutions."
Example
pbrchttp://www.blogger.com/profile/08886303380215934723noreply@blogger.com0tag:blogger.com,1999:blog-33446923.post-15543173640696514212015-05-30T00:49:00.000-07:002015-05-30T00:49:57.448-07:0099 Clojure Problems – 58: Generate-and-Test Paradigm
"Apply the generate-and-test paradigm to construct all symmetric, completely balanced binary trees with a given number of nodes.
How many such trees are there with 57 nodes? Investigate about how many solutions there are for a given number of nodes? What if the number is even? Write an appropriate function."
Example
>(symmetric-cbalanced-trees 5 'x)
([x [x nil [x nil nil]] [x [x nil nil] nilpbrchttp://www.blogger.com/profile/08886303380215934723noreply@blogger.com0tag:blogger.com,1999:blog-33446923.post-29521796626788440252015-05-21T11:26:00.003-07:002015-05-21T11:28:57.912-07:0099 Clojure Problems – 56: Symmetric Binary Trees
"Let us call a binary tree symmetric if you can draw a vertical line through the root node and then the right subtree is the mirror image of the left subtree. Write a predicate symmetric/1 to check whether a given binary tree is symmetric. Hint: Write a predicate mirror/2 first to check whether one tree is the mirror image of another. We are only interested in the structure, not in the contents pbrchttp://www.blogger.com/profile/08886303380215934723noreply@blogger.com0tag:blogger.com,1999:blog-33446923.post-72392987086034024772015-05-21T11:16:00.000-07:002015-05-25T04:25:27.849-07:0099 Clojure Problems – 57: Binary Search Trees
Write a function insert-val to add elements to a binary search tree. Then write a function to construct a binary search tree from a list of integer numbers.
Then use this function to test the solution of the problem P56.
Example
>(->binary-search-tree 3 2 5 7 1)
[3 [2 [1 nil nil] nil] [5 nil [7 nil nil]]]
>(->binary-search-tree 5, 3, 18, 1, 4, 12, 21)
[5 [3 [1 nil nil] [4 nil nil]] [18 [12 pbrchttp://www.blogger.com/profile/08886303380215934723noreply@blogger.com0tag:blogger.com,1999:blog-33446923.post-17135304876397397532015-05-17T02:14:00.000-07:002015-05-17T02:14:22.090-07:0099 Clojure Problems – 55: Construct Completely Balanced Binary Trees
"In a completely balanced binary tree, the following property holds for every node: The number of nodes in its left subtree and the number of nodes in its right subtree are almost equal, which means their difference is not greater than one."
Example
>(balanced-trees 3 'x)
([x [x nil nil] [x nil nil]])
Verification
(defspec balanced-trees-are-balanced
20
(prop/for-all [i gen/nat]
pbrchttp://www.blogger.com/profile/08886303380215934723noreply@blogger.com0tag:blogger.com,1999:blog-33446923.post-18837864378764645522015-04-03T11:55:00.005-07:002015-04-06T09:45:01.934-07:0099 Clojure Problems－54: Is This A Binary Tree?
"Write a predicate tree? that succeeds if and only if its argument is representing a binary tree."
Example/Test
(deftest nil-is-a-tree
(is (= true (tree? nil))))
Discussion
This is an interesting problem because it allows us to touch the basic question of static vs. dynamic typing.
If we look at the Scala solution, we see that in a statically typed language this problem can be fully pbrchttp://www.blogger.com/profile/08886303380215934723noreply@blogger.com1tag:blogger.com,1999:blog-33446923.post-60066468622707329142014-12-31T01:26:00.000-08:002014-12-31T01:26:29.264-08:0099 Clojure Problems－50: Huffman CodeExample
(deftest huffmann
(is (= '([a "0"] [c "100"] [b "101"] [f "1100"] [e "1101"] [d "111"])
(-> '([a 45] [b 13] [c 12] [d 16] [e 9] [f 5])
build-huffman-tree
map-symbols))))
Discussion
Huffman coding is a variable length coding based on the frequency of each possible source value. You might have a look at the wikipedia article (or a good book on discretepbrchttp://www.blogger.com/profile/08886303380215934723noreply@blogger.com0tag:blogger.com,1999:blog-33446923.post-12426759778801645512014-10-28T09:24:00.001-07:002014-10-31T02:10:17.001-07:0099 Clojure Problems – 49: 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 function to generate Gray codes.
See if you can use memoization to make the function more efficient."
pbrchttp://www.blogger.com/profile/08886303380215934723noreply@blogger.com0tag:blogger.com,1999:blog-33446923.post-13185212627190838132014-08-20T12:42:00.003-07:002014-08-21T23:53:53.193-07:0099 Clojure Problems – 48: Truth Tables for Logical Expressions (3)
Generalize problem 47 in such a way that the logical expression may contain any number of logical variables. Define table in a way that (table vector expr) prints the truth table for the expression expr, which contains the logical variables enumerated in vector.
Example
ninety-nine-clojure.logic> (table (i [a b c], (a and (b or c) equ a and b or a and c)))
| :a | :b | :c | :result |pbrchttp://www.blogger.com/profile/08886303380215934723noreply@blogger.com0tag:blogger.com,1999:blog-33446923.post-6223104960095964442014-08-12T12:44:00.002-07:002014-08-20T12:42:16.077-07:0099 Clojure Problems – 47: Truth Tables for Logical Expressions (2)
"Continue problem P46 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 Java."
If we want to have this 'natural way' of writing logical expressions we will have to introduce infix notation into Clojure's prefix world.
Example
pbrchttp://www.blogger.com/profile/08886303380215934723noreply@blogger.com0tag:blogger.com,1999:blog-33446923.post-3043211916353175642014-08-05T09:58:00.000-07:002014-08-20T12:43:48.202-07:0099 Clojure Problems – 46: Truth Tables For Logical Expressions
Define functions and, or, nand, nor, xor, impl, and equ (for logical equivalence) which return true or false according to the result of their respective operations; e.g. (and A B) is true if and only if both A and B are true.
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 whichpbrchttp://www.blogger.com/profile/08886303380215934723noreply@blogger.com0tag:blogger.com,1999:blog-33446923.post-65490384891698704502014-07-13T02:11:00.001-07:002014-07-13T02:14:03.918-07:0099 Clojure Problems: 41: A List Of Goldbach Compositions"Given a range of integers by its lower and upper limit, print a list of all even numbers and their Goldbach composition."
Example
(print-goldbach (range 9 21))
10 = 3 + 7
12 = 5 + 7
14 = 3 + 11
16 = 3 + 13
18 = 5 + 13
20 = 3 + 17
"In most cases, if an even number is written as the sum of two prime numbers, one of them is very small. Very rarely, the primes are both bigger than, say, 50. Try pbrchttp://www.blogger.com/profile/08886303380215934723noreply@blogger.com0tag:blogger.com,1999:blog-33446923.post-69971364943900034052014-07-07T12:51:00.002-07:002015-05-14T13:27:00.310-07:0099 Clojure Problems – 40: Goldbach's ConjectureGoldbach's conjecture says that every positive even number greater than 2 is the sum of two prime numbers. Example: 28 = 5 + 23. It is one of the most famous facts in number theory that has not been proved to be correct in the general case. It has been numerically confirmed up to very large numbers. Write a predicate to find the two prime numbers that sum up to a given even integer.
Test/Examplepbrchttp://www.blogger.com/profile/08886303380215934723noreply@blogger.com0tag:blogger.com,1999:blog-33446923.post-41590990450060617112014-07-06T11:19:00.000-07:002014-07-06T11:19:24.876-07:0099 Clojure Problems: 39 – A List Of Prime Numbers
Given a range of integers by its lower and upper limit, construct a list of all prime numbers in that range.
Example:
(deftest p39-primes-range
(is (= '(7 11 13 17 19 23 29 31) (primes-range 7 31))))
Solution:
This is a quick one. As we have already defined a lazy seq of prime numbers to solve P35 we can reuse that. To produce the desired range drop from that sequence until we reach the pbrchttp://www.blogger.com/profile/08886303380215934723noreply@blogger.com0tag:blogger.com,1999:blog-33446923.post-14324685574054495072014-06-19T06:33:00.000-07:002015-04-05T03:32:44.541-07:0099 Clojure Problems – 37/38: Calculate Euler's Totient Function phi(m) (Improved)
See problem P34 for the definition of Euler's totient function. If the list of the prime factors of a number m is known in the form of problem P36 then the function phi(m>) can be efficiently calculated as follows: Let [[p1, m1], [p2, m2], [p3, m3], ...] be the list of prime factors (and their multiplicities) of a given number m. Then phi(m) can be calculated with the following formula:
$$\pbrchttp://www.blogger.com/profile/08886303380215934723noreply@blogger.com0tag:blogger.com,1999:blog-33446923.post-10717524651832520392014-06-13T12:51:00.000-07:002014-06-13T12:51:08.716-07:0099 Clojure Problems – 36: Determine the Prime Factors of a Given Positive Integer (2)
Construct a list containing the prime factors and their multiplicity.
Alternately, use a map for the result.
Example
(deftest p36-prime-factors-multiplicity
(is (= {3 2, 5 1, 7 1} (prime-factors-multiplicity 315) )))
Solution
If you have been following this series this problem might sound familiar. In fact it is just a slight variation on the combination of Problem 35 (prime factors) and pbrchttp://www.blogger.com/profile/08886303380215934723noreply@blogger.com0tag:blogger.com,1999:blog-33446923.post-42308687903886694892014-05-29T12:40:00.000-07:002014-05-29T12:43:45.494-07:0099 Clojure Problems – 35: Determine the Prime Factors of a Given Positive IntegerExample
(deftest p35-prime-factors
(is (= '(3 3 5 7) (prime-factors 315))))
Solution
If you have ever done the "Prime Factors Kata" the solution to this problem is probably already in your muscle memory. One reason why this problem works well as an exercise is that there exists a very simple solution to it. In fact the solution can be expressed in just a few lines of code (in almost any pbrchttp://www.blogger.com/profile/08886303380215934723noreply@blogger.com0