オフラインどう書く第15回参考問題解答

問題はこちら->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
#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
#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
#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はメモの書き込みにも読み込みにも用います。

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