1 # This file is part of NIT ( http://www.nitlanguage.org ).
2 # This program is public domain
3 # Copyright 2014 amineorion <amineorion@gmail.com>
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
9 # http://www.apache.org/licenses/LICENSE-2.0
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.
17 # Task: Hamming numbers
18 # SEE: <http://rosettacode.org/wiki/Hamming_numbers>
20 # Version that don't support 1,000,000th position of Hamming number yet.
31 redef type OTHER: HammingTriple
33 init(a
: Int, b
: Int, c
: Int)
40 redef fun >(other
: OTHER): Bool
42 if a
> other
.a
and b
> other
.b
and c
> other
.c
then
46 if a
< other
.a
and b
< other
.b
and c
< other
.c
then
57 if not log1
.is_approx
(log2
, 0.000001) then
65 return a
.to_f
* 2.0.log
+ b
.to_f
* 3.0.log
+ c
.to_f
* 5.0.log
70 return o
isa HammingTriple and a
== o
.a
and b
== o
.b
and c
== o
.c
75 return (2 ** a
) * (3 ** b
) * (5 ** c
)
78 redef fun to_s
: String
80 return "a: {a}, b: {b}, c: {c}"
85 super Array[HammingTriple]
87 fun get_min
: HammingTriple
91 for i
in [1..length
[ do
102 fun hamming
(limit_position
: Int): Int
104 var hamming_triple
= new HammingArray
105 hamming_triple
.add
(new HammingTriple(0, 0, 0))
107 var current
= hamming_triple
.get_min
109 if limit_position
== 0 then
110 return current
.calcul
113 if current
.a
== 0 and current
.b
== 0 then
114 hamming_triple
.add
(new HammingTriple(current
.a
, current
.b
, current
.c
+ 1))
117 if current
.a
== 0 then
118 hamming_triple
.add
(new HammingTriple(current
.a
, current
.b
+ 1, current
.c
))
121 hamming_triple
.add
(new HammingTriple(current
.a
+ 1, current
.b
, current
.c
))
126 print
"{i}: {hamming(i)}"
129 print
"1691: {hamming(1691)}"