読者です 読者をやめる 読者になる 読者になる

37.50.48

%20 の ブログ

ferNANDo という言語で足し算をした。

ferNANDo という esolang(難解プログラミング言語)で A plus B problem という問題を解いた。
endless 問題のネタバレなので、自力で解きたい人は引き返して下さい(いないと思うけど)。

 

 

ferNANDo の命令は「入力を1文字読む」「1文字出力する」「2変数を NAND して変数に代入する」「変数が真のとき戻る」の4種類しかない。変数は01の値しか持たない。

この問題では、1~4桁の、桁数が固定されていない整数を読み取る必要があるので、スタックのようなものが必要だが、この言語には配列もスタックも無いので、自分でスタックのようなものを作る必要がある。スタックのようなものは、疑似コードで言うと、do{e=!d,d=!c,c=!b,b=!a;}while(a=input());という具合になる。「ループする毎に『値がどの変数に入っているか』がずれていく構造」と言ったほうが適切か。なお、b=aではなくb=!aとなっているのは、その方がコードが簡潔になるからである。

 

提出したコードでやっていることは、おおよそ以下の通り。

左側の整数を読み込む

スペースが来るまで入力を読んでスタックAに積む。文字コードが、数字は0011????、スペースは00100000なので、下から5ビット目を見れば数字かどうかが分かる。

右側の整数を読み込む

改行が来るまで入力を読んでスタックBに積む。改行の文字コード00001010なので、下から5ビット目を見れば数字かどうかが分かる。

足し算する

スタックA,Bから1桁ずつ取り出して、足し算して、その結果をスタックC(実際にはスタックAを反対向きに見たもの)に積む。
入力が何桁だろうと、スタックA,Bに最後に積んだものは(十進の)一の位なので、そこから順に計算していく。(二進の)1の位で足し算、2の位で足し算、4の位で足し算、8の位で足し算、足した結果が10以上なら「繰り上がりがある」という情報を持った上で10を引く(6を足す)。それをスタックAの反対側に積む。入力の最大桁数は4桁なので、(4桁未満の場合は0を補完して4桁とみなして、)これを4回繰り返すと上手くいく。

先頭の0を捨てる

出力する時は、先頭にある0は要らないので、スタックCの先頭から連続する0を取り出して捨てる。(この時、スタックCの底に目印(00001001でない値)をつける。)

出力する

スタックCの底の目印が来るまで、スタックCから1桁ずつ取り出して出力する。

EOF かどうかを判定する

EOF が来たら終了、そうでなければ最初に戻る。EOF が来たら終わるのは、Brainfuck,+[-ほげほげ,+]に似ていると思う。

 

最初に提出したコードは 1219 B、227 行であり、2番目に長い COBOL でさえ 222 B である。とにかく長い。

9
D 0
C 0
B 0
A 0
d 0
c 0
b 0
a 0
5
P L L
O K K
N J J
M I I
L H H
K G G
J F F
I E E
H D D
G C C
F B B
E A A
D 4 4
C 3 3
B 2 2
A 1 1
9 0 0 9 5 4 3 2 1
5
p l l
o k k
n j j
m i i
l h h
k g g
j f f
i e e
h d d
g c c
f b b
e a a
d 4 4
c 3 3
b 2 2
a 1 1
9 0 0 5 5 4 3 2 1
5
6
A A
a a
r A a
A r
a r
A a
s A q
A s
q s
A q
r s
B B
b b
q B b
B q
b q
B b
s B r
B s
r s
B r
q s
C C
c c
r C c
C r
c r
C c
s C q
C s
q s
C q
r s
D D
d d
q D d
D q
d q
D d
s D r
D s
r s
D r
q s
r B B
s C C
r s
r D
q q
q r
Q q q
r B q
B r
r q
B r
r B q
r r
s C r
C s
s r
C s
r C B
r q
r r
s D r
D s
s r
D s
1 A A
2 B B
3 C C
4 D D
A E E
B F F
C G G
D H H
E I I
F J J
G K K
H L L
I M M
J N N
K O O
L P P
M 1 1
N 2 2
O 3 3
P 4 4
a e e
b f f
c g g
d h h
e i i
f j j
g k k
h l l
i m m
j n n
k o o
l p p
6 6
6
5 5
5
R 0
S 0
T 0
5
4 T T
3 S S
2 R R
1 Q Q
T P P
S O O
R N N
Q M M
P L L
O K K
N J J
M I I
L H H
K G G
J F F
I E E
H D D
G C C
F B B
E A A
D 9 9
C 9 9
5 1 1
a 2 2
5 a
5 5
a 3 3
5 a
5 5
a 4 4
5 a
5 5
5
0 0 9 9 4 3 2 1
4 T T
3 S S
2 R R
1 Q Q
T P P
S O O
R N N
Q M M
P L L
O K K
N J J
M I I
L H H
K G G
J F F
I E E
H D D
G C C
F B B
E A A
5 4 3
5
0 0 0 0 9 0 9 0
9 H h L l 4 3 2 1
K 0
J 0
I 0
G 9 9
F 9 9
E 9 9
k 0
j 0
i 0
g 9 9
f 9 9
e 9 9
q 9 9
9

 

この記事を読んで、もっと短く書けるぞと思った人がもしいれば、是非提出してほしい(そもそも、この記事自体、誰向けなのか分からないが)。

Perl では「偽⇒0」は真だが「0⇒偽」は必ずしも真でない

Perl では、真偽値として解釈した値が偽であるならば、数値として解釈した値は 0 である。しかし、数値として解釈した値が 0 であっても、真偽値として解釈した値が偽になるとは限らない。

真偽+0 .''備考
0 0 '0'  
0b0 0 '0'  
0x0 0 '0'  
0e5 0 '0'  
0.0 0 '0'  
.0 0 '0'  
'0' 0 '0' 空でない文字列で偽になるのはこれだけ
'' 0 ''  
() 0 ''  
(123,456,0) 0 '0' コンマ演算子
(@a=()) 0 ''  
undef 0 ''  
11 11 '11'  
011 9 '9' 8進数
0b11 3 '3' 2進数
0x11 17 '17' 16進数
1e5 100000 '100000' 指数表記
123.456 123.456 '123.456'  
0.123 0.123 '0.123'  
.123 0.123 '0.123'  
'11' 11 '11'  
'011' 11 '011' 8進数として解釈されない
'0b11' 0 '0b11' 2進数として解釈されない
'0x11' 0 '0x11' 16進数として解釈されない
'0e5' 0 '0e5'  
'1e5' 100000 '1e5' 指数表記として解釈される
'0.0' 0 '0.0'  
'123.456' 123.456 '123.456'  
'0.123' 0.123 '0.123'  
'.123' 0.123 '.123'  
'0abc' 0 '0abc'  
'123abc' 123 '123abc'  
'abc' 0 'abc'  
(0,123,456) 456 '456' コンマ演算子
(@a=(0)) 1 '1'  
(@a=(123,456,0)) 3 '3'  

AtCoder での Perl golf に関するメモ

最近、AtCoder の問題を(ゴルフで)解き始めた。それに関するメモ。気が向いたら追記する。

 

N
$_**=3,print$_,$/for<>
$_=<>;print$_**3,$/
print+($_=<>)**3,$/
$_=<>**3;print$_,$/
print$_**3,$/for<>
print<>**3,$/

 

S
$_=<>;print s/abc/xyz/r
$_=<>;s/abc/xyz/;print
print s/abc/xyz/rfor<>
s/abc/xyz/,print for<>
print<>=~s/abc/xyz/r

 

X Y
print eval<>=~y/ /+/r,$/
<>=~$";print$`+$',$/
print<>!~$"+$`+$',$/

 

n
a1 a2 ... an
<>;$x+=$_ for split$",<>;print$x,$/
<>;$x+=$_ for<>=~/\d+/g;print$x,$/
<>;s/\d+/$x+=$&/gefor<>;print$x,$/
<>;<>=~s/\d+/$_+=$&/ger;print$_,$/
<>;$/=$";$x+=$_ for<>;print"$x
"
<>;print eval<>=~y/ /+/r,$/

 

ブログを始めるよりも前にあなごるで出題した問題

Anarchy Golf で自分が出題した問題について、ブログを始めたら何かしら書こうと以前から思っていたので書く。

 

850. A045718

素数±1 の数を 1 から 252 まで出力する問題。初めての出題だったので、簡単だし出題期間は1週間でいいよね・・・とか思って1週間にしてしまった。

861. tetration

テトレーションの問題。これを Whitespace で解こうとしたところ、普通に書くと TLE したので、2↑↑5 の代わりに 4**32768 の結果を出力して TLE を回避した。

889. 42

ultimate problem の入力と出力を逆にしたネタ問題。同じ入力に対して、異なる3つの出力が求められるので、何らかの乱数を使わないと解けない。しかも分岐が地味に面倒臭い。乱数を使わないと解けない問題として、123 という問題が既にあることは知っていたので、それとの違いをはっきり出すためにも、2回分岐するのはちょうど良かったと思う。Brainfuck では解けないと思っていたが、上手いこと cheat すると解けるらしい。

893. 32 div 0

Befunge のインタプリタの仕様を利用したネタ問題。Befunge の最短解が全体の最短解になる想定で出題した。exec を allow しているので、他の言語から Befunge を呼び出すこともできるようになっている。Befunge で最短解にたどりつくには、1Byte で 32 を作る方法を知らないといけない。

895. sandglass

入力を砂時計の形に変形する問題。あまり解答者が増えず、難易度調整の難しさを思い知った問題でもある。出題時に問題ページに署名をするようになったのはこの問題から。

902. 1 2 32 4 512

先頭が 1, 2, 3, 4, 5, ... , 100 になるような 2のn乗 の数を出力する問題。OEIS にもさすがにこれは載ってないだろと思ったら載ってて OEIS すげーってなった。

903. from 1 to 100

1 から 100 までの整数を改行区切りで出力する、とてもシンプルな問題。出題期間を初めてエンドレスにした。慣れていない言語に手を出すときに、まずは ASCII from 0x01 to 0x7f とセットでこれをやってみるといいんじゃないかな的な問題。一応、似たような問題として、Print out a lot _56K BEWARE_ という問題がある、ということを知ったのは出題したよりも後のことだった。

909. Convert hex to ASCII

16進数の入力に対して、最初の入出力例に示した変換を施す問題。FerNANDo で解くのがとても楽しかった。

913. differentiation

微分する問題。例外はあまり多くない方が良いと思い、なるべくシンプルに解けるような入出力にした。sed でも一応解いた。

914. antidifferentiation

不定積分する問題。こちらは敢えて例外を多くしてエンドレスで出題。面倒なのはよく分かっているので、解答者はあまりいないが気にしない。

916. FizzFizz

あの FizzBuzz をちょっと改変した問題。3のn乗の倍数なら Fizz をn回、5のm乗の倍数なら Buzz をm回出力する。この問題を出題した結果、FizzBuzz の解答も増え、何故か FizzBuzzBash の最短解が更新されるなどした。あと「アレンジ」が変な日本語だってことも分かった。



問題を解くのは楽しいので、出題者が増えれば嬉しいし、出題するのもそれはそれで楽しいので、今後も出題していきたいと思う。