「LINE × SUSI = ?」JJUG CCC 2017 Spring 箸袋の文字列合成コードを解説

はじめに

こんにちは、LINE Fukuokaのきしだです。

LINEでは、2017/5/20に行われた JJUG CCC 2017 Spring で寿司スポンサーをさせていただきました。
このときの模様は、次のブログでお伝えしています。

JJUG CCC 2017 Spring 登壇&協賛レポート : LINE Engineering Blog

このとき、写真のような箸袋で箸を配っています。

ここには次のようなコードが印刷されていました。

IntStream.range(0, 4)
         .mapToObj(idx -> new int[]{"SUSI".charAt(idx),
                                    "LINE".charAt(idx)})
         .map(p -> p[0]*p[0]*311-p[0]*49_578+p[1]*1320+1_876_615)
         .map(value -> (char) (value / 60))
         .forEach(System.out::print);

このコードを実行すると何が表示されるでしょうか、というのが問題だったのですが、このエントリでは、実際にこのコードがどうできているかを解説してみます。

まずは2文字の単語を別の単語に変換する

まず最初に「いぬ」を「ねこ」に変換することを考えてみましょう。
「いぬ」から「ねこ」に一文字ずつ変換するためには、下式のような関係が成り立つ関数f(x)を求めればいいということになります。

Javaでは文字がUTF-16で扱われます。それぞれの文字のUTF-16コードは次のようになっています。

い:12356
ぬ:12396
ね:12397
こ:12371

これをグラフ上で表すと次のような位置関係になっています。

そこで、これらを結ぶ直線がわかれば「いぬ」から「ねこ」への変換式が求まることになります。
直線の式を

とすると、次のような連立方程式を満たすa、bを探せばいいということになりますね。

さて、連立方程式の解き方ははるか昔に習ったような気がしますが、当時のような体力はないので手では計算したくありません。
そこで、今回はMaximaという数式処理ソフトを使って連立方程式を解いてみます。

Maximaでは、次のようなコマンドで方程式の解を求めることができます。

solve([a*12356+b=12397,a*12396+b=12371], [a,b]);

ソフトをインストールするほどでもないという場合は、Wolfram Alphaというサイトでも方程式の解を求めることができます。上記のコマンドがそのまま使えるので試してみるといいと思います。

早速 連立方程式を解いてみると次のような解がでました。

求める直線は、次のような式であることがわかります。

グラフを描いてみると、ちゃんと「い-ね」「ぬ-こ」の点に乗っていますね。

では、Javaのコードを書いてみます。

"いぬ".chars()
      .map(x -> -13 * x + 102142*4)
      .forEach(c -> System.out.print((char) (c / 20)))

割り算はまとめてやりたいので、表示のときにcharにキャストするついでにやっています。

JDK9のEarly Access版のJShellで試してみると、ちゃんと「ねこ」と表示されました!

jshell> "いぬ".chars().
   ...>        map(x -> -13 * x + 102142*4).
   ...>        forEach(c -> System.out.print((char) (c / 20)))
ねこ

JShellでは、式の中途半端なところで行を終わると改行ができるので、.で行を終わらせています。

3文字で考える

それでは、3文字の単語を別の単語に変換することを考えてみましょう。

「たまご」を「ひよこ」に変換してみます。「たまご」「ひよこ」の文字コードは次のようになっています。

た:12383
ま:12414
ご:12372
ひ:12402
よ:12424
こ:12371

先ほどと同じようにグラフにプロットすると、次のようになります。

直線では3つの点を通れなさそうですね。3つの点を通るには、線をグニョっと曲げる必要があります。つまり、グニョっと曲がった線を引ける関数を探す必要があるということです。
ここで、グニョっと曲がった線が引ける関数というと、二次関数というのが思い浮かびます。

次のような形の関数です。

「たまご」「ひよこ」の文字コードを二次関数の式のx,yにあてはめて連立方程式を作ります。

次のようなコマンドでMaximaが連立方程式を解いてくれます。

solve([
a * 12383^2 + b * 12383 + c = 12402,
a * 12414^2 + b * 12414 + c = 12424,
a * 12372^2 + b * 12372 + c = 12371
],[a,b,c]);

解が得れました。

つまり、次のような二次関数で点を結べるということです。

グラフでも確認できました。ちゃんとグニョっと曲がりながら三点を通ってますね。

Javaのコードで書いてみると次のようになります。

"たまご".chars()
       .mapToLong(x -> -719L*x*x + 17839207L*x - 2630351463L*42)
       .forEach(c -> System.out.print((char) (c / 14322)));

今回は値が大きくなるのでlongとして計算するようにしています。

JShellで実行すると、「ひよこ」と表示されました。

jshell> "たまご".chars().
  ...>          mapToLong(x -> -719L*x*x + 17839207L*x - 2630351463L*42).
  ...>          forEach(c -> System.out.print((char) (c / 14322)));
ひよこ

3つのデータで考える

ここまで、1つの単語から別の単語への変換を考えましたが、今回やりたいのは2つの単語を組み合わせて別の単語に変換することです。
試しに「まぐろ」と「すめし」から「おすし」に変換してみましょう。

それぞれの文字コードは次のようになります。

ま:12414
ぐ:12368
ろ:12429
す:12377
め:12417
し:12375
お:12362
す:12377
し:12375

グラフに描いてみると、次のようになります。

3次元のグラフで表しています。静止画だと位置関係がわからないので、アニメーションさせています。
この3点を通るのは直線ではなく平面になりそうです。

平面は次のような式で表せますね。

x,y,zに「まぐろ」「すめし」「おすし」それぞれの文字コードをあてはめて連立方程式を作ります。

次のようなコマンドでMaximaに解いてもらいましょう。

solve([
a * 12414 + b * 12377 + c = 12362,
a * 12368 + b * 12417 + c = 12377,
a * 12429 + b * 12375 + c = 12375
],[a,b,c])

解が得られました。

次のような式の平面が3点を通っているということですね。

グラフを描くと、確かに3点を通っているように見えます。

zipメソッドがほしい

無事に平面の式が得れたので、「まぐろ」「すめし」から「おすし」を求めるJavaコードを書いてみましょう。

ここで、"まぐろ".chars()というIntStream"すめし".chars()というIntStreamを結びつけてひとつのStreamとして扱いたいところです。

他の言語であれば、こういうときzipというメソッドが用意されていて、次のような感じで書くことができます。

zip("まぐろ".chars(), "すめし".chars())
 .map((x, y) -> 275 * 2 * x + 823 * y - 10734075)
 .forEach(c -> System.out.print((char) (c / 508));

実はJava 8でも開発段階では標準ライブラリにzipメソッドがありました。
しかし残念ながら、zipメソッドを導入することは見送られました。

Java 8では、オブジェクト型を扱うStreamの他に、int型を扱うIntStreamやlong型を扱うLongStreamなど基本型を扱うものも用意されています。zipメソッドが欲しいシチュエーションとして多いのがリストの処理時にインデックス番号を付けたいというものです。
そうすると、オブジェクト型だけを扱うzipメソッドの他に、オブジェクト型とint型を扱うzipも欲しくなります。他の組み合わせを使うことが多いという人もいると思います。

そのような要望に対応しようとするとintObjZipメソッドやlongObjZipなどたくさんの種類のzipメソッドが必要になってきそうです。この中から、ユーザーが本当に必要なものを見極めて提供する必要があります。
また、Java 10に入るかどうかは未定ですが、基本型と参照型を統一的に扱うSpecializationという仕組みがValhallaというプロジェクトで開発中です。List<int>などと書けるようになるものです。

このSpecializationが導入されれば、様々な型の組み合わせに対応したzipメソッドを用意する必要はなくなります。また、メソッド名を分けずにオーバーロードで実装していた場合には、Specializationが導入されたときにメソッドの解決があいまいになってしまう可能性があります。
このような事情から、zipメソッドはJava 8に含まないことが決められたのだと思います。

ないものは仕方ないので、どうにかして実装する必要があります。今回は限られた紙面に印刷することを前提としたコードなので、zipメソッドを独自に実装するわけにもいきません。外部ライブラリの利用も避けるべきでしょう。
そこで、文字列からcharAtメソッドで各文字を取り出します。通常なら普通のforループで書くところですが、ひとつの式として書きたかったのでIntStream.rangeを使います。

IntStream.range(0, 3)
        .mapToObj(idx -> new int[]{"まぐろ".charAt(idx), 
                                   "すめし".charAt(idx)})
        .map(p -> 275 * 2 * p[0] + 823 * p[1] - 10734075)
        .forEach(c -> System.out.print((char) (c / 508)));

2つの文字を扱うためにPairのような2値を扱えるクラスが欲しいところですが、Valhallaプロジェクトではユーザー定義基本型も導入される予定なので、こちらもValhalla待ちなのだと思います。仕方がないので、ここではint配列を使っています。

JShellで実行すると、たしかに「おすし」と表示されました。

jshell> java.util.stream.IntStream.range(0, 3).
  ...>                            mapToObj(idx -> new int[]{"まぐろ".charAt(idx), 
  ...>                                                      "すめし".charAt(idx)}).
  ...>                            map(p -> 275 * 2 * p[0] + 823 * p[1] - 10734075).
  ...>                            forEach(c -> System.out.print((char) (c / 508)));
おすし

JShellではjava.util.streamはデフォルトではimportされていないので、IntStreamを完全修飾名で記述しています。

LINE × SUSI = ?

さて、ここまで来れば冒頭のコードの作り方もわかってきたのではないでしょうか。
ここでバラしてしまうと、冒頭のコードの出力結果は「Java」です。ということで、「SUSI」と「LINE」から「Java」を求めるということになります。「SUSHI」ではないのは、「LINE」や「Java」と文字数を合わせたかったからです。空白文字で文字数を合わせるという手もありますが、印刷では わかりにくいと考えて「SUSHI」から文字数を削ることにしました。

これがそれぞれの文字コードです。

S:83
U:85
S:83
I:73
L:76
I:73
N:78
E:69
J:74
a:97
v:118
a:97

これを3次元グラフに描いてみると、次のようになります。

画像ではわかりにくいですが、4点を全部通る平面というのは難しそうです。面をグニョっと曲げる必要がありますね。
そこで2次曲面を使ってみます。今回は平面の式にx^2の項を追加してみます。

各文字のコードをx,y,zにあてはめて連立方程式を作成します。

この連立方程式をMaximaに解いてもらいましょう。

solve([
a * 83^2 + b * 83 + c * 76 + d = 74,
a * 85^2 + b * 85 + c * 73 + d = 97,
a * 83^2 + b * 83 + c * 78 + d = 118,
a * 73^2 + b * 73 + c * 69 + d = 97
],[a,b,c,d])

次のような結果がでました。

次のような式で表せる曲面が4点を通るということですね。

グラフを描いてみると、曲面の上に各点が乗っていることがわかります。

次のようなJavaコードを書けばよさそうですね。

IntStream.range(0, 4)
        .mapToObj(idx -> new int[]{"SUSI".charAt(idx), 
                                   "LINE".charAt(idx)})
        .map(p -> 311 * p[0] * p[0] - 8263 * 6 * p[0] + 22 * 60 * p[1] + 375323 * 5)
        .forEach(c -> System.out.print((char) (c / 60)));

定数式をちゃんと計算すると、次のようになります。

IntStream.range(0, 4)
        .mapToObj(idx -> new int[]{"SUSI".charAt(idx), 
                                   "LINE".charAt(idx)})
        .map(p -> 311 * p[0] * p[0] - 49578 * p[0] + 1320 * p[1] + 1876615)
        .forEach(c -> System.out.print((char) (c / 60))); 

JShellで動かすと、確かに「Java」と表示されました。

jshell> java.util.stream.IntStream.range(0, 4).
  ...>                            mapToObj(idx -> new int[]{"SUSI".charAt(idx), 
  ...>                                                      "LINE".charAt(idx)}).
  ...>                            map(p -> 311 * p[0] * p[0] - 49578 * p[0] + 1320 * p[1] + 1876615).
  ...>                            forEach(c -> System.out.print((char) (c / 60)));
Java

あとは長い数値を_で区切れば、箸袋と同じコードになります。

まとめ

これを応用すると、「KYURI」「SUSHI」から「KAPPA」を出力するコードなど、いろいろな文字列合成プログラムを作ることができます。

また、機械学習でデータの精度が足りないときにデータの2乗を追加するという手法がありますが、今回やったようにデータをグニョっとしてるというイメージを持つとわかりやすいかもしれません。

今回のエントリでは、簡単な数式を扱って ちょっと変なプログラムを組んでみました。
面倒な方程式もツールやWebサービスを使えば簡単に答えが得れます。最近は数式を見てないなぁという人も、たまにはこうやって数式で遊んでみるのもいいのではないでしょうか。(いつももっと難しい数式を見てる人は、単純な数式で頭を休めてください)