Wed Mar 06 2019

sed で加算をする

sed は文字列を処理する editor だから int も無いので当然加算も減算も無い. けど文字列の操作でシミュレートすることは出来る. 今は10進数で0以上の整数だけを考える.

加算を今から実装したい. いきなりは難しいのでまずは +1 を実装する.

123+1 を今 123@ と書くことにする. @ という記号は、その手前の桁に +1 するよというマークである. だから例えば 123+10 は 12@3 と書ける. これを使うと桁上がりが簡単に表現できて良い.

1つの非負整数が10進数で stdin から与えられるとする:

echo 1999 | sed ???

このときに、末尾に @ を付け足せば表現としては正しく、可能ならばこの @ を取り除くことで普通の算数の +1 が出来る. そして @ の除去は普通に出来る. つまり 0-8 の範囲で 0@..8@ があったら 1@..9@ に置換すればよい. 9@ は桁上がりで @0 になる. また、最上位に @ が来た場合は、仮想的に一番上の桁に 0 があるとして 1 に置換すればよい.

あとはこの置換を @ がある間、ループしてあげればよくて結局

s/$/@/
:a
s/^@/1/
s/9@/@0/
s/8@/9/
s/7@/8/
s/6@/7/
s/5@/6/
s/4@/5/
s/3@/4/
s/2@/3/
s/1@/2/
s/0@/1/
/@/ba

となる. 確認をしたければ上を add1.sed などと保存して

   echo 1999 | sed -f add1.sed
2000
   seq 0 20 | sed -f add1.sed
1
.
.
21

と確認できる.

となると -1 も難しくない.

今扱う数は非負整数だけなので 0-1 = 0 とすることにして、他は適当にやっぱり置換してあげればよい. さっきは @ を使ったので区別のために今度は % を使うことにする. とすると気をつけるべきは 0% で、これは %9 にしてやる. あとは入力が 1 以上であるようにしてやれば問題は起きない. というわけで

s/$/%/
:a
s/^0%$/0/g
s/0%/%9/
s/1%/0/
s/2%/1/
s/3%/2/
s/4%/3/
s/5%/4/
s/6%/5/
s/7%/6/
s/8%/7/
s/9%/8/
/%/ba
s/^0*//g
/^$/c0

これで良い.

以上で道具が揃ったので足し算が出来る. 入力は非負整数が空白区切りで入力されるとする. 1つめを +1 して2つめを -1 するのを2つめが 0 になるまで繰り返せば1つめが2つの和になっている.

n + m = (n+1) + (m-1)
n + 0 = n

このことと今さっき定義した +1 と -1 を組み合わせれば良い. ただし -1 する数は空白の後ろにあるようにするので少し修正する.

: loop

# 2つめが 0 なら1つめを出力して終了
/.* 0$/{
    s/ .*//
    b
}

# 1つめを +1, 2つめを -1 する
s/ /@ /
s/$/%/

# +1 の処理
: add1
s/^@/1/
s/9@/@0/
s/8@/9/
s/7@/8/
s/6@/7/
s/5@/6/
s/4@/5/
s/3@/4/
s/2@/3/
s/1@/2/
s/0@/1/
/@/b add1

# -1 の処理
: sub1
s/ 0%$/0/g
s/0%/%9/
s/1%/0/
s/2%/1/
s/3%/2/
s/4%/3/
s/5%/4/
s/6%/5/
s/7%/6/
s/8%/7/
s/9%/8/
/%/b sub1
s/ 0*/ /g
s/ $/ 0/g

# これを繰り返す
b loop

これを add.sed として,

   echo "10 100" | sed -f add.sed
110
   echo "999 0" | sed -f add.sed
999
   echo "999 1" | sed -f add.sed
1000
   echo "999 2" | sed -f add.sed
1001

良さそう.

A - はじめてのあっとこーだー（Welcome to AtCoder）

こいつを解いてみる: atcoder.jp/contests/practice/tasks/practice_1

3つの整数の和と、1つの文字列をそのまま出力すればよい. 文字列についてはともかく、和を出力しなければいけないので初心者殺しだ. でも2つの和を得ることは出来たので、いい感じにやれば3つの和も得ることが出来るはずだ.

あとは入出力にだけ気をつければ

x
N
s/\n//

: loop1

/.* 0$/{
    s/ .*//
    b exit-loop1
}

s/ /@ /
s/$/%/

: add1
s/^@/1/
s/9@/@0/
s/8@/9/
s/7@/8/
s/6@/7/
s/5@/6/
s/4@/5/
s/3@/4/
s/2@/3/
s/1@/2/
s/0@/1/
/@/b add1

: sub1
s/ 0%$/0/g
s/0%/%9/
s/1%/0/
s/2%/1/
s/3%/2/
s/4%/3/
s/5%/4/
s/6%/5/
s/7%/6/
s/8%/7/
s/9%/8/
/%/b sub1
s/ 0*/ /g
s/ $/ 0/g

b loop1
: exit-loop1

G;s/\n/ /

: loop2

/.* 0$/{
    s/ .*//
    b exit-loop2
}

s/ /@ /
s/$/%/

: add1_2
s/^@/1/
s/9@/@0/
s/8@/9/
s/7@/8/
s/6@/7/
s/5@/6/
s/4@/5/
s/3@/4/
s/2@/3/
s/1@/2/
s/0@/1/
/@/b add1_2

: sub1_2
s/ 0%$/0/g
s/0%/%9/
s/1%/0/
s/2%/1/
s/3%/2/
s/4%/3/
s/5%/4/
s/6%/5/
s/7%/6/
s/8%/7/
s/9%/8/
/%/b sub1_2
s/ 0*/ /g
s/ $/ 0/g

b loop2
: exit-loop2

N
s/\n/ /g

お疲れ様でした.

gsed has e flag in s command.

GNU sed の s コマンドはフラグに e というのを指定できる.

   echo 9 13
9 13

   echo 9 13 | sed 's/\(.*\) \(.*\)/echo $((\1+\2))/'
echo $((9+13))

   echo 9 13 | sed 's/\(.*\) \(.*\)/echo $((\1+\2))/e'
22

お疲れ様でした.