CodeIQ《結城浩のスペーストーキー問題》に挑戦した(Python)

今回のは簡単だった

• 挑戦者求む！【アルゴリズム】スペーストーキー社の危機を救え！ by The Essence of Programming 結城 浩│CodeIQ

https://codeiq.jp/achievement/135

概要

以下のURLで動いている文字列の変換の仕組みを推定する

• http://spacetalky.textfile.org/api.cgi?input=INPUT

与えられた単語リストについて、変換後にそれらの単語になるような入力を求める。
変換できない場合は'X'を出力する。

文字列の変換の詳細

試しにAPIに文字列を投げるとランレングス符号化をしていることがわかった

• 連長圧縮 - Wikipedia

ランレングス符号化は文字列を文字とそれがいくつ続いたかという2つで符号化するものである
例えば以下のURLにアクセスすると'azabbc'という出力が返ってくる。
これは'a'がz(26)+b(2)文字連続し、次に'b'がc(3)回続いているということを表している。

• http://spacetalky.textfile.org/api.cgi?input=aaaaaaaaaaaaaaaaaaaaaaaaaaaabbb

このことから変換できない場合に気をつけて与えられたリストの単語を逆変換すればいいことがわかる。

変換できない条件

• 変換先の単語の長さが偶数でない場合には、ランレングス符号化の文字と長さのペアになっていないことがわかる
• 'abab'などのように同じ文字の連続が続いている場合も生成できない。これは'abab'を逆変換すると'aaaa'になってしまい、'ad'を変換したものと等しくなってしまうためである。ただし最後以外の長さが最大であるz(26)になっている場合は生成できる→'ezed'
• 逆変換したときに入力の最大長である1024文字よりも大きくなってしまう場合(与えられた単語リストは短いものしかなかったので考慮しないでもよい)

ソースコード

単語リストが標準入力に与えられた時に、逆変換した単語とペアで出力する

import sys
import string

def decode(text):
    L = len(text)
    if L % 2 != 0:
        return 'X'
    
    length = {}
    for i, c in zip(range(1, 27), string.ascii_lowercase):
        length[c] = i
    prev_len = 0
    prev_c = ''
    ret = ''
    i = 0
    while i < L:
        if prev_c != text[i] or prev_len == 26:
            prev_c = text[i]
            prev_len = length[text[i+1]]
            ret += prev_c * prev_len
        else:
            ret = 'X'
            break
        i += 2
    return ret

if __name__ == '__main__':
    for line in sys.stdin:
        line = line.strip()
        print '{}:{}'.format(decode(line), line)