今回は簡単な例題として、有理数 (分数) を表すクラスを作ってみましょう。
有理数 (Rational) は分子と分母を整数の組で表すと簡単に定義できます。次のリストを見てください。
リスト : 有理数の定義
package rational
class Rat private (val n: BigInt, val d: BigInt) {
override def toString: String =
if (d == 1) n.toString else s"$n/$d"
}
フィールド変数 n が分子を表し、d が分母を表します。どちらも val で宣言します。簡単な定義ですが、多倍長整数を使っているので、大きな数値を扱っても桁あふれの心配はありません。
次は有理数を生成するメソッド apply を作ります。次のリストを見てください。
リスト : 有理数の生成
object Rat {
def apply(a: BigInt, b: BigInt): Rat = {
if (b == 0) throw new ArithmeticException
val g = a gcd b
val n = a * b.signum / g
val d = b * b.signum / g
new Rat(n, d)
}
}
引数 a が分子で、b が分母を表します。b が 0 の場合はエラーを送出します。そうでなければ、Rat (a, b) を生成します。このとき、BigInt のメソッド gcd で最大公約数を求めて、約分することに注意してください。それから、有理数の符号は分子に付けることにします。signum は符号 (-1, 0, 1) を求めるメソッドです。分母 b が負の場合は a と b に -1 を掛け算して、分母を正の値にします。
それでは実際に試してみましょう。
$ scalac rat.scala $ scala -classpath . ... 略 ... scala> import rational._ scala> Rat(10, 100) val res0: rational.Rat = 1/10 scala> Rat(10, -12) val res1: rational.Rat = -5/6 scala> Rat(-1234, -2) val res2: rational.Rat = 617 scala> Rat(-1234, -4) val res3: rational.Rat = 617/2
Scala の演算子はメソッドで「多重定義」もできるので、算術演算子の定義は簡単です。次のリストを見てください。
リスト : 算術演算子の定義
class Rat private (val n: BigInt, val d: BigInt) {
override def toString: String = n + "/" + d
def +(that: Rat): Rat = Rat(n * that.d + that.n * d, d * that.d)
def -(that: Rat): Rat = Rat(n * that.d - that.n * d, d * that.d)
def *(that: Rat): Rat = Rat(n * that.n, d * that.d)
def /(that: Rat): Rat = Rat(n * that.d, d * that.n)
}
単純な分数の計算なので、難しいところはないでしょう。この場合、演算子の優先順位は +, -, *, / と同じです。
それでは実際に試してみましょう。
scala> val a = Rat(1, 2) val a: rational.Rat = 1/2 scala> val b = Rat(1, 3) val b: rational.Rat = 1/3 scala> a + b val res4: rational.Rat = 5/6 scala> a - b val res5: rational.Rat = 1/6 |
scala> b - a val res6: rational.Rat = -1/6 scala> a * b val res7: rational.Rat = 1/6 scala> a / b val res8: rational.Rat = 3/2 scala> b / a val res9: rational.Rat = 2/3 |
これで有理数と有理数の計算はできますが、有理数と整数の計算はできません。そこで、有理数と多倍長整数の計算を行う演算子を定義します。次のリストを見てください。
リスト : 算術演算子の多重定義
class Rat private (val n: BigInt, val d: BigInt) {
override def toString: String = n + "/" + d
def +(that: Rat): Rat = Rat(n * that.d + that.n * d, d * that.d)
def +(x: BigInt): Rat = Rat(n + x * d, d)
def -(that: Rat): Rat = Rat(n * that.d - that.n * d, d * that.d)
def -(x: BigInt): Rat = Rat(n - x * d, d)
def *(that: Rat): Rat = Rat(n * that.n, d * that.d)
def *(x: BigInt): Rat = Rat(n * x, d)
def /(that: Rat): Rat = Rat(n * that.d, d * that.n)
def /(x: BigInt): Rat = Rat(n, d * x)
}
Int や Long に対応するメソッドが定義されていませんが、これでも有理数と整数 (Int, Long, BigInt) の計算を行うことができます。これは、Scala が Int や Long を自動的に BigInt に型変換してくれるからです。次の例を見てください。
scala> val a: BigInt = 10: Int val a: BigInt = 10 scala> val b: BigInt = 10: Long val b: BigInt = 10 scala> val e: BigInt = 10: Double -- [E007] Type Mismatch Error: -------------------------------- 1 |val e: BigInt = 10: Double | ^^^^^^^^^^ | Found: Double | Required: BigInt | | longer explanation available when compiling with `-explain` 1 error found
整数は BigInt に型変換されますが、Double は型変換されずにエラーになります。Scala は型が一致しない場合、事前に用意されている変換関数を呼び出して、型変換を自動的に行います。この機能を「暗黙の型変換 (implicit conversion)」とか「暗黙変換」といいます。整数は BigInt に変換する関数が用意されていますが、Double は用意されていないのでエラーになるわけです。
今のままでは、式が "有理数 演算子 整数" の場合は計算できますが、"整数 演算子 有理数" だとコンパイルエラーになります。そこで、整数を有理数に変換する関数を定義することにしましょう。
変換関数の定義は def の前に implicit を付けます。
implicit def 名前(引数: 元の型): 変換後の型 = 式
名前は "元の型" + "To" + "変換後の型" とするのが一般的なようです。
変換関数はシングルトンオブジェクトに定義しておいて、使用するときにそれを import します。次のリストを見てください。
リスト : 変換関数の定義
object RatConversion {
implicit def intToRat(x: Int): Rat = Rat(x, 1)
implicit def longToRat(x: Long): Rat = Rat(x, 1)
implicit def bigIntToRat(x: BigInt): Rat = Rat(x, 1)
}
変換関数は簡単ですね。有理数 Rat(x, 1) を生成して返すだけです。あとは、有理数を使用するファイルで RatConversion をインポートします。具体的には、次のように宣言します。
import RatConversion._
たとえば、Int を Rat に変換する場合、intToRat が必要になりますが、このとき intToRat が RatConversion の中に入ったままだと、暗黙の型変換で intToRat を見つけることができません。つまり、変換関数は RatConversion.intToRat ではなく intToRat で参照できるようにしておかないと、暗黙の型変換は機能しないのです。
実は、もうひとつ簡単な方法があります。それはコンパニオンオブジェクトに変換関数を定義することです。次のリストを見てください。
リスト : 変換関数の定義
object Rat {
//
// ・・・省略・・・
//
implicit def byteToRat(x: Byte): Rat = Rat(x, 1)
implicit def shortToRat(x: Short): Rat = Rat(x, 1)
implicit def intToRat(x: Int): Rat = Rat(x, 1)
implicit def longToRat(x: Long): Rat = Rat(x, 1)
implicit def bigIntToRat(x: BigInt): Rat = Rat(x, 1)
}
クラス Rat にはコンパニオンオブジェクトがあるので、そこに変換関数を定義するだけです。今回はこの方法を使うことにします。
それでは実際に試してみましょう。
$ $ scalac rat.scala there were 3 feature warnings; re-run with -feature for details 1 warning found
scala> import rational._ scala> val a = Rat(1, 2) val a: rational.Rat = 1/2 scala> val b = 10 val b: Int = 10 scala> val c: BigInt = 20 val c: BigInt = 20 scala> b + a val res0: rational.Rat = 21/2 scala> c + a val res1: rational.Rat = 41/2 scala> b * a val res2: rational.Rat = 5 scala> c * a val res3: rational.Rat = 10
Scala 3 の場合、暗黙の型変換を使うと warning がでるようです。これは次に示す import 文をファイルに書くと抑制することができます。
import scala.language.implicitConversions
warning を表示するということは、暗黙の型変換は使用に注意が必要な機能なのでしょう。暗黙の型変換は、ちょっと危険で難しい話のようなので、今回はここまでにしておきます。もっと勉強してから再度取り上げることにします。
次は比較演算子を定義します。プログラムは次のようになります。
リスト : 比較演算子の定義
class Rat private (val n: BigInt, val d: BigInt) {
//
// ・・・省略・・・
//
override def equals(other: Any): Boolean =
other match {
case that: Rat => that.n == n && that.d == d
case _ => false
}
private def compare(that: Rat): Int = (this - that).n.signum
def < (that: Rat): Boolean = compare(that) < 0
def <=(that: Rat): Boolean = compare(that) <= 0
def > (that: Rat): Boolean = compare(that) > 0
def >=(that: Rat): Boolean = compare(that) >= 0
}
等値の判定はメソッド equals をオーバーライドするだけです。大小関係の比較はメソッド compare を呼び出します。これは左辺の値から右辺の値を引き算して、その符号を返します。あとは、各メソッドで compare の返り値と 0 を比較するだけです。
それでは実際に試してみましょう。
scala> import rational._ import rational._ scala> val a = Rat(1, 2) val a: rational.Rat = 1/2 scala> val b = Rat(1, 3) val b: rational.Rat = 1/3 scala> a == Rat(1, 2) val res0: Boolean = true scala> a == b val res1: Boolean = false scala> a != b val res2: Boolean = true |
scala> a < b val res3: Boolean = false scala> b < a val res4: Boolean = true scala> a + a >= Rat(1, 1) val res5: Boolean = true scala> a + a <= Rat(1, 1) val res6: Boolean = true scala> a + a >= Rat(2, 1) val res7: Boolean = false scala> a + a <= Rat(1, 4) val res8: Boolean = false |
最後にちょっと便利なメソッドを定義しておきます。
リスト : その他のメソッド
class Rat private (val n: BigInt, val d: BigInt) {
//
// ・・・省略・・・
//
def abs: Rat = if (n >= 0) this else Rat(-n, d)
def inv: Rat = Rat(d, n)
def signum: Int = n.signum
def isInteger: Boolean = d == 1
def toInteger: BigInt = n / d
}
メソッド abs は有理数の絶対値を求めます。inv は有理数の逆数を求めます。これは分子と分母を逆にするだけです。signum は符号を求めます。isInteger は有理数が整数ならば真を返します。これは分母 d が 1 かチェックするだけです。toInteger は有理数を整数に変換します。単純に割り算するだけです。
それではクラス Rat を使ってパズルを解いてみましょう。それでは問題です。
下図の A から I の場所に 1 から 9 までの数字をひとつずつ配置します。3 つの分数を足すと 1 / N になる配置を求めてください。
このパズルの元ネタは N = 1 の場合で、参考文献 [1] に掲載されています。ちなみに、3 つの分数の和が整数になる場合、その値は 1 しかありません。
プログラムは次のようになります。
リスト : 小町分数の解法
import rational._
object komachiRat {
def komachi(): Unit = {
val iter = Range(1, 10).toList.permutations
while (iter.hasNext) {
// a/bc + d/ef + g/hi = N
val xs = iter.next()
val x = Rat(xs(0), xs(1) * 10 + xs(2))
val y = Rat(xs(3), xs(4) * 10 + xs(5))
val z = Rat(xs(6), xs(7) * 10 + xs(8))
val r = x + y + z
if (xs(0) < xs(3) && xs(3) < xs(6) && r.inv.isInteger) {
print(s"${xs(0)}/${xs(1)}${xs(2)} + ")
print(s"${xs(3)}/${xs(4)}${xs(5)} + ")
print(s"${xs(6)}/${xs(7)}${xs(8)} = ")
println(r)
}
}
}
def main(args: Array[String]): Unit = {
komachi()
}
}
1 から 9 までの数字の順列を生成して、条件を満たしているかチェックするだけです。今回は Scala の permutations をそのまま呼び出して、9! 通りの順列を生成しています。次に、3 つの分数を計算して変数 x, y, z にセットし、x + y + z の結果を変数 r にセットします。
次の if 式で条件を満たしているかチェックします。重複解を取り除くため、分子の数字を A < D < G に限定しています。順列の生成でこの処理を入れると枝刈りの効果で実行速度はもう少し速くなります。結果 r の逆数が整数であれば、条件を満たしているので print で式を表示します。
実行結果は次のようになります。
$ scalac komachiRat.scala $ scala komachiRat 1/24 + 3/56 + 7/98 = 1/6 1/26 + 5/39 + 7/84 = 1/4 1/32 + 5/96 + 7/84 = 1/6 1/38 + 2/95 + 4/76 = 1/10 1/48 + 5/32 + 7/96 = 1/4 1/56 + 3/72 + 9/84 = 1/6 1/96 + 5/32 + 7/84 = 1/4 1/96 + 5/48 + 7/32 = 1/3 2/18 + 5/63 + 7/49 = 1/3 2/19 + 4/57 + 6/38 = 1/3 3/27 + 6/54 + 9/81 = 1/3 3/48 + 5/16 + 9/72 = 1/2 3/54 + 6/72 + 9/81 = 1/4 5/34 + 7/68 + 9/12 = 1
結果は全部で 14 通りになりました。
Rat を使ってもう一つパズルを解いてみましょう。Four fours は数字を使ったパズルです。いろいろなルールがあるのですが、今回は簡易ルールで行きましょう。それでは問題です。
数字 4 を 4 つと +, - *, /, () を使って、答えが 1 から 10 になる式を作ってください。数字は 4 だけではなく、44 や 444 のように合体させてもかまいません。ただし、- を符号として使ってはいけません。
数字の 4 を 4 つ使うので Four fours という名前なのだと思います。ところで、このルールでは 11 になる式を作ることができません。ほかのルール、たとえば小数点を付け加えると、次のように作ることができます。
4 / .4 + 4 / 4 = 11
今回は簡易ルールということで、小数点を使わないで 1 から 10 までの式を作ってください。まずは、ご自分の頭を使って解いてみましょう。気分転換や息抜きのときにでも考えてみてください。
Ｘ Ｘ Ｘ
／ ＼ ／ ＼ ／ ＼
／ ＼ ４ Ｙ Ｙ ４
Ｙ Ｚ ／ ＼ ／ ＼
／ ＼ ／ ＼ ４ Ｚ Ｚ ４
４ ４ ４ ４ ／ ＼ ／ ＼
４ ４ ４ ４
（１） （２） （３）
Ｘ Ｘ
／ ＼ ／ ＼
４ Ｙ Ｙ ４
／ ＼ ／ ＼
Ｚ ４ ４ Ｚ
／ ＼ ／ ＼
４ ４ ４ ４
（４） （５）
図 : 数式のパターン (二分木)
それではプログラムを作りましょう。基本的には、数式を生成して答えをチェックするだけです。Four fours の場合、4 つの数値に 3 つの演算子しかありませんから、数式のパターンは簡単に求めることができます。数式を二分木で表すと、上図に示す 5 つのパターンになります。
X, Y, Z が演算子を表します。これを式で表すと、次のようになります。
(1) (4 Y 4) X (4 Z 4) (2) 4 X (4 Y (4 Z 4)) (3) ((4 Z 4) Y 4) X 4 (4) 4 X ((4 Z 4) Y 4) (5) (4 Y (4 Z 4)) X 4
あとは、X, Y, Z に演算子 +, -, *, / を入れて数式を計算すればいいわけです。
Four fours は数字を合体できるので、数字が 3 つで演算子が 2 つ、数字が 2 つで演算子がひとつ、というパターンもあります。演算子がひとつの場合は簡単ですね。演算子が 2 つの場合は、次の式になります。
(A) (a Y b) X c (B) a X (b Y c)
a, b, c が数字で X, Y が演算子を表しています。数字は 4 か 44 になります。この場合、a, b, c の組み合わせを生成する必要があります。組み合わせを (a, b, c) で表すと、(4, 4, 44), (4, 44, 4), (44, 4, 4) の 3 通りとなります。これと演算子の組み合わせにより数式を生成して、答えを求めてチェックします。
最後に演算子がひとつの場合をチェックします。これは (4 op 444), (44 op 44), (444 op 4) の 3 通りをチェックするだけです。
それではプログラムを作りましょう。最初に数式を表す二分木を定義します。
リスト : 数式の定義
// 数式 (抽象クラス)
abstract class Expr {
def eval: Rat
def printExpr(): Unit
}
// 節
case class Node(op: String, left: Expr, right: Expr) extends Expr {
def eval: Rat = op match {
case "+" => left.eval + right.eval
case "-" => left.eval - right.eval
case "*" => left.eval * right.eval
case "/" => left.eval / right.eval
}
def printExpr(): Unit = {
print("(")
left.printExpr()
print(" " + op + " ")
right.printExpr()
print(")")
}
}
// 葉
case class Leaf(n: Rat) extends Expr {
def eval: Rat = n
def printExpr(): Unit = print(n)
}
Expr は数式を表す二分木です。数式の場合、数値は葉 (Leaf) に格納され、演算子は節 (Node) に格納されます。値を正確に計算するため、数値には Rat を使います。メソッド eval は式を計算し、printExpr は式を表示します。
節 Node は演算子 op と、左右の式を格納します。eval は簡単で、right.eval, left.eval で左右の式を計算し、それを op に対応する演算子で計算するだけです。printExpr は "(右辺 演算子 左辺)" を表示します。右辺と左辺は printExpr を再帰呼び出しするだけです。
葉 Leaf は数値を格納します。メソッド eval は簡単で、格納している数値 n を返すだけです。printExpr は n を表示するだけです。
次は数式を生成する処理を作ります。
リスト : 数式の生成
def makeExpr4(op1: String, op2: String, op3: String): List[Expr] = {
val four = Leaf(4)
List(Node(op1, Node(op2, four, four), Node(op3, four, four)),
Node(op1, four, Node(op2, four, Node(op3, four, four))),
Node(op1, Node(op2, Node(op3, four, four), four), four),
Node(op1, four, Node(op2, Node(op3, four, four), four)),
Node(op1, Node(op2, four, Node(op3, four, four)), four))
}
def calc(e: Expr): Unit = {
val r: Rat = try { e.eval } catch { case e:ArithmeticException => 0 }
if (r.isInteger && 0 < r && r <= 10) {
e.printExpr
println(" = " + r)
}
}
def fourfours(): Unit = {
val ops = List("+", "-", "*", "/")
for (op1 <- ops; op2 <- ops; op3 <- ops) {
for (e <- makeExpr4(op1, op2, op3)) calc(e)
}
for (op1 <- ops; op2 <- ops) {
for (e <- makeExpr3(op1, op2)) calc(e)
}
for (op1 <- ops) {
for (e <- makeExpr2(op1)) calc(e)
}
}
演算子の組み合わせは関数 fourfours の for ループで生成しています。それを関数 makeExpr4, makeExpr3, makeExpr2 に渡します。たとえば、makeExpr4 は 5 通りの数式をリストに格納して返すので、それを for ループ で一つずつ取り出して関数 calc に渡して計算します。
式の計算で 0 除算の例外が送出されるので、それを try の catch で捕捉します。そして、計算結果が整数で、その値が 1 から 10 の範囲であれば、PrintExpr で式を表示します。
あとは特に難しいところはないでしょう。詳細はプログラムリスト２を参照してください。
さっそく実行してみたところ、全部で 100 通りの式が出力されました。このプログラムは重複解のチェックを行っていないので、多数の式が出力されることに注意してください。実行結果の一部を示します。
((4 - 4) + (4 / 4)) = 1 ((4 / 4) + (4 / 4)) = 2 (((4 + 4) + 4) / 4) = 3 (4 + (4 * (4 - 4))) = 4 (((4 * 4) + 4) / 4) = 5 (((4 + 4) / 4) + 4) = 6 (4 + (4 - (4 / 4))) = 7 ((4 + 4) + (4 - 4)) = 8 ((4 + 4) + (4 / 4)) = 9 ((44 - 4) / 4) = 10
この中で、10 になる式は (44 - 4) / 4 しかありません。数字 4 を 4 つと +, -, *, / () だけでは、10 になる式を作ることはできないことがわかります。
また、このプログラムはカッコをはずす処理を行っていないので、数式はちょっとわかりづらいですね。興味のある方は演算子の優先順位を考慮してカッコをはずすプログラムにも挑戦してみてください。
//
// rat.scala : Rational number
//
// Copyright (C) 2014-2024 Makoto Hiroi
//
package rational
import scala.language.implicitConversions
class Rat private (val n: BigInt, val d: BigInt) {
def +(that: Rat): Rat = Rat(n * that.d + that.n * d, d * that.d)
def +(x: BigInt): Rat = Rat(n + x * d, d)
def -(that: Rat): Rat = Rat(n * that.d - that.n * d, d * that.d)
def -(x: BigInt): Rat = Rat(n - x * d, d)
def *(that: Rat): Rat = Rat(n * that.n, d * that.d)
def *(x: BigInt): Rat = Rat(n * x, d)
def /(that: Rat): Rat = Rat(n * that.d, d * that.n)
def /(x: BigInt): Rat = Rat(n, d * x)
override def toString: String =
if (d == 1) n.toString else s"$n/$d"
override def equals(other: Any): Boolean =
other match {
case that: Rat => that.n == n && that.d == d
case _ => false
}
private def compare(that: Rat): Int = (this - that).n.signum
def < (that: Rat): Boolean = compare(that) < 0
def <=(that: Rat): Boolean = compare(that) <= 0
def > (that: Rat): Boolean = compare(that) > 0
def >=(that: Rat): Boolean = compare(that) >= 0
def abs: Rat = if (n >= 0) this else Rat(-n, d)
def inv: Rat = Rat(d, n)
def signum: Int = n.signum
def isInteger: Boolean = d == 1
def toInteger: BigInt = n / d
}
object Rat {
def apply(a: BigInt, b: BigInt): Rat = {
if (b == 0) throw new ArithmeticException
val g = a gcd b
val n = a * b.signum / g
val d = b * b.signum / g
new Rat(n, d)
}
implicit def intToRat(x: Int): Rat = Rat(x, 1)
implicit def longToRat(x: Long): Rat = Rat(x, 1)
implicit def bigIntToRat(x: BigInt): Rat = Rat(x, 1)
}
//
// fourfours.scala : Four fours
//
// Copyright (C) 2014-2024 Makoto Hiroi
//
import rational._
// 式 (抽象クラス)
abstract class Expr {
def eval: Rat // 式の評価
def printExpr(): Unit // 式の表示
}
// 節
case class Node(op: String, left: Expr, right: Expr) extends Expr {
def eval: Rat = op match {
case "+" => left.eval + right.eval
case "-" => left.eval - right.eval
case "*" => left.eval * right.eval
case "/" => left.eval / right.eval
}
def printExpr(): Unit = {
print("(")
left.printExpr()
print(" " + op + " ")
right.printExpr()
print(")")
}
}
// 葉
case class Leaf(n: Rat) extends Expr {
def eval: Rat = n
def printExpr(): Unit = print(n)
}
object FourFours {
// 数式の生成
def makeExpr4(op1: String, op2: String, op3: String): List[Expr] = {
val four = Leaf(4)
List(Node(op1, Node(op2, four, four), Node(op3, four, four)),
Node(op1, four, Node(op2, four, Node(op3, four, four))),
Node(op1, Node(op2, Node(op3, four, four), four), four),
Node(op1, four, Node(op2, Node(op3, four, four), four)),
Node(op1, Node(op2, four, Node(op3, four, four)), four))
}
def makeExpr3(op1: String, op2: String): List[Expr] = {
val a = Leaf(4)
val b = Leaf(44)
List(Node(op1, Node(op2, a, a), b),
Node(op1, a, Node(op2, a, b)),
Node(op1, Node(op2, a, b), a),
Node(op1, a, Node(op2, b, a)),
Node(op1, Node(op2, b, a), a),
Node(op1, b, Node(op2, a, a)))
}
def makeExpr2(op1: String): List[Expr] = {
val a = Leaf(4)
val b = Leaf(44)
val c = Leaf(444)
List(Node(op1, a, c), Node(op1, c, a), Node(op1, b, b))
}
// 式を計算する
def calc(e: Expr): Unit = {
val r: Rat = try { e.eval } catch { case e: ArithmeticException => 0 }
if (r.isInteger && 0 < r && r <= 10) {
e.printExpr()
println(" = " + r)
}
}
def fourfours(): Unit = {
val ops = List("+", "-", "*", "/")
for (op1 <- ops; op2 <- ops; op3 <- ops) {
for (e <- makeExpr4(op1, op2, op3)) calc(e)
}
for (op1 <- ops; op2 <- ops) {
for (e <- makeExpr3(op1, op2)) calc(e)
}
for (op1 <- ops) {
for (e <- makeExpr2(op1)) calc(e)
}
}
def main(args: Array[String]): Unit = {
fourfours()
}
}