Counting Triangles in Golang

序言

正月十五是一年一度的元宵節(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ù)下圖中一共包含多少個三角形齿梁?

triangle.png

答案是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)都有哪些陪毡?
  • 計算機怎么知道connectedin_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) -> boolin_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)域問題時要選擇最合適的編程范式,從而簡單高效的解決問題兴革。

最后編輯于
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者
  • 序言:七十年代末绎晃,一起剝皮案震驚了整個濱河市,隨后出現(xiàn)的幾起案子杂曲,更是在濱河造成了極大的恐慌庶艾,老刑警劉巖,帶你破解...
    沈念sama閱讀 211,348評論 6 491
  • 序言:濱河連續(xù)發(fā)生了三起死亡事件擎勘,死亡現(xiàn)場離奇詭異咱揍,居然都是意外死亡,警方通過查閱死者的電腦和手機棚饵,發(fā)現(xiàn)死者居然都...
    沈念sama閱讀 90,122評論 2 385
  • 文/潘曉璐 我一進(jìn)店門述召,熙熙樓的掌柜王于貴愁眉苦臉地迎上來,“玉大人蟹地,你說我怎么就攤上這事√傥” “怎么了怪与?”我有些...
    開封第一講書人閱讀 156,936評論 0 347
  • 文/不壞的土叔 我叫張陵,是天一觀的道長缅疟。 經(jīng)常有香客問我分别,道長,這世上最難降的妖魔是什么存淫? 我笑而不...
    開封第一講書人閱讀 56,427評論 1 283
  • 正文 為了忘掉前任耘斩,我火速辦了婚禮,結(jié)果婚禮上桅咆,老公的妹妹穿的比我還像新娘括授。我一直安慰自己,他們只是感情好岩饼,可當(dāng)我...
    茶點故事閱讀 65,467評論 6 385
  • 文/花漫 我一把揭開白布荚虚。 她就那樣靜靜地躺著,像睡著了一般籍茧。 火紅的嫁衣襯著肌膚如雪版述。 梳的紋絲不亂的頭發(fā)上,一...
    開封第一講書人閱讀 49,785評論 1 290
  • 那天寞冯,我揣著相機與錄音渴析,去河邊找鬼晚伙。 笑死,一個胖子當(dāng)著我的面吹牛俭茧,可吹牛的內(nèi)容都是我干的咆疗。 我是一名探鬼主播,決...
    沈念sama閱讀 38,931評論 3 406
  • 文/蒼蘭香墨 我猛地睜開眼恢恼,長吁一口氣:“原來是場噩夢啊……” “哼民傻!你這毒婦竟也來了?” 一聲冷哼從身側(cè)響起场斑,我...
    開封第一講書人閱讀 37,696評論 0 266
  • 序言:老撾萬榮一對情侶失蹤漓踢,失蹤者是張志新(化名)和其女友劉穎,沒想到半個月后漏隐,有當(dāng)?shù)厝嗽跇淞掷锇l(fā)現(xiàn)了一具尸體喧半,經(jīng)...
    沈念sama閱讀 44,141評論 1 303
  • 正文 獨居荒郊野嶺守林人離奇死亡,尸身上長有42處帶血的膿包…… 初始之章·張勛 以下內(nèi)容為張勛視角 年9月15日...
    茶點故事閱讀 36,483評論 2 327
  • 正文 我和宋清朗相戀三年青责,在試婚紗的時候發(fā)現(xiàn)自己被綠了挺据。 大學(xué)時的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片。...
    茶點故事閱讀 38,625評論 1 340
  • 序言:一個原本活蹦亂跳的男人離奇死亡脖隶,死狀恐怖扁耐,靈堂內(nèi)的尸體忽然破棺而出,到底是詐尸還是另有隱情产阱,我是刑警寧澤婉称,帶...
    沈念sama閱讀 34,291評論 4 329
  • 正文 年R本政府宣布,位于F島的核電站构蹬,受9級特大地震影響王暗,放射性物質(zhì)發(fā)生泄漏。R本人自食惡果不足惜庄敛,卻給世界環(huán)境...
    茶點故事閱讀 39,892評論 3 312
  • 文/蒙蒙 一俗壹、第九天 我趴在偏房一處隱蔽的房頂上張望。 院中可真熱鬧藻烤,春花似錦绷雏、人聲如沸。這莊子的主人今日做“春日...
    開封第一講書人閱讀 30,741評論 0 21
  • 文/蒼蘭香墨 我抬頭看了看天上的太陽。三九已至依许,卻和暖如春棺禾,著一層夾襖步出監(jiān)牢的瞬間,已是汗流浹背峭跳。 一陣腳步聲響...
    開封第一講書人閱讀 31,977評論 1 265
  • 我被黑心中介騙來泰國打工膘婶, 沒想到剛下飛機就差點兒被人妖公主榨干…… 1. 我叫王不留缺前,地道東北人。 一個月前我還...
    沈念sama閱讀 46,324評論 2 360
  • 正文 我出身青樓悬襟,卻偏偏與公主長得像衅码,于是被迫代替她去往敵國和親。 傳聞我的和親對象是個殘疾皇子脊岳,可洞房花燭夜當(dāng)晚...
    茶點故事閱讀 43,492評論 2 348

推薦閱讀更多精彩內(nèi)容