0015 - Palindrome

この問題は色々なテクニックの宝庫かもしれない。
色々なネタバレを含むので、解けてない人は先にRepeat、Min digitあたりを解いておくと良いかも。
ヒント２以降は、「ヒントのヒント」と「ヒントの答え」みたいな感じで複数行に分けて書いているので、１行目から少しずつ読んで考えるのもいいかも。
各ヒントに対応するコードは下の方に書いてあるのでそれも参考に。。

ヒント１（白文字）（14 line）
先頭の文字を末尾に持って行き、比較し、一致していれば消し、そうでなければ違うことを表すマークを置く。奇数長のときは１文字余るので、例外処理する。
ヒント２（13 line）
「$00:0$0」で 4l 使ってるのを 2l に減らす。
0 と 1 のエンコード方法を工夫する。
0→oo、1→o みたいなエンコードをすることで 「o0:0o、o1:1o」の 2l に減らせる。
さらに「$0:」「$1:」も 1l に圧縮できる。
そのかわり、oにエンコードするために 2l 増える。
ヒント３（12 line）
末尾の一致判定に 4l 使っているのを 2l+1l に圧縮するための天才アイデアがある。
oを右に持って行くときに通過したbitを反転してやると末尾での判定が「一致してるか？」から「0ならOK、1ならNG」とできる。（ooとoに変換した恩恵）
ヒント４（11 line）
o と x を別のものにすることで、「oo:o」と「xx:x」をまとめる。
括弧列テクを使う。
「o → （）」「x → （（））」としてやることで、「)(:」にまとめられる。
ヒント５（10 line）
「^（）:^」を削る
^ を （（）） に変えてやると「)(:」により （（））（） は （（）） になる。
さらに「x → （（（）））」としてやるとちゃんと yes/no 判定もできる。
括弧列テクはすごい。
ヒント６（9 line）
終了処理を 1l に圧縮する
なにかの代わりにyesとnoを文字として使う
（）をyesnoかnoyesにする
あとは答えが yes のときと答えが no のときで yesの個数 - noの個数が 2 変わるように出来れば微調整すれば完成。
括弧列に「)(:」をすると深い方の括弧だけが残るのを利用して、一度no判定されたら括弧を吸収し続けられるのとかも使うとゴミを消せる。
このパートは難しいしコードもカオスになるので、自力で頑張って。

別解

白文字
真ん中から消していく方針でも9 lineいけるらしい。
文字を２倍すると奇数文字の場合もうまくいく。
括弧列を駆使すると9lineに
下の方に9line解を。
ヒント（8 line）
「（）」のかわりに「no」を使って「（（（）））::no」を削ります。
その上で障害になるのは２点「::yesがあるとnoのときにも終了規則を書く必要がある」と「残るのが（）でなく（（（）））である」点です
「::yes」は、２文字を削除するときにyesを追加し、まだ残ってるならyesを消して続行、みたいにやると「::」を使わずにすみます。（yesを消す行は増えますが、xはいらなくなります。）
「（（（）））」の方は、カッコの相殺は「max」を取る操作なので、maxが３ではなく１になるようにしたいです。
ただし１は「（）」かそれを連結したものしかなく、０は空文字列だけなので、元の文字列の'0','1'を区別できません。
そこで、0,1 には -1, -2（ちょっと違うけど）などを使います。
つまり、「）（」や「））（（」です。

以下、コード (14,を上から順に)
↓
↓
↓
↓
↓
↓
↓
↓
↓
↓
↓
↓
↓
↓
↓
↓
↓
↓
↓
↓
↓
↓
↓
↓
↓
↓
↓
↓
↓
↓
↓
↓
↓
↓
↓
↓
↓
↓
↓
↓
↓
↓
↓
↓
↓
↓
↓
↓
↓
↓
↓
↓
↓
↓
↓
↓
↓
↓
↓
↓
↓
↓
↓
↓
↓
↓
↓
↓
↓
↓
↓
↓
↓
↓
↓
↓
↓
↓
↓
↓
↓
↓
↓
↓
↓
↓
↓
↓
↓
↓
↓
↓
↓
↓
↓
14 line

移動
$00:0$0
$01:1$0
$10:0$1
$11:1$1
.
OK/NG判定
0$0:
1$1:
0$1:x
1$0:x
.
奇数長のときの例外処理
$0:
$1:
.
xがあるかないかで判定
xx:x
$x::no
$::yes
.
カーソル生成
:$

↓
↓
↓
↓
↓
↓

13 line

o0:0o
o1:1o
.
0oo:
1oo:x
0o:x
1o:
.
^0:^oo
^1:^o
^o:^
.
xx:x
^x::no
^::yes
.
:^

↓
↓
↓
↓
↓
↓

12 line

o0:1o
o1:0o
.
oo:o
0o:
1o:x
.
^0:^oo
^1:^o
^o:^
.
xx:x
^x::no
^::yes
.
:^

↓
↓
↓
↓
↓
↓

11 line

()0:1()
()1:0()
.
)(:
0():
1():(())
.
^0:^()()
^1:^()
^():^
.
^(())::no
^::yes
.
:^

↓
↓
↓
↓
↓
↓

10 line

()0:1()
()1:0()
.
)(:
0():
1():((()))
.
(())0:(())()()
(())1:(())()
.
((()))::no
(())::yes
.
:(())

↓
↓
↓
↓
↓
↓
↓
↓
↓
↓
↓
↓

別解
9 line (xllend3氏の解)

0:(())(())((()))
1:(()())(()())((()))
((()))(())(():(())((()))(()
((()))(()())(():(()())((()))(()
(())(())((())):
(()())(()())((())):
)(:
((()))::no
::yes

括弧列を置換して読みやすくした版↓

0:[a][a]x
1:[b][b]x
x[a][:[a]x[
x[b][:[b]x[
[a][a]x:
[b][b]x:
[a]:
[b]:
xx:x
x::no
::yes