1

Deadfish 是一种深奥的“编程”语言（作为一个笑话而创建的，不是图灵完备的）。其中，有一个变量——一个初始化为 0 的整数——有 4 个操作：

  • Counter += 1= 我
  • Counter += -1= d
  • Counter = Counter * Counter= 小号
  • 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)

此代码按预期工作，并且应该是不言自明的。但是，它非常非常低效。任何改进或优化的建议将不胜感激。

4

1 回答 1

1

这是我的看法。

您想找到仅包含ncrement i、decrement 和 quare的最小代码段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
于 2016-11-26T14:09:31.550 回答