在 Python 中优化 Deadfish 常数计算器

Question

Deadfish 是一种深奥的 "programming" 语言（作为一个笑话创建，并非图灵完整）。其中，有一个变量——一个初始化为 0 的整数——有 4 个操作：

Counter += 1 = 我
Counter += -1 = d
Counter = Counter * Counter = s
print(counter) = o

虽然 Deadfish 通常将变量设为字节，但就我的目的而言，它将是 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='0123456789abcdefghijklmnopqrstuvwxyz'):
    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增量和 s平方的最小代码段。由于 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

在 Python 中优化 Deadfish 常数计算器

Optimizing Deadfish Constant Calculator in Python

python

esoteric-languages

python-3.x

python-3.5