😈

Malbolgeで何か1文字出力する

2023/12/01に公開

Ruby

esolang

Malbolge

tech

はじめに

この記事は、Qiita esolang Advent Calendar 2023 の1日目の話題です。

背景

Malbolgeとはesolangの1つで、敢えてプログラミングが難解となる仕様で作成された言語です。
※参考: WikipediaのMalbolgeの記事

ある日、github上で「ただ a を出力する」というコードを募っているリポジトリpurpleblueslime/aの話を目にしました。ということで、折角なのでプルリクを送るためにMalbolgeのコードを考えましたので、今回はその話をまとめました。

※注: 他の言語でプルリクを送ろうと考えている方は「1人1言語まで」ということにご注意ください。

環境

今回、以下の環境で動作確認を行ってます。

OS
WSL1(Windows10)上のUbuntu18
Malbolge実行系(オフライン)
こちらのCソースコードをgccによりコンパイルしたバイナリ
Malbolge実行系(オンライン)
Try It Online
独自コンバータ
記事「難解言語 Malbolge でラクして FizzBuzz」で紹介したRubyで書いた独自コンバータ

実装内容

実装コード

ということで、実装した「ただaを出力する」Malbolgeのコードは次の通りです。

a.mal

(&aN$

なお、実行確認はTry It onlineの実行例でも行っています。

このコードは、「環境」の章で紹介した独自コンバータに DRPED という入力を与えて作成したものです。

実装方針

記事「難解言語 Malbolge でラクして FizzBuzz」で、固定メッセージの出力は実現できているのですが、これは数百文字対応用なのでかなりコードが長くなってしまいます。そこでまず、なるべく短くコードを組む方針とします。
また、どのような状況で実行されるか分かりませんので、入力処理の結果をあてにするコードも避けます。この2点を基本とします。

ここで、コードの説明は「環境」の章で紹介した独自コンバータへの入力 DIRCPGEN の8文字種で書いていくことにします。コンバータ冒頭のコメントにも簡易説明がありますが、次のような処理に対応しています。

D ( j ): D=[D]
Dレジスタの指すアドレスのデータでDレジスタを置き換え
I ( i ): C=[D]
Dレジスタの指すアドレスのデータでCレジスタを置き換え
R ( * ): A=[D]=rotr1([D])
Dレジスタの指すアドレスのデータを1桁右ローテートシフトして同アドレスのデータ、Aレジスタを置き換え
C ( p ): A=[D]=crazy(A,[D])
Aレジスタのデータ、Dレジスタの指すアドレスのデータをcrazy演算して同アドレスのデータ、Aレジスタを置き換え
P ( < ): putc(A)
Aレジスタのデータを文字コードとして1文字出力 ( mod 256 で考える )
G ( / ): A=getc()
1文字入力し、その文字コードの数値でAレジスタを置き換え
E ( v ): exit()
プログラム終了
N ( o ): nop()
何も行わない

さて、そうすると最短のコードとして考えられるのは DRPE あるいは DCPE です。

先頭の D は冒頭で紹介した以前の記事でも説明した通り、C,Dレジスタの値をずらすために必要です。次に、出力用のデータをAレジスタに設定するには R,Cのどちらかが必要です。そして P による出力の後、Eによる終了を行わないとプログラムが暴走してしまいます。

そういう意味で最短4文字なのですが、そのいずれの4文字コードも a の出力にはなりません。

ということで、5文字以上のコードで a を出力するものを探索する必要が出てきます。Malbolgeはコード内の位置によって、同じ処理を示す命令を表す文字がずれていきますから、たとえ処理のシーケンスが ( nopであるNを除いて ) 同じであっても、Aレジスタに作り出されるデータは様々変化していきます。それを利用して、ちょうど a を出力するコードをうまいこと作り出そうということです。

探索

さて、では探索を行うわけですが、今回は短いコードを目指すため、「末尾2文字を元に先のメモリ領域を埋める」という挙動が効いてきます。なぜなら、D命令で置き換わったDレジスタの指すアドレスが、末尾よりも後になるからです。
このことを意識した上で、さらに以下の点に留意してパターンを絞り込みます。

最初のDのタイミング
1文字目にDを置いた場合、Malbolgeコードとしては ( ( ASCII 40 ) のため、C,Dレジスタの差 +40 が生まれます。
ここで D の前に置く N は ( Dに対応するMalbolgeコードのずれから ) Dレジスタの値の減少に、D の後に置く N は ( 次の有効な命令までスキップが入ることから ) 実質Dレジスタの値の増加に働き、同居すると効果が相殺します。
つまり、D の前後ともにNを置くパターンは考慮する必要がなく、正規表現で N*D または DN* という方側に置くパターンが探索の選択肢となります。
Aレジスタを操作する命令
R,C の2命令が候補となりますが、このうちRはそれまでのAレジスタの値に影響されないため、何度も使う意味がありません。逆にCはAレジスタの値を使うので、使う程にバリエーションが増します。
さらに、追加のCの現れるタイミングや、コード全体の長さ ( 埋められるメモリの内容に影響 ) の調整も加味し、色々 N (nop) を挟み込むことも考慮すると、[RC][CN]* が探索のパターンとなります。
末尾
既にコード全体の長さの調整は前項で考慮しているため、P,E 含めた末尾は長さを固定して考えます。
P→Eの途中は無害な命令 D,R,C,N を、Eの後は ( 既に実行終了しているので ) 任意の命令 ( D,I,R,C, P,G,E,N ) を配置できる点と、末尾2文字が先のメモリ領域の内容を決める点を加味すると、探索のパターンは、PE, P[DRCN]E, PE[DIRCPGEN], PE[DIRCPGN][DIRCPGN], PE[IPG]E で十分なことが分かります。

後は、短いコード長から順にパターンを網羅しつつ、出力される文字を調べていくことになります。が、せいぜい千,二千パターンもあれば ( 確率1/256と見て ) aを出力するコードが見つかるだろうと考えて、実際にMalbolge実行系を使ってコードを逐一試すのが話の早い探索法になります。

今回、ひたすら変換→実行のコマンドを呼び出すRubyコードで8文字を上限として、約2,600パターン探索するスクリプトを以下のように作成しました。なお、実行時の作業ディレクトリに、独自コンバータ malconv.rb と、実行系 mal.exe を置く想定です。( 各パターン毎に実行するコマンドは、echo パターン | ruby ./malconv.rb | ./mal.exe となります )

search_a.rb

MALCONV_RB = './malconv.rb'
MAL_EXE = './mal.exe'
T4s = [
  [ 'PE' ],
  [
    *'DRCN'.chars.map{|c| "P#{c}E" },
    *'DIRCPGEN'.chars.map{|c| "PE#{c}" }
  ],
  [
    *'DIRCPGN'.chars.flat_map{|c1|
      'DIRCPGN'.chars.map{|c2|
        "PE#{c1}#{c2}"
      }
    },
    *'IPG'.chars.map{|c| "PE#{c}E" }
  ],
]
mode = case ARGV[0]||'default'
  when 'no-stop'; 1
  when 'code-only'; 2
  else; 0
end

4.upto(8){|s|
  2.upto([s-2,4].min){|s4|
    T4s[s4-2].each{|t4|
      1.upto(s-s4-1){|s1|
        ( s1==1 ? [ ?D ] : [ ?N*(s1-1)+?D, ?D+?N*(s1-1) ] ).each{|t1|
          s2=1
          'RC'.chars{|t2|
            s3=s-s1-s2-s4
            %W(C N).repeated_permutation(s3){|r|
              t3=r.join
              t=t1+t2+t3+t4
              if mode == 2
                puts t
              else
                os=`echo #{t} | ruby #{MALCONV_RB} | #{MAL_EXE} /dev/stdin`.bytes[0]
                puts "#{t} : #{os}"
                exit if os==97 && mode==0
              end
            }
          }
        }
      }
    }
  }
}

これにより、DRPED が最短のコードとして探索できます。まあ実は20パターン目位に見つかってしまうので 2,600パターンも試すまでもなくすぐに終わるのですが、全パターン試すために実行時のコマンドライン引数によって挙動を調整できるようにもしています。
※code-onlyは出力結果を調べずに単に全パターンを列挙するだけ、no-stopはDRPEDが見つかった後も全パターンの調査を続ける挙動です。

おわりに

ということで、文字数が少ない場合はそれほど複雑でない探索でMalbolgeコードを実装することができることが分かるかと思います。

最初に Dレジスタをずらして…といった一連の動きを考える上でも、基本として良い題材になるのではないでしょうか。