Internet Problem Solving Contest 2015 M

M.py

# encoding: utf-8

from commands import getoutput
from math import sqrt

# numbers: DPテーブルっぽいもの。numbers[i]は数値iを作れるJSの最小コードをもつ。
# 生成される数を短くする都合上、numbers[0]とnumbers[1]は単体では数値にならないようになっている(後で変更)
numbers = ["[]", "!+[]"] + [""]*999;

# 0から9までを予め生成
for i in range(2, 10):
    numbers[i] = numbers[i-1] + "+!+[]"

# こっちのが最適
numbers[6] = "[!+[]+!+[]]*[!+[]+!+[]+!+[]]"
numbers[7] = "[!+[]+!+[]]*[!+[]+!+[]+!+[]]+!+[]"
numbers[8] = "[!+[]+!+[]+!+[]+!+[]]*[!+[]+!+[]]"
numbers[9] = "[!+[]+!+[]+!+[]]*[!+[]+!+[]+!+[]]"

# ファイル出力用のバッファ
stream = ""

# 関数createByJoinで用いる。string[i]はiを数値化する前の文字列(文字列から生成されているnumbers[i]を、また文字列化して数値化すると無駄が出来るため)
string = [""] * 1001

# 文字列としてa, bを連結
def joinAsStr(a, b):
    ret = ""
    if not a.startswith("+"):
        ret += "+"
    return ret + "{}+[+{}]".format(a, b)

# 掛け算
def mul(a, b):
    return "[{}]*[{}]".format(a, b)

# 3項の掛け算
def mul3(a, b, c):
    return "[{}]*[{}]*[{}]".format(a, b, c)

# 足し算
def add(a, b):
    if b.startswith("+"):
        b = "[{}]".format(b)
    return "{}+{}".format(a, b)

def sub(a, b):
    if b.startswith("!"):
        b = "[+{}]".format(b)
    return "{}-{}".format(a, b)
# 文字列を整数化
def Str2Int(s):
    return "+[{}]".format(s)

# 既に出来ている数値2つを文字列としてつなげることで新しい数値を生成する
def createByJoin():
    for i in range(10, 1001):
        idx_str = str(i)
        for j in range(1, len(idx_str)):
            if idx_str[j:].startswith("0") and idx_str[j:] != "0":
                continue
    
            a = int(idx_str[:j])
            b = int(idx_str[j:])
            if string[a] and string[b]:
                posstr = joinAsStr(string[a], string[b])
            elif string[a]:
                bs = numbers[b]
                posstr = joinAsStr(string[a], bs)
            elif string[b]:
                bs = numbers[a]
                posstr = joinAsStr(bs, string[b])
            else :
                posstr = joinAsStr(numbers[a], numbers[b])
            possible = Str2Int(posstr)
            if (not numbers[i]) or len(possible) < len(numbers[i]):
                numbers[i] = possible
                string[i] = posstr

# 既に出来ている数値2つを掛け合わせて新しい数値を生成する
def createByMul():
    for i in range(10, 1001):
        for j in range(2, int(sqrt(i))+1):
            k = i/j
            left = i - j*k
            possible = mul(numbers[j], numbers[k])
            if left != 0:
                possible = add(numbers[left], possible)
            if len(possible) < len(numbers[i]):
                numbers[i] = possible
                string[i] = ""

def createByAdd():
    for i in range(10, 1001):
        for j in range(2, i/2+1):
            k = i-j
            possible = add(numbers[j], numbers[k])
            if len(possible) < len(numbers[i]):
                numbers[i] = possible
                string[i] = ""
            
def createBySub():
    for i in range(10, 1001):
        for j in range(i+1, 1001):
            k = j-i
            possible = sub(numbers[j], numbers[k])
            if len(possible) < len(numbers[i]):
                numbers[i] = possible
                string[i] = ""
        

# 3回施工する。どちらかの関数で更新があった場合、他の関数でも更新されるかもしれないため
for _ in range(3):
    createByJoin()
    createByMul()
    createByAdd()
    if _ != 0:
        createBySub()

# 都合上リストやbool値になっていたnumbers[0], numbers[1]を単体でも数値になるように変更
numbers[0] = "+[]"
numbers[1] = "+!+[]"
numbers[174] = "[!+[]+!+[]+!+[]]*[+[+!+[]+!+[]+[+!+[]]]]+[+[+!+[]+[+!+[]]+[+!+[]]]][+![]]"

# i=0~1000についてnumbers[i]が75文字以下になっているかを調べる。ついでに、nodejsに突っ込んでassertするようのコードを生成する
count = 0
maxlen = -1
for i in range(1001):
    if len(numbers[i]) > 75:
        print "length {}: {} {}".format(i, len(numbers[i]), numbers[i])
        maxlen = max(maxlen, len(numbers[i]))
        count += 1
    else :
        print "{}:".format(i), numbers[i]
    stream += "console.log({})\n".format(numbers[i])

print "left: {}".format(count)
print "maxlen: {}".format(maxlen)
            
# nodejsに読ませてassertする。
with open("test.js", "wb") as f:
    f.write(stream)
    
#numbers[i]がちゃんとiを吐き出すかチェック。Pythonがエラーを履く場合はtest.jsが構文エラーを吐いている。
check = getoutput("nodejs test.js")
lines = check.split("\n")
now = 0
for i in range(1001):
    while not lines[now]:
        now += 1

    if lines[now] != str(i):
        print "found: {}".format(i)
    now += 1

# answer.jsに提出用ファイルを生成
stream = ""
for i in range(0, 1001):
    stream += "{}\n".format(numbers[i])
with open("answer.js", "wb") as f:
    f.write(stream)