春假作業

最後編輯：2016-04-08 建立：2016-04-03 歷史紀錄

百千有個遊戲，規則是：

一排人中間某處有個空格，空格左/右邊的人只能向右/左走或跳(跳棋那樣)，最後全部到右/左邊。

寫個程式，教人怎麼走，所以你得先知道怎麼走，或者使用暴力。。。

# coding:utf-8
# python3
# 使用暴力
'''
from time import time
def change(list,index1,index2):
list[index1],list[index2]=list[index2],list[index1]
return list
def move(list,i):
if i>len(list)-2 or i<1:
return
try:
if list[i]=='L':
if list[i+1]==' ':
return change(list,i,list.index(' '))
elif list[i+2]==' ':
return change(list,i,list.index(' '))
elif list[i]=='R':
if list[i-1]==' ':
return change(list,i,list.index(' '))
elif list[i-2]==' ':
return change(list,i,list.index(' '))
except:
return False
def f(list):
if list==target:
return True
recover=list.copy()
block_index=list.index(' ')
for i in range(block_index-2,block_index+3):
list=recover.copy()
key=move(list,i)
if key:
if f(key):
movement.append(list)
return True
start=[]
movement=[]
num_L=int(input('左邊幾人 : '))
num_R=int(input('右邊幾人 : '))
num=num_L+num_R+1
for i in range(num_L):
start.append('L')
start.append(' ')
for i in range(num_R):
start.append('R')
target=start.copy()
target.reverse()
T=time() #
f(start)
print (time()-T) #
movement.reverse()
for i in range(len(movement)):
print (str(i+1).rjust(len(str(len(movement)))),movement[i])
'''
def change(list,index1,index2): #調換list裡的兩個元素
list[index1],list[index2]=list[index2],list[index1]
def move(list,i): #移動(list,index) 每個人只有一種動法或不能動
error=False
if i>len(list)-1: #index超過的話
print ('out of range')
return
if list[i]=='L':
if i>len(list)-2: #L 在最右邊
error=True
elif i>len(list)-3 and list[i+1]!=' ': #L 在最右邊第二且最右邊不是空格
error=True
elif list[i+1] !=' ' and list[i+2] !=' ': #L 右邊和右邊兩格都不是空格
error=True
elif list[i]=='R':
if i<1: #R 在最左邊
error=True
elif i<2 and list[i-1]!=' ': #R 在最左邊第二且最左邊不是空格
error=True
elif list[i-1] !=' ' and list[i-2] !=' ': #R 右邊和右邊兩格都不是空格
error=True
if error or list[i]==' ': #符合上述者動不了
return False
change(list,i,list.index(' ')) #剩下的與空格交換
return list
'''
s=['L','L','L','L','L',' ','R','R','R','R','R'] #level 1
m=[4,6,7,5,3,2,4,6,8,9,7,5,3,1,0,2,4,6,8,10,9,7,5,3,1,2,4,6,8,7,5,3,4,6,5] #level 1
for i in m:
move(s,i)
print (s)
'''
def f(list): #遞迴
if list==target: #目標
return True #找到第一種方法了往上傳回True (最開始的True)
recover=list.copy() #先備份
for i in range(num):
list=recover.copy()
key=move(list,i) #呼叫move()時,如果可以動它會直接幫你動,所以先把結果存下來
if key: #可以動就 : f(key) 進入下一層
if f(key): #如果 f(key) 是True(38行)(46行):
movement.append(list) # 把當前的情況,放入movement
return True # 繼續往上回溯
start=[]
movement=[]
num_L=int(input('左邊幾人 : ')) #輸入
num_R=int(input('右邊幾人 : '))
num=num_L+num_R+1
for i in range(num_L): #將輸入整理成list
start.append('L')
start.append(' ')
for i in range(num_R):
start.append('R')
target=start.copy() #直接 = 的話,之後使用 .pop() .sort()等 targrt 和 start 會一起變
target.reverse() #List.reverse() => 倒轉list裡的元素\\
f(start) #執行遞迴
movement.reverse() #由於movement是由終點往起點存回來的先反轉
for i in range(len(movement)):
print (str(i+1).rjust(len(str(len(movement)))),movement[i]) #STR.rjust() =>向右對齊

# coding:utf-8
# python2
# aprilfools.1001000.io
while True:
try:
L = int(raw_input('左邊人數(數字)：'))
break
except:
continue
while True:
try:
R = int(raw_input('右邊人數(數字)：'))
break
except:
continue
while True:
moves = raw_input('哪邊先走(L或R)：')
if moves == 'L':
moves = -1
break
if moves == 'R':
moves = 1
break
print '\\n解題方法：\\n左或右先走一步，\\n每次換邊走跳時人數加一，\\n但是以可以走跳的人數為上限。\\n'
string = ''
for _ in range(L):
string += 'L'
string += '_'
for _ in range(R):
string += 'R'
underscore = L
print '左邊' + str(L) + '人右邊' + str(R) + '人\ ' + string
def move(moves, who_to_move):
global string, underscore
index = underscore
while(moves):
if who_to_move == 'L':
index -= 1
moves -= 1 if string[index] == 'L' else 0
else:
index += 1
moves -= 1 if string[index] == 'R' else 0
string = string.replace('_', 'L' if who_to_move == 'L' else 'R')
string = string[:index] + '_' + string[index+1:]
underscore = index
def L_left_to_underscore():
number = 0
for char in string[:underscore]:
if char == 'L':
number += 1
return number
def R_right_to_underscore():
number = 0
for char in string[underscore:]:
if char == 'R':
number += 1
return number
while True:
L = L_left_to_underscore()
R = R_right_to_underscore()
if L == 0 and R == 0:
break
if moves < 0:
moves *= -1
moves = min(moves, L)
move(moves, 'L')
print '左邊' + str(moves) + '人向右走跳\ ' + string
moves += 1
else:
moves = min(moves, R)
move(moves, 'R')
print '右邊' + str(moves) + '人向左走跳\ ' + string
moves += 1
moves *= -1