examples/rosettacode/hamming_number.nit

   1 # This file is part of NIT ( http://www.nitlanguage.org ).
   2 # This program is public domain
   3 # Copyright 2014 amineorion <amineorion@gmail.com>
   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 # Task: Hamming numbers
  18 # SEE: <http://rosettacode.org/wiki/Hamming_numbers>
  19 #
  20 # Version that don't support 1,000,000th position of Hamming number yet.
  21
  22 module hamming_number
  23
  24 class HammingTriple
  25         super Comparable
  26
  27         var a: Int
  28         var b: Int
  29         var c: Int
  30
  31         redef type OTHER: HammingTriple
  32
  33         init(a: Int, b: Int, c: Int)
  34         do
  35                 self.a = a
  36                 self.b = b
  37                 self.c = c
  38         end
  39
  40         redef fun >(other: OTHER): Bool
  41         do
  42                 if a > other.a and b > other.b and c > other.c then
  43                         return true
  44                 end
  45
  46                 if a < other.a and b < other.b and c < other.c then
  47                         return false
  48                 end
  49
  50                 if self == other then
  51                         return false
  52                 end
  53
  54                 var log1 = log
  55                 var log2 = other.log
  56
  57                 if not log1.is_approx(log2, 0.000001) then
  58                         return log1 > log2
  59                 end
  60                 return false
  61         end
  62
  63         fun log: Float
  64         do
  65                 return a.to_f * 2.0.log + b.to_f * 3.0.log + c.to_f * 5.0.log
  66         end
  67
  68         redef fun ==(o)
  69         do
  70                 return o isa HammingTriple and a == o.a and b == o.b and c == o.c
  71         end
  72
  73         fun calcul: Int
  74         do
  75                 return (2 ** a) * (3 ** b) * (5 ** c)
  76         end
  77
  78         redef fun to_s: String
  79         do
  80                 return "a: {a}, b: {b}, c: {c}"
  81         end
  82 end
  83
  84 class HammingArray
  85         super Array[HammingTriple]
  86
  87         fun get_min: HammingTriple
  88         do
  89                 var min = self[0]
  90                 var min_index = 0
  91                 for i in [1..length[ do
  92                         if min > self[i] then
  93                                 min = self[i]
  94                                 min_index = i
  95                         end
  96                 end
  97                 remove_at(min_index)
  98                 return min
  99         end
 100 end
 101
 102 fun hamming(limit_position: Int): Int
 103 do
 104         var hamming_triple = new HammingArray
 105         hamming_triple.add(new HammingTriple(0, 0, 0))
 106         loop
 107                 var current = hamming_triple.get_min
 108                 limit_position -= 1
 109                 if limit_position == 0 then
 110                         return current.calcul
 111                 end
 112
 113                 if current.a == 0 and current.b == 0 then
 114                         hamming_triple.add(new HammingTriple(current.a, current.b, current.c + 1))
 115                 end
 116
 117                 if current.a == 0 then
 118                         hamming_triple.add(new HammingTriple(current.a, current.b + 1, current.c))
 119                 end
 120
 121                 hamming_triple.add(new HammingTriple(current.a + 1, current.b, current.c))
 122         end
 123 end
 124
 125 for i in [1..20] do
 126         print "{i}: {hamming(i)}"
 127 end
 128
 129 print "1691: {hamming(1691)}"