Klicken Sie hier für Probleme-> http://nabetani.sakura.ne.jp/hena/ord15subpalin/
Vergleichen Sie die beiden Zeichen, jeweils ein Zeichen, aus der Kombination des ersten und des letzten Zeichens. Wenn das n1ste und das n2ste Zeichen gleich sind, erhöhen Sie die Länge (ans) um 2. Suchen Sie nach dem gleichen Zeichen zwischen n1 + 1 und n2-1. (Schleife in der for-Schleife der Schleifenfunktion) Wenn das letzte n-te und n + 1 nicht gleich sind, addieren Sie 1 zur Länge. Zuerst war es spät, ohne mit Julia zu beschneiden, also versuchte ich es mit Nim und Ruby. Immerhin, wenn die Summe der aktuellen Länge (ans) und der Anzahl der verbleibenden Zeichen größer ist als die maximale Länge (Lüfter) bisher Nur (Fans <j-i + ans + 1) führen eine einfache Zweigjagd durch und fahren mit der Suche fort. Wenn ich nach der Schleife eine Pause in die for-Schleife einlege, wird sie viel schneller. 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 Manchmal ist es nicht viel schneller als Julia, aber in diesem Problem (Code) ist es um Größenordnungen schneller.
#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 Ich habe das Gefühl, dass mehr Ruby-Benutzer unter den Teilnehmern von "How to write" waren. Ich lese die erste Ausgabe von "Object-Oriented Scripting Language Ruby". Ich hatte den Eindruck, dass Delphi für GUI-Programme bequemer ist und das Lösen von Rätseln langsamer ist. Ich habe es ab und zu anstelle von awk benutzt. Aufgrund eines anderen Problems war es jedoch erheblich schneller als Julia, als ich es unter Bezugnahme auf den Code anderer Leute schrieb Diesmal habe ich es auch versucht. Dieses Problem war nicht sehr früh vor dem Beschneiden, aber nach dem Beschneiden passt es gut zu Julia. Aus der Sicht der Ruby-Benutzer mag es altmodisch und überflüssig sein, aber ich werde das beschnittene veröffentlichen.
#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
Eine andere Lösung (Prolog) Dies ist eine Methode, um die längste Kombination desselben Zeichens in der Zeichenkette gegenüber der ursprünglichen Zeichenkette zu finden. Es ist eine Wiederholung des Denkmals. Wenn n1 und n2 der beiden Zeichenfolgen gleich sind, erhöhen Sie die Länge R um 1 und vergleichen Sie n1 + 1 und n2 + 1. Wenn sie unterschiedlich sind, beim Vergleich von n1 + 1th und n2nd und beim Vergleich von n1st und n2 + 1 Fügen Sie den längeren und R hinzu. Wenn Sie es wie Code schreiben f (n1, n2) = wenn n1 == n2: f (n1 + 1, n2 + 1) + 1 # lösen / 4 4. Abschnitt sonst: max (f (n1 + 1, n2), f (n1, n2 + 1)) # lösen / 4 5. Abschnitt Verwenden Sie für den Memokonvertierungsteil den Funktor, um ein Memo des zweidimensionalen Arrays (F) zu erstellen. Im dritten Abschnitt von lösen / 4 wird dieser Wert verwendet, wenn er im Memo (nonvar (R1)) geschrieben ist. data / 4 wird sowohl zum Schreiben als auch zum Lesen von Memos verwendet.
%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").
Recommended Posts