#Python版块活动# 挖(Qiang)钻(Yu)石(Bi) ---结束

戴宇轩

@wei_Y @～风介～

注意: 写出的代码直接发在本帖!
故事是这样的:

2015年2月29日，我的某位朋友意外地发现了一批巨大的钻石矿群！！！

按照他现在学的地理、物理知识，他轻松地算出了每块土地下的钻石数量【毫无压力~~
但当他兴致勃勃地准备开挖时，这时，问题来了

由于此地的土质十分松软，每开挖一步都有土层坍塌的危险，

但是他发现，只要不向两边开挖，不仅土层不会坍塌，还没有被困在矿井的危险(不要在意这些细节，假想~~)
但是贪心的他希望挖得越多越好，究竟怎样才能挖得最多呢

现在进入正题!


########## 凶残的分割线 ##########

传说中的钻石群是类似这样的:

           [[1],
        [2, 3, 5],
    [5, 4, 9, 6, 3],
[1, 4, 8, 2, 1, 3, 6]]

每下一层比上一层多两处钻石矿:



这里，每个数字都代表此处的钻石量
他必须从最顶层出发, 一路向下挖, 但是在开挖的过程中，有三个方向可以选择:

1. 'L'(Left)向偏左边挖, 'M'(Middle)垂直向下挖, 'R'(Right)向偏右边挖

复制代码

如上图，比如从最顶端的1开始，向左('L')就挖到了2，向中间('M')就挖到了3，向右('R')就挖到了5

要求写一段程序，算出最多能挖到多少，和挖的路径
例如上面的解(答案可能不唯一)是: (23, 'RLL')



它代表最多能挖到23块钻石(1 + 5 + 9 + 8)，路径是: '右左左'（顶层的1直接算进去）
不管你怎么走，最多钻石数目一样就行了

#################### 规则的分割线 ####################
代码要求:
满分100分
总要求: 写一段程序，算出最多能挖多少钻石，和挖的路径。返回一个元组: (最多挖到钻石数目, '路径')

1、不可以使用任何模块。
2、可以用任何方式缩短语句。
3、以函数形式封装语句，并且告诉我调用哪个函数。
4、函数用return返回结果，不得出现print。
5、最后结算分数的方法:
        1. 用你写的程序测试我所给的数据各一次(test_1 ~ test_12)，统计运行时间        3. 如果有3题解不出或解错，作废
        2. 分数 = 7250 / (运行时间(秒) * 代码总行数 * (解不出或解错的题数 + 1))，结果保留整数

我提供一组有参考答案的测试数据，供检查程序用。

OK，所有规则就是这样，小伙伴们快点行动吧！

#################### 奖品的分割线 ####################
按照分数高低来决定名次，

第一名（1位）200鱼币
第二名（2位）175鱼币
第三名（2位）150鱼币

参与奖（不限）20鱼币

幸运奖（3位）10鱼币

（PS：名次与回复时间无关！）

测试数据:

1. test_1 = [
   
2.    [8]
   
3. ]
   
4. #参考答案: (8, '')
   
5. ###############################################################################
   
6. test_2 = [
   
7.       [1],
   
8.    [3, 1, 4]
   
9. ]
   
10. #参考答案: (5, 'R')
    
11. ###############################################################################
    
12. test_3 = [
    
13.          [8],
    
14.       [9, 5, 5],
    
15.    [6, 4, 1, 3, 1]
    
16. ]
    
17. #参考答案: (23, 'LL')
    
18. ###############################################################################
    
19. test_4 = [
    
20.             [1],
    
21.          [8, 0, 2],
    
22.       [0, 8, 2, 9, 9],
    
23.    [1, 2, 3, 7, 7, 0, 6]
    
24. ]
    
25. #参考答案: (24, 'LMR')
    
26. ###############################################################################
    
27. test_5 = [
    
28.                [8],
    
29.             [5, 2, 3],
    
30.          [6, 8, 4, 9, 9],
    
31.       [8, 2, 8, 3, 4, 5, 9],
    
32.    [2, 3, 2, 5, 4, 2, 5, 7, 9]
    
33. ]
    
34. #参考答案: (38, 'RRRR')
    
35. ###############################################################################
    
36. test_6 = [
    
37.                   [6],
    
38.                [4, 8, 4],
    
39.             [9, 6, 7, 8, 8],
    
40.          [2, 3, 6, 7, 4, 0, 6],
    
41.       [8, 5, 2, 2, 1, 7, 4, 5, 3],
    
42.    [3, 7, 2, 5, 4, 5, 5, 1, 5, 6, 2]
    
43. ]
    
44. #参考答案: (41, 'MRLRM')
    
45. ###############################################################################
    
46. test_7 = [
    
47.                      [1],
    
48.                   [8, 3, 9],
    
49.                [7, 0, 9, 4, 5],
    
50.             [1, 0, 6, 6, 2, 3, 2],
    
51.          [3, 7, 5, 7, 5, 4, 4, 5, 0],
    
52.       [7, 0, 4, 3, 0, 9, 6, 7, 1, 6, 7],
    
53.    [1, 6, 3, 0, 7, 8, 5, 5, 2, 0, 7, 4, 7]
    
54. ]
    
55. #参考答案: (49, 'RLMLRL')
    
56. ###############################################################################
    
57. test_8 = [
    
58.                         [0],
    
59.                      [2, 1, 0],
    
60.                   [9, 7, 2, 7, 6],
    
61.                [5, 2, 5, 4, 9, 0, 8],
    
62.             [9, 4, 0, 4, 5, 8, 5, 8, 9],
    
63.          [9, 7, 7, 8, 9, 3, 8, 5, 6, 8, 7],
    
64.       [1, 2, 1, 3, 4, 6, 8, 3, 7, 7, 4, 1, 3],
    
65.    [6, 4, 8, 8, 6, 7, 0, 8, 2, 0, 6, 1, 7, 5, 6]
    
66. ]
    
67. #参考答案: (49, 'MRMMMLM')
    
68. ###############################################################################
    
69. test_9 = [
    
70.                            [9],
    
71.                         [3, 9, 2],
    
72.                      [0, 3, 5, 0, 1],
    
73.                   [1, 3, 9, 0, 4, 8, 5],
    
74.                [0, 3, 6, 8, 3, 8, 5, 9, 3],
    
75.             [1, 1, 6, 9, 0, 7, 5, 8, 3, 6, 9],
    
76.          [2, 2, 9, 5, 4, 1, 4, 8, 3, 6, 2, 5, 5],
    
77.       [3, 4, 1, 4, 9, 0, 8, 9, 9, 8, 7, 0, 2, 6, 7],
    
78.    [7, 6, 9, 5, 3, 2, 5, 7, 5, 2, 6, 0, 6, 5, 1, 3, 7]
    
79. ]
    
80. #参考答案: (71, 'MMLMRRLL')
    
81. ###############################################################################
    
82. test_10 = [
    
83.                               [1],
    
84.                            [2, 5, 0],
    
85.                         [1, 6, 7, 0, 8],
    
86.                      [8, 5, 7, 3, 6, 4, 7],
    
87.                   [4, 4, 7, 4, 3, 3, 6, 1, 4],
    
88.                [2, 1, 1, 5, 7, 3, 2, 0, 2, 1, 4],
    
89.             [7, 4, 6, 3, 6, 5, 9, 8, 5, 5, 0, 0, 7],
    
90.          [6, 6, 9, 5, 7, 8, 7, 4, 1, 1, 6, 4, 1, 9, 3],
    
91.       [1, 1, 6, 4, 0, 3, 1, 3, 8, 8, 1, 5, 0, 6, 4, 5, 9],
    
92.    [1, 2, 7, 7, 3, 4, 1, 0, 7, 7, 8, 0, 4, 1, 9, 5, 6, 8, 2]
    
93. ]
    
94. #参考答案: (66, 'MMLLRRLRR')
    
95. ###############################################################################
    
96. test_11 = [
    
97.                                  [4],
    
98.                               [0, 8, 1],
    
99.                            [9, 5, 6, 3, 7],
    
100.                         [3, 7, 7, 5, 8, 7, 5],
     
101.                      [8, 6, 7, 2, 9, 6, 0, 5, 5],
     
102.                   [4, 3, 7, 7, 8, 8, 9, 2, 1, 7, 9],
     
103.                [7, 9, 3, 7, 2, 0, 1, 2, 4, 0, 7, 9, 7],
     
104.             [2, 6, 7, 4, 7, 6, 7, 1, 1, 7, 2, 9, 1, 7, 5],
     
105.          [0, 1, 4, 4, 0, 6, 2, 2, 4, 4, 7, 7, 7, 4, 2, 0, 8],
     
106.       [6, 8, 8, 6, 2, 0, 8, 6, 7, 2, 1, 7, 2, 3, 8, 5, 3, 0, 0],
     
107.    [7, 9, 7, 2, 7, 5, 6, 0, 5, 5, 6, 8, 2, 9, 2, 5, 4, 7, 5, 9, 1]
     
108. ]
     
109. #参考答案: (78, 'MMRLRRMRLR')
     
110. ###############################################################################
     
111. test_12 = [
     
112.                                     [1],
     
113.                                  [8, 4, 5],
     
114.                               [9, 1, 4, 7, 5],
     
115.                            [8, 5, 9, 3, 2, 4, 8],
     
116.                         [0, 5, 8, 5, 6, 8, 9, 6, 8],
     
117.                      [1, 5, 9, 2, 4, 9, 2, 2, 8, 3, 2],
     
118.                   [5, 1, 4, 0, 0, 2, 4, 2, 5, 1, 7, 8, 0],
     
119.                [4, 8, 6, 1, 7, 2, 7, 7, 3, 2, 2, 2, 9, 0, 1],
     
120.             [9, 0, 3, 2, 1, 9, 8, 0, 0, 2, 2, 0, 0, 8, 0, 7, 3],
     
121.          [0, 3, 1, 0, 3, 8, 1, 8, 4, 7, 1, 1, 5, 4, 5, 0, 0, 6, 6],
     
122.       [1, 8, 8, 8, 4, 3, 2, 3, 2, 5, 2, 3, 4, 5, 1, 7, 9, 0, 4, 4, 1],
     
123.    [9, 1, 2, 5, 2, 7, 1, 8, 6, 6, 2, 3, 4, 4, 7, 3, 8, 7, 2, 2, 6, 2, 0]
     
124. ]
     
125. #参考答案: (83, 'LLRLLLRMRRL')
     
126. ###############################################################################

复制代码

wei_Y

1. def dug(dia):
   
2.         num_path = [['' for i in range(len(dia[j-1]))] for j in range(1,len(dia)+1)]
   
3.         # 生成同样结构的空路径。
   
4.         path_dic = {0:'L',1:'M',2:'R'}
   
5.         for i in reversed(range(len(dia)-1)):
   
6.                 # 底层开始取值
   
7.                 for j in range(len(dia[i])):
   
8.                         max_list = [dia[i+1][j], dia[i+1][j+1], dia[i+1][j+2]]
   
9.                         max_dia = max(max_list)
   
10.                         # 取最大值。
    
11.                         dia[i][j] = dia[i][j] + max_dia
    
12.                         num_path[i][j] += path_dic[max_list.index(max_dia)]
    
13.                         # 将每次的路径加入到列表。
    
14.                         if max_list.index(max_dia) == 0:
    
15.                                 num_path[i][j] += num_path[i+1][j]
    
16.                                 # 将上一次的路径累加，下同。
    
17.                         elif max_list.index(max_dia) == 1:
    
18.                                 num_path[i][j] += num_path[i+1][j+1]
    
19.                         elif max_list.index(max_dia) == 2:
    
20.                                 num_path[i][j] += num_path[i+1][j+2]
    
21.         return dia[0][0],num_path[0][0]

复制代码

结果:

1. (83, 'LLRLLLRMLLR')
   
2. (78, 'MMRLRRMMMR')
   
3. (66, 'MMLLRRLRR')
   
4. (71, 'MMLMRRLL')
   
5. (49, 'MRMMMLM')
   
6. (49, 'RLLMRL')
   
7. (41, 'MRLRL')
   
8. (38, 'RRRR')
   
9. (24, 'LMR')
   
10. (23, 'LL')
    
11. (5, 'R')
    
12. (8, '')
    
13. [Finished in 0.1s]

复制代码

3000多分。。7250是不是有点大。。

挥舞乾坤

1. def zs(data):  
   
2.     fx = {0:'L', 1:'M', 2:'R'};result = {}
   
3.     def move(path, x, y, count):
   
4.         count += data[x][y]
   
5.         if x == len(data) - 1:result.update({count:path});return
   
6.         for i in range(3):move('{0}{1}'.format(path, fx[i]), x + 1, y + i, count)
   
7.     move('', 0, 0, 0);return max(result),result[max(result)]

复制代码

结果:

1. (8, '')
   
2. (5, 'R')
   
3. (23, 'LL')
   
4. (24, 'LMR')
   
5. (38, 'RRRR')
   
6. (41, 'MRLRM')
   
7. (49, 'RLMLRL')
   
8. (49, 'MRMMMLM')
   
9. (71, 'MMLMRRLL')
   
10. (66, 'MMLLRRLRR')
    
11. (78, 'MMRLRRMRLR')
    
12. (83, 'LLRLLLRMRRL')

复制代码

用递归写的,效率很低,再想想别的方法.

lightninng

自己顺着树遍历的路子想了半天，最后搁浅，然后看了wei_Y同学的算法，表示给跪，然后翻到了他的这个贴子http://bbs.fishc.com/forum.php?mod=viewthread&tid=54578&ctid=1

觉得这个暴力随机方法很有趣试着实现了一下

1. import random
   
2. def ran_dirc(geo):
   
3.     col = 0;path = []#记录最大收集数和对应路径
   
4.     depth = len(geo)
   
5.     for i in range((1000*depth**2)):
   
6.         col_temp = 0;path_temp = []#记录本次的收集数和路径
   
7.         position  = 0              #记录在一层中的位置
   
8.         for layer in range(depth):
   
9.             #更新钻石数
   
10.             col_temp += geo[layer][position]
    
11.             dirction = random.choice([-1,0,1])
    
12.             #更新新的位置
    
13.             if dirction == -1 :
    
14.                 path_temp.append("L")
    
15.             elif dirction == 0 :
    
16.                 path_temp.append("M")
    
17.                 position += 1
    
18.             else:
    
19.                 path_temp.append("R")
    
20.                 position += 2
    
21.         #更新最收集数和对应路径
    
22.         if col < col_temp:
    
23.             path_temp.pop()
    
24.             path = path_temp
    
25.             col = col_temp
    
26.     return col,"".join(path)

复制代码

然后下面是结果 ：

1. (8, '')
   
2. (5, 'R')
   
3. (23, 'LL')
   
4. (24, 'LMR')
   
5. (38, 'RRRR')
   
6. (41, 'MRLRL')
   
7. (49, 'RLMLRL')
   
8. (49, 'MRMMMLM')
   
9. (71, 'MMLMRRLL')
   
10. (66, 'MMLLRRLRR')
    
11. (78, 'MMRLRRMRLR')
    
12. (83, 'LLRLLLRMRLL')

复制代码

参与一下。嘿嘿~~

微风拂面

代码如果用列表的index（）内置函数，会让代码好看并少一点，（我没用是把题目理解意思歪了，Σ( ° △ °|||)︴）

1. path_dic_in = 0
   
2. def dig(test_data):
   
3.     def maxNumber(datali):
   
4.         global path_dic_in
   
5.         if datali[0] >= datali[1] and datali[0] >= datali[2]:
   
6.             path_dic_in = 0
   
7.             return datali[0]
   
8.         if datali[1] > datali[0] and datali[1] >= datali[2]:
   
9.             path_dic_in = 1
   
10.             return datali[1]
    
11.         if datali[2] > datali[1] and datali[2] > datali[0]:
    
12.             path_dic_in = 2
    
13.             return datali[2]
    
14.     def set_tree(n1, m1,digpath):
    
15.         tree[n1][m1] += maxNumber(tree[n1+1][m1:m1+3])
    
16.         digpath[n1][m1] =  path_dic[path_dic_in] + digpath[n1+1][m1+path_dic_in]
    
17.     tree = test_data
    
18.     n = len(tree)
    
19.     m = len(tree[n-1])
    
20.     path_dic = {0:'L',1:'M',2:'R'}
    
21.     digpath = [['' for i in range(len(tree[j-1]))]for j in range(1,len(tree)+1)]
    
22.     while n > 1 :
    
23.         i = 0
    
24.         while i <= m -3:
    
25.             set_tree(n-2, i,digpath)
    
26.             i = i + 1
    
27.         n = n-1
    
28.         m = m -2
    
29.    
    
30.     return (tree[0][0],digpath[0][0])

复制代码

～风介～

有兴趣来看下哦！@Python_GoWithMe

wei_Y

这个。我好像发过贴。。不一样。我试试。

挥舞乾坤

先支持再来看

L-0

看看先

03111030

有兴趣来看下哦！

戴宇轩

wei_Y 发表于 2015-3-10 10:53
这个。我好像发过贴。。不一样。我试试。

我看过那个，加了一个M，可以垂直向下的

戴宇轩

wei_Y 发表于 2015-3-10 12:41
结果:

3000多分。。7250是不是有点大。。

我电脑慢（iPad），不能怪我。。。

freeparty

我来支持一下楼主。

小甲鱼

好家伙，啥时候搞了个新活动，Python版块真是贼活跃咧~~~

戴宇轩

小甲鱼 发表于 2015-3-10 19:57
好家伙，啥时候搞了个新活动，Python版块真是贼活跃咧~~~

谁让老师的课讲得那么生动呢~~

戴宇轩

挥舞乾坤 发表于 2015-3-10 11:58
先支持再来看

老战友了。。。这次估计你能突破40000分。。。

呆木木

终于出完啦

hbxtly

哇，又有活动，让朋友来参加下，我来学习

煈愛

:cry默默的关注...

小龙_h

支持楼主，有时间了写写试试

gelebo

先看看 看不懂~~~

挥舞乾坤

戴宇轩 发表于 2015-3-10 21:30
老战友了。。。这次估计你能突破40000分。。。

不一定,还没思路

wing1995

这个，是算法？支持一下