Optimizing Deadfish Constant Calculator in Python

Question

Deadfish is an esoteric "programming" language (created as a joke, not turing complete). In it, there is a single variable - an integer initialized at 0 - with 4 operations:

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

Although Deadfish normally makes the variable a byte, for my purposes, it will be an integer in python. My program attempts to find that fastest way to print out any given number, that is, the fewest commands. Here are some examples

To reach 10,

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

To reach 15,

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

I have written a simple brute force program to solve this by checking ever combination of i, d, and s. Here is the code:

#!/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)

This code works as expected, and should be self-explanatory. However, it is very, very inefficient. Any suggestions for improvement or optimizing would be greatly appreciated.

Answer 1

Here's my take.

You want to find the smallest piece of code just containing increment, decrement and square. As s is one character, and creates the highest number of them all, you want to find the nearest square number, and use recursion to produce the code that gets you to the root of it.

#!/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