Um das Problem zu lösen, habe ich mir zwei Strategien ausgedacht.
Die erste (diff2bf_dumb) ist die einfachste, die vorstellbar ist. Sie addiert/subtrahiert einfach solange, bis die aktuelle Stelle den richtigen Wert hat, der dann ausgegeben wird.
Die zweite (diff2bf_loop) ist schon etwas komplizierter, ist aber nur bei größeren Differenzen besser. Es werden Lösungen für die Formel "diff = a * b + c" gesucht, mit der Bedingung, dass "|a| + |b| + |c|" minimal werden soll. Mithilfe dieser Werte wird die benachbarte Zelle auf den Wert a gebracht, sodass in einer Schleife der Wert der Haupt-Zelle "a" mal um "b" verändert werden kann, anschließend wird "c" mal der nötige Operator verwandt; nicht jede Zahl lässt sich schließlich gut faktorisieren.
Das Ergebnis ist schon mal ganz gut, es gibt aber sicher noch Optimierungspotential. Vielleicht wäre es sinnvoll, zwei Haupt-Zellen statt einer zu nutzen, wobei eine immer im niedrigen, und eine im hohen Bereich bleibt. Vor Allem bei häufigem Wechsel von Groß- und Kleinschreibung ist mein Algorithmus noch extrem ineffektiv.
Mich würde interessieren, ob ihr noch Ideen habt (oder konkrete Umsetzungen). Mein Code darf auch gerne erweitert werden.
Code:
#!/usr/bin/python
import math
def diff2bf_dumb(diff):
op = ['+', '-'][diff < 0]
return op * abs(diff)
def bestFactors(N):
N = abs(N)
a = int(round(0.5 + math.sqrt(N)))
best = 10000000000
bestA = bestB = 0
while a > 1:
a -= 1
b = int(round(N/a))
val = a + b + abs(N-a*b)
if val < best:
bestA, bestB = a, b
best = val
return bestA, bestB, abs(N - bestA * bestB)
def diff2bf_loop(diff):
if diff == 0:
return ''
op = ['+', '-'][diff < 0]
a, b, c = bestFactors(diff)
code = '>' + '+' * a + '[<' + op * b + '>-]<' + op * c
return code
def diff2bf(diff):
strategies = [diff2bf_dumb, diff2bf_loop]
bestCode = ''
bestLen = 100000000
for s in strategies:
code = s(diff)
l = len(code)
if (l < bestLen):
bestCode = code
bestLen = l
return bestCode
def string2bf(s):
val1 = 0
result = ''
for c in list(s):
goal = ord(c)
diff = goal - val1
code = diff2bf(diff)
val1 = goal
result += code + '.\n'
return result
print string2bf("Hello, world!")
Ausgabe für "Hello, world!":
Code:
>++++++++[<+++++++++>-]<.
>++++[<+++++++>-]<+.
+++++++.
.
+++.
>++++++[<----------->-]<-.
------------.
>+++++++[<++++++++++++>-]<+++.
--------.
+++.
------.
--------.
>++++++[<----------->-]<-.
Länge: 182 Befehle