CASL2で回文判定

ところで、「回文」をご存知ですか？「しんぶんし」などの前後から読んでも同じ言葉になる文章のことをいいます。回文は、前と後ろからの読みを同じにすることに加え、文章の意味も通じるように考えないといけないため、とても頭を使う作業になります。


今回は、CASL2を使用して、コンピュータが回文をどのように判定しているかについて、その方法の一例として見てみたいと思います。


とはいえ、COMET2程度のコンピュータでは、文字の並びが回文かどうかは判定できても、意味が通じるかどうかまでは判定できないため、本記事では回文の意味については考慮しないプログラムを紹介します。

回文判定

例1: 回文「ABCDEDCBA」の判定

1	MAIN	START
2		CALL　PAL
3		RET
4
5	PAL	LAD　GR1, 0	;前半文字の現在位置
6		LD　GR4, STRLEN	;回文の長さ
7	LP1	LAD　GR4, -1, GR4	;回文の長さをデクリメント
8		LD　GR2, STR, GR1	;回文前半の文字
9		LD　GR3, STR, GR4	;回文後半の文字
10		LAD　GR1, 1, GR1	;前半文字の現在位置をインクリメント
11		CPA　GR2, GR3	;前半と後半の文字を比較
12		JZE　MATCH	;同じ文字なら"MATCH"行へ
13		OUT　FAL, BOOLEN	;違う文字なら"偽"判定
14		RET
15	MATCH	CPA　GR1, GR4	;前半文字位置<後半文字位置　であるか判定
16		JMI　LP1	;前半文字位置<後半文字位置　であるならラベルLP1へ
17		OUT　TRU, BOOLEN	;前半文字位置<後半文字位置　でないなら"真"判定
18		RET
19
20	STR	DC　'ABCDEDCBA'	;回文
21	STRLEN	DC　9	;回文の長さ
22	TRU	DC　'TRUE_'	;回文のとき
23	FAL	DC　'FALSE'	;回文でないとき
24	BOOLEN	DC　5	;判定文言の長さ
25		END

シミュレータにそのままコピー&ペーストで使えます。

解説

回文判定は、最初の文字と最後の文字が同じか否か、最初から2番目の文字と最後から2番目の文字が同じか否か...というように順番に文字の違いを判定していきます。


文字の最初と最後の比較から始まって、参照する文字位置が真ん中で交わったときに終了します。真ん中の文字位置まで参照が終了した場合は、回文であるため、「真」を示します。


一方で、真ん中の文字位置まで参照する途中で文字に違いがあった場合は、その時点で「偽」を示します。


このプログラムの場合は、「TRUE_」と「FALSE」をそれぞれ真と偽を指す情報としてディスプレイに表示させるように組まれています。


とりわけ、判定した文字列が、真か偽のいずれかを表せればいいため、ディスプレイに表示する文字は、好きな表示に変えてしまって大丈夫です。


「TRUE_」の最後の文字「_ (アンダースコア)」は、「FALSE」と文字数を合わせるためにつけ加えています。ここでは、アンダースコアを使用していますが、スペースに置き換えても大丈夫です。


文字数を合わせないと、プログラム上の不整合があるため、その穴埋めにこのように記述してあります。どのような不整合かについては、一旦、横に置いておきます。


【回文判定の方法】



ここで、トレースを見てみましょう。



【例1のPAL(5～18行)のトレース】


文字列「ABCDEDCBA」は、回文のため、答えは「真」を示す「TRUE_」が表示されます。


したがって、正しい答えになっていますね。

回文とは？

回文とは、前から読んでも、後ろから読んでも同じ言葉として成立する文章のことをいいます。


例えば、「しんぶんし」や「イカした歯科医」などが挙げられるでしょう。


回文を考える際は、意味が通るように工夫する必要もあるため、大変に頭を使う文章でもあります。


今回プログラムで判定した回文「ABCDEDCBA」は、意味が通らない文字列のため、厳密には回文とはいえません。


しかし、意味が伴うか否かを抜きにしても、回文とは、前から1番目と後ろから1番目が同じ、前から2番目と後ろから2番目が同じ...というように前後の同一番目で同じ文字が対応することに変わりはありません。


したがって、簡易的に「ABCDEDCBA」を例に用いました。



確かな回文の例は下記のサイト様にたくさん載せられていますので、参考にしてみてください。


「言葉遊び『おもしろ回文』一覧 50選｜キッズの無料学習プリント素材」

最後に

今回は、回文の判定方法についてご紹介しました。


回文は、前と後ろから数えた同一番目の文字が同じか否かを確かめればいい、という処理です。


したがって、今回紹介したプログラムに拘(こだわ)らず、上記の処理を実現できればいいため、他のパターンのプログラムも考えてみてください。


それでは、続きはまた次回にご期待を！