Python技术巧妙破解Google计算题

开头先讲一下自己的亲身经历，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种操作:

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了，还是没有倒满)

(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了，还是没有倒满)

(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算法题.

今天也给大家分享几个Python的定位：

1， 网站业务逻辑的开发

Python有一个优良的网页开发框架django， django支持各种主流数据库，有好用的orm系统和模板系统，完善的第三方库能帮助解决遇到的大部分问题。 并且支持各种操作系统。

2， 数据分析和科学计算

Python有numpy,scipy等一大批科学计算库，有pandas数据分析库 还有matplotlib等绘图库，在科学计算和数据分析领域已经成为主流语言。

3， 网络爬虫

scrapy做为Python实现的爬虫库，被广泛使用，同时Python还拥有beatifulsoup, pyquery等html解析库 requests网络库可以用来做爬取和分析用途。

4， 自动化运维

主流的操作系统都集成有Python， 同时自动化运维领域主流技术栈 saltstack和ansible也是基于Python技术开发。可以使用Python打造强大的自动化运维工具。

关于自学Python，个人最大的3点经验：

找一本浅显易懂，例程比较好的教程，从头到尾看下去。不要看很多本，专注于一本。把里面的例程都手打一遍，搞懂为什么。我当时看的是《简明Python教程》，不过这本书不是非常适合零基础初学者。

去找一个实际项目练手。我当时是因为要做一个网站，不得已要学Python。这种条件下的效果比你平时学一门新语言要好很多。所以最好是要有真实的项目做。可以找几个同学一起做个网站之类。注意，真实项目不一定非要是商业项目，你写一个只是自己会用的博客网站也是真实项目，关键是要核心功能完整。

最好能找到一个已经会Python的人。问他一点学习规划的建议（上知乎也是个途径），然后在遇到卡壳的地方找他指点。这样会事半功倍。但是，要学会搜索，学会如何更好地提问。没人愿意帮你写作业或是回答“一搜便知”的问题。

然而，别人的经验未必能完全复制。比如我没有说的是，在自学Python之前，我已经系统学习过其他的编程语言。

对于完全没有编程经验的初学者，在学习Python的时候，面对的不仅仅是Python这门语言，还需要面临“编程”的一些普遍问题，比如：

从零开始，不知道从何入手，找了本编程教材发现第二章开始就看不懂了

缺少计算机基础知识，被一些教程略过的“常识性”问题卡住

遇到问题不知道怎么寻找解决方案

看懂语法之后不知道拿来做什么，学完一阵子就又忘了

缺少数据结构、设计模式等编程基础知识，只能写出小的程序片段

所以除了前面说的3点经验，给初学编程者的额外建议：

首先要有信心。虽然可能你看了几个小时也没在屏幕上打出一个三角形，或者压根儿就没能把程序运行起来。但相信我，几乎所有程序员一开始都是这么折腾过来的。

选择合适的教程。有些书很经典，但未必适合你，可能你写了上万行代码之后再看它会比较好。

写代码，然后写更多的代码。光看教程，编不出程序。从书上的例程开始写，再写小程序片段，然后写完整的项目。

除了学习编程语言，也兼顾补一点计算机基础，和英语。

不但要学写代码，还要学会看代码，更要会调试代码。读懂你自己程序的报错信息。再去找些github上的程序，读懂别人的代码。

学会查官方文档，用好搜索引擎和开发者社区。

我是张杨，今天的文章就分享到这里。