【Kotlin】三角形の数を数える

![Fig.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/61280/e255f931-a41f-1081-0cd7-8e43517b6150.png)
この図の中に三角形はいくつあるだろうか。（答えは[こちら](#結果)。）
これを数えるプログラムを作成する。

## 基本方針

まず「最長線分」という造語を定義する。
これは、「1つの直線上にある線分の中で最も長い、他の線分の部分線分とならない線分」という意味で使う。
（他に適当な言葉があればご教授いただけると幸いです。）
この図の場合であれば、次の7つが「最長線分」となる。

- 上の水平線
- 下の水平線
- 左の垂直線
- 中央の垂直線
- 右の垂直線
- 左上から中央下に引かれた斜め線
- 右上から左下に引かれた斜め線

プログラムでは、このような「最長線分」だけを指定すれば三角形の数が求められるようにする。

## 組み合わせと直積

このプログラムでは別の記事で書いた次の API を使用する。

- 記事「[Kotlin: 順列 / 組み合わせ / 重複順列 / 重複組み合わせ を まとめて関数にしてみた。（Sequence版）](https://qiita.com/sdkei/items/1fecaebeeff3e39f8299)」より
    - `List<T>.combination` 関数
- 記事「[Kotlin: 配列の直積を返すSequenceを作ってみた](https://qiita.com/sdkei/items/2aaf9e40b579c0814076)」より
    - `List<List<T>>.product` 関数

## `Double` 値の比較

`Double` 値には誤差が含まれるため、単純に `==` で等価性を判定してはならない。
そこで同じ値を見なして良いかどうかを判定する関数と、
2つの値の間にあるかどうかを判定する関数を作成した。
（このようなことをするのが初めてなので、これで適切なのかどうかよく分からない…。
　有識者がいらっしゃれば、是非ご指摘いただきたい。）

```Kotlin
import kotlin.math.abs
import kotlin.math.ulp

/** 同じ値と見なして良いかどうかを返す。 */
infix fun Double.nearlyEquals(other: Double): Boolean =
    maxOf(this.ulp, other.ulp) * 2 >= abs(this - other)

/**
 * この値が指定された2つの値の値の間にあるかどうかを返す。
 *
 * この値が2つの値のいずれかと同じ値と見なして良い場合は
 * 2つの値の間にあると見なす。
 */
private fun Double.isIn(from: Double, to: Double): Boolean {
    listOf(from, to).sorted().also { (min, max) ->
        if (this in min..max) {
            return true
        }
    }

    if (this nearlyEquals from) return true
    if (this nearlyEquals to) return true

    return false
}
```

## 2次元平面上の点

2次元平面上の点を表すクラスを作成した。

`equals` 関数では、先ほどの `Double` 値を比較する関数を使用して、
同一の点と見なして良いかどうかを判定している。
また、ソートできるように `Comparable` インターフェイスを実装した。

```Kotlin
/** 2次元平面上の点。 */
data class Point(
    val x: Double,
    val y: Double
) : Comparable<Point> {
    override fun compareTo(other: Point): Int =
        comparator.compare(this, other)

    /** X座標・Y座標それぞれがともに同じ値と見なして良ければ等価とする。 */
    override fun equals(other: Any?): Boolean {
        if (other !is Point) return false

        return this.x nearlyEquals other.x
                && this.y nearlyEquals other.y
    }

    // equals 関数が true を返すような2つのオブジェクトに対して同じ値を返す必要があるため、
    // 常に 0 を返す。
    override fun hashCode(): Int = 0

    override fun toString(): String = "($x, $y)"

    companion object {
        val comparator: Comparator<Point> = Comparator { a, b ->
            if (a == b) 0
            else comparatorInternal.compare(a, b)
        }

        private val comparatorInternal = compareBy<Point> { it.x }.thenBy { it.y }
    }
}
```

## 直線

直線を表すクラスを作成した。

鉛直線は傾きとy切片では表せないため、
鉛直線とそうでない直線とでサブクラスを分けた。

点が直線上にあるかどうかを判定する関数と、
2つの直線の交点を求める関数も作成した。

また、指定した2つの点を通る直線を生成するフェイクコンストラクターも作成した。

```Kotlin
/** 直線。 */
sealed class Line {
    /** 指定された点がこの直線上にあるかどうかを返す。 */
    abstract operator fun contains(point: Point): Boolean

    /** 鉛直線でない直線。 */
    data class Regular(
        /** 傾き。 */
        val slope: Double,
        /** y切片。 */
        val yIntercept: Double
    ) : Line() {
        override fun contains(point: Point): Boolean =
            point.y nearlyEquals (slope * point.x + yIntercept)

        override fun equals(other: Any?): Boolean {
            if (other !is Regular) return false

            if ((this.slope nearlyEquals other.slope).not()) return false
            if ((this.yIntercept nearlyEquals other.yIntercept).not()) return false
            return true
        }

        // equals 関数が true を返すような2つのオブジェクトに対して同じ値を返す必要があるため、
        // 常に 0 を返す。
        override fun hashCode(): Int = 0
    }

    /** 鉛直線。 */
    data class Vertical(
        /** x切片。 */
        val xIntercept: Double
    ) : Line() {
        override fun contains(point: Point): Boolean =
            point.x nearlyEquals xIntercept

        override fun equals(other: Any?): Boolean {
            if (other !is Vertical) return false

            if ((this.xIntercept nearlyEquals other.xIntercept).not()) return false
            return true
        }

        // equals 関数が true を返すような2つのオブジェクトに対して同じ値を返す必要があるため、
        // 常に 0 を返す。
        override fun hashCode(): Int = 0
    }

    companion object {
        /**
         * 2つの直線の交点を返す。
         *
         * 交差しない（平行である）場合のみ null を返す。
         */
        fun intersectionPoint(a: Line, b: Line): Point? =
            when (a) {
                is Regular -> when (b) {
                    is Regular -> intersectionPoint(a, b)
                    is Vertical -> intersectionPoint(a, b)
                }
                is Vertical -> when (b) {
                    is Regular -> intersectionPoint(b, a)
                    is Vertical -> null // 平行
                }
            }

        /** 2つの直線の交点を返す。 */
        private fun intersectionPoint(a: Regular, b: Regular): Point? {
            if (a.slope nearlyEquals b.slope) {
                return null // 平行
            }

            val x = -(b.yIntercept - a.yIntercept) / (b.slope - a.slope)
            val y = a.slope * x + a.yIntercept
            return Point(x, y)
        }

        /** 2つの直線の交点を返す。 */
        private fun intersectionPoint(regular: Regular, vertical: Vertical): Point? {
            val x = vertical.xIntercept
            val y = regular.slope * x + regular.yIntercept
            return Point(x, y)
        }
    }
}

/** 指定された2つの点を通る直線を返す。 */
@Suppress("FunctionName")
fun Line(from: Point, to: Point): Line {
    require((from == to).not()) {
        "同一と見なされる2点を引数に指定することは出来ません。from: $from, to: $to"
    }

    return if (from.x nearlyEquals to.x) {
        Line.Vertical(from.x)
    } else {
        val slope = (to.y - from.y) / (to.x - from.x)
        val yIntercept = from.y - slope * from.x
        Line.Regular(slope, yIntercept)
    }
}
```

## 線分

線分を表すクラスを作成した。

自身と重なる直線をプロパティとして持ち、
指定された点が自身の上にあるかどうかを返す関数を持つ。

```Kotlin
/** 線分。 */
open class LineSegment(
    val from: Point,
    val to: Point
) {
    /** この線分と重なる直線。 */
    val line: Line = Line(from, to)

    /** 指定された点がこの線分上にあると見なされるかどうかを返す。 */
    operator fun contains(point: Point): Boolean {
        if (point !in line) return false
        if (point.x.isIn(from.x, to.x).not()) return false
        if (point.y.isIn(from.y, to.y).not()) return false
        return true
    }

    override fun toString(): String =
        "[$from, $to]"
}
```

## 「最長線分」

「最長線分」を表すクラスを作成した。

他の「最長線分」との交点を求めてそれを保持し、
自身の上にあるすべての線分を返すことが出来る。

```Kotlin
/** 「最長線分」（1つの直線上にある線分の中で最も長い、他の線分の部分線分とならない線分）。 */
class SuperLineSegment(
    from: Point, to: Point
) : LineSegment(from, to) {
    /**
     * この線分上にある交点。
     *
     * この線分の始点・終点も含まれる。
     */
    val intersectionPoints: List<Point>
        get() = intersectionPointsInternal
    private val intersectionPointsInternal: MutableList<Point> =
        mutableListOf(from, to).apply {
            sort()
        }

    /**
     * この線分上にあるすべての交点の組み合わせからなるすべての線分の Sequence を返す。
     *
     * この線分と始点・終点が一致する線分も含まれる。
     */
    fun subLineSegments(): Sequence<LineSegment> =
        intersectionPoints.combination(2, Repetition.WITHOUT_REPETITION)
            .map { (oneEnd, otherEnd) ->
                LineSegment(oneEnd, otherEnd)
            }

    /** 交点を追加する。 */
    private fun addIntersectionPoint(point: Point) {
        if (intersectionPointsInternal.any { it == point }) {
            return
        }

        intersectionPointsInternal.apply {
            add(point)
            sort()
        }
    }

    override fun toString(): String =
        "SuperLineSegment(from:$from, to:$to, intersectionPoints:$intersectionPoints)"

    companion object {
        /** 2つの線分の交点を両者に追加する。 */
        fun addIntersectionPoint(a: SuperLineSegment, b: SuperLineSegment) {
            intersectionPoint(a, b)?.also {
                a.addIntersectionPoint(it)
                b.addIntersectionPoint(it)
            }
        }

        /**
         * 2つの線分の交点を返す。
         *
         * 交点がなければ null を返す。
         */
        private fun intersectionPoint(a: SuperLineSegment, b: SuperLineSegment): Point? =
            Line.intersectionPoint(a.line, b.line)?.takeIf {
                it in a && it in b
            }
    }
}
```

## 3つの線分が三角形になっているかどうか

3つの線分が閉じた三角形を構築しているかどうかを返す関数を作成した。

```Kotlin
/** リストに含まれる線分が閉じた三角形になっているかどうかを返す。  */
fun List<LineSegment>.isTriangle(): Boolean {
    if (size != 3) return false

    return first().let { first ->
        drop(1).takeEndPointIfSinglePath(first.to)
            ?.let { it == first.from }
            ?: false
    }
}

/**
 * リストに含まれる線分が一連のパスを構築するのであれば
 * その終端の点を返し、そうでなければ null を返す。
 *
 * リストが空の場合は [startPoint] を返すことに注意。
 *
 * @param startPoint 一連のパスの始点。
 */
private fun List<LineSegment>.takeEndPointIfSinglePath(startPoint: Point): Point? {
    // 空の場合は startPoint を返す。
    if (isEmpty()) {
        return startPoint
    }

    forEachIndexed { index, lineSegment ->
        when {
            lineSegment.from == startPoint -> {
                return (take(index) + drop(index + 1))
                    .takeEndPointIfSinglePath(lineSegment.to)
            }
            lineSegment.to == startPoint -> {
                return (take(index) + drop(index + 1))
                    .takeEndPointIfSinglePath(lineSegment.from)
            }
        }
    }

    return null
}
```

## 三角形の数を数える

最後に、三角形の数を数える関数を作成した。

```Kotlin
/** リストに含まれる線分が構築する図に含まれる三角形の数を返す。 */
fun List<LineSegment>.countTriangles(): Int {
    // 同一直線上の線分がないことを確認する。
    combination(2, Repetition.WITHOUT_REPETITION)
        .forEach { (a, b) ->
            require(a.line != b.line) { "同一直線上の線分があります。a: $a, b: $b" }
        }

    val superLineSegments = map { SuperLineSegment(it.from, it.to) }

    // すべての交点を求める。
    superLineSegments
        .combination(2, Repetition.WITHOUT_REPETITION)
        // ↑「最長線分」2つを選ぶすべての組み合わせの Sequence 。
        .forEach { (a: SuperLineSegment, b: SuperLineSegment) ->
            SuperLineSegment.addIntersectionPoint(a, b)
        }

    return superLineSegments
        .combination(3, Repetition.WITHOUT_REPETITION)
        // ↑「最長線分」3つを選ぶすべての組み合わせの Sequence 。
        .flatMap { threeSuperLineSegments: List<SuperLineSegment> ->
            threeSuperLineSegments
                .map { it.subLineSegments().toList() } // : List<List<LineSegment>>
                .product() // : Sequence<List<LineSegment>>
        } // : Sequence<List<LineSegment>>
        // ↑すべての線分の中から3つを選ぶ組み合わせの Sequence。（ただし同じ直線上のものは組み合わせに入っていない。）
        .count { threeSubLineSegments: List<LineSegment> ->
            threeSubLineSegments
                .isTriangle()
        }
}
```

## 冒頭の図に含まれる三角形の数

では、これで冒頭の図に含まれる三角形の数を数えてみよう。

図の左上隅を原点とし、
2つの正方形の1辺の長さをを1.0とする。

```Kotlin
fun main() {
    // 「最長線分」の始点・終点をすべて定義する。
    val pointLeftTop = Point(0.0, 0.0) // 左上
    val pointCenterTop = Point(1.0, 0.0) // 中央上
    val pointRightTop = Point(2.0, 0.0) // 右上
    val pointLeftBottom = Point(0.0, 1.0) // 左下
    val pointCenterBottom = Point(1.0, 1.0) // 中央下
    val pointRightBottom = Point(2.0, 1.0) // 右下

    // 「最長線分」をすべて定義する。
    val lineSegments = listOf(
        LineSegment(pointLeftTop, pointRightTop), // 左上から右上（水平）
        LineSegment(pointLeftBottom, pointRightBottom), // 左下から右下（水平）
        LineSegment(pointLeftTop, pointLeftBottom), // 左上から左下（垂直）
        LineSegment(pointCenterTop, pointCenterBottom), // 中央上から中央下（垂直）
        LineSegment(pointRightTop, pointRightBottom), // 右上から右下（垂直）
        LineSegment(pointLeftTop, pointCenterBottom), // 左上から中央下（斜め）
        LineSegment(pointRightTop, pointLeftBottom), // 右上から左下（斜め）
    )

    // 三角形の数を出力する。
    lineSegments.countTriangles()
        .also { println(it) }
}
```

### 結果

```
10
```

## Kotlin Playground

Kotlin Playground で試せるようにした。
→https://pl.kotl.in/gxYgYL2FK

他の図形でも試してみていただきたい。

## 所感

- 「1時間くらいで解けるだろう」と思って始めたのだが、  
  4時間くらい掛かってしまった。  
  Kotlin でなければめんどくさくて途中で投げ出してただろう。  
- ほぼバグなしで実装できたのは幸い。  
  デバッグするのは難しそう。
- 四角形やそれ以上の多角形に拡張することも可能だが、  
  線分が交差する場合を考慮する必要が出てくるのでちょっと面倒。  
  （なので今回はそこまではやらなかった。）
- 久しぶりに方程式を解いた。

／以上