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         meth top: Int
  22         # Diameter of the last discus.
  23         do
  24                 return _t.last
  25         end
  26
  27         meth height: Int
  28         # Number of discus.
  29         do
  30                 return _t.length
  31         end
  32
  33         meth push(i: Int)
  34         # Put an discus of diameter `i'.
  35         do
  36                 _t.push(i)
  37         end
  38
  39         meth 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 meth 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         attr _t: 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 = new Array[Int].with_capacity(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                 _t = new Array[Int]
  72         end
  73 end
  74
  75 class Hanoi
  76         # Hanoi is a city with 3 towers.
  77         meth run
  78         do
  79                 move(_tower1.height, _tower1, _tower2, _tower3)
  80         end
  81
  82         private meth move(nb: Int, source: Tower, intermediate: Tower, destination: Tower)
  83         do
  84                 if nb <= 0 then
  85                         return
  86                 end
  87                 move(nb-1, source, destination, intermediate)
  88                 destination.push(source.pop)
  89                 print(self)
  90                 move(nb-1, intermediate, source, destination)
  91         end
  92
  93         redef meth to_s: String
  94         do
  95                 return "{_tower1} {_tower2} {_tower3}"
  96         end
  97
  98         attr _tower1: Tower
  99         attr _tower2: Tower
 100         attr _tower3: Tower
 101
 102         init(nb: Int)
 103         do
 104                 _tower1 = new Tower.full(nb)
 105                 _tower2 = new Tower.empty
 106                 _tower3 = new Tower.empty
 107         end
 108 end
 109
 110 meth usage
 111 do
 112         print("Usage: hanoi <number of discus>")
 113         exit(0)
 114 end
 115
 116 #
 117
 118 if args.length != 1 then
 119         usage
 120 end
 121
 122 var nb = args.first.to_i
 123 if nb < 1 then
 124         usage
 125 end
 126 var h = new Hanoi(nb)
 127 print(h)
 128 h.run