在Python中優化死魚常數計算器

Question

死魚是一種深奧的「編程」語言（創建爲一個笑話，而不是完整的）。在這裏面，有一個單一的可變 - 在0初始化的整數 - 與4個操作：

• Counter += 1 = I
• Counter += -1 = d
• Counter = Counter * Counter = S
• print(counter) = O

儘管死魚通常使變量成爲一個字節，但爲了我的目的，它將是一個Python中的整數。我的程序試圖找到打印出任何給定數字的最快方式，即最少的命令。下面是一些例子

要達到10，

0> 1> 2> 3> 9> 10 = IIISI

達到15，

0> 1> 2> 4> 16 > 15 = iissd

我寫了一個簡單的蠻力程序，通過檢查i，d和s的組合來解決這個問題。以下是代碼：

#!/usr/bin/python 
# -*- coding: utf-8 -*- 


def baseN(num, base, numerals='abcdefghijklmnopqrstuvwxyz'): 
    return num == 0 and numerals[0] or baseN(num // base, base, 
     numerals).lstrip(numerals[0]) + numerals[num % base] 


def validCode(code): 
    for k in range(0, len(code)): 
     if code[k] == '!': 
      return False 
    return True 


def deadFish(code): 
    counter = 0 
    for l in range(0, len(code)): 
     cmd = code[l] 
     if cmd == 'i': 
      counter += 1 
     if cmd == 'd': 
      counter += -1 
     if cmd == 's': 
      counter = counter * counter 
    return counter 


def format(code): 
    counter = 0 
    chain = "0" 
    for m in range(0, len(code)): 
     cmd = code[m] 
     if cmd == 'i': 
      counter += 1 
     if cmd == 'd': 
      counter += -1 
     if cmd == 's': 
      counter = counter * counter 
     chain += " -> " + str(counter) 
    return(chain) 


codeChars = '!ids' 
i = 0 
solutions = [0] 
while True: 
    i += 1 
    codeInt = baseN(i, 4) 
    codeStr = '' 
    for j in range(0, len(str(codeInt))): 
     codeStr += codeChars[int(str(codeInt)[j])] 
    if validCode(codeStr) and deadFish(codeStr) < 1000 and deadFish(codeStr) > -1: 
     if deadFish(codeStr) > len(solutions) - 1: 
      solutions += [0] * (deadFish(codeStr) - len(solutions) + 1) 
     if solutions[deadFish(codeStr)] == 0: 
      solutions[deadFish(codeStr)] = codeStr 
      print(codeStr, ':', format(codeStr)) 
     else: 
      print(codeStr) 

此代碼按預期工作，應該不言自明。但是，這是非常非常低效的。任何改進或優化的建議將不勝感激。

Answer 1

這是我的要求。

你想要找到最小的一段代碼只包含i增量，d ecrement和s quare。因爲s是一個字符，並且創建它們的最大數量，所以您希望找到最接近的方形數字，並使用遞歸來生成將您引導至其根目錄的代碼。

#!/usr/bin/env python3 
# -*- coding: utf-8 -*- 

import math 


def nearest_square(n): 
    root = math.sqrt(n) 
    lower = math.floor(root) 
    higher = math.ceil(root) 
    if n - lower**2 < higher**2 - n: 
     return lower, n - lower**2 
    else: 
     return higher, n - higher**2 # we want a negative error here 


def produce_code_for(n): 
    # squaring doesn't make sense for n < 0, as it always returns positive numbers. 
    # you can leave this part out if you don't want support for negative numbers. 
    if n < 0: 
     return "d" * (-n) 

    # 2^2 = 4 is the first square that is greater than its square root 
    # -> for n < 4, the solution is "i" repeated n times 
    if n < 4: 
     return "i" * n 
    else: 
     root, error = nearest_square(n) 
     if error < 0: 
      return produce_code_for(root) + "s" + "d"*(-error) 
     else: 
      return produce_code_for(root) + "s" + "i"*error