俺が列名変換問題を解くと…

今回はLibreOfficeは直接関係ない話。

まずは俺の解き方の紹介から。

条件変更: 問題1と問題2は同時に公開されて出題されたものとする。アルゴリズムを考えればOK。Perl？知らない子ですね。

ある数の上位の桁が書かれていないときって、そこに0が書かれているって考えてもいいよね。基本的には。
例として3桁で揃えた場合、1なら001でもいいし…。
{ {A, B , C …,X , Y , Z } , {AA,AB,AC…AZ,BA,BB,BC…ZZ},{AAA,AAB,AAC…AAZ,ABA,ABB,ABC…AZZ, BAA ,…ZZZ} }
を1次配列にflattenしたやつ(以下arrとする)を、各桁{0,A,B…,Z}の27文字からなる普通の27進法として捉えてはいけない「はず」、本来ならば。
{ 000, 00A, 00B,00C 00Z, 0A0,0AA 0AB,…,0ZZ,A00, A0A, A0B, … ,ZZZ }
というパターンと一致しないから。まぁこういう形で求めておいて、後で、上記と一致しないものをカウントして差し引きして調整してもいいけどコードがごちゃごちゃしそう。似たような横着して昔音楽の筆記小テストでメジャーコードマイナーコードを書く問題でボロボロになっちゃった身としてはなおさら。

愚直に上記の群数列の何番目の群の、何番目の項目か、を計算して求めたほうが、間違いのないスッキリしたコードになりそう。各群内の何番目になるか、はA=0,B=1,Z=25として26進数扱いして求めても問題ない。

n桁の文字からなる文字列(3桁の文字列の例:XYZ)はarr内で何番目から何番目に存在しているのだろう？0スタートの列番号をxとして
{{0,1,…25},{25+1=26,25+2,…,25+26^2},{25+26^2+1=26+26^2,25+26^2+2,…,25+26^2+26^3}…}
だから
n >= 2のとき
S[n] = (∑(k=1からn-1) 26^k)
S[n+1] = (∑(k=1からn) 26^k)
と定めると
S[n] <= x < S[n+1]
か。
なお、n = 1のときは
0 <= x < 26
n >= 2においては、等比数列の和の公式から
S[n] = (26^n - 26) / (26 - 1)
S[n+1] = (26^(n + 1) - 26)/(26 - 1)
よって
(26^n - 26) / (26 - 1) <= x < (26^(n + 1) - 26)/(26 - 1)
(26^n - 26) <= (26 - 1) * x < (26^(n + 1) - 26)
26^n <= (26 - 1) * x + 26 < 26^(n + 1)
対数関数は単調増加関数だから26を底とする対数をとっても不等号の向きはそのままで
n <= Log ( (26 - 1) * x + 26, 26) < n + 1
となり
n = Floor( Log( (26 - 1) * x + 26, 26 ) )
とするとスッキリする。

後は x - S[n] を 26進数として処理すれば、xからアルファベットの列名を取り出せる。
あ、一応、xは0からカウントしていることに留意する。

例題を解いてみる。ええと、1から数えたときの16384列目は
0から数えたときはx = 16383で、Wolfram AlphaさんはC#とかと違ってLog関数の第一引数に底を取るからそのへん調整して
3桁の文字列だと分かるから
16383 - (26^3 - 26) / (26 - 1) = 15681
あとは、
15681 Mod 26 = 3
((15681 - 3) / 26) Mod 26 = 5
((((15681 - 3) / 26) - 5) / 26) Mod 26 = 23
0カウントだから
0 : A, 1 : B, 2 : C , 3 : D…
ええとXFD…かな？正解ですね。
逆にXFDを数値に直したいときは、3桁だから
(26^3 - 26) / (26 - 1) + 26^2 * 23 + 26^1 * 5 + 26^0 * 3 = 16383が求められる。1からカウントにしたければ1を足して16384

ここまでの議論を前座として

当該記事の前編と後編を通して読むと、こんなグチャグチャした場合分けしてない。うーん、最初の方で言ったとおり、そもそも各群の元の順番がぜんぜん違うんだから、普通に考えたらその計算方法では求められないはず。でも問題1の答えはあってるっぽい。検証してみるか。うーん場合分けが必要だった俺のやり方と何が違うんだ、どうしてこんなやり方で求まるんだ、どうして問題2で26進数扱いして戻しただけじゃ答えが一致しないんだ。なんで？どうして？

X、F、Dを後ろから一文字ずつ取得する。
D は アルファベットの4番目でかつ、後ろから1番目(0)なので「26の0乗 × 4 = 1 × 4 = 4」と評価する。
F は アルファベットの6番目でかつ、後ろから2番目(1)なので、「26の1乗 × 6 = 26 × 6 = 156」と評価する。
X は アルファベットの24番目でかつ、後ろから3番目(2)なので、「26の2乗 × 24 = 676 × 24 = 16224」と評価する。
3つの値を合計した「4 + 156 + 16224 = 16384」が答えとなる。

…結構時間がかかったが、しばらく後に重大なことに気がついた。自分はA=0とカウントしているから、D=3なのに、この文章では桁に"0"という文字があることを前提としているからD=4として扱っている。あとなぜ27進数じゃない！？もしかして。

俺は自分が使った式を見返してみる。
(26^3 - 26) / (26 - 1) + 26^2 * 23 + 26^1 * 5 + 26^0 * 3 = 16383
これはそもそも、
(26^2 + 26) + 26^2 * 23 + 26^1 * 5 + 26^0 * 3 = 16383
だったはず。
(26^2 + 26) + 26^2 * 23 + 26^1 * 5 + 26^0 * 3 = 16383
これを変形して、
26^2 * (23 + 1) + 26^1 * (5 + 1) + 26^0 * 3 = 16383
あとは、自分が、0スタートで考えたことを補正すると、
26^2 * (23 + 1) + 26^1 * (5 + 1) + 26^0 * (3+1) = 16384

つまり、文字列→数値は常に一致する。偶然に。
偶然だから第二問で逆変換を行おうとしたときに元に戻せなかったんだ。(= 罠)
例えば680とか当該記事の方法でちゃんとアルファベットに出来る？
きちんと場合分けして考える分には罠でも何でもない。

ここで、後編では、時間制限無しで考えてきてレビューをし合う、ということをやった、とある。もし自分が遠慮せずにレビューをするなら、その説明タイムのときに、「どうして逆変換じゃ出来ないのか？何が違うのか？」を考えたか？説明したか？が自分の最大の評価ポイントになるし、そこが説明に出てきてなかったら点数半分からスタートだろうな、と読みながら当時思った覚えがある。マサカリとかが怖かったから、当時は自分から関わろうとはしてなかった。別に当事者にそういうキツイ空気を作ろうという人は少なかっただろうし、ある程度は自分もそういう状況であることは理解していたけど、中々勇気がでなかったな。完全に当時の俺の問題。残念ながら性格・思考傾向は今もあんまりその辺変わってない。おっと愚痴になっちゃったな。ここらで記事を締めるか。