序言
正月十五是一年一度的元宵節(jié)斑唬,是春節(jié)之后的第一個重要節(jié)日。在我們中國人眼里黎泣,過完正月十五元宵節(jié)恕刘,這年才算是真正地過完了。猜燈謎抒倚、賞花燈褐着、舞龍獅、吃元宵托呕、看晚會含蓉,老百姓把元宵節(jié)過得有滋有味,熱鬧非凡项郊。還值得一提的是馅扣,古城西安今年在元宵節(jié)推出了“西安年·最中國”的壓軸大戲,即500架無人機燈光秀着降,點亮了元宵節(jié)的璀璨夜空差油。
除了過元宵節(jié),在朋友圈也看到“猿霄節(jié)“的說法:
猿霄節(jié)任洞,是程序猿通宵趕代碼的中國傳統(tǒng)節(jié)日蓄喇,在此佳節(jié)來臨之際,恭祝全國程序猿節(jié)日快樂交掏。
筆者感覺“猿霄節(jié)“非常好玩妆偏,就有了即興寫篇文章的想法,于是在過完元宵節(jié)后耀销,找了一個題目:數(shù)三角形楼眷。這個題目是2015年參加一個軟件設(shè)計類培訓(xùn)的練習(xí)題之一铲汪,當(dāng)時是用Erlang語言實現(xiàn)的,今天打算用Golang實現(xiàn)一下罐柳,并將整個建模和實現(xiàn)過程通過文章記錄下來掌腰,以便作為“猿霄節(jié)“的一個禮物送給廣大讀者,尤其是Gophers张吉。
題目
數(shù)數(shù)下圖中一共包含多少個三角形齿梁?
答案是24,你數(shù)對了嗎肮蛹?
記得當(dāng)時參加培訓(xùn)的同學(xué)給出的答案有很多個勺择,有少于24的,也有多于24的伦忠,每個人的數(shù)法不盡相同省核。但如果讓計算機來數(shù)的話,就必須將數(shù)三角形的方法描述成計算機可以執(zhí)行的形式化算法昆码。這種描述方法可以有很多種气忠,而我們希望找到一套抽象層次高且非常貼合領(lǐng)域的描述,以便降低后續(xù)的維護(hù)成本赋咽。
領(lǐng)域模型設(shè)計
我們考慮一下:什么是三角形旧噪?
如果沒有記錯的話,我們在小學(xué)就學(xué)過:三角形就是三個點脓匿,兩兩相連淘钟,但是三個點不同時在一條直線上。
我們用形式化的方法表達(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è)計的核心是解決下面兩個問題:
- 三角形的三個點
(x, y, z)
都有哪些陪毡? - 計算機怎么知道
connected
和in_same_line
米母?
(x, y, z)的集合
從題目中,我們可以知道點的集合points
缤骨,不妨用字符串來表示:
points = "abcdefghijk"
(x, y, z)
的集合簡單講就是從points
的集合中取三個點的子集爱咬,每個子集是個字符串,所有子集就是一個字符串?dāng)?shù)組切片绊起,可以簡單用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)是要知道點與點之間關(guān)系:2個點的關(guān)系connected
,3個點的關(guān)系in_same_line
笋鄙,等價于2個點或3個點組成的集合points
是否為lines
中任一元素的子集师枣,不妨用belong(points, lines) : (string, []string) -> bool
來表示這種關(guān)系,而belong
已經(jīng)是一個原子語義萧落。
我們下面用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)域模型實現(xiàn)
subset
的實現(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
的實現(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
的實現(xiàn):
func not(flag bool) bool {
return !flag
}
CountingTriangles
的實現(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)
}
運行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)秀的代碼簡潔地表達(dá)領(lǐng)域模型洗贰。我們通常習(xí)慣于將所有問題按OO
范式的思維來建模,而FP
范式非常適合將領(lǐng)域映射到數(shù)學(xué)本質(zhì)上陨倡。今后敛滋,我們在解決特定領(lǐng)域問題時要選擇最合適的編程范式,從而簡單高效的解決問題兴革。