Hackerboard Wiki HaboBlog
Hackerboard bei Facebook Hackerboard bei Google+ Hackerboard bei Twitter

[HaBo]

 
Programmieraufgaben Hier wird regelmäßig eine neue Programmieraufgabe gestellt, die dann gelöst werden soll und in Zusammenarbeit mit den Moderatoren auch besprochen werden kann.

Text->Brainfuck Konverter

Diskussion: Text->Brainfuck Konverter im Forum Programmieraufgaben, in der Kategorie Code Kitchen; Anzeige Von Eydeet, nicht ganz trivial: Zitat: "Schreibe ein Programm, das einen eingegebenen Text möglichst kurz in BrainFuck-Code umsetzt". Es ...
Like Tree2Likes
  • 2 Post By Inviz

Antwort
Themen-Optionen Ansicht
   
Alt 25.05.08, 16:44   #1 (permalink)
CDW
Moderator
 
Benutzerbild von CDW
 
Registriert seit: 20.07.05
CDW Leistung: OpteronCDW Leistung: OpteronCDW Leistung: OpteronCDW Leistung: OpteronCDW Leistung: OpteronCDW Leistung: Opteron
Likes: 202
Standard Text->Brainfuck Konverter
Anzeige

Von Eydeet, nicht ganz trivial:

Zitat:
"Schreibe ein Programm, das einen eingegebenen Text möglichst kurz in BrainFuck-Code umsetzt".
Es geht also darum, einen Text "selbstausgebend" in BF umzuschreiben.
Statt Brainfuck können auch gerne andere Sprachen (Ook!, Whitespace) genommen werden.
__________________
Noch mal, für alle Pseudo-Geeks: 1+1=0. -> 10 wäre Überlauf!
Selig, wer nichts zu sagen hat und trotzdem schweigt.
CDW ist offline   Mit Zitat antworten
Alt 25.05.08, 21:07   #2 (permalink)
 
Registriert seit: 14.06.07
Machine Leistung: Facit NTK
Machine eine Nachricht über ICQ schicken
Likes: 0
Standard
C++   

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
Machine ist offline   Mit Zitat antworten
   
HaBOT
 
- Anzeige -

Werbung ist gerade online    
Alt 20.07.08, 21:29   #3 (permalink)
 
Registriert seit: 22.03.08
MontyPerl Leistung: Facit NTK
Likes: 0
Standard
text2bfsource.c   
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.
MontyPerl ist offline   Mit Zitat antworten
Alt 23.06.11, 11:42   #4 (permalink)
 
Benutzerbild von Eydeet
 
Registriert seit: 14.04.06
Eydeet Leistung: Facit NTK
Likes: 4
Standard
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
Eydeet ist offline   Mit Zitat antworten
Alt 10.10.11, 16:41   #5 (permalink)
 
Benutzerbild von Sleepprogger
 
Registriert seit: 17.10.09
Sleepprogger Leistung: Facit NTK
Likes: 10
Standard
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.

Java code   
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
Geändert von Sleepprogger (10.10.11 um 16:45 Uhr)
Sleepprogger ist offline   Mit Zitat antworten
Alt 05.12.11, 01:28   #6 (permalink)
 
Registriert seit: 05.12.11
Inviz Leistung: Facit NTK
Likes: 2
Standard
Ich spiel auch nochmal kurz den Nekrophilen.
Meine Lösung in Perl produziert zwar schrecklichen BF-Code, ist aber maximal (?) kurz
PHP-Code:
print"+"x ord,".>"for split"",<> 
Usage   

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

Greetz,
inviz
reaLInsanity and bitmuncher like this.
Geändert von Inviz (05.12.11 um 01:47 Uhr)
Inviz ist offline   Mit Zitat antworten
Antwort
   
- Anzeige -

Werbung ist gerade online    

[HaBo] » Software Home » Code Kitchen » Programmieraufgaben » Text->Brainfuck Konverter
« Vorheriges Thema | Nächstes Thema »
Themen-Optionen
Ansicht
Linear-Darstellung Linear-Darstellung

Forumregeln
Es ist Ihnen nicht erlaubt, neue Themen zu verfassen.
Es ist Ihnen nicht erlaubt, auf Beiträge zu antworten.
Es ist Ihnen nicht erlaubt, Anhänge hochzuladen.
Es ist Ihnen nicht erlaubt, Ihre Beiträge zu bearbeiten.
BB-Code ist an.
Smileys sind an.
[IMG] Code ist an.
HTML-Code ist aus.
Trackbacks sind aus
Pingbacks sind aus
Refbacks sind aus

Ähnliche Themen
Thema Autor Forum Antworten Letzter Beitrag
Brainfuck Interpreter CDW Programmieraufgaben 15 02.04.11 16:35
Brainfuck Easyrider Code Kitchen 3 20.10.09 23:29
brainfuck - serien :) _fux_ Music- & Filmbox 0 12.06.09 03:32
assembler :(.text+0x6a): relocation truncated to fit: R_386_16 against `.text:' <b00n> Code Kitchen 0 05.02.09 12:07
Spam als Brainfuck? non Spiced Pork and Ham - Spam & seine Brüder 6 08.05.06 21:42

Alle Zeitangaben in WEZ +2. Es ist jetzt 15:36 Uhr.
vBulletin® v3.8.7, Copyright ©2000-2012, vBulletin Solutions, Inc.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61