一道Google的算法题 |Python巧妙破解
这是菜鸟学python的第54篇原创文章
阅读本文大概需要半个小时
开头先讲一下自己的亲身经历，05年的时候，也就是12年前，我去T公司面试，当时T公司在这个城市非常有名,有很多高手(号称小微软).我当时也是抱着初生牛犊不怕虎，想去会一会.在通过第一轮的笔试(当时考算法,程序,还有IQ)和初级面试后，进入第二轮,来了一个台湾技术经理，问了一些问题之后出了一道题,要求3分钟给出答案，这道题就是今天下面要讲的~~这3分钟我当时是又惊又囧，10多年过去了我现在依然记忆犹新(也许我以后会写一篇"10年了外企面试的那些往事")
今天先说正题，没有想到十多年后，我无意中浏览硅谷的一些网站时候，竟然又碰到了这道题，太有缘了.这次是一个Google大牛分析这道题，而且是用Python解的(Python在Google里号称是最喜欢的语言之一),我觉得太过瘾了,力道雄厚而刚劲，招式非常巧妙,我加上自己的理解一起分享给大家.
题目#翻译成中文:
一个和尚去河边挑水，带了两个桶，一个是能装4斤水，一个能装9斤水
1),要求写出算法，目标是如何装出6斤水
2),假设两个桶容量任意，比如X斤和Y斤,目标是Z斤;要求写出算法
一.就像我们解数学题一样,我们先化繁为简,先从最简单的入手
AB两个桶:一个能装3斤水，一个能装5斤水=>目标4斤
上面只是一个很简单的实例，我相信一个4斤水，一个9斤，大家也能类似的推导出6斤水，只是步骤多一点而已，不是很难.
那么如果用计算机算法来解决任意X,Y的问题的,这个就很有意思了.我们接着分析~~
二.好有了这个感性的认识之后，我们开始抽象化，建模成算法.
我们发现穷举所有的组合,无非就这下面6种操作:
1.B->A
2.A->B
3.Fill A
4.Fill B
5.Empty A
6.Empty B
假设A桶容量是X,B桶容量是Y，A桶里面倒入的水是x,B桶倒入的是y
数据结构,很容易就想到我们应该用字典:我们用元组来表示两个桶的水,用字符串表示操作步骤
我们先从易到难开始说:
1.Empty B
(x,0)=>'Empty Y' #把B桶的水倒空
2.Empty A
(0,y)=>'Empty X' #把A桶的水倒空
3.Fill A
(X,y)=>'Fill X' #把A桶的水加满
4.Fill B
(x,Y)=>'Fill Y' #把B桶的水加满
5.A倒水到B
这个时候分两种情况
1).若A里的水倒入B，若把B倒满了，这个时候B就的值Y,A倒了Y-y的水进入，那么A剩下的就是X-(Y-y)
if x+y>=Y:
(X-(Y-y),Y):"X->Y"
2).若A里的水倒入B，若没有把B倒满了，这个时候B的值x+y,A为了0(A的水已经全部倒进B了，还是没有倒满)
if x+y<Y:
(0,x+y):"X->Y"
6.B倒水到A
这个时候分两种情况
1).若B里的水倒入A，若把A倒满了，这个时候A就的值X,B倒了X-x的水进入，那么B剩下的就是Y-(X-x)
if x+y>=X:
(X,Y-(X-x))
2).若B里的水倒入A，若没有把A倒满了，这个时候A的值x+y,B为了0(B的水已经全部倒进A了，还是没有倒满)
if x+y<X:
(x+y,0):
三.好了上面的铺垫之后，我们来进入主旋律
我们定义一个函数叫def solutions(x,y,X,Y),里面会return (state,action)
就是我们定义的6种情况的数据格式.所以的操作都在这个6种状态机里面转
思路:
其实就是6步就是6个状态机，也就是我们整个的操作始终都在这6个状态机里面操作转圈，我们需要做的就是遍历每一种状态机的下一个状态,除了自己之外一共有5种,看下面的图:
start是起始状态,假设起始的时候两桶水都是空的,然后start可以操作如下操作:
Fill X(把A桶打满)
Fill Y(把B桶打满)
Empty X(把A桶的水倒掉)
Empty Y(把A桶的水倒掉)
然后到了Fill X 这个状态机之后，又可以有其他5种状态，接着转起来，就这样不断的探索下去,我们举个最简单的例子,一桶容量是3斤的水和一桶容量是5斤的水，倒出4斤，看一下状态机的图:
经过6步，到了第7步的时候，就找到了4斤的水了.
那么代码的设计是如何呢:
1).存放所有的有效的探索步骤我们用一个set()来存，大家有没有注意到每一步里面发散下去，会有重复的状态~~
比如第二次的(0,5),和第三次的(0,5)是一样的，所以我们用set很巧妙的过滤掉重复的状态，这样大大优化了我们的代码和搜索的速度.
见如下的图:红色的实心圈是set()要存的，空心的是重复的状态:
set()里面其实就是存的最后我们搜索到的两个桶的状态:
set([(3, 2), (0, 0), (3, 0), (2, 0), (0, 5), (2, 5), (3, 4), (0, 2), (3, 5)])
若4在里面就说明找到了.
2).外面有一个while循环，去遍历所有的状态
3).我们一开始有一个start状态比如(0,0)进入solutions函数，它会返回6种状态机，是用字典表示的
4).我们去判断每一种状态,(state,action),比如(3,4,"Y->X"),如果4出现在state里面，就算找到了break出去
5).若没有找到，我们继续循环搜索,大家一定想问while的入口是什么,也是一个列表:
比如(0,0)状态下可能要操作的所有步骤Path:
[[(0, 0), 'fill X', (3, 0)], [(0, 0), 'empty y', (0, 0)], [(0, 0), 'fill Y', (0, 5), 'Y->X', (3, 2), 'empty x', (0, 2), 'Y->X', (2, 0), 'fill Y', (2, 5)]]
6).每次从这个列表中取一个继续下次的搜索，直到找到目标为止.
看一下结果：一桶4斤，一桶9斤，如何倒出6斤水
[(0, 0), 'fill X', (4, 0), 'X->Y', (0, 4), 'fill X', (4, 4), 'X->Y', (0, 8), 'fill X', (4, 8), 'X->Y', (3, 9), 'empty y', (3, 0), 'X->Y', (0, 3), 'fill X', (4, 3), 'X->Y', (0, 7), 'fill X', (4, 7), 'X->Y', (2, 9), 'empty y', (2, 0), 'X->Y', (0, 2), 'fill X', (4, 2), 'X->Y', (0, 6)]
结论：
其实题目并不是很难，关键是解题的思路,学Python招式掌握之后，关键是心法，而心法其实就是算法和软件技巧,这个没有什么好的诀窍，一半靠悟，一半靠练.以后我还会分享一些精妙而又有趣的Python算法题.
对源码有兴趣的同学可以后台跟我联系，打不打赏并不重要(当然打赏也是欢迎的,是对别人劳动的一种尊重)，也欢迎转发我的文章，算是对我一种鼓励和支持
下面是我公号赞助商100offer，一个非常不错的平台，希望大家支持一下
公号赞助商100offer
优秀人才不缺工作机会，只缺适合自己的好机会。但是他们往往没有精力从海量机会中找到最适合的那个。100offer 会对平台上的人才和企业进行严格筛选，让「最好的人才」和「最好的公司」相遇。
扫描下方二维码，注册 100offer，谈谈你对下一份工作的期待。一周内，收到 5-10 个满足你要求的好机会！