Text->Brainfuck Konverter

CDW

CDW

Moderator
Mitarbeiter
Von Eydeet, nicht ganz trivial:
"Schreibe ein Programm, das einen eingegebenen Text möglichst kurz in BrainFuck-Code umsetzt".
Zum Vergrößern anklicken....
Es geht also darum, einen Text "selbstausgebend" in BF umzuschreiben.
Statt Brainfuck können auch gerne andere Sprachen (Ook!, Whitespace) genommen werden.
 
Machine

Machine

Member
Code: 
void CThread::InterpretText(CString sInp)
{
	char c, lastVal;
	for(int z = 0; z != sInp.GetLength(); z++)
    {

        if( z > 0)
		{
            c = sInp[z];
			lastVal = sInp[z - 1];
		}
        else
		{
            c = sInp[z];
			lastVal = 0;
		}

		int i;
		int sqrtval;
		int missing;
		int isPlus = 1;

		c = c - lastVal;
		if (c < 0)
		{
			isPlus = 0;
			c = c * -1;
		}

		if (c > 8)
		{
			sqrtval = sqrt((double)c);
			missing = c - (sqrtval * sqrtval);

			AddText(">");

			for (i = 0; i < sqrtval; i++)
			{
				AddText("+");
			}
			AddText("[<");
			for (i = 0; i < sqrtval; i++)
			{
				if (isPlus)
					AddText("+");
				else
					AddText("-");
			}
			AddText(">-]<");
			for (i = 0; i < missing; i++)
			{
				if (isPlus)
					AddText("+");
				else
					AddText("-");
			}
			AddText(".\n");
		}
		else
		{
			for (i = 0; i < c; i++)
			{
				if (isPlus)
					AddText("+");
				else
					AddText("-");
			}
			AddText(".\n");
		}
    }
}
sorry für die formatierung.. hatte hier nur notepad. achso: die Funktion AddText() gibt den Text in einem Richedit aus.. hatte da mal ne kleine IDE für Brainf*ck geschrieben ;)
 
M

MontyPerl

New member
Code: 
#include <stdio.h>      // For printf and putchar
#include <stdlib.h>     // For malloc
#include <string.h>     // For strcat

char *textToBrainfuck(char *);

int main(void) {
    char *bfSource = textToBrainfuck("Hello, cruel world! :(\n");
    int i;
    for (i = 0; bfSource[i] != '\0'; i++)
        putchar(bfSource[i]);

    return 0;
}

char *textToBrainfuck(char *output) {
    char *bfSource = malloc(1000 * sizeof(char));       // We're generous here.
    char *ptr = malloc(sizeof(char));
    *ptr = 0;
    int diff;
    int i = 0;
    int j;
    while (output[i] != '\0') {
        diff = output[i] - *ptr;
        if (diff > 0) {
            *ptr += diff;
            for (j = 1; j <= diff; j++)
                bfSource = strcat(bfSource, "+");
            bfSource = strcat(bfSource, ".");
        }
        else if (diff < 0) {
            *ptr += diff;
            for (j = 1; j <= -diff; j++)
                bfSource = strcat(bfSource, "-");
            bfSource = strcat(bfSource, ".");
        }
        else {
            bfSource = strcat(bfSource, ".");
        }
        i++;
    }
    return bfSource;
}
Wäre natürlich kürzer (also mein sourcecode), wenn ich die brainfuck-Source nicht in einem extra-Chararray halten würde, sondern einfach direkt ausgeben würde. Jetzt müsste ich nur noch drauf kommen, wie ich dem "so kurz wie möglich" (also in Bezug auf den generierten brainfuck-sourcecode) der Aufgabenstellung Rechnung tragen könnte. (Denn das ist ja der eigentliche "Witz" der Aufgabe.) Ich glaube der generierte brainfuck-code hat sogar so ziemlich die "worst-length".
Mal schaun ob mich ne Idee überfällt.
 
Eydeet

Eydeet

Member
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
 
S

Sleepprogger

New member
Ich habe vor einiger Zeit ein wenig mit genau der selben Aufgabe herumexperimentiert und habe mich dazu entschlossen alle auftretenden Zeichen on demand in einem Register zu speichern und diese dann nur noch auszugeben.
Bei langen Texten funktiniert das ziemlich gut.
Meine "Komprimierungsfunktion" ist allerdings noch nicht so prall ;)
Da werde ich wahrscheinlich teile von Eydeets code einbauen.

Code: 
    private static String getChar(char thisChar, boolean delete){
        StringBuilder builder = new StringBuilder();
        int tmp = 0;
        int cur = thisChar;
        if(cur > 10){
            builder.append(">");
            tmp = cur;
            for (int i = 0; i < (int)(tmp/10.0); i++){
                builder.append("+");
                cur -= 10;
            }
            builder.append("[<++++++++++>-]<");
        }        
        for (int i = 0; i < cur; i++)builder.append("+");
        if(delete)builder.append("[-]");
        return builder.toString();
    }
    public static String generateLargTextOutput(String text){
        Map<Character, Integer> usedMap = new HashMap<Character, Integer>();
        char data[] = text.toCharArray();
        StringBuilder string = new StringBuilder();
        int maxReg = 0;
        int lastUsdReg = 0;
        int curReg = 0;
        for (int i = 0; i < data.length; i++) {
            if(usedMap.get(data[i]) != null){
                curReg = usedMap.get(data[i]);
                if(lastUsdReg < curReg)
                    for (int j = lastUsdReg; j < curReg; j++)string.append(">");
                else if(lastUsdReg > curReg)
                    for (int j = lastUsdReg; j > curReg; j--)string.append("<");
                string.append(".");
                lastUsdReg = curReg;
            }else{
                for (int j = lastUsdReg; j < maxReg && maxReg != 0; j++)string.append(">");
                String tmp = getChar(data[i], false);
                string.append(tmp + ".");
                usedMap.put(data[i], maxReg);
                lastUsdReg = maxReg;
                maxReg += 1;
            }
            string.append("\r\n");
        }
        return string.toString();
    }

"Hello, World!" mit 346 Zeichen.
Code: 
>+++++++[<++++++++++>-]<++.
>>++++++++++[<++++++++++>-]<+.
>>++++++++++[<++++++++++>-]<++++++++.
.
>>+++++++++++[<++++++++++>-]<+.
>>++++[<++++++++++>-]<++++.
>>+++[<++++++++++>-]<++.
>>+++++++++++[<++++++++++>-]<+++++++++.
<<<.
>>>>>+++++++++++[<++++++++++>-]<++++.
<<<<<.
>>>>>>>++++++++++[<++++++++++>-]<.
>>+++[<++++++++++>-]<+++.
edit: Ich hoffe das ist in Ordnung das ich hier die alten Threads wieder belebe. Wenn nicht einfach schrei(b)en ;)
 
Zuletzt bearbeitet:
I

Inviz

New member
Ich spiel auch nochmal kurz den Nekrophilen.
Meine Lösung in Perl produziert zwar schrecklichen BF-Code, ist aber maximal (?) kurz :D
PHP: 
print"+"x ord,".>"for split"",<>
ivz@h0m3 bf $ perl -e 'print"+"x ord,".>"for split"",<>' > file
BF-Generator 4 HaBo
ivz@h0m3 bf $ ./bf file
BF-Output: BF-Generator 4 HaBo

Thanks for using my BF-Interpreter!
ivz@h0m3 bf $
Sind momentan 32 Zeichen, ich weiß, nicht ganz im Sinne der Aufgabe, aber mir war danach :p

Greetz,
inviz
 
Zuletzt bearbeitet:
Um antworten zu können musst du eingeloggt sein.
Oben