Problem 1008 Maya Calendar

PKU Problem 1008 Maya Calendar
http://acm.pku.edu.cn/JudgeOnline/problem?id=1008

• 問題説明
  • 入力
  • 出力
• 最短329Bコード
• 解説
  • 3つのメモリ違反
  • 入力月の判定
  • Input依存
  • まとめ
• 2006-11-12 追記： 最短286Bコード
  • 286Bコード解説

問題説明

マヤでは、日付を表す方法として、HaabとTzolkinという二種類の方法が用いられている。入力としてHaabでの日付が与えられるので、Tzolkinでの日付に変換して出力しなさい。

っていう問題。

入力

最初の行で日付の個数が与えられる。それ以降の行は、各々のHaabで表された日付となっている。

Haabで表記したとき、1年は365日で、19つの月から成っている。

それぞれの月は、

pop, no, zip, zotz, tzec, xul, yoxkin, mol, chen, yax, zac, ceh, mac, kankin, muan, pax, koyab, cumhu, uayet

と、それぞれ呼ばれていて、uayet以外のNumberOfTheDayはそれぞれ0〜19の20日間ずつ、uayetは特別で0〜4の5日間しかない月となっている。

このときの入力は

NumberOfTheDay. Month Year

と与えられる。

出力

最初の行で日付の個数を出力する必要がある。それ以降の行は、各々、入力をTzolkinに変換した日付を出力する。

Tzolkinで表記したとき、月という概念は無く、20日周期の名前と、13日周期の数字で表され、両方が一周したら1年経ったと考える。
即ちTzolkinで表したときの１年は、260日である。

名前のついた周期はそれぞれ、

imix, ik, akbal, kan, chicchan, cimi, manik, lamat, muluk, ok, chuen, eb, ben, ix, mem, cib, caban, eznab, canac, ahau

と呼ばれている。

数字のついた周期は、1から13までの数字になる。

このときの出力形式は

Number NameOfTheDay Year

とせよ。

最短329Bコード

以下のソースはgccでしか動きませんが、329Bとなっていて、今のところのPKU1008での最短となっています。

（ 2006-11-09 追記： id:Ozyさんにアッサリ抜かれました→ http://d.hatena.ne.jp/Ozy/20061109#p1 ）

y;
*s[]=
{
    "imix","ik","akbal","kan","chicchan",
    "cimi","manik","lamat","muluk","ok",
    "chuen","eb","ben","ix","mem",
    "cib","caban","eznab","canac","ahau"
};
r[]=
{
    13,6,11,7,10,2,1,15,16,3,18,4,0,12,9,8,5,17,14
};

main(d,k)
{
    for
    (
            puts(gets(k))
        ;
            ~scanf("%d.%s%d",&d,&k,&y)
        ;
            printf("%d %s %d\n",d%13+1,s[d%20],d/260)
    )
        d+=r[(k^'Spa5')%21]*20+y*365;
}

解説

3つのメモリ違反

実はこのコード、3つのメモリ違反を堂々とやってのけています。

1つは静的な配列rの末尾より先のメモリが0になっていることを利用した読み込みのメモリ違反。

1つはmain関数の第2引数の値が本来はargvになっていて、どこかの書き込み可能なメモリを指しているはずなことを利用した、getsによる書き込みのメモリ違反。

最後の1つは、mainの第2引数となるkの収納番地の直後のメモリ（main関数を呼び出した何らかの関数の作業用メモリとして使われているはず）を破壊しつつの、scanfによる書き込みのメモリ違反。

入力月の判定

19種類の月をそれぞれstrcmp等でチェックしていると、ソースコードの文字数が膨大になります。なので最短を目指す今回、この方法は用いません。19種類の月の、とある特徴のみを抜き出すことによって、それで判別を行います。入力は19種類しかないので、この19種類で重複のない特徴抽出方法なら、どんな方法を用いてもokです。

入力の文字列をint型に読み込むと、リトルエンディアンとしてメモリ内に読み込まれます。
これは入力文字列をchar型の配列cだったと仮定すると、以下の式で表されます。（頭4文字はkに収納されて、5文字目以降はメモリ違反を行う）

k = c[0] + c[1]*256 + c[2]*65536 + c[3]*16777216

となっていることを利用して、これを特徴化するために

(k^'Spa5')%21

とします。%21しただけだと19種類中に重複が生まれるので、xorすることで重複が1つも生まれなくなるような特別な値として見つけ出してきたのが'Spa5'という文字リテラルです（16進表記だと0x53706135、10進表記だと1399873845となります）。これを逆写像配列rで写像してあげると、その特徴がゼロオリジンで考えて何番目の月であるか？を見つけ出すことができます。

重複が1つも生まれないような文字リテラルは他にもいくつか存在しますが、'Spa5'という文字リテラルは優秀で、逆写像配列rのサイズが19と、私の知っている範囲では最小となります。これは本当は、'Spa5'の時の逆写像配列rのサイズは20必要なのですが、20番目の要素…つまりr[19]の値は0となるので、使われてない静的メモリの値が0になっていることを利用してメモリ違反を行うことで、プログラムの文字数を減らすことに成功しています。

（尚、r[12]は絶対にアクセスされることのないメモリなのですが、C言語のルール上空白にはできなかったので、仮で0を入れています）

Input依存

月の名称はいくつかありますが、2文字しかない月の名称は終端文字を含めて3バイト目までしか既知なことになりません。そのためscanfを呼び出す前は、kの値を4バイト目が0の状態で呼び出してあげる必要があります。

この改良を加えると1バイト増えて330Bとなります。（d+=r[(k^'Spa5')%21]*20+y*365 を k=d+r[(k^'Spa5')%21]*20+y*365 にしてprintfの参照変数をdからkに全部変える、とかね）

しかし、PKU側のチェックのためのInputファイルが、どうやら2文字の月の前は必ず3文字以下の月になっている様で、2文字の月を読み込む時は常に4バイト目が0の状態での呼び出しを行っている様です。そんなわけで、329Bで動くわけです。

まとめ

今回、gccのコンパイラ依存・環境依存・入力依存の3拍子そろったコードを書きましたが、これらを用いなくても、この原理に基づいてプログラムを組めば340Bには十分に収まると思われます。

2006-11-12 追記： 最短286Bコード

上記までの記事を公開後、1日と経たぬうちに、id:Ozyさんに更に短いコードを出されてしまいました。

参照 → http://d.hatena.ne.jp/Ozy/20061109#p1

そんなわけで、それを更に縮めてみました。前のコードはgccでしか通りませんでしたが、今度のコードはMicrosoftのCでしか通りません。

*a;
main(d,k,y)
{
    for(
            puts(gets(a=k))
        ;
            a[d]=strtok(--d?0:
"imix,ik,akbal,kan,chicchan,cimi,\
manik,lamat,muluk,ok,chuen,eb,ben\
,ix,mem,cib,caban,eznab,canac,ahau"
                ,",")
        ;
    );
    for(
        ;
            ~scanf("%d.%s%d",&d,&k,&y)
        ;
            printf("%d %s %d\n",d%13+1,a[-d%20],d/260)
    )
        d+="4,(<@H*0$ D8"[(k^'Spa5')%21]*5+y*365;
}

286Bコード解説

最後の行の文字化けっぽい文字列は、Ozyさんの日記で紹介されているのと同じものなので、そちらの解説を読んでください。

見て分かるとおり、配列を直に書くことをやめて1文字列化し、それをstrtokを用いて展開しています。gccの場合、strtok周りでうまく動いてくれないようです。そこでMicrosoftCでAcceptすることにしました。PKUのMicrosoftCの場合、グローバル変数宣言時のintを省けません。ただし*のつくポインタはintを省いて定義できます。そのため、3つの変数を全てmainの引数に収納します。

変数kに入っているはずのargvにあたるポインタ値を、ポインタaに収納して使うことで、書き込み可能領域を持って来ています。最初から分かっててメモリ違反していますので、argvの辺りは、その後のメモリだけ使えるという固定観念にとらわれず、前後どちらも使えるかもしれないということを頭においておきましょう。尚、文字列配列aを展開後にgetsを呼び出すと、せっかく展開したものが壊れてしまうので、getsは必ず前でなければいけません。

dの値は1からスタートするので、もしもa[d++]と書いてしまうと、後ほど参照する際にa[d%20+1]と書かなければならなくなってしまいます。そればかりか、strtokの初回呼び出し時の判定も、strtok(d-1?0:"...",",")のように書かなければならなくなります。そこでぶっちゃけまして、d++ではなく--dを用います。そうすることで、呼び出し時はa[-d%20]でよくなりますし、判定の時の引き算も不要になります。

329Bコードの時より更にメモリ違反が激しくなってしまいました。別に普段からメモリ違反する様なプログラムを量産しているわけではありませんので、あしからず。