[已解决]鱼C论坛python挑战赛（01期）

jerryxjr1220 · 发表于 2017-6-17 07:50:21

Teagle 发表于 2017-6-17 07:46
怎么可能没有呢

L = ['AhCBDk','ADBekC','eCBDgD','CABghD']

['A', 'h', 'e', 'C', 'A', 'g', 'h', 'B', 'D', 'B', 'e', 'k', 'g', 'D']

我说的是这条，对照你提交的答案和原始列表

WelanceLee · 发表于 2017-6-17 10:11:38

SixPy 发表于 2017-6-16 21:01
L = ['AhCBDk','ADBekC','eCBDgD','CABghD']

用你的程序试试这个~

##L = ['ACBD','ADBC','CBDD','CABD']
L = ['AhCBDk','ADBekC','eCBDgD','CABghD']
result = []
mmin = 100
def check(l):
for each in l:
if each != '':
return False
return True
def poplist(l):
x = []
for each in l:
if each != '':
x.append(each[0])
x = list(set(x))
x.sort()
return x
def dele(l, x):
y = [ ]
for each in l:
if each == '':
y.append(each)
else:
if each[0] == x:
y.append(each[1:])
else:
y.append(each)
return y
def dfs(step, l):
global mmin
if check(l):
## result.append(step)
if mmin > step:
mmin = step
return
x = poplist(l)
for each in x:
lx = dele(l, each)
dfs(step+1, lx)
dfs(0, L)
##print(min(result))
print(mmin)

复制代码

计算出来是13，之前用result记录所有的情况列表太大了，所以稍微调整了下程序，用一个mmin记录最小值，不过计算的时间挺长的~

Teagle · 发表于 2017-6-17 12:38:37

修改好了，这次绝对可以！！

整的我在考试的时候就在担心，会不会有人抢在我前头提交

# 基列表挑选准则：挑选含不同字母多的字符串
def base(a):
c = []
for i in range(len(a)):
c.append(len(set(a[i])))
return (c.index(max(c))) #返回符合要求的字符串在列表中的位置
# 次列表的挑选准则：挑选字母在基列表中位置靠前的字符串，如果没有则选择第一个字符串
def less(a,a_base):
if len(a) == 1:
return 0
else:
temp = []
for i in a_base:
for j in range(len(a)):
try:
temp.append(a[j].index(i))
except ValueError:
temp.append(len(a[j]))
if min(temp)<len(a[j]):
return(temp.index(min(temp))) #返回符合要求的字符串在列表中的位置
return 0 #如果没有与基列表重复的字母，则选择第一个字符串
# 寻找所有的匹配组合，返回匹配超度最长的组合。
def seek_index(a_base,a_less):
#返回在主列表中的位置T=[组合1,..,组合n] 组合1=[位置0,...,位置n]
T = []
for i in range(len(a_less)):
temp = []
for j in range(i,len(a_less)):
if temp==[]:
k=0
try:
k = a_base.index(a_less[j],k)
temp.append(k) #偶数位置是对应元素在基列表中的位置
temp.append(j) #奇数位置是对应元素在次列表中的位置
k += 1
except ValueError:
pass
T.append(temp)
#返回最长组合
temp = []
for k in T:
temp.append(len(k))
return (T[temp.index(max(temp))])
#利用得到的最优匹配位置进行匹配，在基列表中插入不满足次列表的元素
def match(a_base,a_less,index):
temp_base = []
temp_less = []
for i in range(len(index)):
if not i % 2:
temp_base.append(index[i])#得到对应元素在基列表中的位置
else:
temp_less.append(index[i])#得到对应元素在次列表中的位置
for i in range(len(temp_less)):
if i == 0:
if temp_less[i] != 0:
temp = a_less[:temp_less[i]]
temp.reverse()
for j in range(len(temp)):
a_base.insert(temp_base[i],temp[j])
for k in range(i+1,len(temp_base)):
temp_base[k] += len(temp)
else:
if temp_less[i] - temp_less[i-1] > 1:
temp = a_less[temp_less[i-1]+1:temp_less[i]]
temp.reverse()
for j in range(len(temp)):
a_base.insert(temp_base[i],temp[j])
if i != len(temp_less)-1:
for k in range(i+1,len(temp_base)):
temp_base[k] += len(temp)
if i == len(temp_less)-1 and temp_less[i] < len(a_less)-1:
temp = a_less[temp_less[i]+1:]
for j in range(len(temp)):
a_base.append(temp[j])
return a_base
L = ['ACBD','ADBC','CBDD','CABD']
##L = ['AhCBDk','ADBekC','eCBDgD','CABghD']
list_base = list(L[base(L)]) # 挑选基列表
L.remove(''.join(list_base)) # 在L中移除选中的基列表所对应的字符串
for i in range(len(L)):
list_less = list(L[less(L,list_base)]) #挑选次列表
L.remove(''.join(list_less))# 在L中移除选中的次列表中对应的字符串
nice_index = seek_index(list_base,list_less) #查找最佳匹配顺序
list_base = match(list_base,list_less,nice_index) #进行匹配
print (list_base)
print (len(list_base))

复制代码

Teagle · 发表于 2017-6-17 12:39:54

SixPy 发表于 2017-6-16 21:01
L = ['AhCBDk','ADBekC','eCBDgD','CABghD']

用你的程序试试这个~

['A', 'h', 'e', 'C', 'A', 'B', 'g', 'h', 'D', 'B', 'e', 'k', 'C', 'g', 'D']
15

复制代码

wei_Y · 发表于 2017-6-17 14:19:45

本帖最后由 wei_Y 于 2017-6-17 20:29 编辑

贡献个低效率版本。

递归，俗称暴力破解。

def combinations(rawList):
result = ['']
length = 0
currentStr = ''
def combination(rawList, currentStr, currentLength=0):
# 列表不需要进行nonlocal操作也可以直接操作。
nonlocal length
# 在计算时减少不必要的长度。
if length:
# 大于当前最小长度，直接返回。
if currentLength > length:
return
# 等于当前最小长度，但是还可以计算，直接返回。
if currentLength == length and any(rawList):
return
# 祈祷一下？
# 它的顺序直接决定效率。低或高大约相差3~5倍。
currentWords = {i[0] for i in rawList if i}
if not currentWords:
# 正常迭代的结果。
result[0] = currentStr
length = currentLength
return
# 每次都将各个字符串的第一个字符作为种子，
# 将相同的字符清空，继续递归。(因为也会清空来源所以不会无限递归。)
# 例： 'CBDD', 'CABD', 'ACBD', 'ADBC'
# C清空后。BDD ABD ACBD ADBC.
# [BDD ABD ACBD ADBC], C, 1
# 接下来会清空 B 与 A。结果分别会生成 CB开始与 A开始的两个分支。
for j in currentWords:
# 字符串不需要深拷贝。
copyList = rawList.copy()
for index, data in enumerate(copyList):
if data:
if data[0] == j:
copyList[index] = data[1:]
combination(copyList, currentStr+j, currentLength+1)
combination(rawList, currentStr)
return result

复制代码

jerryxjr1220 · 发表于 2017-6-17 16:15:44

挑战赛第二天，目前提交答案的有三位鱼油，最终评选结果将在挑战截止日期后公布，欢迎继续提交优秀的解答程序！

Teagle · 发表于 2017-6-17 17:35:36

最终版，这次绝对是可以的，绝对是正确的！！

from itertools import combinations
# 基列表挑选准则：挑选含不同字母多的字符串
def base(a):
c = []
for i in range(len(a)):
c.append(len(set(a[i])))
return (c.index(max(c))) #返回符合要求的字符串在列表中的位置
# 次列表的挑选准则：挑选字母在基列表中位置靠前的字符串，如果没有则选择第一个字符串
def less(a,a_base):
if len(a) == 1:
return 0
else:
temp = []
for i in a_base:
for j in range(len(a)):
try:
temp.append(a[j].index(i))
except ValueError:
temp.append(len(a[j]))
if min(temp)<len(a[j]):
return(temp.index(min(temp))) #返回符合要求的字符串在列表中的位置
return 0 #如果没有与基列表重复的字母，则选择第一个字符串
# 寻找所有的匹配组合，返回匹配长度最长的组合。
def seek_index(a_base,a_less):
T = []
all_index = []
#列出所有的次列表进行匹配的元素的所有可能性，将对应位置放到all_index列表
for i in range(len(a_less)):
all_index.extend(combinations(range(len(a_less)),i+1))
for i in range(len(all_index)):
temp = []
for j in range(len(all_index[i])):
index = all_index[i][j] #a_less中的位置
if temp == []:
k = 0
try :
k = a_base.index(a_less[index],k)
temp.append(k)
temp.append(index)
k += 1
except ValueError:
pass
T.append(temp)
#返回最长组合
temp = []
for k in T:
temp.append(len(k))
return (T[temp.index(max(temp))])
#利用得到的最优匹配位置进行匹配，在基列表中插入不满足次列表的元素
def match(a_base,a_less,index):
temp_base = []
temp_less = []
for i in range(len(index)):
if not i % 2:
temp_base.append(index[i])#得到对应元素在基列表中的位置
else:
temp_less.append(index[i])#得到对应元素在次列表中的位置
for i in range(len(temp_less)):
if i == 0:
if temp_less[i] != 0:
temp = a_less[:temp_less[i]]
temp.reverse()
for j in range(len(temp)):
a_base.insert(temp_base[i],temp[j])
for k in range(i+1,len(temp_base)):
temp_base[k] += len(temp)
else:
if temp_less[i] - temp_less[i-1] > 1:
temp = a_less[temp_less[i-1]+1:temp_less[i]]
temp.reverse()
for j in range(len(temp)):
a_base.insert(temp_base[i],temp[j])
if i != len(temp_less)-1:
for k in range(i+1,len(temp_base)):
temp_base[k] += len(temp)
if i == len(temp_less)-1 and temp_less[i] < len(a_less)-1:
temp = a_less[temp_less[i]+1:]
for j in range(len(temp)):
a_base.append(temp[j])
return a_base
L = ['ACBD','ADBC','CBDD','CABD']
L = ['AhCBDk','ADBekC','eCBDgD','CABghD']
list_base = list(L[base(L)]) # 挑选基列表
L.remove(''.join(list_base)) # 在L中移除选中的基列表所对应的字符串
for i in range(len(L)):
list_less = list(L[less(L,list_base)]) #挑选次列表
L.remove(''.join(list_less))# 在L中移除选中的次列表中对应的字符串
nice_index = seek_index(list_base,list_less) #查找最佳匹配顺序
list_base = match(list_base,list_less,nice_index) #进行匹配
print (list_base)
print (len(list_base))

复制代码

达锅 · 发表于 2017-6-17 19:55:02

我的思路有点特别，计算机就是为计算而生
根据题目，答案并不唯一，所以我用的是抽样穷举法

思路是用已有的元素随机组合，然后匹配生成较短的母字符
代码还有待改进，使用排列组合生成母字符应该更好

import re
from random import randrange
c=[]
a_base='AhCBDk ADBekC eCBDgD CABghD'.split()
len_base=len(''.join(a_base))
for l in range(20000):#重复运行次数
base=''#用于记录生成的母字符
a=a_base[:]#复制列表，用于查找母字符
#随机生成母字符，思路：每次从a列表中抽取任意一个元素的最左边的字符
for i in range(len_base):#
r=randrange(len(a))
while True:#若抽中的元素为空，取下一个元素
if a[r]!="":
break
r=(r+1)%4
base+=a[r][0]#接上，生成母字符base
a[r]=a[r][1:]#去除左边第一个字符
#print(base)
b=[0]*len(base)#用于记录查到找的字符
a=a_base[:]#复制列表，用于查找母字符
for i in a: #遍历每一个元素，查找字符对应的位置并记录
s_count=0 #
for j in range(len(base)):#j遍历base的每一个字符，与i的字符比较，s_count记录i中的顺序
if i[s_count]==base[j]:#如果一样，s_count+1，即判断i的下一个字符
b[j]=1 #b对应的位置设置为1
s_count+=1
if s_count==len(i):#如果查找完毕，退出，判断下一个元素
break
temp=''.join([base[i] for i in range(len(base)) if b[i]==1])
if len(temp)<=13:
c.append(temp)
c=set(c)#去除重复项
a=a_base[:]
#print(c)
#以下展示用
for w in c:
if len(w)<=13:
for i in a:
s_count=0
for j in range(len(w)):
if i[s_count]==w[j]:
print(w[j],end="")
s_count+=1
else:
print(' ',end='')
if s_count==len(i):
break
print('')
print(w)

复制代码

我找到了长度为13的哦

  A hCBD k
  A D B ekC
eC BDg D
CAB gh  D
eCABDghCBDekC  #这个
  A hCB Dk
  A D Be kC
eC BDg D
CAB gh D
eCABDghCBeDkC#这个

瓦蓝 · 发表于 2017-6-17 23:13:07

达锅发表于 2017-6-17 19:55
我的思路有点特别，计算机就是为计算而生
根据题目，答案并不唯一，所以我用的是抽样穷举法

很明显你做的结果错了哦
你的结果应该是
ecacbdghcbedkc

达锅 · 发表于 2017-6-18 02:18:00

本帖最后由达锅于 2017-6-18 02:19 编辑

瓦蓝发表于 2017-6-17 23:13
很明显你做的结果错了哦
你的结果应该是
ecacbdghcbedkc

没错，因为随机数不够大，你试一下40000，或者多运行几次就看到了

jerryxjr1220 · 发表于 2017-6-18 13:35:53

Teagle 发表于 2017-6-17 17:35
最终版，这次绝对是可以的，绝对是正确的！！

如果L=['1','2','3','4']
你的程序的结果是什么？

jerryxjr1220 · 发表于 2017-6-18 14:03:00

精英挑战赛最后一天，目前已经有4位鱼油提交了答案。

Teagle · 发表于 2017-6-18 20:40:41

jerryxjr1220 发表于 2017-6-18 13:35
如果L=['1','2','3','4']
你的程序的结果是什么？

唉，我已经意识到我的程序是错误的了，不完善。。
唉，编程的经验太少，我还得继续多做练习，
谢谢大佬的鼓励

Teagle · 发表于 2017-6-18 23:47:45

Teagle 发表于 2017-6-18 20:40
唉，我已经意识到我的程序是错误的了，不完善。。
唉，编程的经验太少，我还得继续多做练习，
谢谢大佬 ...

，感谢大佬，我今天真是太幸运了，被两位大神鼓励

lh625243422 · 发表于 2017-6-19 00:09:04

本帖最后由 lh625243422 于 2017-6-19 00:37 编辑

import random
r=random.randint
l=['ACBD','ADBC','CBDD','CABD']
first=list(l[0])
rest=''.join(list(l[1:]))
def is_sub(s, strings):
if len(s) == 1 and s in strings:
return True
if s[0] not in strings:
return False
return is_sub(s[1:], strings[strings.find(s[0])+1:])
def sr(s):
b1=s
for i in s:
b1=b1.replace(i+i,i,1)
return b1
def lh(x,y):#将剩余部分随机插入第一个字符串中
z=x[:]
n=0
for i in range(len(y)):
if i%len(first)==0: #在同一个字符串中必然后插入的在先插入的后面
n=r(0,len(z))
else:
n=r(n+1,len(z)) #在同一个字符串中必然后插入的在先插入的后面
z.insert(n,y[i])
c=''.join(z)
return sr(c)
d={}
for i in range(200000):
st=lh(first,rest)
if is_sub(l[0],st) and is_sub(l[1],st) and is_sub(l[2],st) and is_sub(l[3],st):#此处可不判断，会产生最短7位的，但CBDD没匹配上，加上一个D就是8位
lst=len(st)
d[lst]=st
print(min(d.keys()),':',d[min(d.keys())])

复制代码

采用思想是随机插入法消除相邻相同的字符，要求每个字符串的长度一致，随机次数越多越好，不会产生CACBDDBC这样的母字符串

jerryxjr1220 · 发表于 2017-6-19 11:00:42

SixPy 发表于 2017-6-16 15:07
早就写好了，不想发，怕影响其他人的思路。
等等看~

期待看看你的解答。

ooxx7788 · 发表于 2017-6-19 14:37:35

答案已经出来了，我贡献一个我找到的解题思路的ppt给各位参考参考。这东西其实我第一天就找到了，不过最近事情有点多，加上这种题目也不是我擅长的，所以解不了题。版权当然还是归PPT里面那位作者的了。没有代码，只有思路，不过基本应该和wei_y的差不多，BFS的思路。

jerryxjr1220 · 发表于 2017-6-19 15:05:51

ooxx7788 发表于 2017-6-19 14:37
答案已经出来了，我贡献一个我找到的解题思路的ppt给各位参考参考。这东西其实我第一天就找到了，不过最近 ...

不错，解题思路基本都是一致的。
我写的递归插入法也是同样原理。

python黑帽 · 发表于 2017-6-19 20:59:19

还有这种比赛

SixPy · 发表于 2017-6-21 10:54:00

python黑帽发表于 2017-6-19 20:59
还有这种比赛

@～风介～帮发个系统消息宣传一下呗~

账号		自动登录	找回密码
密码			立即注册

[已解决]鱼C论坛python挑战赛（01期）

评分

评分

评分

评分

浏览过的版块