tests/example_hanoi.nit

   1 # This file is part of NIT ( http://www.nitlanguage.org ).
   2 #
   3 # Copyright 2004-2008 Jean Privat <jean@pryen.org>
   4 #
   5 # Licensed under the Apache License, Version 2.0 (the "License");
   6 # you may not use this file except in compliance with the License.
   7 # You may obtain a copy of the License at
   8 #
   9 #     http://www.apache.org/licenses/LICENSE-2.0
  10 #
  11 # Unless required by applicable law or agreed to in writing, software
  12 # distributed under the License is distributed on an "AS IS" BASIS,
  13 # WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  14 # See the License for the specific language governing permissions and
  15 # limitations under the License.
  16
  17 # A simple exemple
  18
  19 class Tower
  20         # A tower is a stack of discus.
  21         fun top: Int
  22         # Diameter of the last discus.
  23         do
  24                 return _t.last
  25         end
  26
  27         fun height: Int
  28         # Number of discus.
  29         do
  30                 return _t.length
  31         end
  32
  33         fun push(i: Int)
  34         # Put an discus of diameter `i'.
  35         do
  36                 _t.push(i)
  37         end
  38
  39         fun pop: Int
  40         # Remove the last discus and get its diameter.
  41         do
  42                 assert not_empty: not _t.is_empty
  43                 return _t.pop
  44         end
  45
  46         redef fun to_s: String
  47         # Display the tower
  48         do
  49                 if _t.is_empty then
  50                         return "-"
  51                 else
  52                         return "({_t.join(":")})"
  53                 end
  54         end
  55
  56         var t = new Array[Int] # The stack of discus (only the diameter is stored).
  57
  58         init full(n: Int)
  59         # Build a new tower with `n' discus.
  60         do
  61                 assert positive: n >= 0
  62                 t.enlarge(n)
  63                 for i in [0..n[ do
  64                         push(n-i)
  65                 end
  66         end
  67
  68         init empty
  69         # Build a empty tower.
  70         do
  71         end
  72 end
  73
  74 class Hanoi
  75         # Hanoi is a city with 3 towers.
  76         fun run
  77         do
  78                 move(_tower1.height, _tower1, _tower2, _tower3)
  79         end
  80
  81         private fun move(nb: Int, source: Tower, intermediate: Tower, destination: Tower)
  82         do
  83                 if nb <= 0 then
  84                         return
  85                 end
  86                 move(nb-1, source, destination, intermediate)
  87                 destination.push(source.pop)
  88                 print(self)
  89                 move(nb-1, intermediate, source, destination)
  90         end
  91
  92         redef fun to_s: String
  93         do
  94                 return "{_tower1} {_tower2} {_tower3}"
  95         end
  96
  97         var tower1: Tower
  98         var tower2: Tower
  99         var tower3: Tower
 100
 101         init(nb: Int)
 102         do
 103                 _tower1 = new Tower.full(nb)
 104                 _tower2 = new Tower.empty
 105                 _tower3 = new Tower.empty
 106         end
 107 end
 108
 109 fun usage
 110 do
 111         print("Usage: hanoi <number of discus>")
 112         exit(0)
 113 end
 114
 115 #
 116
 117 if args.length != 1 then
 118         usage
 119 end
 120
 121 var nb = args.first.to_i
 122 if nb < 1 then
 123         usage
 124 end
 125 var h = new Hanoi(nb)
 126 print(h)
 127 h.run