Programming Problem Set: 99 Problems Chapter 5

Home / Programming Problem Set: 99 Problems Chapter 5

Programming Problem Set: 99 Problems Chapter 5

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 Multiway Trees. Multiway tree is composed of a root element and a (possibly) empty set of successors which are multiway trees themselves.

The problems in this chapter is a continuation of previous chapter, therefore the numbering will start from the last problem.

For the sake of writing, we will denote tree node as t (value, left, right).

63. Check whether a given object / term is a multiway tree

The predicate is succeeds if and only if its argument is a representing a multiway tree.

example:
is_tree_mp(t(a,[t(f,[t(g,[])]),t(c,[]),t(b,[t(d,[]),t(e,[])])])) -> true

64. Count the nodes of a multiway tree

Example: nnodes_m_p( t(a,[t(f,[])]),N )
 ->
2
Write another version which allows for a flow pattern

65. Tree construction from a node string

We suppose that the nodes of a multiway tree contain single characters. In the
depth-first order sequence of its nodes, a special character ^ has been inserted
whenever, during the tree traversal, the move is a backtrack to the previous level.

By this rule, the tree in the figure opposite is represented as: <tt>afg^^c^bd^e^^^</tt>

Define the syntax of the string and write a predicate tree(String,Tree) to construct
the Tree when the String is given. Work with atoms (instead of strings). Make your
predicate work in both directions.

66. Determine the internal path length of a tree

We define the internal path length of a multiway tree as the total sum of the path
lengths from the root to all nodes of the tree. By this definition, the tree in the
figure of problem 5.03 has an internal path length of 9

Write a predicate ipl(Tree,IPL) for the flow pattern (+,-).

67. Construct the bottom-up order sequence of the tree nodes

Write a predicate bottom_up(Tree,Seq) which constructs the bottom-up sequence of the
nodes of the multiway tree Tree. Seq should be a Prolog list.

What happens if you run your predicate back words?

68. Lisp-like tree representation

There is a particular notation for multiway trees in Lisp. Lisp is a prominent
functional programming language, which is used primarily for artificial intelligence
problems. As such it is one of the main competitors of Prolog. In Lisp almost
everything is a list, just as in Prolog everything is a term.

The following pictures show how multiway tree structures are represented in Lisp.

Note that in the "lispy" notation a node with successors (children) in the tree is
always the first element in a list, followed by its children. The "lispy"
representation of a multiway tree is a sequence of atoms and parentheses '(' and ')',
which we shall collectively call "tokens". We can represent this sequence of tokens as
a Prolog list; e.g. the lispy expression (a (b c)) could be represented as the Prolog
list ['(', a, '(', b, c, ')', ')']. Write a predicate tree_ltl(T,LTL) which constructs
the "lispy token list" LTL if the tree is given as term T in the usual Prolog notation.

Example:
tree_ltl_p (t(a,[t(b,[]),t(c,[])]),LTL).
-->
['(', a, '(', b, c, ')', ')']

As a second, even more interesting exercise try to rewrite tree_ltl/2 in a way that
the inverse conversion is also possible: Given the list LTL, construct the Prolog
tree T. Use difference lists.

Solution:

  1. Haskell
  2. Lisp
  3. Prolog
  4. Python

, ,

About Author

about author

xathrya

A man who is obsessed to low level technology.

Leave a Reply

Your email address will not be published. Required fields are marked *

Social media & sharing icons powered by UltimatelySocial