[RUBY] How to write offline 15th reference question answer

Click here for problems-> http://nabetani.sakura.ne.jp/hena/ord15subpalin/

Compare the two letters, one letter at a time from the combination of the first and last letters, If the n1st and n2nd characters are the same, increase the length (ans) by 2. Look for the same character between n1 + 1 and n2-1. (Loop in the for loop of the loop function) If the last nth and n + 1th are not the same, add 1 to the length. At first it was late without pruning in Julia, so I tried it with Nim and Ruby, After all, if the sum of the current length (ans) and the number of remaining characters is greater than the maximum length (fans) so far Only (fans <j-i + ans + 1) do a simple branch hunting to proceed with the search, If I put a break after the loop in the for loop, it became much faster. 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 Sometimes it's not much faster than Julia, but in this problem (code) it's orders of magnitude faster.

#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 I feel that there were more Ruby users among the participants in "How to write". I'm reading the first edition of "Object-Oriented Scripting Language Ruby" I had the impression that Delphi is more convenient for GUI programs and it is slower to solve puzzles. I used to use it instead of awk once in a while. However, due to another problem, it was considerably faster than Julia when I wrote it with reference to the code of other people, so I also tried this time. This problem wasn't very early before pruning, but after pruning it's a good match with Julia. From the point of view of ruby users, it may be old-fashioned and redundant writing, but I will post the pruned one.

#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

Another solution (Prolog) This is a method to find the longest combination of the same character in the character string opposite to the original character string. Memoization recursion. If the n1 and n2 of the two strings are the same, increase the length R by 1 and compare the n1 + 1 and n2 + 1th. If they are different, when comparing the n1 + 1th and n2nd, and when comparing the n1st and n2 + 1th Add the longer one and R. If you write it like a code f (n1, n2) = if n1 == n2: f (n1 + 1, n2 + 1) + 1 # solve / 4 4th section else: max (f (n1 + 1, n2), f (n1, n2 + 1)) # solve / 4 5th section For the memoization part, use functor to make a memo of the two-dimensional array (F), In the third section of solve / 4, if it is written in the memo (nonvar (R1)), that value is used. data / 4 is used for writing and reading memos.

%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").