一道erlang的建模练习

领域建模在于不断挖掘领域的本质,然后用优秀的代码简洁地表现出来。而函数式非常适合将领域映射到数学本质上。前一阵子学习erlang,用erlang做了一些练习,分享其中的一个。


题目: 数数如下图形中一共包含多少三角形?

答案是24,你数对了吗?回忆一下你刚才是怎么数的?

这道题如果由人来数,每个人数法各异!但是如果要交给计算机来做,就必须将数的方法描述成计算机可以执行的形式化算法。这种描述方法可以有非常多种,而我们希望找到一套抽象层次高的和领域非常贴切的描述,以降低后续理解、维护成本。

对于该问题,我们首先站在领域角度定义什么是三角形?

triangle([A, B, C]) ->
    connected(A, B) andalso
    connected(B, C) andalso
    connected(C, D) andalso
    (not in_same_line(A, B, C)).

如上,我们定义了一个三角形就是三个点,两两相连,但是三个点不同时在一条直线上。

对于如上描述,关键是如何定义connectedin_same_line
对于connected,就是两个点同时在一条直线连接上。那么什么是一条直线连接?
由于我们关注的是点在线上的关系,所以我们定义一条直线为在直线上所有点得集合。
例如对以上例,我们存在直线:[a, b, h],[a, c, g, i]等等。

我们把上图中所有直线用erlang描述出来:

lines() ->
    ["abh", "acgi", "adfj", "aek", "bcde", "hgfe", "hijk"].

由于我们用单字符表示点,而字符串在erlang中实际就是list,所以我们将一条直线简写为在线上所有点的字符的字符串。

有了对直线的定义,接下来,一个点是否在直线上,那就是元素与集合的属于关系;而两个点是否相连就是集合与集合之间的包含关系。

subset([], _S) -> true;
subset([H|T], S) -> 
    lists:member(H, S) andalso subset(T, S).

belong(_, []) -> false;
belong(S, [H|T]) -> subset(S, H) orelse belong(S, T).

connected(P1, P2) -> belong([P1, P2], lines()).

in_same_line(P1, P2, P3) -> belong([P1, P2, P3], lines()).

可以看到,connected的定义是两个点组成的集合属于所有直线的集合的任一个的子集。而in_same_line则是三个点的集合属于所有直线的集合的任一个的子集。
我们在这里将该问题映射到熟悉的集合领域。

在有了对connectedin_same_line的定以后,我们就可以对triangle进行测试了!

test() ->
    true = triangle("abc"),
    false = triangle("abh").

下来我们来进行数三角形。要能够数三角形,我们需要找到所有三个点的组合,用来验证是否满足triangle?将满足triangle的进行统计,这样我们就得到了结果!

在这里我们已经有了所有点的集合:

Points = "abcdefghijk"

为了得到所有3个点的组合,我们实现一个算法,对于集合L,求其N个元素的所有组合的集合。

comb(L, 1) -> [[I] || I <- L];
comb(L, N) when length(L) =:= N -> [L];
comb([H|T], N) -> 
    [[H|R] || R <- comb(T, N - 1)] ++ comb(T, N).
Points = "abcdefghijk",
TriplePoints = comb(Points, 3),

下面我们实现一个count方法,用来数满足要求的三角形个数:

count(Triple) -> count(Triple, 0).

count([], N) -> N;
count([H|T], N) ->
    case triangle(H) of
        true -> count(T, N + 1);
        false -> count(T, N)
    end.

最后可以调用run测试一下是不是24!

run() ->
    Points = "abcdefghijk",
    TriplePoints = comb(Points, 3),
    count(TriplePoints).
最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
  • 序言:七十年代末,一起剥皮案震惊了整个滨河市,随后出现的几起案子,更是在滨河造成了极大的恐慌,老刑警刘岩,带你破解...
    沈念sama阅读 213,047评论 6 492
  • 序言:滨河连续发生了三起死亡事件,死亡现场离奇诡异,居然都是意外死亡,警方通过查阅死者的电脑和手机,发现死者居然都...
    沈念sama阅读 90,807评论 3 386
  • 文/潘晓璐 我一进店门,熙熙楼的掌柜王于贵愁眉苦脸地迎上来,“玉大人,你说我怎么就摊上这事。” “怎么了?”我有些...
    开封第一讲书人阅读 158,501评论 0 348
  • 文/不坏的土叔 我叫张陵,是天一观的道长。 经常有香客问我,道长,这世上最难降的妖魔是什么? 我笑而不...
    开封第一讲书人阅读 56,839评论 1 285
  • 正文 为了忘掉前任,我火速办了婚礼,结果婚礼上,老公的妹妹穿的比我还像新娘。我一直安慰自己,他们只是感情好,可当我...
    茶点故事阅读 65,951评论 6 386
  • 文/花漫 我一把揭开白布。 她就那样静静地躺着,像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上,一...
    开封第一讲书人阅读 50,117评论 1 291
  • 那天,我揣着相机与录音,去河边找鬼。 笑死,一个胖子当着我的面吹牛,可吹牛的内容都是我干的。 我是一名探鬼主播,决...
    沈念sama阅读 39,188评论 3 412
  • 文/苍兰香墨 我猛地睁开眼,长吁一口气:“原来是场噩梦啊……” “哼!你这毒妇竟也来了?” 一声冷哼从身侧响起,我...
    开封第一讲书人阅读 37,929评论 0 268
  • 序言:老挝万荣一对情侣失踪,失踪者是张志新(化名)和其女友刘颖,没想到半个月后,有当地人在树林里发现了一具尸体,经...
    沈念sama阅读 44,372评论 1 303
  • 正文 独居荒郊野岭守林人离奇死亡,尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 36,679评论 2 327
  • 正文 我和宋清朗相恋三年,在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 38,837评论 1 341
  • 序言:一个原本活蹦乱跳的男人离奇死亡,死状恐怖,灵堂内的尸体忽然破棺而出,到底是诈尸还是另有隐情,我是刑警宁泽,带...
    沈念sama阅读 34,536评论 4 335
  • 正文 年R本政府宣布,位于F岛的核电站,受9级特大地震影响,放射性物质发生泄漏。R本人自食恶果不足惜,却给世界环境...
    茶点故事阅读 40,168评论 3 317
  • 文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹,春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 30,886评论 0 21
  • 文/苍兰香墨 我抬头看了看天上的太阳。三九已至,却和暖如春,着一层夹袄步出监牢的瞬间,已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 32,129评论 1 267
  • 我被黑心中介骗来泰国打工, 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留,地道东北人。 一个月前我还...
    沈念sama阅读 46,665评论 2 362
  • 正文 我出身青楼,却偏偏与公主长得像,于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子,可洞房花烛夜当晚...
    茶点故事阅读 43,739评论 2 351

推荐阅读更多精彩内容