problems.html


<!-- saved from url=(0037)http://aperiodic.net/phil/scala/s-99/ -->
<html><head><meta http-equiv="Content-Type" content="text/html; charset=ISO-8859-2">
    <title>S-99: Ninety-Nine Scala Problems</title>
  </head>
  <body>
    <h1>S-99: Ninety-Nine Scala Problems</h1>

    <p>These are an adaptation of
    the <a href="https://prof.ti.bfh.ch/hew1/informatik3/prolog/p-99/">Ninety-Nine
    Prolog Problems</a> written by Werner Hett at the Berne University of
    Applied Sciences in Berne, Switzerland.  I
    (<a href="http://aperiodic.net/phil/">Phil Gold</a>) have altered them
    to be more amenable to programming in
    Scala.  <a href="mailto:phil_g@pobox.com">Feedback is appreciated</a>,
    particularly on anything marked TODO.</p>

    <p>The problems have different levels of difficulty.  Those marked
    with a single asterisk (*) are easy.  If you have successfully solved
    the preceeding problems you should be able to solve them within a few
    (say 15) minutes.  Problems marked with two asterisks (**) are of
    intermediate difficulty.  If you are a skilled Scala programmer it
    shouldn't take you more than 30-90 minutes to solve them.  Problems
    marked with three asterisks (***) are more difficult.  You may need
    more time (i.e. a few hours or more) to find a good solution.  The
    difficulties were all assigned for the Prolog problems, but the Scala
    versions seem to be of roughly similar difficulty.</p>

    <p>Your goal should be to find the most elegant solution of the given
    problems.  Efficiency is important, but clarity is even more crucial.
    Some of the (easy) problems can be trivially solved using built-in
    functions.  However, in these cases, you learn more if you try to find
    your own solution. </p>

    <p>Solutions are available by clicking on the link at the beginning of
    the problem description.</p>

    <p>[I don't have example solutions to all of the problems yet.  I'm
    working on getting them all done, but in the meantime, contributed
    solutions, particularly from seasoned Scala programmers would be
    appreciated.  If you feel a particular problem can be solved in a
    better manner than I did, please let me know that, too.  &lt;<a href="mailto:phil_g@pobox.com">PMG</a>&gt;]</p>

    <h2 id="lists">Working with lists</h2>

    <p>In Scala, lists are objects of type <code>List[A]</code>,
    where <i>A</i> can be any type.  Lists are effective for many
    recursive algorithms, because it's easy to add elements to the head of
    a list, and to get the tail of the list, which is everything but the
    first element.</p>

    <p>The solutions to the problems in this section will be in objects
    named after the problems (P01, P02, etc.).  You can compile the source
    files with <code>scalac</code> and thereafter use <code>import</code>
    to bring the functions into scope.  Some of the problems can be solved
    easily by using imported solutions to previous problems.</p>
    
    <p>In many cases, there's more than one reasonable approach.  The
    files linked here may include multiple solutions, with all but one
    commented out.  They'll also indicate whether there's a builtin
    method in Scala that accomplishes the task.</p>

    <dl>
      <dt id="p01"><strong><a href="http://aperiodic.net/phil/scala/s-99/p01.scala">P01</a> (*)
          Find the last element of a list.</strong></dt>
      <dd>Example:
<pre>scala&gt; last(List(1, 1, 2, 3, 5, 8))
res0: Int = 8</pre></dd>

      <dt id="p02"><strong><a href="http://aperiodic.net/phil/scala/s-99/p02.scala">P02</a> (*)
          Find the last but one element of a list.</strong></dt>
      <dd>Example:
<pre>scala&gt; penultimate(List(1, 1, 2, 3, 5, 8))
res0: Int = 5</pre></dd>

      <dt id="p03"><strong><a href="http://aperiodic.net/phil/scala/s-99/p03.scala">P03</a> (*)
          Find the <i>K</i>th element of a list.</strong></dt>
      <dd>By convention, the first element in the list is element
        0.

        <p>Example:</p>
<pre>scala&gt; nth(2, List(1, 1, 2, 3, 5, 8))
res0: Int = 2</pre></dd>

      <dt id="p04"><strong><a href="http://aperiodic.net/phil/scala/s-99/p04.scala">P04</a> (*)
          Find the number of elements of a list.</strong></dt>
      <dd>Example:
<pre>scala&gt; length(List(1, 1, 2, 3, 5, 8))
res0: Int = 6</pre></dd>

      <dt id="p05"><strong><a href="http://aperiodic.net/phil/scala/s-99/p05.scala">P05</a> (*)
          Reverse a list.</strong></dt>
      <dd>Example:
<pre>scala&gt; reverse(List(1, 1, 2, 3, 5, 8))
res0: List[Int] = List(8, 5, 3, 2, 1, 1)</pre></dd>

      <dt id="p06"><strong><a href="http://aperiodic.net/phil/scala/s-99/p06.scala">P06</a> (*)
          Find out whether a list is a palindrome.</strong></dt>
      <dd>Example:
<pre>scala&gt; isPalindrome(List(1, 2, 3, 2, 1))
res0: Boolean = true</pre></dd>

      <dt id="p07"><strong><a href="http://aperiodic.net/phil/scala/s-99/p07.scala">P07</a> (**)
          Flatten a nested list structure.</strong></dt>
      <dd>Example:
<pre>scala&gt; flatten(List(List(1, 1), 2, List(3, List(5, 8))))
res0: List[Any] = List(1, 1, 2, 3, 5, 8)</pre></dd>

      <dt id="p08"><strong><a href="http://aperiodic.net/phil/scala/s-99/p08.scala">P08</a> (**)
          Eliminate consecutive duplicates of list elements.</strong></dt>
      <dd>If a list contains repeated elements they should be replaced
        with a single copy of the element.  The order of the elements
        should not be changed.
        <p>Example:</p>
<pre>scala&gt; compress(List('a, 'a, 'a, 'a, 'b, 'c, 'c, 'a, 'a, 'd, 'e, 'e, 'e, 'e))
res0: List[Symbol] = List('a, 'b, 'c, 'a, 'd, 'e)</pre></dd>

      <dt id="p09"><strong><a href="http://aperiodic.net/phil/scala/s-99/p09.scala">P09</a> (**)
          Pack consecutive duplicates of list elements into sublists.</strong></dt>
      <dd>If a list contains repeated elements they should be placed in
        separate sublists.
        <p>Example:</p>
<pre>scala&gt; pack(List('a, 'a, 'a, 'a, 'b, 'c, 'c, 'a, 'a, 'd, 'e, 'e, 'e, 'e))
res0: List[List[Symbol]] = List(List('a, 'a, 'a, 'a), List('b), List('c, 'c), List('a, 'a), List('d), List('e, 'e, 'e, 'e))</pre></dd>
    
      <dt id="p10"><strong><a href="http://aperiodic.net/phil/scala/s-99/p10.scala">P10</a> (*)
          Run-length encoding of a list.</strong></dt>
      <dd>Use the result of problem <a href="http://aperiodic.net/phil/scala/s-99/#p09">P09</a> to implement
        the so-called run-length encoding data compression method.
        Consecutive duplicates of elements are encoded as tuples <code>(N,
        E)</code> where <i>N</i> is the number of duplicates of the
        element <i>E</i>.
        <p>Example:</p>
<pre>scala&gt; encode(List('a, 'a, 'a, 'a, 'b, 'c, 'c, 'a, 'a, 'd, 'e, 'e, 'e, 'e))
res0: List[(Int, Symbol)] = List((4,'a), (1,'b), (2,'c), (2,'a), (1,'d), (4,'e))</pre></dd>

      <dt id="p11"><strong><a href="http://aperiodic.net/phil/scala/s-99/p11.scala">P11</a> (*)
          Modified run-length encoding.</strong></dt>
      <dd>Modify the result of problem <a href="http://aperiodic.net/phil/scala/s-99/#p10">P10</a> in such a
        way that if an element has no duplicates it is simply copied into
        the result list.  Only elements with duplicates are transferred as
        <code>(N, E)</code> terms.
        <p>Example:</p>
<pre>scala&gt; encodeModified(List('a, 'a, 'a, 'a, 'b, 'c, 'c, 'a, 'a, 'd, 'e, 'e, 'e, 'e))
res0: List[Any] = List((4,'a), 'b, (2,'c), (2,'a), 'd, (4,'e))</pre></dd>
    
      <dt id="p12"><strong><a href="http://aperiodic.net/phil/scala/s-99/p12.scala">P12</a> (**)
          Decode a run-length encoded list.</strong></dt>
      <dd>Given a run-length code list generated as specified in
        problem <a href="http://aperiodic.net/phil/scala/s-99/#p10">P10</a>, construct its uncompressed
        version.
        <p>Example:</p>
<pre>scala&gt; decode(List((4, 'a), (1, 'b), (2, 'c), (2, 'a), (1, 'd), (4, 'e)))
res0: List[Symbol] = List('a, 'a, 'a, 'a, 'b, 'c, 'c, 'a, 'a, 'd, 'e, 'e, 'e, 'e)</pre></dd>

      <dt id="p13"><strong><a href="http://aperiodic.net/phil/scala/s-99/p13.scala">P13</a> (**)
          Run-length encoding of a list (direct solution).</strong></dt>
      <dd>Implement the so-called run-length encoding data compression
        method directly.  I.e. don't use other methods you've written
        (like <a href="http://aperiodic.net/phil/scala/s-99/#p09">P09</a>'s <code>pack</code>); do all the work
        directly.
        <p>Example:</p>
<pre>scala&gt; encodeDirect(List('a, 'a, 'a, 'a, 'b, 'c, 'c, 'a, 'a, 'd, 'e, 'e, 'e, 'e))
res0: List[(Int, Symbol)] = List((4,'a), (1,'b), (2,'c), (2,'a), (1,'d), (4,'e))</pre></dd>

      <dt id="p14"><strong><a href="http://aperiodic.net/phil/scala/s-99/p14.scala">P14</a> (*)
          Duplicate the elements of a list.</strong></dt>
      <dd>Example:
<pre>scala&gt; duplicate(List('a, 'b, 'c, 'c, 'd))
res0: List[Symbol] = List('a, 'a, 'b, 'b, 'c, 'c, 'c, 'c, 'd, 'd)</pre></dd>

      <dt id="p15"><strong><a href="http://aperiodic.net/phil/scala/s-99/p15.scala">P15</a> (**)
          Duplicate the elements of a list a given number of times.</strong></dt>
      <dd>Example:
<pre>scala&gt; duplicateN(3, List('a, 'b, 'c, 'c, 'd))
res0: List[Symbol] = List('a, 'a, 'a, 'b, 'b, 'b, 'c, 'c, 'c, 'c, 'c, 'c, 'd, 'd, 'd)</pre></dd>

      <dt id="p16"><strong><a href="http://aperiodic.net/phil/scala/s-99/p16.scala">P16</a> (**)
          Drop every <i>N</i>th element from a list.</strong></dt>
      <dd>Example:
<pre>scala&gt; drop(3, List('a, 'b, 'c, 'd, 'e, 'f, 'g, 'h, 'i, 'j, 'k))
res0: List[Symbol] = List('a, 'b, 'd, 'e, 'g, 'h, 'j, 'k)</pre></dd>

      <dt id="p17"><strong><a href="http://aperiodic.net/phil/scala/s-99/p17.scala">P17</a> (*)
          Split a list into two parts.</strong></dt>
      <dd>The length of the first part is given.  Use a Tuple for your
        result.
      <p>Example:</p>
<pre>scala&gt; split(3, List('a, 'b, 'c, 'd, 'e, 'f, 'g, 'h, 'i, 'j, 'k))
res0: (List[Symbol], List[Symbol]) = (List('a, 'b, 'c),List('d, 'e, 'f, 'g, 'h, 'i, 'j, 'k))</pre></dd>

      <dt id="p18"><strong><a href="http://aperiodic.net/phil/scala/s-99/p18.scala">P18</a> (**)
          Extract a slice from a list.</strong></dt>
      <dd>Given two indices, <i>I</i> and <i>K</i>, the slice is the list
        containing the elements from and including the <i>I</i>th element
        up to but not including the <i>K</i>th element of the original
        list.  Start counting the elements with 0.
        <p>Example:</p>
<pre>scala&gt; slice(3, 7, List('a, 'b, 'c, 'd, 'e, 'f, 'g, 'h, 'i, 'j, 'k))
res0: List[Symbol] = List('d, 'e, 'f, 'g)</pre></dd>

      <dt id="p19"><strong><a href="http://aperiodic.net/phil/scala/s-99/p19.scala">P19</a> (**)
          Rotate a list <i>N</i> places to the left.</strong></dt>
      <dd>Examples:
<pre>scala&gt; rotate(3, List('a, 'b, 'c, 'd, 'e, 'f, 'g, 'h, 'i, 'j, 'k))
res0: List[Symbol] = List('d, 'e, 'f, 'g, 'h, 'i, 'j, 'k, 'a, 'b, 'c)

scala&gt; rotate(-2, List('a, 'b, 'c, 'd, 'e, 'f, 'g, 'h, 'i, 'j, 'k))
res1: List[Symbol] = List('j, 'k, 'a, 'b, 'c, 'd, 'e, 'f, 'g, 'h, 'i)</pre></dd>

      <dt id="p20"><strong><a href="http://aperiodic.net/phil/scala/s-99/p20.scala">P20</a> (*)
          Remove the <i>K</i>th element from a list.</strong></dt>
      <dd>Return the list and the removed element in a Tuple.  Elements
          are numbered from 0.
      <p>Example:</p>
<pre>scala&gt; removeAt(1, List('a, 'b, 'c, 'd))
res0: (List[Symbol], Symbol) = (List('a, 'c, 'd),'b)</pre></dd>

      <dt id="p21"><strong><a href="http://aperiodic.net/phil/scala/s-99/p21.scala">P21</a> (*)
          Insert an element at a given position into a list.</strong></dt>
      <dd>Example:
<pre>scala&gt; insertAt('new, 1, List('a, 'b, 'c, 'd))
res0: List[Symbol] = List('a, 'new, 'b, 'c, 'd)</pre></dd>

      <dt id="p22"><strong><a href="http://aperiodic.net/phil/scala/s-99/p22.scala">P22</a> (*)
          Create a list containing all integers within a given range.</strong></dt>
      <dd>Example:
<pre>scala&gt; range(4, 9)
res0: List[Int] = List(4, 5, 6, 7, 8, 9)</pre></dd>

      <dt id="p23"><strong><a href="http://aperiodic.net/phil/scala/s-99/p23.scala">P23</a> (**)
          Extract a given number of randomly selected elements from a list.</strong></dt>
      <dd>Example:
<pre>scala&gt; randomSelect(3, List('a, 'b, 'c, 'd, 'f, 'g, 'h))
res0: List[Symbol] = List('e, 'd, 'a)</pre>

      <p>Hint: Use the solution to problem <a href="http://aperiodic.net/phil/scala/s-99/#p20">P20</a></p></dd>

      <dt id="p24"><strong><a href="http://aperiodic.net/phil/scala/s-99/p24.scala">P24</a> (*)
          Lotto: Draw <i>N</i> different random numbers from the set 1..<i>M</i>.</strong></dt>
      <dd>Example:
<pre>scala&gt; lotto(6, 49)
res0: List[Int] = List(23, 1, 17, 33, 21, 37)</pre></dd>

      <dt id="p25"><strong><a href="http://aperiodic.net/phil/scala/s-99/p25.scala">P25</a> (*)
          Generate a random permutation of the elements of a list.</strong></dt>
      <dd>Hint: Use the solution of problem <a href="http://aperiodic.net/phil/scala/s-99/#p23">P23</a>.
        <p>Example:</p>
<pre>scala&gt; randomPermute(List('a, 'b, 'c, 'd, 'e, 'f))
res0: List[Symbol] = List('b, 'a, 'd, 'c, 'e, 'f)</pre></dd>

      <dt id="p26"><strong><a href="http://aperiodic.net/phil/scala/s-99/p26.scala">P26</a> (**)
          Generate the combinations of <i>K</i> distinct objects chosen
          from the <i>N</i> elements of a list.</strong></dt>
      <dd>In how many ways can a committee of 3 be chosen from a group of 12
        people?  We all know that there are <code>C(12,3) = 220</code>
        possibilities (<code>C(N,K)</code> denotes the well-known binomial
        coefficient).  For pure mathematicians, this result may be great.
        But we want to really generate all the possibilities.
        <p>Example:</p>
<pre>scala&gt; combinations(3, List('a, 'b, 'c, 'd, 'e, 'f))
res0: List[List[Symbol]] = List(List('a, 'b, 'c), List('a, 'b, 'd), List('a, 'b, 'e), ...</pre></dd>

      <dt id="p27"><strong><a href="http://aperiodic.net/phil/scala/s-99/p27.scala">P27</a> (**)
          Group the elements of a set into disjoint subsets.</strong></dt>
      <dd>a) In how many ways can a group of 9 people work in 3 disjoint
        subgroups of 2, 3 and 4 persons?  Write a function that generates
        all the possibilities.
        <p>Example:</p>
<pre>scala&gt; group3(List("Aldo", "Beat", "Carla", "David", "Evi", "Flip", "Gary", "Hugo", "Ida"))
res0: List[List[List[String]]] = List(List(List(Aldo, Beat), List(Carla, David, Evi), List(Flip, Gary, Hugo, Ida)), ...</pre>

        <p>b) Generalize the above predicate in a way that we can specify
          a list of group sizes and the predicate will return a list of
          groups.</p>
        <p>Example:</p>
<pre>scala&gt; group(List(2, 2, 5), List("Aldo", "Beat", "Carla", "David", "Evi", "Flip", "Gary", "Hugo", "Ida"))
res0: List[List[List[String]]] = List(List(List(Aldo, Beat), List(Carla, David), List(Evi, Flip, Gary, Hugo, Ida)), ...</pre>

        <p>Note that we do not want permutations of the group members;
          i.e. ((Aldo, Beat), ...) is the same solution as ((Beat, Aldo),
          ...).  However, we make a difference between ((Aldo, Beat),
          (Carla, David), ...) and ((Carla, David), (Aldo, Beat), ...).</p>

        <p>You may find more about this combinatorial problem in a good
          book on discrete mathematics under the term "multinomial
          coefficients".</p></dd>

      <dt id="p28"><strong><a href="http://aperiodic.net/phil/scala/s-99/p28.scala">P28</a> (**)
          Sorting a list of lists according to length of sublists.</strong></dt>
      <dd>a) We suppose that a list contains elements that are lists
        themselves.  The objective is to sort the elements of the list
        according to their length.  E.g. short lists first, longer lists
        later, or vice versa.
        <p>Example:</p>
<pre>scala&gt; lsort(List(List('a, 'b, 'c), List('d, 'e), List('f, 'g, 'h), List('d, 'e), List('i, 'j, 'k, 'l), List('m, 'n), List('o)))
res0: List[List[Symbol]] = List(List('o), List('d, 'e), List('d, 'e), List('m, 'n), List('a, 'b, 'c), List('f, 'g, 'h), List('i, 'j, 'k, 'l))</pre>

        <p>b) Again, we suppose that a list contains elements that are
          lists themselves.  But this time the objective is to sort the
          elements according to their <em>length frequency</em>; i.e. in
          the default, sorting is done ascendingly, lists with rare
          lengths are placed, others with a more frequent length come
          later.</p>
        <p>Example:</p>
<pre>scala&gt; lsortFreq(List(List('a, 'b, 'c), List('d, 'e), List('f, 'g, 'h), List('d, 'e), List('i, 'j, 'k, 'l), List('m, 'n), List('o)))
res1: List[List[Symbol]] = List(List('i, 'j, 'k, 'l), List('o), List('a, 'b, 'c), List('f, 'g, 'h), List('d, 'e), List('d, 'e), List('m, 'n))</pre>

        <p>Note that in the above example, the first two lists in the
          result have length 4 and 1 and both lengths appear just once.
          The third and fourth lists have length 3 and there are two list
          of this length.  Finally, the last three lists have length 2.
          This is the most frequent length.</p></dd>
    </dl>


    <h2 id="math">Arithmetic</h2>

    <p>For the next section, we're going to take a different tack with
      the solutions.  We'll declare a new class, <code>S99Int</code>, and
      an implicit conversion from regular <code>Int</code>s.
      The <a href="http://aperiodic.net/phil/scala/s-99/arithmetic1.scala">arithmetic1</a> file contains the
      starting definitions for this section.  Each individual solution
      will show the relevant additions to the <code>S99Int</code> class.
      The full class will be given at the end of the section.</p>

    <dl>
      <dt id="p31"><strong><a href="http://aperiodic.net/phil/scala/s-99/p31.scala">P31</a> (**)
          Determine whether a given integer number is prime.</strong></dt>
      <dd>
<pre>scala&gt; 7.isPrime
res0: Boolean = true</pre></dd>

      <dt id="p32"><strong><a href="http://aperiodic.net/phil/scala/s-99/p32.scala">P32</a> (**)
          Determine the greatest common divisor of two positive integer
          numbers.</strong></dt>
      <dd>Use Euclid's algorithm.
<pre>scala&gt; gcd(36, 63)
res0: Int = 9</pre></dd>

      <dt id="p33"><strong><a href="http://aperiodic.net/phil/scala/s-99/p33.scala">P33</a> (*)
          Determine whether two positive integer numbers are
          coprime.</strong></dt>
      <dd>Two numbers are coprime if their greatest common divisor equals
        1.
<pre>scala&gt; 35.isCoprimeTo(64)
res0: Boolean = true</pre></dd>

      <dt id="p34"><strong><a href="http://aperiodic.net/phil/scala/s-99/p34.scala">P34</a> (**)
          Calculate Euler's totient function <code>phi(m)</code>.</strong></dt>
      <dd>Euler's so-called totient function <code>phi(m)</code> is
        defined as the number of positive integers
        <i>r</i> (1 &lt;= <i>r</i> &lt;= <i>m</i>) that are coprime
        to <i>m</i>.
<pre>scala&gt; 10.totient
res0: Int = 4</pre></dd>

      <dt id="p35"><strong><a href="http://aperiodic.net/phil/scala/s-99/p35.scala">P35</a> (**)
          Determine the prime factors of a given positive integer. </strong></dt>
      <dd>Construct a flat list containing the prime factors in ascending
        order.
<pre>scala&gt; 315.primeFactors
res0: List[Int] = List(3, 3, 5, 7)</pre></dd>

      <dt id="p36"><strong><a href="http://aperiodic.net/phil/scala/s-99/p36.scala">P36</a> (**)
          Determine the prime factors of a given positive integer (2).</strong></dt>
      <dd>Construct a list containing the prime factors and their
        multiplicity.
<pre>scala&gt; 315.primeFactorMultiplicity
res0: List[(Int, Int)] = List((3,2), (5,1), (7,1))</pre>

        <p>Alternately, use a Map for the result.</p>
<pre>scala&gt; 315.primeFactorMultiplicity
res0: Map[Int,Int] = Map(3 -&gt; 2, 5 -&gt; 1, 7 -&gt; 1)</pre></dd>

      <dt id="p37"><strong><a href="http://aperiodic.net/phil/scala/s-99/p37.scala">P37</a> (**)
          Calculate Euler's totient function phi(m) (improved).</strong></dt>
      <dd>See problem <a href="http://aperiodic.net/phil/scala/s-99/#p34">P34</a> for the definition of Euler's
        totient function.  If the list of the prime factors of a
        number <i>m</i> is known in the form of
        problem <a href="http://aperiodic.net/phil/scala/s-99/#p36">P36</a> then the
        function <code>phi(m&gt;)</code> can be efficiently calculated as
        follows: Let [[<i>p</i><sub>1</sub>, <i>m</i><sub>1</sub>],
        [<i>p</i><sub>2</sub>, <i>m</i><sub>2</sub>],
        [<i>p</i><sub>3</sub>, <i>m</i><sub>3</sub>], ...] be the list of
        prime factors (and their multiplicities) of a given
        number <i>m</i>.  Then <code>phi(m)</code> can be calculated with
        the following formula:

        <p>phi(<i>m</i>) =
          (<i>p</i><sub>1</sub>-1)*<i>p</i><sub>1</sub><sup>(<i>m</i><sub>1</sub>-1)</sup>
          *
          (<i>p</i><sub>2</sub>-1)*<i>p</i><sub>2</sub><sup>(<i>m</i><sub>2</sub>-1)</sup>
          *
          (<i>p</i><sub>3</sub>-1)*<i>p</i><sub>3</sub><sup>(<i>m</i><sub>3</sub>-1)</sup> * ...</p>

        <p>Note that <i>a</i><sup><i>b</i></sup> stands for the <i>b</i>th
        power of <i>a</i>.</p></dd>

      <dt id="p38"><strong><a href="http://aperiodic.net/phil/scala/s-99/p38.scala">P38</a> (*)
          Compare the two methods of calculating Euler's totient function.</strong></dt>
      <dd>Use the solutions of problems <a href="http://aperiodic.net/phil/scala/s-99/#p34">P34</a>
        and <a href="http://aperiodic.net/phil/scala/s-99/#p37">P37</a> to compare the algorithms.  Try to
        calculate phi(10090) as an example.</dd><br>

      <dt id="p39"><strong><a href="http://aperiodic.net/phil/scala/s-99/p39.scala">P39</a> (*)
          A list of prime numbers.</strong></dt>
      <dd>Given a range of integers by its lower and upper limit,
        construct a list of all prime numbers in that range.
<pre>scala&gt; listPrimesinRange(7 to 31)
res0: List[Int] = List(7, 11, 13, 17, 19, 23, 29, 31)</pre></dd>

      <dt id="p40"><strong><a href="http://aperiodic.net/phil/scala/s-99/p40.scala">P40</a> (**)
          Goldbach's conjecture.</strong></dt>
      <dd>Goldbach's conjecture says that every positive even number
        greater than 2 is the sum of two prime numbers.  E.g. 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 (much larger than
        Scala's Int can represent).  Write a function to find the two
        prime numbers that sum up to a given even integer.
<pre>scala&gt; 28.goldbach
res0: (Int, Int) = (5,23)</pre></dd>

      <dt id="p41"><strong><a href="http://aperiodic.net/phil/scala/s-99/p41.scala">P41</a> (**)
          A list of Goldbach compositions.</strong></dt>
      <dd>Given a range of integers by its lower and upper limit, print a
        list of all even numbers and their Goldbach composition.
<pre>scala&gt; printGoldbachList(9 to 20)
10 = 3 + 7
12 = 5 + 7
14 = 3 + 11
16 = 3 + 13
18 = 5 + 13
20 = 3 + 17</pre>

        <p>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 to find out how many
          such cases there are in the range 2..3000.</p>
        <p>Example (minimum value of 50 for the primes):</p>
<pre>scala&gt; printGoldbachListLimited(1 to 2000, 50)
992 = 73 + 919
1382 = 61 + 1321
1856 = 67 + 1789
1928 = 61 + 1867</pre></dd>

      <p>The file containing the full class for this section
      is <a href="http://aperiodic.net/phil/scala/s-99/arithmetic.scala">arithmetic.scala</a>.</p>

      <h2 id="logic">Logic and Codes</h2>

      <p>As in the previous section, we will start with a skeleton file,
      <a href="http://aperiodic.net/phil/scala/s-99/logic1.scala">logic1.scala</a>, and add code to it for each
      problem.  The difference here is that the file starts out almost
      empty.</p>

      <dt id="p46"><strong><a href="http://aperiodic.net/phil/scala/s-99/p46.scala">P46</a> (**)
          Truth tables for logical expressions.</strong></dt>
      <dd>Define
        functions <code>and</code>, <code>or</code>, <code>nand</code>, <code>nor</code>, <code>xor</code>, <code>impl</code>,
        and <code>equ</code> (for logical equivalence) which return true
        or false according to the result of their respective operations;
        e.g. <code>and(A, B)</code> is true if and only if both <i>A</i>
        and <i>B</i> are true.
<pre>scala&gt; and(true, true)
res0: Boolean = true

scala&gt; xor(true. true)
res1: Boolean = false</pre>

    <p>A logical expression in two variables can then be written as an
    function of two variables, e.g: <code>(a: Boolean, b: Boolean) =&gt;
    and(or(a, b), nand(a, b))</code></p>
    
    <p>Now, write a function called <code>table2</code> which prints the
    truth table of a given logical expression in two variables.</p>
<pre>scala&gt; table2((a: Boolean, b: Boolean) =&gt; and(a, or(a, b)))
A     B     result
true  true  true
true  false true
false true  false
false false false</pre></dd>

      <dt id="p47"><strong><a href="http://aperiodic.net/phil/scala/s-99/p47.scala">P47</a> (*)
          Truth tables for logical expressions (2).</strong></dt>
      <dd>Continue problem <a href="http://aperiodic.net/phil/scala/s-99/#p46">P46</a> by
      redefining <code>and</code>, <code>or</code>, etc as operators.
      (i.e. make them methods of a new class with an implicit conversion
      from Boolean.)  <code>not</code> will have to be left as a object
      method.
<pre>scala&gt; table2((a: Boolean, b: Boolean) =&gt; a and (a or not(b)))
A     B     result
true  true  true
true  false true
false true  false
false false false</pre></dd>
      
      <dt id="p48"><strong>P48 (**) Truth tables for logical expressions (3).</strong></dt>
      <dd>Omitted for now.<br><br><!--Generalize problem <a href="#p47">P47</a> and write a
      function <code>table</code> that will accept expressions containing
      any number of parameters.
<pre>scala> table((a: Boolean, b: Boolean, c: Boolean) => a and (b or c) equ ((a and b) or (a and c)))
A     B     C     result
true  true  true  true
true  true  false true
true  false true  true
true  false false true
false true  true  true
false true  false true
false false true  true
false false false true</pre>--></dd>
      
      <dt id="p49"><strong><a href="http://aperiodic.net/phil/scala/s-99/p49.scala">P49</a> (**)
          Gray code.</strong></dt>
      <dd>An <i>n</i>-bit Gray code is a sequence of <i>n</i>-bit strings
        constructed according to certain rules. For example,<br>
        n = 1: C(1) = ("0", "1").<br>
        n = 2: C(2) = ("00", "01", "11", "10").<br>
        n = 3: C(3) = ("000", "001", "011", "010", "110", "111", "101", "100").
    
        <p>Find out the construction rules and write a function to
          generate Gray codes.</p>
<pre>scala&gt; gray(3)
res0 List[String] = List(000, 001, 011, 010, 110, 111, 101, 100)</pre>

        <p>See if you can use memoization to make the function more
        efficient.</p></dd>

      <dt id="p50"><strong><a href="http://aperiodic.net/phil/scala/s-99/p50.scala">P50</a> (***)
          Huffman code.</strong></dt>
      <dd>First of all, consult a good book on discrete mathematics or
        algorithms for a detailed description of Huffman codes!
    
        <p>We suppose a set of symbols with their frequencies, given as a
          list of <code>(S, F)</code> Tuples.  E.g. <code>(("a", 45),
          ("b", 13), ("c", 12), ("d", 16), ("e", 9), ("f", 5))</code>.
          Our objective is to construct a list of <code>(S, C)</code>
          Tuples, where <i>C</i> is the Huffman code word for the
          symbol <i>S</i>.
</p><pre>scala&gt; huffman(List(("a", 45), ("b", 13), ("c", 12), ("d", 16), ("e", 9), ("f", 5)))
res0: List[String, String] = List((a,0), (b,101), (c,100), (d,111), (e,1101), (f,1100))</pre></dd>
    </dl>    

    <h2 id="btrees">Binary Trees</h2>

    <p><img align="right" src="./README_files/p67.gif">A binary tree is either empty or
    it is composed of a root element and two successors, which are binary
    trees themselves.</p>

    <p>We shall use the following classes to represent binary trees.
      (Also available in <a href="http://aperiodic.net/phil/scala/s-99/tree1.scala">tree1.scala</a>.)  An End
      is equivalent to an empty tree.  A Branch has a value, and two
      descendant trees.  The <code>toString</code> functions are
      relatively arbitrary, but they yield a more compact output than
      Scala's default.  Putting a plus in front of the <code>T</code>
      makes the class <em>covariant</em>; it will be able to hold subtypes
      of whatever type it's created for.  (This is important so
      that <code>End</code> can be a singleton object; as a singleton, it
      must have a specific type, so we give it type <code>Nothing</code>,
      which is a subtype of every other type.)</p>

<pre>sealed abstract class Tree[+T]
case class Node[+T](value: T, left: Tree[T], right: Tree[T]) extends Tree[T] {
  override def toString = "T(" + value.toString + " " + left.toString + " " + right.toString + ")"
}
case object End extends Tree[Nothing] {
  override def toString = "."
}
object Node {
  def apply[T](value: T): Node[T] = Node(value, End, End)
}</pre>

    <p>The example tree on the right is given by</p>

<pre>Node('a',
     Node('b', Node('d'), Node('e')),
     Node('c', End, Node('f', Node('g'), End)))</pre>

    <p>A tree with only a root node would be <code>Node('a')</code> and an
      empty tree would be <code>End</code>.</p>

    <p>Throughout this section, we will be adding methods to the classes
      above, mostly to <code>Tree</code>.</p>

    <dl>
      <dt id="p54"><strong>P54 Omitted; our tree representation will only
          allow well-formed trees.</strong></dt>
      <dd>Score one for static typing.<br><br></dd>

      <dt id="p55"><strong><a href="http://aperiodic.net/phil/scala/s-99/p55.scala">P55</a> (**)
          Construct completely balanced binary trees.</strong></dt>
      <dd>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. 
    
        <p>Define an object named <code>Tree</code>.  Write a
          function <code>Tree.cBalanced</code> to construct completely
          balanced binary trees for a given number of nodes.  The function
          should generate all solutions.  The function should take as
          parameters the number of nodes and a single value to put in all
          of them.</p>
<pre>scala&gt; Tree.cBalanced(4, "x")
res0: List(Node[String]) = List(T(x T(x . .) T(x . T(x . .))), T(x T(x . .) T(x T(x . .) .)), ...</pre></dd>

      <dt id="p56"><strong><a href="http://aperiodic.net/phil/scala/s-99/p56.scala">P56</a> (**)
          Symmetric binary trees.</strong></dt>
      <dd>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.  Add an <code>isSymmetric</code>
        method to the Tree class to check whether a given binary tree is
        symmetric.  Hint: Write an <code>isMirrorOf</code> method first to
        check whether one tree is the mirror image of another.  We are
        only interested in the structure, not in the contents of the nodes.
<pre>scala&gt; Node('a', Node('b'), Node('c')).isSymmetric
res0: Boolean = true</pre></dd>

      <dt id="p57"><strong><a href="http://aperiodic.net/phil/scala/s-99/p57.scala">P57</a> (**)
          Binary search trees (dictionaries).</strong></dt>
      <dd>Write a function to add an element to a binary search tree.
<pre>scala&gt; End.addValue(2)
res0: Node[Int] = T(2 . .)

scala&gt; res0.addValue(3)
res1: Node[Int] = T(2 . T(3 . .))

scala&gt; res1.addValue(0)
res2: Node[Int] = T(2 T(0 . .) T(3 . .))</pre>

        <p>Hint: The abstract definition of <code>addValue</code>
          in <code>Tree</code> should be <code>def addValue[U &gt;: T
          &lt;% Ordered[U]](x: U): Tree[U]</code>.  The <code>&gt;: T</code> is
          because <code>addValue</code>'s parameters need to
          be <em>contravariant</em> in <code>T</code>.  (Conceptually,
          we're adding nodes above existing nodes.  In order for the
          subnodes to be of type <code>T</code> or any subtype, the upper
          nodes must be of type <code>T</code> or any supertype.)
          The <code>&lt;% Ordered[U]</code> allows us to use
          the <code>&lt;</code> operator on the values in the tree.</p>

        <p>Use that function to construct a binary tree from a list of
          integers.</p>
<pre>scala&gt; Tree.fromList(List(3, 2, 5, 7, 1))
res3: Node[Int] = T(3 T(2 T(1 . .) .) T(5 . T(7 . .)))</pre>

        <p>Finally, use that function to test your solution
          to <a href="http://aperiodic.net/phil/scala/s-99/#p56">P56</a>.</p>
<pre>scala&gt; Tree.fromList(List(5, 3, 18, 1, 4, 12, 21)).isSymmetric
res4: Boolean = true

scala&gt; Tree.fromList(List(3, 2, 5, 7, 4)).isSymmetric
res5: Boolean = false</pre></dd>


<dt id="p58"><strong><a href="http://aperiodic.net/phil/scala/s-99/p58.scala">P58</a> (**)
    Generate-and-test paradigm.</strong></dt>
<dd>Apply the generate-and-test paradigm to construct all symmetric,
   completely balanced binary trees with a given number of nodes.
<pre>scala&gt; Tree.symmetricBalancedTrees(5, "x")
res0: List[Node[String]] = List(T(x T(x . T(x . .)) T(x T(x . .) .)), T(x T(x T(x . .) .) T(x . T(x . .))))</pre></dd>

<dt id="p59"><strong><a href="http://aperiodic.net/phil/scala/s-99/p59.scala">P59</a> (**)
    Construct height-balanced binary trees.</strong></dt>
<dd>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.
    
    <p>Write a method <code>Tree.hbalTrees</code> to construct
    height-balanced binary trees for a given height with a supplied value
    for the nodes.  The function should generate all solutions.</p>
<pre>scala&gt; Tree.hbalTrees(3, "x")
res0: List[Node[String]] = List(T(x T(x T(x . .) T(x . .)) T(x T(x . .) T(x . .))), T(x T(x T(x . .) T(x . .)) T(x T(x . .) .)), ...</pre></dd>

<dt id="p60"><strong><a href="http://aperiodic.net/phil/scala/s-99/p60.scala">P60</a> (**)
    Construct height-balanced binary trees with a given number of nodes.</strong></dt>
<dd>Consider a height-balanced binary tree of height <i>H</i>.  What is
  the maximum number of nodes it can contain?  Clearly, <i>MaxN</i> =
  2<sup><i>H</i></sup> - 1.  However, what is the minimum
  number <i>MinN</i>?  This question is more difficult.  Try to find a
  recursive statement and turn it into a function <code>minHbalNodes</code>
  that takes a height and returns <i>MinN</i>.
<pre>scala&gt; minHbalNodes(3)
res0: Int = 4</pre>

  <p>On the other hand, we might ask: what is the maximum
    height <i>H</i> a height-balanced binary tree with <i>N</i> nodes can
    have?  Write a <code>maxHbalHeight</code> function.</p>
<pre>scala&gt; maxHbalHeight(4)
res1: Int = 3</pre>

  <p>Now, we can attack the main problem: construct all the
    height-balanced binary trees with a given nuber of nodes.</p>
<pre>scala&gt; Tree.hbalTreesWithNodes(4, "x")
res2: List[Node[String]] = List(T(x T(x T(x . .) .) T(x . .)), T(x T(x . T(x . .)) T(x . .)), ...</pre>

  <p>Find out how many height-balanced trees exist for <i>N</i> = 15.</p></dd>

<dt id="p61"><strong><a href="http://aperiodic.net/phil/scala/s-99/p61.scala">P61</a> (*)
    Count the leaves of a binary tree.</strong></dt>
<dd>A leaf is a node with no successors.  Write a
  method <code>leafCount</code> to count them.
<pre>scala&gt; Node('x', Node('x'), End).leafCount
res0: Int = 1</pre></dd>

<dt id="pP61A"><strong><a href="http://aperiodic.net/phil/scala/s-99/p61a.scala">61A</a> (*)
    Collect the leaves of a binary tree in a list.</strong></dt>
<dd>A leaf is a node with no successors.  Write a
  method <code>leafList</code> to collect them in a list.
<pre>scala&gt; Node('a', Node('b'), Node('c', Node('d'), Node('e'))).leafList
res0: List[Char] = List(b, d, e)</pre></dd>

<dt id="p62"><strong><a href="http://aperiodic.net/phil/scala/s-99/p62.scala">P62</a> (*)
    Collect the internal nodes of a binary tree in a list.</strong></dt>
<dd>An internal node of a binary tree has either one or two non-empty
  successors.  Write a method <code>internalList</code> to collect them
  in a list.
<pre>scala&gt; Node('a', Node('b'), Node('c', Node('d'), Node('e'))).internalList
res0: List[Char] = List(a, c)</pre></dd>

<dt id="p62B"><strong><a href="http://aperiodic.net/phil/scala/s-99/p62b.scala">P62B</a> (*)
    Collect the nodes at a given level in a list.</strong></dt>
<dd>A node of a binary tree is at level <i>N</i> if the path from the root
  to the node has length <i>N</i>-1.  The root node is at level 1.  Write a
  method <code>atLevel</code> to collect all nodes at a given level in a
  list.
<pre>scala&gt; Node('a', Node('b'), Node('c', Node('d'), Node('e'))).atLevel(2)
res0: List[Char] = List(b, c)</pre>

  <p>Using <code>atLevel</code> it is easy to construct a
    method <code>levelOrder</code> which creates the level-order sequence
    of the nodes.  However, there are more efficient ways to do that.</p></dd>

<dt id="p63"><strong><a href="http://aperiodic.net/phil/scala/s-99/p63.scala">P63</a> (**)
    Construct a complete binary tree.</strong></dt>
<dd>A complete binary tree with height <i>H</i> is defined as follows: The
  levels 1,2,3,...,<i>H</i>-1 contain the maximum number of nodes (i.e
  2<sup>(<i>i</i>-1)</sup> at the level <i>i</i>, note that we start
  counting the levels from 1 at the root).  In level <i>H</i>, 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 first, the leaves come second, and empty successors
  (the <code>End</code>s which are not really nodes!) come last.
    
  <p>Particularly, complete binary trees are used as data structures (or
    addressing schemes) for heaps.</p>
    
  <p>We can assign an address number to each node in a complete binary
    tree by enumerating the nodes in levelorder, starting at the root with
    number 1.  In doing so, we realize that for every node <i>X</i> with
    address <i>A</i> the following property holds: The address
    of <i>X</i>'s left and right successors are 2*<i>A</i> and
    2*<i>A</i>+1, respectively, supposed the successors do exist.  This
    fact can be used to elegantly construct a complete binary tree
    structure.  Write a method <code>completeBinaryTree</code> that takes
    as parameters the number of nodes and the value to put in each node.</p>
<pre>scala&gt; Tree.completeBinaryTree(6, "x")
res0: Node[String] = T(x T(x T(x . .) T(x . .)) T(x T(x . .) .))</pre></dd>

<dt id="p64"><strong><a href="http://aperiodic.net/phil/scala/s-99/p64.scala">P64</a> (**)
    Layout a binary tree (1).</strong></dt>
<dd><img align="right" src="./README_files/p64.gif">As a preparation for drawing a tree,
  a layout algorithm is required to determine the position of each node in
  a rectangular grid.  Several layout methods are conceivable, one of them
  is shown in the illustration on the right.
  
  <p>In this layout strategy, the position of a node <i>v</i> is obtained
    by the following two rules:</p>

  <ul>
    <li>x(<i>v</i>) is equal to the position of the node <i>v</i> in the
      inorder sequence</li>
    <li>y(<i>v</i>) is equal to the depth of the node <i>v</i> in the
      tree</li>
  </ul>

  <p>In order to store the position of the nodes, we add a new class
    with the additional information.</p>

<pre>case class PositionedNode[+T](override val value: T, override val left: Tree[T], override val right: Tree[T], x: Int, y: Int) extends Node[T](value, left, right) {
  override def toString = "T[" + x.toString + "," + y.toString + "](" + value.toString + " " + left.toString + " " + right.toString + ")"
}</pre>
    
  <p>Write a method <code>layoutBinaryTree</code> that turns a tree of
    normal <code>Node</code>s into a tree
    of <code>PositionedNode</code>s.</p>
<pre>scala&gt; Node('a', Node('b', End, Node('c')), Node('d')).layoutBinaryTree
res0: PositionedNode[Char] = T[3,1](a T[1,2](b . T[2,3](c . .)) T[4,2](d . .))</pre>

  <p>The tree at right may be constructed
  with <code>Tree.fromList(List('n','k','m','c','a','h','g','e','u','p','s','q'))</code>.
  Use it to check your code.</p></dd>

<dt id="p65"><strong><a href="http://aperiodic.net/phil/scala/s-99/p65.scala">P65</a> (**)
    Layout a binary tree (2).</strong></dt>
<dd><img align="right" src="./README_files/p65.gif">An alternative layout method is
  depicted in the illustration opposite.  Find out the rules and write the
  corresponding method.  Hint: On a given level, the horizontal distance
  between neighboring nodes is constant.

  <p>Use the same conventions as in problem <a href="http://aperiodic.net/phil/scala/s-99/#p64">P64</a>.</p>
<pre>scala&gt; Node('a', Node('b', End, Node('c')), Node('d')).layoutBinaryTree2
res0: PositionedNode[Char] = T[3,1]('a T[1,2]('b . T[2,3]('c . .)) T[5,2]('d . .))</pre>

  <p>The tree at right may be constructed
    with <code>Tree.fromList(List('n','k','m','c','a','e','d','g','u','p','q'))</code>.
    Use it to check your code.</p></dd>

<dt id="p66"><strong><a href="http://aperiodic.net/phil/scala/s-99/p66.scala">P66</a> (***)
    Layout a binary tree (3).</strong></dt>
<dd><img align="right" src="./README_files/p66.gif">Yet another layout strategy is shown
  in the illustration opposite.  The method yields a very compact layout
  while maintaining a certain symmetry in every node.  Find out the rules
  and write the corresponding method.  Hint: Consider the horizontal
  distance between a node and its successor nodes.  How tight can you pack
  together two subtrees to construct the combined binary tree?

  <p>Use the same conventions as in problem <a href="http://aperiodic.net/phil/scala/s-99/#p64">P64</a>
    and <a href="http://aperiodic.net/phil/scala/s-99/#p65">P65</a>.  Note: This is a difficult problem.  Don't
    give up too early!</p>
<pre>scala&gt; Node('a', Node('b', End, Node('c')), Node('d')).layoutBinaryTree3
res0: PositionedNode[Char] = T[2,1]('a T[1,2]('b . T[2,3]('c . .)) T[3,2]('d . .))</pre>

  <p>Which layout do you like most?</p></dd>

<dt id="p67"><strong><a href="http://aperiodic.net/phil/scala/s-99/p67.scala">P67</a> (**)
    A string representation of binary trees.</strong></dt>
<dd><img align="right" src="./README_files/p67.gif">Somebody represents binary trees as
  strings of the following type (see example opposite):

<pre>a(b(d,e),c(,f(g,)))</pre>

  <p>Write a method which generates this string representation, if the
    tree is given as usual (in <code>Node</code>s and <code>End</code>s).
    Use that method for the <code>Tree</code> class's and
    subclass's <code>toString</code> methods.  Then write a method (on
    the <code>Tree</code> object) which does this inverse; i.e. given the
    string representation, construct the tree in the usual form.</p>

  <p>For simplicity, suppose the information in the nodes is a single
    letter and there are no spaces in the string.</p>
<pre>scala&gt; Node('a', Node('b', Node('d'), Node('e')), Node('c', End, Node('f', Node('g'), End))).toString
res0: String = a(b(d,e),c(,f(g,)))

scala&gt; Tree.fromString("a(b(d,e),c(,f(g,)))")
res1: Node[Char] = a(b(d,e),c(,f(g,)))</pre></dd>

<dt id="p68"><strong><a href="http://aperiodic.net/phil/scala/s-99/p68.scala">P68</a> (**)
    Preorder and inorder sequences of binary trees.</strong></dt>
<dd>We consider binary trees with nodes that are identified by single
  lower-case letters, as in the example of
  problem <a href="http://aperiodic.net/phil/scala/s-99/#p67">P67</a>.

  <p>a) Write methods <code>preorder</code> and <code>inorder</code> that
    construct the preorder and inorder sequence of a given binary tree,
    respectively.  The results should be lists,
    e.g. <code>List('a','b','d','e','c','f','g')</code> for the preorder
    sequence of the example in problem <a href="http://aperiodic.net/phil/scala/s-99/#p67">P67</a>.</p>
<pre>scala&gt; Tree.string2Tree("a(b(d,e),c(,f(g,)))").preorder
res0: List[Char] = List(a, b, d, e, c, f, g)

scala&gt; Tree.string2Tree("a(b(d,e),c(,f(g,)))").inorder
res1: List[Char] = List(d, b, e, a, c, g, f)</pre>

  <p>b) If both the preorder sequence and the inorder sequence of the
    nodes of a binary tree are given, then the tree is determined
    unambiguously.  Write a method <code>preInTree</code> that does the
    job.</p>
<pre>scala&gt; Tree.preInTree(List('a', 'b', 'd', 'e', 'c', 'f', 'g'), List('d', 'b', 'e', 'a', 'c', 'g', 'f'))
res2: Node[Char] = a(b(d,e),c(,f(g,)))</pre>

  <p>What happens if the same character appears in more than one node?
    Try, for instance, <code>Tree.preInTree(List('a', 'b', 'a'), List('b',
    'a', 'a'))</code>.</p></dd>

<dt id="p69"><strong><a href="http://aperiodic.net/phil/scala/s-99/p69.scala">P69</a> (**)
    Dotstring representation of binary trees.</strong></dt>
<dd>We consider again binary trees with nodes that are identified by
  single lower-case letters, as in the example of
  problem <a href="http://aperiodic.net/phil/scala/s-99/#p67">P67</a>.  Such a tree can be represented by the
  preorder sequence of its nodes in which dots (.) are inserted where an
  empty subtree (<code>End</code>) is encountered during the tree
  traversal.  For example, the tree shown in
  problem <a href="http://aperiodic.net/phil/scala/s-99/#p67">P67</a> is represented
  as <code>"abd..e..c.fg..."</code>.  First, try to establish a syntax
  (BNF or syntax diagrams) and then write two
  methods, <code>toDotstring</code> and <code>fromDotstring</code>, which
  do the conversion in both directions.
<pre>scala&gt; Tree.string2Tree("a(b(d,e),c(,f(g,)))").toDotstring
res0: String = abd..e..c.fg...

scala&gt; Tree.fromDotstring("abd..e..c.fg...")
res1: Node[Char] = a(b(d,e),c(,f(g,)))</pre></dd>
</dl>

<p>The file containing the full class definitions for this section
  is <a href="http://aperiodic.net/phil/scala/s-99/tree.scala">tree.scala</a>.</p>

<h2 id="mtrees">Multiway Trees</h2>

<p><img align="right" src="./README_files/p70.gif">A multiway tree is composed of a root
  element and a (possibly empty) set of successors which are multiway
  trees themselves.  A multiway tree is never empty.  The set of successor
  trees is sometimes called a forest.</p>

<p>The code to represent these is somewhat simpler than the code for
  binary trees, partly because we don't separate classes for nodes and
  terminators, and partly because we don't need the restriction that the
  value type be ordered.</p>

<pre>case class MTree[+T](value: T, children: List[MTree[T]]) {
  def this(value: T) = this(value, List())
  override def toString = "M(" + value.toString + " {" + children.map(_.toString).mkString(",") + "})"
}

object MTree {
  def apply[T](value: T) = new MTree(value, List())
  def apply[T](value: T, children: List[MTree[T]]) = new MTree(value, children)
}</pre>

<p>The example tree is, thus:</p>

<code>MTree('a', List(MTree('f', List(MTree('g'))), MTree('c'), MTree('b', List(MTree('d'), MTree('e')))))</code>

<p>The starting code skeleton for this section
  is <a href="http://aperiodic.net/phil/scala/s-99/mtree1.scala">mtree1.scala</a>.</p>

<dl>
<dt id="pP70B"><strong>P70B Omitted; we can only create well-formed
    trees.</strong></dt>
<dd><br></dd>

<dt id="pP70C"><strong><a href="http://aperiodic.net/phil/scala/s-99/p70c.scala">P70C</a> (*)
    Count the nodes of a multiway tree.</strong></dt>
<dd>Write a method <code>nodeCount</code> which counts the nodes of a
  given multiway tree.
<pre>scala&gt; MTree('a', List(MTree('f'))).nodeCount
res0: Int = 2</pre></dd>

<dt id="p70"><strong><a href="http://aperiodic.net/phil/scala/s-99/p70.scala">P70</a> (**)
    Tree construction from a node string.</strong></dt>
<dd><img align="right" src="./README_files/p70.gif">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.

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

    <p>Define the syntax of the string and write a
    function <code>string2MTree</code> to construct an <code>MTree</code>
    from a <code>String</code>.  Make the function an
    implicit conversion from <code>String</code>.  Write the reverse
    function, and make it the toString method of MTree.</p>
<pre>scala&gt; MTree('a', List(MTree('f', List(MTree('g'))), MTree('c'), MTree('b', List(MTree('d'), MTree('e'))))).toString
res0: String = afg^^c^bd^e^^^</pre></dd>
    
<dt id="p71"><strong><a href="http://aperiodic.net/phil/scala/s-99/p71.scala">P71</a> (*)
    Determine the internal path length of a tree.</strong></dt>
<dd>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 <a href="http://aperiodic.net/phil/scala/s-99/3p70">P70</a> has
  an internal path length of 9.  Write a
  method <code>internalPathLength</code> to return that sum.
<pre>scala&gt; "afg^^c^bd^e^^^".internalPathLength
res0: Int = 9</pre></dd>

<dt id="p72"><strong><a href="http://aperiodic.net/phil/scala/s-99/p72.scala">P72</a> (*)
    Construct the postorder sequence of the tree nodes.</strong></dt>
<dd>Write a method <code>postorder</code> which constructs the postorder
  sequence of the nodes of a multiway tree.  The result should be
  a <code>List</code>.
<pre>scala&gt; "afg^^c^bd^e^^^".postorder
res0: List[Char] = List(g, f, c, d, e, b, a)</pre></dd>

<dt id="p73"><strong><a href="http://aperiodic.net/phil/scala/s-99/p73.scala">P73</a> (**)
    Lisp-like tree representation.</strong></dt>
<dd>There is a particular notation for multiway trees in Lisp.  Lisp is a
  prominent functional programming language.  In Lisp almost everything
  is a list.
    
  <p>Our example tree would be represented in Lisp as <code>(a (f g) c (b d
    e))</code>.  The following pictures give some more examples.</p>

  <p><img src="./README_files/p73.png"></p>

  <p>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 ')', with the atoms separated by
    spaces.  We can represent this syntax as a Scala <code>String</code>.
    Write a method <code>lispyTree</code> which constructs a "lispy
    string" from an <code>MTree</code>.

</p><pre>scala&gt; MTree("a", List(MTree("b", List(MTree("c"))))).lispyTree
res0: String = (a (b c))</pre>

  <p>As a second, even more interesting, exercise try to write a method
    that takes a "lispy" string and turns it into a multiway tree.</p>

  <p>[Note: Much of this problem is taken from the wording of the same
    problem in the Prolog set.  This is certainly one way of looking at
    Lisp notation, but it's not how the language actually represents that
    syntax internally.  I can elaborate more on this, if requested.
    &lt;<a href="mailto:phil_g@pobox.com">PMG</a>&gt;]</p></dd>
</dl>

<p>The complete source file for this section
  is <a href="http://aperiodic.net/phil/scala/s-99/mtree.scala">mtree.scala</a>.</p>

<h2 id="graphs">Graphs</h2>

<p><img align="right" src="./README_files/graph1.gif">A graph is defined as a set of
  nodes and a set of edges, where each edge is a pair of nodes.</p>

<p>The class to represent a graph is mutable, which isn't in keeping with
  pure functional programming, but a pure functional data structure would
  make things much, much more complicated.  [Pure functional graphs with
  cycles require laziness; I think Scala can handle it, but I think that
  would add too much of a barrier to the following questions.
  &lt;<a href="mailto:phil_g@pobox.com">PMG</a>&gt;]</p>

<p>Our <code>Graph</code>s use an incidence list internally.  Each has a
  list of nodes and a list of edges.  Each node also has a list of edges
  that connect it to other nodes.  In a directed graph, nodes that are the
  target of arcs do not have references to those arcs in their adjacency
  list.</p>

<pre>abstract class GraphBase[T, U] {
  case class Edge(n1: Node, n2: Node, value: U) {
    def toTuple = (n1.value, n2.value, value)
  }
  case class Node(value: T) {
    var adj: List[Edge] = Nil
    def neighbors: List[Node] = adj.map(edgeTarget(_, this).get)
  }

  var nodes: Map[T, Node] = Map()
  var edges: List[Edge] = Nil

  // If the edge E connects N to another node, returns the other node,
  // otherwise returns None.
  def edgeTarget(e: Edge, n: Node): Option[Node]

  override def equals(o: Any) = o match {
    case g: GraphBase[T,U] =&gt; (nodes.keys.toList -- g.nodes.keys.toList == Nil &amp;&amp;
                               edges.map(_.toTuple) -- g.edges.map(_.toTuple) == Nil)
    case _ =&gt; false
  }

  def addNode(value: T) = {
    val n = new Node(value)
    nodes = Map(value -&gt; n) ++ nodes
    n
  }
}

class Graph[T, U] extends GraphBase[T, U] {
  override def equals(o: Any) = o match {
    case g: Graph[T,U] =&gt; super.equals(g)
    case _ =&gt; false
  }

  def edgeTarget(e: Edge, n: Node): Option[Node] =
    if (e.n1 == n) Some(e.n2)
    else if (e.n2 == n) Some(e.n1)
    else None

  def addEdge(n1: T, n2: T, value: U) = {
    val e = new Edge(nodes(n1), nodes(n2), value)
    edges = e :: edges
    nodes(n1).adj = e :: nodes(n1).adj
    nodes(n2).adj = e :: nodes(n2).adj
  }
}

class Digraph[T, U] extends GraphBase[T, U] {
  override def equals(o: Any) = o match {
    case g: Digraph[T,U] =&gt; super.equals(g)
    case _ =&gt; false
  }

  def edgeTarget(e: Edge, n: Node): Option[Node] =
    if (e.n1 == n) Some(e.n2)
    else None

  def addArc(source: T, dest: T, value: U) = {
    val e = new Edge(nodes(source), nodes(dest), value)
    edges = e :: edges
    nodes(source).adj = e :: nodes(source).adj
  }
}</pre>

<p>The full initial Graph code, which also includes objects for creating
  graphs, is in <a href="http://aperiodic.net/phil/scala/s-99/graph1.scala">graph1.scala</a>.</p>

<p>There are a few ways to create a graph from primitives.
The <em>graph-term form</em> lists the nodes and edges separately:</p>

<pre>Graph.term(List('b', 'c', 'd', 'f', 'g', 'h', 'k'),
           List(('b', 'c'), ('b', 'f'), ('c', 'f'), ('f', 'k'), ('g', 'h')))</pre>

<p>The <em>adjacency-list form</em> associates each node with its adjacent
nodes.  In an undirected graph, care must be taken to ensure that all
links are symmetric--if b is adjacent to c, c must also be adjacent to
b.</p>

<pre>Graph.adjacent(List(('b', List('c', 'f')), ('c', List('b', 'f')), ('d', Nil),
                    ('f', List('b', 'c', 'k')), ('g', List('h')), ('h', List('g')),
                    ('k', List('f'))))</pre>

<p>The representations we introduced so far are bound to our
implementation and therefore well suited for automated processing, but
their syntax is not very user-friendly.  Typing the terms by hand is
cumbersome and error-prone.  We can define a more compact and
"human-friendly" notation as follows: A graph is represented by a string
of terms of the type X or Y-Z separated by commas.  The standalone terms
stand for isolated nodes, the Y-Z terms describe edges.  If an X appears
as an endpoint of an edge, it is automatically defined as a node.  Our
example could be written as:</p>

<pre>[b-c, f-c, g-h, d, f-b, k-f, h-g]</pre>

<p>We call this the <em>human-friendly form</em>.  As the example shows,
the list does not have to be sorted and may even contain the same edge
multiple times.  Notice the isolated node d.</p>

<p><img align="right" src="./README_files/graph2.gif">When the edges of a graph
are <em>directed</em>, we call them arcs.  These are represented by
ordered pairs.  Such a graph is called directed graph.  To represent a
directed graph, the forms discussed above are slightly modified.  The
example graph opposite is represented as follows:</p>

<p><em>graph-term form</em>:</p>
<pre>Digraph.term(List('r', 's', 't', 'u', 'v'),
             List(('s', 'r'), ('s', 'u'), ('u', 'r'), ('u', 's'), ('v', 'u')))</pre>

<p><em>adjacency-list form</em>:</p>
<pre>Digraph.adjacent(List(('r', Nil), ('s', List('r', 'u')), ('t', Nil),
                      ('u', List('r', 's')), ('v', List('u'))))</pre>

<p>(Note that the adjacency-list form is the same for graphs and
digraphs.)</p>

<p><em>human-friendly form</em>:</p>
<pre>[s&gt;r, t, u&gt;r, s&gt;u, u&gt;s, v&gt;u]</pre>

<p><img align="right" src="./README_files/graph3.gif">Finally, graphs and digraphs may
have additional information attached to nodes and edges (arcs).  For the
nodes, this is no problem, as we can put any type into them.  On the other
hand, for edges we have to extend our notation.  Graphs with additional
information attached to edges are called labeled graphs.</p>

<p><em>graph-term form</em>:</p>
<pre>Digraph.termLabel(List('k', 'm', 'p', 'q'),
                  List(('m', 'q', 7), ('p', 'm', 5), ('p', 'q', 9)))</pre>

<p><em>adjacency-list form</em>:</p>
<pre>Digraph.adjacentLabel(
  List(('k', Nil), ('m', List(('q', 7))), ('p', List(('m', 5), ('q', 9))),
       ('q', Nil)))</pre>

<p><em>human-friendly form</em>:</p>
<pre>[p&gt;q/9, m&gt;q/7, k, p&gt;m/5]</pre>

<p>The notation for labeled graphs can also be used for so-called
multi-graphs, where more than one edge (or arc) is allowed between two
given nodes.</p>

<dl>
<dt id="p80"><strong><a href="http://aperiodic.net/phil/scala/s-99/p80.scala">P80</a> (***)
    Conversions.</strong></dt>
<dd>Write methods to generate the graph-term and adjacency-list forms
  from a <code>Graph</code>.  Write another method to output the
  human-friendly form for a graph.  Make it the <code>toString</code>
  method for <code>Graph</code>.  Write more functions to create graphs
  from strings.

  <p>Hint: You might need separate functions for labeled and unlabeled
    graphs.</p>

<pre>scala&gt; Graph.fromString("[b-c, f-c, g-h, d, f-b, k-f, h-g]").toTermForm
res0: (List[String], List[(String, String, Unit)]) = (List(d, k, h, c, f, g, b),List((h,g,()), (k,f,()), (f,b,()), (g,h,()), (f,c,()), (b,c,())))

scala&gt; Digraph.fromStringLabel("[p&gt;q/9, m&gt;q/7, k, p&gt;m/5]").toAdjacentForm
res1: List[(String, List[(String, Int)])] = List((m,List((q,7))), (p,List((m,5), (q,9))), (k,List()), (q,List()))</pre></dd>

<dt id="p81"><strong><a href="http://aperiodic.net/phil/scala/s-99/p81.scala">P81</a> (**)
    Path from one node to another one.</strong></dt>
<dd>Write a method named <code>findPaths</code> to find acyclic paths
  from one node to another in a graph.  The method should return all
  paths.
<pre>scala&gt; Digraph.fromStringLabel("[p&gt;q/9, m&gt;q/7, k, p&gt;m/5]").findPaths("p", "q")
res0: List[List[String]] = List(List(p, q), List(p, m, q))
    
scala&gt; Digraph.fromStringLabel("[p&gt;q/9, m&gt;q/7, k, p&gt;m/5]").findPaths("p", "k")
res1: List[List[String]] = List()</pre></dd>

<dt id="p82"><strong><a href="http://aperiodic.net/phil/scala/s-99/p82.scala">P82</a> (*)
    Cycle from a given node.</strong></dt>
<dd>Write a method named <code>findCycles</code> to find closed paths
  (cycles) starting at a given node in a graph.  The method should return
  all cycles.
<pre>scala&gt; Graph.fromString("[b-c, f-c, g-h, d, f-b, k-f, h-g]").findCycles("f")
res0: List[List[String]] = List(List(f, c, b, f), List(f, b, c, f))</pre></dd>

<dt id="p83"><strong><a href="http://aperiodic.net/phil/scala/s-99/p83.scala">P83</a> (**)
    Construct all spanning trees.</strong></dt>
<dd><img align="right" src="./README_files/p83.gif">Write a
  method <code>spanningTrees</code> to construct all spanning trees of a
  given graph.  With this method, find out how many spanning trees there
  are for the graph depicted to the right.  The data of this example graph
  can be found below.  When you have a correct solution for
  the <code>spanningTrees</code> method, use it to define two other useful
  methods: <code>isTree</code> and <code>isConnected</code>.  Both are
  five-minute tasks!
    
  <p>Graph:</p>
<pre>Graph.term(List('a', 'b', 'c', 'd', 'e', 'f', 'g', 'h'),
           List(('a', 'b'), ('a', 'd'), ('b', 'c'), ('b', 'e'),
                ('c', 'e'), ('d', 'e'), ('d', 'f'), ('d', 'g'),
                ('e', 'h'), ('f', 'g'), ('g', 'h')))</pre>

<pre>scala&gt; Graph.fromString("[a-b, b-c, a-c]").spanningTrees
res0: List[Graph[String,Unit]] = List([a-b, b-c], [a-c, b-c], [a-b, a-c])</pre></dd>

<dt id="p84"><strong><a href="http://aperiodic.net/phil/scala/s-99/p84.scala">P84</a> (**)
    Construct the minimal spanning tree.</strong></dt>
<dd><img align="right" src="./README_files/p84.gif">Write a
  method <code>minimalSpanningTree</code> to construct the minimal
  spanning tree of a given labeled graph.  Hint: Use Prim's Algorithm.  A
  small modification of the solution of <a href="http://aperiodic.net/phil/scala/s-99/#p83">P83</a> does the
  trick.  The data of the example graph to the right can be found below.

  <p>Graph:</p>
<pre>Graph.termLabel(
  List('a', 'b', 'c', 'd', 'e', 'f', 'g', 'h'),
       List(('a', 'b', 5), ('a', 'd', 3), ('b', 'c', 2), ('b', 'e', 4),
            ('c', 'e', 6), ('d', 'e', 7), ('d', 'f', 4), ('d', 'g', 3),
            ('e', 'h', 5), ('f', 'g', 4), ('g', 'h', 1)))</pre>

<pre>scala&gt; Graph.fromStringLabel("[a-b/1, b-c/2, a-c/3]").minimalSpanningTree
res0: Graph[String,Int] = [a-b/1, b-c/2]</pre></dd>

<dt id="p85"><strong><a href="http://aperiodic.net/phil/scala/s-99/p85.scala">P85</a> (**)
    Graph isomorphism.</strong></dt>
<dd>Two
  graphs <i>G</i><sub>1</sub>(<i>N</i><sub>1</sub>,<i>E</i><sub>1</sub>)
  and <i>G</i><sub>2</sub>(<i>N</i><sub>2</sub>,<i>E</i><sub>2</sub>) are
  isomorphic if there is a bijection f: <i>N</i><sub>1</sub>
  → <i>N</i><sub>2</sub> such that for any nodes <i>X</i>,<i>Y</i>
  of <i>N</i><sub>1</sub>, <i>X</i> and <i>Y</i> are adjacent if and only
  if f(<i>X</i>) and f(<i>Y</i>) are adjacent.
    
  <p>Write a method that determines whether two graphs are isomorphic.</p>
<pre>scala&gt; Graph.fromString("[a-b]").isIsomorphicTo(Graph.fromString("[5-7]"))
res0: Boolean = true</pre></dd>

<dt id="p86"><strong><a href="http://aperiodic.net/phil/scala/s-99/p86.scala">P86</a> (**)
    Node degree and graph coloration.</strong></dt>
<dd>a) Write a method <code>Node.degree</code> that determines the degree
  of a given node. 
    
  <pre>scala&gt; Graph.fromString("[a-b, b-c, a-c, a-d]").nodes("a").degree
res0: Int = 3</pre>

  <p>b) Write a method that lists all nodes of a graph sorted according to
    decreasing degree.</p>

  <pre>scala&gt; Graph.fromString("[a-b, b-c, a-c, a-d]").nodesByDegree
res1: List[Graph[String,Unit]#Node] = List(Node(a), Node(c), Node(b), Node(d))</pre>

  <p>c) Use Welsh-Powell's algorithm to paint the nodes of a graph in such
    a way that adjacent nodes have different colors.  Make a
    method <code>colorNodes</code> that returns a list of tuples, each of
    which contains a node and an integer representing its color.</p>

  <pre>scala&gt; Graph.fromString("[a-b, b-c, a-c, a-d]").colorNodes
res2: List[(Graph[String,Unit]#Node,Int)] = List((Node(a),1), (Node(b),2), (Node(c), 3), (Node(d), 2))</pre></dd>

<dt id="p87"><strong><a href="http://aperiodic.net/phil/scala/s-99/p87.scala">P87</a> (**)
    Depth-first order graph traversal.</strong></dt>
<dd>Write a method that generates a depth-first order graph traversal
  sequence.  The starting point should be specified, and the output
  should be a list of nodes that are reachable from this starting point
  (in depth-first order).

<pre>scala&gt; Graph.fromString("[a-b, b-c, e, a-c, a-d]").nodesByDepthFrom("d")
res0: List[String] = List(c, b, a, d)</pre></dd>

<dt id="p88"><strong><a href="http://aperiodic.net/phil/scala/s-99/p88.scala">P88</a> (**)
    Connected components.</strong></dt>
<dd>Write a function that splits a graph into its connected components.
<pre>scala&gt; Graph.fromString("[a-b, c]").splitGraph
res0: List[Graph[String,Unit]] = List([a-b], [c])</pre></dd>

<dt id="p89"><strong><a href="http://aperiodic.net/phil/scala/s-99/p89.scala">P89</a> (**)
    Bipartite graphs.</strong></dt>
<dd>Write a function that determines whether a given graph is
  bipartite.

<pre>scala&gt; Digraph.fromString("[a&gt;b, c&gt;a, d&gt;b]").isBipartite
res0: Boolean = true

scala&gt; Graph.fromString("[a-b, b-c, c-a]").isBipartite
res1: Boolean = false

scala&gt; Graph.fromString("[a-b, b-c, d]").isBipartite
res2: Boolean = true

scala&gt; Graph.fromString("[a-b, b-c, d, e-f, f-g, g-e, h]").isBipartite
res3: Boolean = false</pre></dd>
</dl>

<p>The complete source file for this section
  is <a href="http://aperiodic.net/phil/scala/s-99/graph.scala">graph.scala</a>.</p>

<h2 id="misc">Miscellaneous Problems</h2>

<dl>
<dt id="p90"><strong><a href="http://aperiodic.net/phil/scala/s-99/p90.scala">P90</a> (**)
    Eight queens problem</strong></dt>
<dd>This is a classical problem in computer science.  The objective is to
  place eight queens on a chessboard so that no two queens are attacking
  each other; i.e., no two queens are in the same row, the same column,
  or on the same diagonal.

  <p>Hint: Represent the positions of the queens as a list of numbers
    1..<i>N</i>.  Example: <code>List(4, 2, 7, 3, 6, 8, 5, 1)</code> means
    that the queen in the first column is in row 4, the queen in the
    second column is in row 2, etc.  Use the generate-and-test paradigm.</p></dd>

<dt id="p91"><strong><a href="http://aperiodic.net/phil/scala/s-99/p91.scala">P91</a> (**)
    Knight's tour.</strong></dt>
<dd>Another famous problem is this one: How can a knight jump on
    an <i>N</i>×<i>N</i> chessboard in such a way that it visits every
    square exactly once?

  <p>Hints: Represent the squares by pairs of their coordinates of the
    form (<i>X</i>, <i>Y</i>), where both <i>X</i> and <i>Y</i> are
    integers between 1 and <i>N</i>. (Alternately, define a Point class
    for the same purpose.)  Write a function jumps(<i>N</i>,
    (<i>X</i>, <i>Y</i>)) to list the squares that a knight can jump to
    from (<i>X</i>, <i>Y</i>) on a <i>N</i>×<i>N</i> chessboard.  And
    finally, represent the solution of our problem as a list of knight
    positions (the knight's tour).</p>

  <p>It might be nice to find more than one tour, but a computer will take
    a long time trying to find them all at once.  Can you make a lazy list
    that only calculates the tours as needed?</p>

  <p>Can you find only "closed tours", where the knight can jump from its
    final position back to its starting position?</p></dd>

<dt id="p92"><strong><a href="http://aperiodic.net/phil/scala/s-99/p92.scala">P92</a> (***)
    Von Koch's conjecture.</strong></dt>
<dd>Several years ago I met a mathematician who was intrigued by a problem
  for which he didn't know a solution.  His name was Von Koch, and I don't
  know whether the problem has been solved since.  [The "I" here refers to
  the author of the Prolog problems.
  &lt;<a href="mailto:phil_g@pobox.com">PMG</a>&gt;]
    
  <p><img src="./README_files/p92a.gif"></p>

  <p>Anyway the puzzle goes like this: Given a tree with <i>N</i> nodes
    (and hence <i>N</i>-1 edges), find a way to enumerate the nodes from 1
    to <i>N</i> and, accordingly, the edges from 1 to <i>N</i>-1 in such a
    way, that for each edge <i>K</i> the difference of its node numbers is
    equal to <i>K</i>.  The conjecture is that this is always possible.</p>

  <p>For small trees the problem is easy to solve by hand.  However, for
    larger trees, and 14 is already very large, it is extremely difficult
    to find a solution.  And remember, we don't know for sure whether
    there is always a solution!</p>

  <p>Write a function that calculates a numbering scheme for a given tree.
    What is the solution for the larger tree pictured below?</p>

  <p><img src="./README_files/p92b.gif"></p></dd>

<dt id="p93"><strong>P93 (***) An arithmetic puzzle.</strong></dt>
<dd>Given a list of integer numbers, find a correct way of inserting
  arithmetic signs (operators) such that the result is a correct
  equation.  Example: With the list of
  numbers <code>List(2,3,5,7,11)</code> we can form the equations 2-3+5+7
  = 11 or 2 = (3*5+7)/11 (and ten others!).<br><br></dd>

<dt id="p94"><strong>P94 (***) Generate K-regular simple graphs with N
    nodes.</strong></dt>
<dd>In a K-regular graph all nodes have a degree of <i>K</i>; i.e. the
  number of edges incident in each node is <i>K</i>.  How many
  (non-isomorphic!) 3-regular graphs with 6 nodes are there?  See also a
  <a href="http://aperiodic.net/phil/scala/s-99/p94.txt">table of results</a> and
  a <a href="https://prof.ti.bfh.ch/hew1/informatik3/prolog/p-99/GraphLayout/index.html">Java
  applet</a> that can represent graphs geometrically.<br><br></dd>

<dt id="p95"><strong>P95 (**) English number words.</strong></dt>
<dd>On financial documents, like checks, numbers must sometimes be
  written in full words.  Example: 175 must be written as one-seven-five.
  Write a function fullWords(num: Int) to print (non-negative) integer
  numbers in full words.<br><br></dd>

<dt id="p96"><strong>P96 (**) Syntax checker.</strong></dt>
<dd><img align="right" src="./README_files/p96.gif">In a certain programming language
  (Ada) identifiers are defined by the syntax diagram (railroad chart)
  opposite.  Transform the syntax diagram into a system of syntax diagrams
  which do not contain loops; i.e. which are purely recursive.  Using
  these modified diagrams, write a function isIdentifier that can check
  whether or not a given string is a legal identifier.<br><br></dd>

<dt id="p97"><strong><a href="http://aperiodic.net/phil/scala/s-99/p97.scala">P97</a> (**)
    Sudoku.  <a href="http://aperiodic.net/phil/scala/s-99/p97b.scala">(alternate solution)</a></strong></dt>
<dd>Sudoku puzzles go like this:

<pre>   Problem statement                 Solution

    .  .  4 | 8  .  . | .  1  7	     9  3  4 | 8  2  5 | 6  1  7	     
            |         |                      |         |
    6  7  . | 9  .  . | .  .  .	     6  7  2 | 9  1  4 | 8  5  3
            |         |                      |         |
    5  .  8 | .  3  . | .  .  4      5  1  8 | 6  3  7 | 9  2  4
    --------+---------+--------      --------+---------+--------
    3  .  . | 7  4  . | 1  .  .      3  2  5 | 7  4  8 | 1  6  9
            |         |                      |         |
    .  6  9 | .  .  . | 7  8  .      4  6  9 | 1  5  3 | 7  8  2
            |         |                      |         |
    .  .  1 | .  6  9 | .  .  5      7  8  1 | 2  6  9 | 4  3  5
    --------+---------+--------      --------+---------+--------
    1  .  . | .  8  . | 3  .  6	     1  9  7 | 5  8  2 | 3  4  6
            |         |                      |         |
    .  .  . | .  .  6 | .  9  1	     8  5  3 | 4  7  6 | 2  9  1
            |         |                      |         |
    2  4  . | .  .  1 | 5  .  .      2  4  6 | 3  9  1 | 5  7  8</pre>
   

  <p>Every spot in the puzzle belongs to a (horizontal) row and a
    (vertical) column, as well as to one single 3×3 square (which we call
    "square" for short).  At the beginning, some of the spots carry a
    single-digit number between 1 and 9.  The problem is to fill the
    missing spots with digits in such a way that every number between 1
    and 9 appears exactly once in each row, in each column, and in each
    square.</p></dd>

<dt id="p98"><strong>P98 (***) Nonograms.</strong></dt>
<dd>Around 1994, a certain kind of puzzles was very popular in England.
  The "Sunday Telegraph" newspaper wrote: "Nonograms are puzzles from
  Japan and are currently published each week only in The Sunday
  Telegraph.  Simply use your logic and skill to complete the grid and
  reveal a picture or diagram."  As a programmer, you are in a better
  situation: you can have your computer do the work!  Just write a
  little program ;-).
  
  <p>The puzzle goes like this: Essentially, each row and column of a
    rectangular bitmap is annotated with the respective lengths of its
    distinct strings of occupied cells.  The person who solves the puzzle
    must complete the bitmap given only these lengths.</p>

<pre>          Problem statement:          Solution:

          |_|_|_|_|_|_|_|_| 3         |_|X|X|X|_|_|_|_| 3           
          |_|_|_|_|_|_|_|_| 2 1       |X|X|_|X|_|_|_|_| 2 1         
          |_|_|_|_|_|_|_|_| 3 2       |_|X|X|X|_|_|X|X| 3 2         
          |_|_|_|_|_|_|_|_| 2 2       |_|_|X|X|_|_|X|X| 2 2         
          |_|_|_|_|_|_|_|_| 6         |_|_|X|X|X|X|X|X| 6           
          |_|_|_|_|_|_|_|_| 1 5       |X|_|X|X|X|X|X|_| 1 5         
          |_|_|_|_|_|_|_|_| 6         |X|X|X|X|X|X|_|_| 6           
          |_|_|_|_|_|_|_|_| 1         |_|_|_|_|X|_|_|_| 1           
          |_|_|_|_|_|_|_|_| 2         |_|_|_|X|X|_|_|_| 2           
           1 3 1 7 5 3 4 3             1 3 1 7 5 3 4 3              
           2 1 5 1                     2 1 5 1                      </pre>
   

  <p>For the example above, the problem can be stated as the two lists
    <code>[[3],[2,1],[3,2],[2,2],[6],[1,5],[6],[1],[2]]</code> and
    <code>[[1,2],[3,1],[1,5],[7,1],[5],[3],[4],[3]]</code> which give the
    "solid" lengths of the rows and columns, top-to-bottom and
    left-to-right, respectively.  Published puzzles are larger than this
    example, e.g. 25×20, and apparently always have unique solutions.</p></dd>

<dt id="p99"><strong>P99 (***) Crossword puzzle.</strong></dt>
<dd>Given an empty (or almost empty) framework of a crossword puzzle and a
  set of words.  The problem is to place the words into the framework.

  <p><img align="right" src="./README_files/p99.gif">The particular crossword puzzle is
    specified in a text file which first lists the words (one word per
    line) in an arbitrary order. Then, after an empty line, the crossword
    framework is defined.  In this framework specification, an empty
    character location is represented by a dot (.).  In order to make the
    solution easier, character locations can also contain predefined
    character values.  The puzzle opposite is defined in the
    file <a href="http://aperiodic.net/phil/scala/s-99/p99a.dat">p99a.dat</a>, other examples
    are <a href="http://aperiodic.net/phil/scala/s-99/p99b.dat">p99b.dat</a>
    and <a href="http://aperiodic.net/phil/scala/s-99/p99d.dat">p99d.dat</a>.  There is also an example of a
    puzzle (<a href="http://aperiodic.net/phil/scala/s-99/p99c.dat">p99c.dat</a>) which does not have a
    solution.</p>

  <p>Words are strings of at least two characters.  A horizontal or
    vertical sequence of character places in the crossword puzzle
    framework is called a site.  Our problem is to find a compatible way
    of placing words onto sites.</p>

  <p>Hints: (1) The problem is not easy.  You will need some time to
    thoroughly understand it.  So, don't give up too early!  And remember
    that the objective is a clean solution, not just a quick-and-dirty
    hack!</p>
  <p>(2) For efficiency reasons it is important, at least for larger
    puzzles, to sort the words and the sites in a particular order.  For
    this part of the problem, the solution of <a href="http://aperiodic.net/phil/scala/s-99/#p28">P28</a> may
    be very helpful.</p></dd>
</dl>


</body></html>