問題はこちら->http://nabetani.sakura.ne.jp/hena/ord15subpalin/
最初と最後の文字の組み合わせから一文字づつ近づけながら2文字を比較し、
n1番目とn2番目が同じ文字なら長さ(ans)を2増やし
n1+1番目とn2-1番目の間で同じ文字を調べます。（loop関数のforループ中のloop）
最後n番目とn+1番目が同じにならなければ長さに1をたします。
最初Juliaで枝刈せずに遅かったので、NimやRubyでも試しましたが、
結局、今の長さ(ans)と残りの文字数の和が今までの最大の長さ(fans)より大きい場合
（fans<j-i+ans+1）のみ探索を進める簡単な枝狩りをし、
forループ中のloopの後にbreakを入れたら、だいぶ速くなりました。
Julia
#Julia v 0.6-1.4
inp="0 I_believe_you_can_solve 9 evo_n_ove
1 a 1 a
2 aa 2 aa
3 aaa 3 aaa
4 ab 1 b
5 aabb 2 bb
6 ABBA 4 ABBA
7 Abba 2 bb
8 1234567890 1 0
9 1234567890987654321 19 1234567890987654321
10 abcdcba 7 abcdcba
11 0a1b2c3d4c5b6a7 7 abc4cba
12 abcdcba0123210 7 0123210
13 abcdcba_123210 7 abcdcba
14 _bcdcba0123210 7 0123210
15 abcddcba0123210 8 abcddcba
16 abcdcba01233210 8 01233210
17 a0bc1dc2ba3210a 9 a0123210a
18 a0bc1ddc2ba3210 8 0bcddcb0
19 3a0bc1ddc2ba3210 10 3abcddcba3
20 11oooo1111o1oo1o111ooooooooooo 20 oooo111o1oo1o111oooo
21 11o1111o1111oo11ooo11111ooo1oo 20 o1o1111oo11oo1111o1o
22 111111oo11o111ooo1o1ooo11ooo1o 21 1ooo11ooo1o1ooo11ooo1
23 11o1o1o11oo11o11oo111o1o1o11oo 27 11o1o1o11oo11o11oo11o1o1o11
24 oo111o1o11o1oo1ooo11o1o11o1o1o 27 oo111o1o11ooo1ooo11o1o111oo
25 1o1oo11111o1o1oo1o1o1111oo1o1o 28 1o1oo1111o1o1oo1o1o1111oo1o1
26 QQooooQooooQQyQoyQQQyyyyQQoyoy 15 ooQQyyQQQyyQQoo
27 oQoooQooooQyoyQoyoyyyQQyQQQQoQ 16 QoQQyQyyyyQyQQoQ
28 yyyyyooyQyyyoyyQyyooyQoQoQQoQy 17 yooQyoyyQyyoyQooy
29 yyQoyQoyyQyQQoyooooyyQQyQyooQy 24 yQooyQyQQyooooyQQyQyooQy
30 oQQooQoQyQQoyoQQoQyQyQyQoQoooo 24 oooQoQyQQyoQQoyQQyQoQooo
31 oQQyQQyyQyQQoooyQQyyyQQQyyQQoy 25 oQQyQQyyyQQoooQQyyyQQyQQo
32 WAk9iHI4jVDlStyudwTNqE138kwan2 3 wkw
33 c43fIu1Mlz0K9hEVOgGcUdbeB5ksa7 3 cGc
34 CAbYcW5VqHjzFdIkH_61PM0TsyRuie 3 HkH
35 jInQnUvSayrJTsQWujovbbqW0STvoj 10 jvTWbbWTvj
36 iZDrvpUKgtj3FrZsZ4CLjrEgUdZzQG 11 ZUgrZsZrgUZ
37 ROgYUOu6er_DA7nB6UGquO1GUHC62R 11 RUOu6B6uOUR
38 Oh_be_a_fine_girl_kiss_me 9 e_i_l_i_e
39 8086_6502_6809_Z80 11 8086_2_6808
40 xcode_visualstudio_eclipse 11 ce_iutui_ec
41 word_excel_powerpoint_outlook 9 ol_opo_lo
42 abcdefghijklmnopqrstuvwxyz0123 1 3"
function main()
local fans
function loop(str,ans)
if str !=""
for i in 1:length(str)-1
for j in length(str):-1:i+1
if str[j]==str[i] && fans<j-i+ans+1
loop(str[i+1:j-1],ans+2)
break
end
end
end
ans +=1
end
if fans<ans
fans=ans
end
end
str0=split(inp,"\n")
for s0 in str0
s1=split(s0," ")
fans=0
ans=0
loop(strip(s1[2]),ans)
if fans==parse(Int,s1[3])
sel="pass"
else
sel="fail"
end
print(sel," ",fans,"\n")
end
end
@time main()
Nim
Juliaと大差ない速さの時もありますが、この問題（コード）では、桁違いに速いです。
#Nim v 0.194
import os,strutils,sequtils,times
import math
const inp="""0 I_believe_you_can_solve 9 evo_n_ove
1 a 1 a
2 aa 2 aa
3 aaa 3 aaa
4 ab 1 b
5 aabb 2 bb
6 ABBA 4 ABBA
7 Abba 2 bb
8 1234567890 1 0
9 1234567890987654321 19 1234567890987654321
10 abcdcba 7 abcdcba
11 0a1b2c3d4c5b6a7 7 abc4cba
12 abcdcba0123210 7 0123210
13 abcdcba_123210 7 abcdcba
14 _bcdcba0123210 7 0123210
15 abcddcba0123210 8 abcddcba
16 abcdcba01233210 8 01233210
17 a0bc1dc2ba3210a 9 a0123210a
18 a0bc1ddc2ba3210 8 0bcddcb0
19 3a0bc1ddc2ba3210 10 3abcddcba3
20 11oooo1111o1oo1o111ooooooooooo 20 oooo111o1oo1o111oooo
21 11o1111o1111oo11ooo11111ooo1oo 20 o1o1111oo11oo1111o1o
22 111111oo11o111ooo1o1ooo11ooo1o 21 1ooo11ooo1o1ooo11ooo1
23 11o1o1o11oo11o11oo111o1o1o11oo 27 11o1o1o11oo11o11oo11o1o1o11
24 oo111o1o11o1oo1ooo11o1o11o1o1o 27 oo111o1o11ooo1ooo11o1o111oo
25 1o1oo11111o1o1oo1o1o1111oo1o1o 28 1o1oo1111o1o1oo1o1o1111oo1o1
26 QQooooQooooQQyQoyQQQyyyyQQoyoy 15 ooQQyyQQQyyQQoo
27 oQoooQooooQyoyQoyoyyyQQyQQQQoQ 16 QoQQyQyyyyQyQQoQ
28 yyyyyooyQyyyoyyQyyooyQoQoQQoQy 17 yooQyoyyQyyoyQooy
29 yyQoyQoyyQyQQoyooooyyQQyQyooQy 24 yQooyQyQQyooooyQQyQyooQy
30 oQQooQoQyQQoyoQQoQyQyQyQoQoooo 24 oooQoQyQQyoQQoyQQyQoQooo
31 oQQyQQyyQyQQoooyQQyyyQQQyyQQoy 25 oQQyQQyyyQQoooQQyyyQQyQQo
32 WAk9iHI4jVDlStyudwTNqE138kwan2 3 wkw
33 c43fIu1Mlz0K9hEVOgGcUdbeB5ksa7 3 cGc
34 CAbYcW5VqHjzFdIkH_61PM0TsyRuie 3 HkH
35 jInQnUvSayrJTsQWujovbbqW0STvoj 10 jvTWbbWTvj
36 iZDrvpUKgtj3FrZsZ4CLjrEgUdZzQG 11 ZUgrZsZrgUZ
37 ROgYUOu6er_DA7nB6UGquO1GUHC62R 11 RUOu6B6uOUR
38 Oh_be_a_fine_girl_kiss_me 9 e_i_l_i_e
39 8086_6502_6809_Z80 11 8086_2_6808
40 xcode_visualstudio_eclipse 11 ce_iutui_ec
41 word_excel_powerpoint_outlook 9 ol_opo_lo
42 abcdefghijklmnopqrstuvwxyz0123 1 3"""
proc main()=
var fans=0
proc loop(str:string,ans:int)=
var ans1=ans
if str != "":
for i in 0..len(str)-2:
for j in countdown(len(str)-1,i+1):
if str[j]==str[i] and fans<j-i+ans1+1:
loop(str[i+1..j-1],ans1+2)
break
ans1=ans1+1
if fans<ans1:
fans=ans1
for s0 in inp.splitLines :
var s1=s0.split(" ")
fans=0
loop(s1[1].strip,0)
var sel=""
if fans==s1[2].strip.parseInt:
sel="pass"
else:
sel="fail"
echo(sel," ",fans)
var t = cpuTime()
main()
echo cpuTime()-t
Ruby
「どう書く」の参加者にはRuby使いの方が多かったような気がします。
私は「オブジェクト指向スクリプト言語Ruby」の初版を読んでいるのですが、
GUIプログラムはDelphiのほうが便利だし、パズルを解くには遅いという印象がありましたので、
たまにawkの代わりに使うくらいでした。
しかし別の問題で、他の方のコードを参考に書いてJuliaと比べたら結構早かったので、
今回も試してみました。
この問題では枝刈前はあまり早くありませんでしたが枝刈後はJuliaといい勝負です。
ruby使いの方から見れば古風で冗長な書き方かもしれませんが、枝刈した方を載せます。
#ruby v 2.5.5
require 'benchmark'
$inp="0 I_believe_you_can_solve 9 evo_n_ove
1 a 1 a
2 aa 2 aa
3 aaa 3 aaa
4 ab 1 b
5 aabb 2 bb
6 ABBA 4 ABBA
7 Abba 2 bb
8 1234567890 1 0
9 1234567890987654321 19 1234567890987654321
10 abcdcba 7 abcdcba
11 0a1b2c3d4c5b6a7 7 abc4cba
12 abcdcba0123210 7 0123210
13 abcdcba_123210 7 abcdcba
14 _bcdcba0123210 7 0123210
15 abcddcba0123210 8 abcddcba
16 abcdcba01233210 8 01233210
17 a0bc1dc2ba3210a 9 a0123210a
18 a0bc1ddc2ba3210 8 0bcddcb0
19 3a0bc1ddc2ba3210 10 3abcddcba3
20 11oooo1111o1oo1o111ooooooooooo 20 oooo111o1oo1o111oooo
21 11o1111o1111oo11ooo11111ooo1oo 20 o1o1111oo11oo1111o1o
22 111111oo11o111ooo1o1ooo11ooo1o 21 1ooo11ooo1o1ooo11ooo1
23 11o1o1o11oo11o11oo111o1o1o11oo 27 11o1o1o11oo11o11oo11o1o1o11
24 oo111o1o11o1oo1ooo11o1o11o1o1o 27 oo111o1o11ooo1ooo11o1o111oo
25 1o1oo11111o1o1oo1o1o1111oo1o1o 28 1o1oo1111o1o1oo1o1o1111oo1o1
26 QQooooQooooQQyQoyQQQyyyyQQoyoy 15 ooQQyyQQQyyQQoo
27 oQoooQooooQyoyQoyoyyyQQyQQQQoQ 16 QoQQyQyyyyQyQQoQ
28 yyyyyooyQyyyoyyQyyooyQoQoQQoQy 17 yooQyoyyQyyoyQooy
29 yyQoyQoyyQyQQoyooooyyQQyQyooQy 24 yQooyQyQQyooooyQQyQyooQy
30 oQQooQoQyQQoyoQQoQyQyQyQoQoooo 24 oooQoQyQQyoQQoyQQyQoQooo
31 oQQyQQyyQyQQoooyQQyyyQQQyyQQoy 25 oQQyQQyyyQQoooQQyyyQQyQQo
32 WAk9iHI4jVDlStyudwTNqE138kwan2 3 wkw
33 c43fIu1Mlz0K9hEVOgGcUdbeB5ksa7 3 cGc
34 CAbYcW5VqHjzFdIkH_61PM0TsyRuie 3 HkH
35 jInQnUvSayrJTsQWujovbbqW0STvoj 10 jvTWbbWTvj
36 iZDrvpUKgtj3FrZsZ4CLjrEgUdZzQG 11 ZUgrZsZrgUZ
37 ROgYUOu6er_DA7nB6UGquO1GUHC62R 11 RUOu6B6uOUR
38 Oh_be_a_fine_girl_kiss_me 9 e_i_l_i_e
39 8086_6502_6809_Z80 11 8086_2_6808
40 xcode_visualstudio_eclipse 11 ce_iutui_ec
41 word_excel_powerpoint_outlook 9 ol_opo_lo
42 abcdefghijklmnopqrstuvwxyz0123 1 3"
def main()
def loop(str,ans)
if str !=""
for i in 0..str.length-2
(str.length-1).downto(i+1) {
|j|
if str[j]==str[i] && $fans<j-i+ans+1
loop(str[i+1..j-1],ans+2)
break
end
}
end
ans +=1#*string(str[1])
end
if $fans<ans
$fans=ans
end
end
$inp.lines do |s0|
s1=s0.split(" ")
$fans=0
ans=0
loop(s1[1].strip,ans)
if $fans==s1[2].to_i
sel="pass"
else
sel="fail"
end
print(sel," ",$fans,"\n")
end
end
time = Benchmark.realtime do
main()
end
p time
別解(Prolog)
元の文字列と逆向きの文字列で同じ文字の組み合わせの最長を求める方法です。メモ化再帰です。
二つの文字列のn1番目とn2番目が同じ文字なら、長さRを1増やしてn1+1番目とn2+1番目を比べます。
違う場合はn1+1番目とn2番目を比較した場合と、n1番目とn2+1番目を比較した場合の
長いほうとRを加えます。
コード風に書くと
f(n1,n2) = if n1==n2: f(n1+1,n2+1)+1 #solve/4の4節目
else:max(f(n1+1,n2),f(n1,n2+1)) #solve/4の5節目
メモ化の部分はfunctorを利用して二次元配列(F)のメモを作り、
solve/4の3節目で、メモに書き込まれている場合（nonvar(R1)）、その値を利用します。
data/4はメモの書き込みにも読み込みにも用います。
%SWI-Prolog v 7.4.2,7.6.4
%start.
%:-initialization(start). %ideone
twoar(_,0,_). % two dimensional array
twoar(F,X,Y):-arg(X,F,V),functor(V,y,Y),X1 is X-1,twoar(F,X1,Y).
data(F,X,Y,V):-arg(X,F,V1),arg(Y,V1,V).
solve([],_,_,0).
solve(_,[],_,0).
solve(L1,L2,F,R):-
length(L1,N1),length(L2,N2),data(F,N1,N2,R1),nonvar(R1),!,R=R1.
solve([H1|T1],[H2|T2],F,R):-
H1==H2,!,length([H1|T1],N1),length([H2|T2],N2),
solve(T1,T2,F,R1),R is R1+1,data(F,N1,N2,R).
solve([H1|T1],[H2|T2],F,R):-
length([H1|T1],N1),length([H2|T2],N2),
solve([H1|T1],T2,F,R1),solve(T1,[H2|T2],F,R2),R is max(R1,R2),data(F,N1,N2,R).
start:-str(S),split_string(S,"\s,\n","\s",L),pre(L),!.
disp(R,Q):-
number_string(R,R1),(R1==Q->Str="pass ";Str=" fail "),
write(" "),write(Str),writeln(R).
pre([]).
pre([_,B,C,_|T]):-
atom_chars(B,L),reverse(L,L1),length(L,M),M1 is M+5,functor(F,x,M1),twoar(F,M1,M1),
solve(L,L1,F,R),disp(R,C),pre(T).
str("0 I_believe_you_can_solve 9 evo_n_ove
1 a 1 a
2 aa 2 aa
3 aaa 3 aaa
4 ab 1 b
5 aabb 2 bb
6 ABBA 4 ABBA
7 Abba 2 bb
8 1234567890 1 0
9 1234567890987654321 19 1234567890987654321
10 abcdcba 7 abcdcba
11 0a1b2c3d4c5b6a7 7 abc4cba
12 abcdcba0123210 7 0123210
13 abcdcba_123210 7 abcdcba
14 _bcdcba0123210 7 0123210
15 abcddcba0123210 8 abcddcba
16 abcdcba01233210 8 01233210
17 a0bc1dc2ba3210a 9 a0123210a
18 a0bc1ddc2ba3210 8 0bcddcb0
19 3a0bc1ddc2ba3210 10 3abcddcba3
20 11oooo1111o1oo1o111ooooooooooo 20 oooo111o1oo1o111oooo
21 11o1111o1111oo11ooo11111ooo1oo 20 o1o1111oo11oo1111o1o
22 111111oo11o111ooo1o1ooo11ooo1o 21 1ooo11ooo1o1ooo11ooo1
23 11o1o1o11oo11o11oo111o1o1o11oo 27 11o1o1o11oo11o11oo11o1o1o11
24 oo111o1o11o1oo1ooo11o1o11o1o1o 27 oo111o1o11ooo1ooo11o1o111oo
25 1o1oo11111o1o1oo1o1o1111oo1o1o 28 1o1oo1111o1o1oo1o1o1111oo1o1
26 QQooooQooooQQyQoyQQQyyyyQQoyoy 15 ooQQyyQQQyyQQoo
27 oQoooQooooQyoyQoyoyyyQQyQQQQoQ 16 QoQQyQyyyyQyQQoQ
28 yyyyyooyQyyyoyyQyyooyQoQoQQoQy 17 yooQyoyyQyyoyQooy
29 yyQoyQoyyQyQQoyooooyyQQyQyooQy 24 yQooyQyQQyooooyQQyQyooQy
30 oQQooQoQyQQoyoQQoQyQyQyQoQoooo 24 oooQoQyQQyoQQoyQQyQoQooo
31 oQQyQQyyQyQQoooyQQyyyQQQyyQQoy 25 oQQyQQyyyQQoooQQyyyQQyQQo
32 WAk9iHI4jVDlStyudwTNqE138kwan2 3 wkw
33 c43fIu1Mlz0K9hEVOgGcUdbeB5ksa7 3 cGc
34 CAbYcW5VqHjzFdIkH_61PM0TsyRuie 3 HkH
35 jInQnUvSayrJTsQWujovbbqW0STvoj 10 jvTWbbWTvj
36 iZDrvpUKgtj3FrZsZ4CLjrEgUdZzQG 11 ZUgrZsZrgUZ
37 ROgYUOu6er_DA7nB6UGquO1GUHC62R 11 RUOu6B6uOUR
38 Oh_be_a_fine_girl_kiss_me 9 e_i_l_i_e
39 8086_6502_6809_Z80 11 8086_2_6808
40 xcode_visualstudio_eclipse 11 ce_iutui_ec
41 word_excel_powerpoint_outlook 9 ol_opo_lo
42 abcdefghijklmnopqrstuvwxyz0123 1 3").