[Ruby] How to write offline 15th reference problem solution

6 minute read

Problem is here -> http://nabetani.sakura.ne.jp/hena/ord15subpalin/

Compare the two characters while approaching them one by one from the combination of the first and last characters, If n1st and n2th are the same character, increase length (ans) by 2 Find the same character between the n1+1th and the n2-1th. (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 slow without pruning with Julia, so I tried it with Nim and Ruby, but 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 (Fans<j-i+ans+1) only Perform a simple branch hunt to advance 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 There are times when it is not much different from Julia, but in this problem (code), it is 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 think that the participants of “how to write” used Ruby more often. I am reading the first version of “Object-oriented scripting language Ruby”, I had the impression that Delphi was the most convenient GUI program and it was slow to solve puzzles. Sometimes I used it instead of awk. However, because of another problem, it was fairly quick compared to Julia by writing other people’s code as a reference, I also tried this time. In this problem, it was not so early before pruning, but after pruning it was a good game with Julia. It may be old-fashioned and redundant writing from the viewpoint of ruby users, but I will put 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 method finds the longest combination of the same characters in the original string and the reverse string. Memoization recursion. If the n1th and n2th characters of two strings are the same character, increase the length R by 1 and compare the n1+1th and n2+1th characters. If they are not the same, the n1+1th and the n2th are compared and the n1th and the n2+1th are compared. Add the longer one and R. If you write like a code f(n1,n2) = if n1==n2: f(n1+1,n2+1)+1 4th node of #solve/4 Else:max(f(n1+1,n2),f(n1,n2+1)) #solve/4 5th paragraph For the memoization part, make a memo of a two-dimensional array (F) using functor, If it is written in the memo in the third paragraph of solve/4 (nonvar(R1)), use that value. 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 abcdcba11      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").