序言

正月十五是一年一度的元宵節(jié)，是春節(jié)之后的第一個(gè)重要節(jié)日。在我們中國(guó)人眼里，過完正月十五元宵節(jié)，這年才算是真正地過完了。猜燈謎、賞花燈、舞龍獅、吃元宵、看晚會(huì)，老百姓把元宵節(jié)過得有滋有味，熱鬧非凡。還值得一提的是，古城西安今年在元宵節(jié)推出了“西安年·最中國(guó)”的壓軸大戲，即500架無人機(jī)燈光秀，點(diǎn)亮了元宵節(jié)的璀璨夜空。

除了過元宵節(jié)，在朋友圈也看到“猿霄節(jié)“的說法：

猿霄節(jié)，是程序猿通宵趕代碼的中國(guó)傳統(tǒng)節(jié)日，在此佳節(jié)來臨之際，恭祝全國(guó)程序猿節(jié)日快樂。

筆者感覺“猿霄節(jié)“非常好玩，就有了即興寫篇文章的想法，于是在過完元宵節(jié)后，找了一個(gè)題目：數(shù)三角形。這個(gè)題目是2015年參加一個(gè)軟件設(shè)計(jì)類培訓(xùn)的練習(xí)題之一，當(dāng)時(shí)是用Erlang語言實(shí)現(xiàn)的，今天打算用Golang實(shí)現(xiàn)一下，并將整個(gè)建模和實(shí)現(xiàn)過程通過文章記錄下來，以便作為“猿霄節(jié)“的一個(gè)禮物送給廣大讀者，尤其是Gophers。

題目

數(shù)數(shù)下圖中一共包含多少個(gè)三角形？

triangle.png

答案是24，你數(shù)對(duì)了嗎？

記得當(dāng)時(shí)參加培訓(xùn)的同學(xué)給出的答案有很多個(gè)，有少于24的，也有多于24的，每個(gè)人的數(shù)法不盡相同。但如果讓計(jì)算機(jī)來數(shù)的話，就必須將數(shù)三角形的方法描述成計(jì)算機(jī)可以執(zhí)行的形式化算法。這種描述方法可以有很多種，而我們希望找到一套抽象層次高且非常貼合領(lǐng)域的描述，以便降低后續(xù)的維護(hù)成本。

領(lǐng)域模型設(shè)計(jì)

我們考慮一下：什么是三角形？
如果沒有記錯(cuò)的話，我們?cè)谛W(xué)就學(xué)過：三角形就是三個(gè)點(diǎn)，兩兩相連，但是三個(gè)點(diǎn)不同時(shí)在一條直線上。
我們用形式化的方法表達(dá)一下：

is_triangle(x, y, z) ->
    connected(x, y) and 
    connected(y, z) and 
    connected(x, z) and
    not(in_same_line(a, b, c))

領(lǐng)域模型設(shè)計(jì)的核心是解決下面兩個(gè)問題：

• 三角形的三個(gè)點(diǎn)(x, y, z)都有哪些？
• 計(jì)算機(jī)怎么知道connected和in_same_line？

（x, y, z)的集合

從題目中，我們可以知道點(diǎn)的集合points，不妨用字符串來表示：

points = "abcdefghijk"

(x, y, z)的集合簡(jiǎn)單講就是從points的集合中取三個(gè)點(diǎn)的子集，每個(gè)子集是個(gè)字符串，所有子集就是一個(gè)字符串?dāng)?shù)組切片，可以簡(jiǎn)單用subset(points, 3)來描述。不過為了通用，我們直接用subset(points, n) : (string, int) -> []string來描述：

subset(points, n) when len(points) < n -> ［］

subset(points, n) when len(points) == n -> [points]

subset(points, n) when n == 1 -> [points[0], points[1], ..., points[len(points) - 1]]

subset(points, n) -> 
    firsts = subset(points[1:], n - 1) with points[0] +
    lasts = subset(points[1:], n)
    firsts append lasts

connected和in_same_line

從題目中，可以知道線的集合lines，不妨用字符串?dāng)?shù)組切片來表示：

lines = {"abh", "acgi", "adfj", "aek", "bcde", "hgfe", "hick"}

目標(biāo)是要知道點(diǎn)與點(diǎn)之間關(guān)系：2個(gè)點(diǎn)的關(guān)系connected，3個(gè)點(diǎn)的關(guān)系in_same_line，等價(jià)于2個(gè)點(diǎn)或3個(gè)點(diǎn)組成的集合points是否為lines中任一元素的子集，不妨用belong(points, lines) : (string, []string) -> bool來表示這種關(guān)系，而belong已經(jīng)是一個(gè)原子語義。

我們下面用belong描述一下connected(x, y) : (byte, byte) -> bool 和in_same_line(x, y, z) : (byte, byte, byte) -> bool:

connected(x, y) ->
    belong(xy, lines)

in_same_line(x, y, z) ->
    belong(xyz, lines)

領(lǐng)域模型實(shí)現(xiàn)

subset的實(shí)現(xiàn)：

func subset(points string, n int) []string {
    l := len(points)
    if l < n {
        return nil
    }
    if l == n {
        return []string{points}
    }

    results := make([]string, 0)
    if n == 1 {
        for i, _ := range points {
            bs := []byte{points[i]}
            results = append(results, string(bs))
        }
        return results
    }

    firsts := subset(points[1:], n - 1)
    for _, first := range firsts {
        results = append(results, string([]byte{points[0]}) + first)
    }

    lasts := subset(points[1:], n)
    results = append(results, lasts...)

    return results
}

belong的實(shí)現(xiàn)：

func belong(points string, lines []string) bool {
    flag := false
    for _, line := range lines {
        flag = true
        for _, r := range points {
            if !strings.ContainsRune(line, r) {
                flag = false
                break
            }
        }
        if flag {
            return true
        }
    }
    return false
}

not的實(shí)現(xiàn)：

func not(flag bool) bool {
    return !flag
}

CountingTriangles的實(shí)現(xiàn)中準(zhǔn)確的表達(dá)了領(lǐng)域模型is_triangle：

func CountingTriangles(points string, lines []string) []string {
    connected := func(x, y byte) bool {
        bs := make([]byte, 2)
        bs[0] = x
        bs[1] = y
        return belong(string(bs), lines)
    }

    in_same_line := func(x, y, z byte) bool {
        bs := make([]byte, 3)
        bs[0] = x
        bs[1] = y
        bs[2] = z
        return belong(string(bs), lines)
    }

    is_triangle := func(x, y, z byte) bool {
        if connected(x, y) &&
            connected(y, z) &&
            connected(x, z) &&
            not(in_same_line(x, y, z)) {
            return true
        }
        return false
    }

    num := 0
    matches := make([]string, 0)
    rs := subset(points, 3)
    for _, r := range rs {
        if len(r) != 3 {
            continue
        }
        if is_triangle(r[0], r[1], r[2]) {
            matches = append(matches, r)
            num++
        }
    }
    return matches
}

領(lǐng)域模型應(yīng)用

在應(yīng)用層表達(dá)題目：

package main

import (
    "fmt"
    "triangle/domain"
)

func main() {
    points := "abcdefghijk"
    lines := []string{"abh", "acgi", "adfj", "aek", "bcde", "hgfe", "hijk"}
    matches := domain.CountingTriangles(points, lines)
    fmt.Println("counting triangles result: ")
    fmt.Println("num of triangles: ", len(matches))
    fmt.Println("detail of triangles: ", matches)
}

運(yùn)行main函數(shù)：

counting triangles result: 
num of triangles:  24
detail of triangles:  [abc abd abe acd ace ade aef aeg aeh afg afh agh ahi ahj ahk aij aik ajk beh ceg def ehk fhj ghi]

小結(jié)

領(lǐng)域建模在于不斷的挖掘領(lǐng)域的本質(zhì)，然后用優(yōu)秀的代碼簡(jiǎn)潔地表達(dá)領(lǐng)域模型。我們通常習(xí)慣于將所有問題按OO范式的思維來建模，而FP范式非常適合將領(lǐng)域映射到數(shù)學(xué)本質(zhì)上。今后，我們?cè)诮鉀Q特定領(lǐng)域問題時(shí)要選擇最合適的編程范式，從而簡(jiǎn)單高效的解決問題。