Operatoren für gegebene Gleichung finden (Bruteforce)

ivegotmail

Member of Honour
#1
Folgende Programmieraufgabe wurde von IsNull eingereicht:

Folgende Gleichung ist gegeben: (6_2)_8_9_1= 13
Die Underlines stellen einen Operator dar, welchen muss man herausfinden.

Ziel: Möglichst schneller Bruteforcer, der die Gleichung mit den richtigen Operatoren ausstattet.
 
#2
welche operatoren sind denn genau zugelassen? also nur +-*/ oder auch %, ^ etc?
punkt vor strich sollte schätze ich mal auch eingehalten werden.. ist das wirklich noch schwierigkeit 1?? ;)

edit: k, habs jetz in javascript gemacht, da c++ keine mit Eval vergleichbare funktion besitzt ^^ dadurch wird natuerlich die forderung nach nem schnellen bruteforcer net erfuellt. evtl mach ich das ganze noch in c, wobei das bzgl. punkt vor strich wohl grauslig wird und schon fast nach ner math engine schreit..

<html>
<script>
//(6_2)_8_9_1= 13
ops = Array('+', '-', '*', '/', '%', '^');
op = Array();
document.write("<table>");
for (op[1] in ops) { //4 unbekannte
for (op[2] in ops) { //4 unbekannte
for (op[3] in ops) { //4 unbekannte
for (op[4] in ops) { //4 unbekannte
str = "(6"+ops[op[1]]+"2)"+ops[op[2]]+"8"+ops[op[3]]+"9"+ops[op[4]]+"1";
if(eval(str)==13) {
document.write("<tr><td>"+str+"</td><td> = </td><td>"+eval(str));
document.write(" <b style=\"color:red\">MATCH!</b></td></tr>")
}
else
document.write("</td></tr>");
}
}
}
}
</script>
</html>
 
#3
Ist die Aufgabenstellung jetzt genau auf "(6_2)_8_9_1= 13" ausgelegt oder soll das eine beliebige dynamische Eingabe sein?
Welche Operatoren sind erlaubt (Priorität?). Division soll genau sein? (keine Integerdivision)
 
#4
Ich habe die Aufgabe mal mit C gelöst, als Operatoren habe ich nur + - * / zugalassen.

Code:
#include <stdio.h>
void format(double * wert, int i, int j, int k, int l);
void ausgabe(char * gleichung, char * op, double erg, int i, int j, int k, int l);
int main(void) {
  char op[4]={'+','-','*','/'};
  int i,j,k,l;
  int f;
  double wert[5];
  wert[0]=6;
  double erg;
  char gleichung[15];
  gleichung[0]='(';
  gleichung[1]='6';
  gleichung[3]='2';
  gleichung[4]=')';
  gleichung[6]='8';
  gleichung[8]='9';
  gleichung[10]='1';
  gleichung[11]='=';
  gleichung[12]='1';
  gleichung[13]='3';
  gleichung[14]='\0';  
  for(i=0;i<4;i++) {
    for(j=0;j<4;j++) {
      for(k=0;k<4;k++) {
        for(l=0;l<4;l++) {
          if((i<2)&&(j<2)&&(k<2)&&(l<2)) {
            format(wert,i,j,k,l);
            erg=wert[0]+wert[1]+wert[2]+wert[3]+wert[4];
            if(erg==13) {
              ausgabe(gleichung,op,erg,i,j,k,l);
            }
          }
          if((i<2)&&(j<2)&&(k<2)&&(l>1)) {
            format(wert,i,j,k,l);
            erg=wert[0]+wert[1]+wert[2]+wert[3]*wert[4];
            if(erg==13) {
              ausgabe(gleichung,op,erg,i,j,k,l);
            }           
          }
          if((i<2)&&(j<2)&&(k>1)&&(l<2)) {
            format(wert,i,j,k,l);
            erg=wert[0]+wert[1]+wert[2]*wert[3]+wert[4];
            if(erg==13) {
              ausgabe(gleichung,op,erg,i,j,k,l);
            }
          }
          if((i<2)&&(j<2)&&(k>1)&&(l>1)) {
            format(wert,i,j,k,l);
            erg=wert[0]+wert[1]+wert[2]*wert[3]*wert[4];
            if(erg==13) {
              ausgabe(gleichung,op,erg,i,j,k,l);
            }
          }
          if((i<2)&&(j>1)&&(k<2)&&(l<2)) {
            format(wert,i,j,k,l);
            erg=wert[0]+wert[1]*wert[2]+wert[3]+wert[4];
            if(erg==13) {
              ausgabe(gleichung,op,erg,i,j,k,l);
            }
          }
          if((i<2)&&(j>1)&&(k<2)&&(l>1)) {
            format(wert,i,j,k,l);
            erg=wert[0]+wert[1]*wert[2]+wert[3]+wert[4];
            if(erg==13) {
              ausgabe(gleichung,op,erg,i,j,k,l);
            }
          }
          if((i<2)&&(j>1)&&(k>1)&&(l<2)) {
            format(wert,i,j,k,l);
            erg=wert[0]+wert[1]*wert[2]*wert[3]+wert[4];
            if(erg==13) {
              ausgabe(gleichung,op,erg,i,j,k,l);
            }
          }
          if((i<2)&&(j>1)&&(k>1)&&(l>1)) {
            format(wert,i,j,k,l);
            erg=wert[0]+wert[1]*wert[2]*wert[3]*wert[4];
            if(erg==13) {
              ausgabe(gleichung,op,erg,i,j,k,l);
            }
          }
          if((i>1)&&(j<2)&&(k<2)&&(l<2)) {
            format(wert,i,j,k,l);
            erg=wert[0]*wert[1]+wert[2]+wert[3]+wert[4];
            if(erg==13) {
              ausgabe(gleichung,op,erg,i,j,k,l);
            }
          }
          if((i>1)&&(j<2)&&(k<2)&&(l>1)) {
            format(wert,i,j,k,l);
            erg=wert[0]*wert[1]+wert[2]+wert[3]*wert[4];
            if(erg==13) {
              ausgabe(gleichung,op,erg,i,j,k,l);
            }
          }
          if((i>1)&&(j<2)&&(k>1)&&(l<2)) {
            format(wert,i,j,k,l);
            erg=wert[0]*wert[1]+wert[2]*wert[3]+wert[4];
            if(erg==13) {
              ausgabe(gleichung,op,erg,i,j,k,l);
            }
          }
          if((i>1)&&(j<2)&&(k>1)&&(l>1)) {
            format(wert,i,j,k,l);
            erg=wert[0]*wert[1]+wert[2]*wert[3]*wert[4];
            if(erg==13) {
              ausgabe(gleichung,op,erg,i,j,k,l);
            }
          }
          if((i>1)&&(j>1)&&(k<2)&&(l<2)) {
            format(wert,i,j,k,l);
            erg=wert[0]*wert[1]*wert[2]+wert[3]+wert[4];
            if(erg==13) {
              ausgabe(gleichung,op,erg,i,j,k,l);
            }
          }
          if((i>1)&&(j>1)&&(k<2)&&(l>1)) {
            format(wert,i,j,k,l);
            erg=wert[0]*wert[1]*wert[2]+wert[3]+wert[4];
            if(erg==13) {
              ausgabe(gleichung,op,erg,i,j,k,l);
            }
          }
          if((i>1)&&(j>1)&&(k>1)&&(l<2)) {
            format(wert,i,j,k,l);
            erg=wert[0]*wert[1]*wert[2]*wert[3]+wert[4];
            if(erg==13) {
              ausgabe(gleichung,op,erg,i,j,k,l);
            }
          }
          if((i>1)&&(j>1)&&(k>1)&&(l>1)) {
            format(wert,i,j,k,l);
            erg=wert[0]*wert[1]*wert[2]*wert[3]*wert[4];
            if(erg==13) {
              ausgabe(gleichung,op,erg,i,j,k,l);
            }
          }
        }
      }
    }
  }
  system("PAUSE");
  return 0;
}

void format(double * wert, int i, int j, int k, int l) {
  switch(i) {
    case 0: wert[1]=2; break;
    case 1: wert[1]=(-2); break;
    case 2: wert[1]=2; break;
    case 3: wert[1]=(double)1/2; break;
  }
  switch(j) {
    case 0: wert[2]=8; break;
    case 1: wert[2]=(-8); break;
    case 2: wert[2]=8; break;
    case 3: wert[2]=(double)1/8; break;
  }
  switch(k) {
    case 0: wert[3]=9; break;
    case 1: wert[3]=(-9); break;
    case 2: wert[3]=9; break;
    case 3: wert[3]=(double)1/9; break;
  }
  switch(l) {
    case 0: wert[4]=1; break;
    case 1: wert[4]=(-1); break;
    case 2: wert[4]=1; break;
    case 3: wert[4]=1; break;
  }
}

void ausgabe(char * gleichung, char * op, double erg, int i, int j, int k, int l) {
  gleichung[2]=op[i];
  gleichung[5]=op[j];
  gleichung[7]=op[k];
  gleichung[9]=op[l];
  printf("%s\tErg: %lf\n",gleichung,erg);
}
 
I

IsNull

Guest
#5
Ist die Aufgabenstellung jetzt genau auf "(6_2)_8_9_1= 13" ausgelegt oder soll das eine beliebige dynamische Eingabe sein?
Da sie jetzt schon gelöst ist, wäre es eine Herausforderung auch mit varierender Operatorzahl eine Lösung zu finden. =)

mfg
IsNull
 
#6
So, meine kurze Lösung... 100 Zeilen, prüft beliebige "Gleichungen". Platzhalter _ sonst sind + - * / Klammern sowie Ziffern von 0-9 erlaubt. Es muss ein = vorkommen. (Syntax wird nicht geprüft.)
Code:
#include <iostream>
#include <string>
#include <sstream>

using namespace std;


int stoi(string str)
{
	stringstream s(str);
	int a;
	s >> a;
	return a;
}

double opt(double w, char o, double x)
{
	switch (o) {
	case '+' : return w + x;
	case '-' : return w - x;
	case '*' : return w * x;
	case '/' : return w / x;
	default: cout << "Unknown tokken " << o << endl;
	};
	return 0.0;
}

double parsestr(string s);

bool parse(string s, double &r, char o)
{
	int i, b = 0, a = 0, f = 0;
	double w = 0.0;
	for (i = 0; i < s.length(); ++i) {
		if (s[i] == '(')
			++b;
		else if (s[i] == ')')
			--b;
		else if (s[i] == o && b == 0) {
			if (f)
				w = opt(w, o, parsestr(s.substr(a, i - a)));
			else
				w = parsestr(s.substr(a, i - a));
			f = 1;
			a = i + 1;
		}
	}
	if (f) {
		r = opt(w, o, parsestr(s.substr(a, i - a)));
		return true;
	}
	return false;
}

double parsestr(string s)
{
	double w = 0.0;
	if (parse(s, w, '+'))
		return w;
	if (parse(s, w, '-'))
		return w;
	if (parse(s, w, '*'))
		return w;
	if (parse(s, w, '/'))
		return w;
	if (s[0] == '(' && s[s.length()-1]==')')
		return parsestr(s.substr(1, s.length() - 2));

	return stoi(s);
}

void solve(string s)
{
	string::size_type p = s.find("_", 0);
	if (p == string::npos) {
		unsigned int p = s.find("=", 0);
		double w = parsestr(s.substr(0, p));
		double x = parsestr(s.substr(p + 1));
		if (w + 1e-12 > x && w - 1e-12 < x)
			cout << s << endl;
		return;
	}
	s[p] = '+';
	solve(s);
	s[p] = '-';
	solve(s);
	s[p] = '*';
	solve(s);
	s[p] = '/';
	solve(s);
}


int main()
{
	string test;
	cin >> test;
	solve(test);
	return 0;
}
Bei mir braucht der Code knapp 15ms für die beiden Lösungen der Beispielgleichung.
 
#7
Mit denselben Funktionen, die ich auch hier benutzt habe, wandle ich den Term hier immer in postfix um und berechne das Ergebnis dann. Der Lösungsalgorithmus ist ein Backtracking Algorithmus (ich bin grade im Backtracking-Fieber). Das, zusammen mit dem ganzen von infix nach postfix Umgewandle resultiert in recht unperformantem code.
Bei mir braucht der Code knapp 15ms für die beiden Lösungen der Beispielgleichung.
Da kann ich drüber:
Code:
time ./equationBacktracker.pl '( 6 _ 2 ) _ 8 _ 9 _ 1 = 13'
( 6 * 2 ) - 8 + 9 * 1
( 6 * 2 ) - 8 + 9 / 1

real    0m2.183s
user    0m1.952s
sys     0m0.013s
Außerdem muss jeder Teil der Gleichung schön durch Leerzeichen von den anderen Teilen der Gleichung getrennt sein (aber in der Aufgabenstellung gehts ja auch nicht darum eine Gleichung möglichst allumfassend zu parsen..)
Code:
#!/usr/bin/env perl
use warnings;
use strict;


my $Operator = qr{[-+/%*x]};
my $Number = qr{[-+]?(:?(:?[1-9][0-9]*)?\.)?[1-9][0-9]*};
my $Bracket = qr{[)(]};


sub calcPostfix {
    my @numStack;
    foreach my $atom (@_) {
        if ($atom =~ m{^$Number$}) {push(@numStack, $atom)}
        elsif ($atom =~ m{^$Operator$}) {
            my ($b, $a) = (pop(@numStack), pop(@numStack));
            unless ($a) {$a = 0}
            unless ($b) {
                $b = 0;
                if ($atom =~ m{[/%]}) {return '1.23456789'} # Division by zero? nothx
            }
            my $result;
            if    ($atom eq '*' or $atom eq 'x'){$result = $a * $b}
            elsif ($atom eq '/' or $atom eq '%'){$result = $a / $b}
            elsif ($atom eq '+')                {$result = $a + $b}
            elsif ($atom eq '-')                {$result = $a - $b}
            push(@numStack, $result)
        }
    }
    return pop(@numStack)
}

sub infix2postfix {
    my (@postfixTerm, @opStack);
    # A precendence-hash mapping operators to integers representing their precendence.
    my %precHash = ('*'   =>   2,
                    'x'   =>   2,
                    '%'   =>   2,
                    '/'   =>   2,
                    '+'   =>   1,
                    '-'   =>   1,
                    ')'   =>   0,
                    '('   =>   0,
                    'EOT' =>   0);

    push(@opStack, "EOT");
    PARSE: foreach my $atom (@_, "EOT") {       # EOT == "End of term" mark
        if    ($atom =~ m{^$Number$}) {push(@postfixTerm, $atom)}
        elsif ($atom =~ m{^$Operator$}) {
            if ($precHash{$atom} > $precHash{$opStack[$#opStack]}) {push(@opStack, $atom)}
            else {
                push(@postfixTerm, pop(@opStack));
                redo PARSE
            }
        }
        elsif ($atom =~ m{^$Bracket$}) {
            if ($atom eq '(') {push(@opStack, $atom)}
            else {
                while($opStack[$#opStack] ne '(') {push(@postfixTerm, pop(@opStack))}
                pop(@opStack)
            }
        }
        elsif ($atom eq "EOT") {
            push(@postfixTerm, pop(@opStack)) until ($opStack[$#opStack] eq "EOT")
        }
    }
    return @postfixTerm
}

sub bruteforce {
    my ($solutions, $res, @data) = @_;
    foreach my $pos (@data) {
        if ($pos eq '_') {
            foreach my $op ('*', '/', '+', '-') {
            $pos = $op;
            if (bruteforce($solutions, $res, @data)) {return 1}
            }
            $pos = '_'
        }
    }
    if (calcPostfix(infix2postfix(@data)) == $res) {
        my $solString = join(' ', @data);
        if (($solString !~ /_/) and (not grep(($_ eq $solString), @$solutions))) {
            push(@$solutions, join(' ', @data));
            return 0
        }
    }
}

my @data;

if (@ARGV) {@data = split(/\s+/, $ARGV[0])}
else {print "\$-> "; my $inp = <>; chomp($inp); @data = split(/\s+/, $inp)}

my $result = pop(@data);
pop(@data);

my @solutions;
bruteforce(\@solutions, $result, @data);

foreach (@solutions) {print "$_\n"}
Der Term wird entweder von stdin oder vom *ersten* Argument gelesen. Außerdem sollte man auf Gleichungen mit "krummen" Ergebnissen absehen. (float Vergleiche mit == unzo, ihr wisst schon..)

?: hier mal das ganze mit eval, unsicherer, aber wesentlich schneller:
Code:
#!/usr/bin/env perl
use warnings;
use strict;

sub bruteforce {
    my ($solutions, $res, @data) = @_;
    foreach my $pos (@data) {
        if ($pos eq '_') {
            foreach my $op ('*', '/', '+', '-') {
            $pos = $op;
            if (bruteforce($solutions, $res, @data)) {return 1}
            }
            $pos = '_'
        }
    }
    if (!grep $_ eq '_', @data) {
        my $solString = join(' ', @data);
        my $result = eval $solString;
        if ((defined $result) and ($result == $res) and (not grep(($_ eq $solString), @$solutions))) {
            push(@$solutions, join(' ', @data));
            return 0
        }
    }
}

my @data;

if (@ARGV) {@data = split(/\s+/, $ARGV[0])}
else {print "\$-> "; my $inp = <>; chomp($inp); @data = split(/\s+/, $inp)}

my $result = pop(@data);
pop(@data);

my @solutions;
bruteforce(\@solutions, $result, @data);

foreach (@solutions) {print "$_\n"}
Code:
time ./equationBacktrackerEval.pl '( 6 _ 2 ) _ 8 _ 9 _ 1 = 13'
( 6 * 2 ) - 8 + 9 * 1
( 6 * 2 ) - 8 + 9 / 1

real    0m0.661s
user    0m0.536s
sys     0m0.005s
??: aber "schnell" isses immernoch nicht:
Code:
time ./equationBacktrackerEval.pl '( 1 _ 2 ) _ 10 _ ( 4 _ ( 5 _ ( 2 _ 1 ) ) ) = -30'
( 1 / 2 ) * 10 * ( 4 - ( 5 * ( 2 * 1 ) ) )
( 1 / 2 ) * 10 * ( 4 - ( 5 * ( 2 / 1 ) ) )
( 1 + 2 ) * 10 * ( 4 - ( 5 * ( 2 - 1 ) ) )
( 1 + 2 ) * 10 * ( 4 - ( 5 / ( 2 - 1 ) ) )
( 1 + 2 ) * 10 / ( 4 - ( 5 * ( 2 - 1 ) ) )
( 1 + 2 ) * 10 / ( 4 - ( 5 / ( 2 - 1 ) ) )
( 1 + 2 ) * 10 - ( 4 * ( 5 * ( 2 + 1 ) ) )
( 1 - 2 ) * 10 - ( 4 * ( 5 * ( 2 - 1 ) ) )
( 1 - 2 ) * 10 - ( 4 * ( 5 / ( 2 - 1 ) ) )
( 1 - 2 ) - 10 - ( 4 + ( 5 * ( 2 + 1 ) ) )

real    7m51.761s
user    6m1.156s
sys     0m0.025s
Bwahahaha..
 
#8
könnte man den für einen bruteforcer, der eine eingegebene gleichung rausfinden soll denn nicht einen codegenerator schreiben?
ist das überhaupt erlaubt?
 
#9
Meine Python Version:

Code:
from __future__ import division

def bruteforcer(gleichung="(6a2)b8c9d1=13", operatoren=["+", "-", "*", "/"]):
    for a in operatoren:
        for b in operatoren:
            for c in operatoren:
                for d in operatoren:
                    neue_gleichung=gleichung.replace("a", "%s"%a)
                    neue_gleichung2=neue_gleichung.replace("b", "%s"%b)
                    neue_gleichung3=neue_gleichung2.replace("c", "%s"%c)
                    neue_gleichung4=neue_gleichung3.replace("d", "%s"%d)
                    neue_gleichung5=neue_gleichung4.replace("=", "==")
                    if eval(neue_gleichung5):
                        print neue_gleichung4
Nicht die eleganteste Lösung aber immerhin sehr kurz...*zu Geists Variante schau*
 

CDW

Moderator
Mitarbeiter
#10
Code:
oper(Op1,Op2,Op1*Op2,*).
oper(Op1,Op2,Op1/Op2,/).
oper(Op1,Op2,Op1+Op2,+).
oper(Op1,Op2,Op1-Op2,-).

suche(Loesung):-  oper(6,2,Temp1,Op1), KlammerErgebnis is Temp1,
                  oper(KlammerErgebnis,8,Temp2,Op2),
                  oper(Temp2,9,Temp3,Op3),
                  oper(Temp3,1,Erg,Op4),
                  13 is Erg, %schöne ausgabe machen
                  concat_atom(['(',6,Op1,2,')',Op2,8,Op3,9,Op4,1,'=',13],Loesung).
Wer sich den Operator zwichen 6 und 2 denken kann:
Code:
oper(Op1,Op2,Op1*Op2).
oper(Op1,Op2,Op1/Op2).
oper(Op1,Op2,Op1+Op2).
oper(Op1,Op2,Op1-Op2).

suche(Loesung):-  oper(6,2,Temp1),Klammer is Temp1,
                  oper(Klammer,8,Temp2),
                  oper(Temp2,9,Temp3),
                  oper(Temp3,1,Loesung),
                  13 is Loesung.
 
#11
Hier meine Lösung in ruby:

Code:
a = ["+", "-", "*", "/"]; b = a; c = a; d = a; string_e = ""
a.each { |part1|
	b.each { |part2|
		c.each { |part3|
			d.each { |part4|
				string_e = "(6.0#{part1}2.0)#{part2}8.0#{part3}9.0#{part4}1.0"
				if eval(string_e).to_f == 13
					puts "Loesung gefunden: #{string_e}=13"; exit
				end
			}
		}
	}
}
Ausgabe:

Code:
athelstan@127.0.0.1:~$ ruby Operator.rb
Loesung gefunden: (6.0*2.0)-8.0+9.0*1.0=13
Lässt man das "exit" in Zeile 8 weg, kommt folgendes heraus, was logisch gesehen genau das gleiche ist:

Code:
athelstan@127.0.0.1:~$ ruby Operator.rb
Loesung gefunden: (6.0*2.0)-8.0+9.0*1.0=13
Loesung gefunden: (6.0*2.0)-8.0+9.0/1.0=13
9 geteilt durch 1 und mal 1 ergibt immer dasselbe, nämlich 9 - sonnenklar =)
 
#12
hello

dashier ist ein ziemlich langer code für sowas,
aber das ist mein erster "brute force" und somit denk ich mal ganz passabel.

c++:

Code:
#include <iostream>
#include <ctime>
#include <conio.h>
#include <string>
using namespace std;

// (6_2)_8_9_1= 13 - finde die Gleichung 

int rechnung = 0;
string kette;

int teste( int zeins, int zzwei, int zdrei, int zvier );

int main()
{
    int oeins = 0, ozwei = 0, odrei = 0, ovier = 0;
    srand(time(NULL));

    while( rechnung != 13)
    {
        rechnung = 0;
        kette = "";
        oeins = (rand() % 4);
        ozwei = (rand() % 4);
        odrei = (rand() % 4);
        ovier = (rand() % 4);
        teste ( oeins, ozwei, odrei, ovier );
    }

    if( rechnung == 13)
    {
        cout << "Ergebnis: " << kette << " = 13" << endl;
    }
    cout << "Druecken Sie eine beliebige Taste um das Fenster zu schliessen" << endl;
    getch();
    return 0;
}

int teste( int zeins, int zzwei, int zdrei, int zvier )
{    
    if( zeins == 0 )
    {
        rechnung += (6+2);
        kette += "(6+2)";
    }
    else if( zeins == 1 )
    {
        rechnung += (6-2);
        kette += "(6-2)";
    }
    else if( zeins == 2 )
    {
        rechnung += (6*2);
        kette += "(6*2)";
    }
    else if( zeins == 3 )
    {
        rechnung += (6/2);
        kette += "(6/2)";
    }

    if( zzwei == 0 )
    {
        rechnung = rechnung + 8;
        kette += " +8";
    }
    else if( zzwei == 1 )
    {
        rechnung = rechnung - 8;
        kette += " -8";
    }
    else if( zzwei == 2 )
    {
        rechnung = rechnung * 8;
        kette += " *8";
    }
    else if( zzwei == 3 )
    {
        rechnung = rechnung / 8;
        kette += " /8";
    }

    if( zdrei == 0 )
    {
        rechnung = rechnung + 9;
        kette += " +9";
    }
    else if( zdrei == 1 )
    {
        rechnung = rechnung - 9;
        kette += " -9";
    }
    else if( zdrei == 2 )
    {
        rechnung = rechnung * 9;
        kette += " *9";
    }
    else if( zdrei == 3 )
    {
        rechnung = rechnung / 9;
        kette += " /9";
    }

    if( zvier == 0 )
    {
        rechnung = rechnung + 1;
        kette += " +1";
    }
    else if( zvier == 1 )
    {
        rechnung = rechnung - 1;
        kette += " -1";
    }
    else if( zvier == 2 )
    {
        rechnung = rechnung * 1;
        kette += " *1";
    }
    else if( zvier == 3 )
    {
        rechnung = rechnung / 1;
        kette += " /1";
    }

    return ( zeins, zzwei, zdrei, zvier );
}

keine ahnung ob der jetzt schnell ist oder nicht...
 
Zuletzt bearbeitet:
#13
Eine weitere Python Lösung für beliebige Gleichungen:
Code:
from __future__ import division
import sys,itertools,time
startTime=time.time()
gleichung=sys.argv[1].replace("_","%s").replace("=","==")
numUnders=sys.argv[1].count("_")
solutions=[]
for opList in itertools.product("+-*/",repeat=numUnders):
	try:
		if eval(gleichung%opList): 
			solutions.append(gleichung%opList)
	except ZeroDivisionError:
		continue
print "Loeseungen: "+str(len(solutions))
for solution in solutions:
	print "\t"+solution
timeTook=time.time()-startTime
print "Dauer: "+str(timeTook)+"s"
Beispiel:
Code:
C:\Code\Python\HaBo>python OpFinder.py "(6_2)_8_9_1=13"
Loeseungen: 2
        (6*2)-8+9*1==13
        (6*2)-8+9/1==13
Dauer: 0.00799989700317s
 

CDW

Moderator
Mitarbeiter
#14
*nach langer Zeit den Thread rauskram*
12 Zeilen Python. Löst/Prüft beliebige Gleichungen. Die üblichen mathematischen Funktionen wie cos, sin, sqrt usw. sind verfügbar.
Wegen 'eval' sollte es nur lokal genutzt werden.
Code:
#! /usr/bin/env python
# -*- coding: utf-8 -*-
from __future__ import division

import sys
import math
import itertools

ops = ['+', '-', '*', '/']
expr = sys.argv[1].replace('=', '==')

for op_combo in itertools.product(ops, repeat=expr.count('_')):
    mod_expr = expr
    for op in op_combo:
        mod_expr = mod_expr.replace('_', op, 1)
    
    if eval(mod_expr, {"__builtins__":None}, math.__dict__):
        print "solution:", mod_expr
Ausgabe:
Code:
>evaluator.py (6_2)_8_9_1=13
solution: (6*2)-8+9*1==13
solution: (6*2)-8+9/1==13
Code:
>evaluator.py 2_3_5_7_11_13=100
solution: 2+3+5+7*11+13==100
Code:
>evaluator.py 2_3_5_7_11_sqrt(25)=20
solution: 2*3+5-7+11+sqrt(25)==20
Edit: hm, die Überschneidung mit dem anderen Python Post ist aber schon fast wie ein Lottotreffer.
 

CDW

Moderator
Mitarbeiter
#16
*war bloß laut gedacht/Selbstkommentar*. Eine Beschwerde würde eher per PM eingehen und zumindest deutlich als solche erkennbar sein ;).
Sehe grundsätzlich kein Problem darin, wenn jemand alte Threads wieder ausgräbt - solange der neue Post sinnvoll ist und vom Inhalt her dazu passt.
 
#17
Sehe grundsätzlich kein Problem darin, wenn jemand alte Threads wieder ausgräbt - solange der neue Post sinnvoll ist und vom Inhalt her dazu passt.
Na dann will ich hier auch nochmal meinen Senf dazugeben :). Habe die Aufgabe erst recht spät entdeckt und fand sie eingentlich recht interessant, also...
Code:
#include <stdio.h>
#include <stdlib.h>

float teste_formel(int a, int b, int c, int d);
int bruteforce();
float berechne_gleichung(char gleichung[11]);

int main()
{
    bruteforce();
    return 0;
}

int bruteforce()
{
    /***************************************************************************/
    /** So wird vorgegangen:                                                  **/
    /** Schritt 1:                                                            **/
    /** nummern[0] wird immer größer(+1), bis nummern[0] = 4                  **/
    /** Schritt 2:                                                            **/
    /** nummern[0] = 1 und nummern[1] wird nun immer größer. Wenn es 4 ist,   **/
    /** wird nummern[0]+1 und nummern[1] = 1. Dann geht es wieder von vorne   **/
    /** los, bis nummern[0] und nummern[1] = 4                                **/
    /** Schritt 3:                                                            **/
    /** nun wird nummern[2] immer größer gemacht. Wenn der Wert 4 beträgt,    **/
    /** dann ist nummern[2] wieder 1 und nummern[1] geht um eins hoch. Wenn   **/
    /** der Wert von nummern[1] ebenfalls wieder 4 beträgt(1-4-4-1), dann wird**/
    /** nummern[0] um 1 erhöht, und dann geht es wieder von vorne los, erst   **/
    /** es dann wieder heißt: 2-4-4-1 geht nummern[0] wieder hoch. Wenn das   **/
    /** Ganze 4-4-4-1 ist, kommt                                              **/
    /** Schritt 4:                                                            **/
    /** nun wird nummern[3] immer erhöht, dann als nächstes nummern[2] usw.   **/
    /** Gleiches Prinzip wie bei Schritt 3                                    **/
    /***************************************************************************/

    int nummern[4];
    /* Ausgangswerte */
    int i = 0;
    while(i <= 3)
    {
        nummern[i] = 1;
        i++;
    }
    i = 1;
    /* Schritt 1 */
    printf("Schleife 1:\n");
    while(i <= 4)
    {
        nummern[0] = i;
        if(teste_formel(nummern[0], nummern[1], nummern[2], nummern[3]) == 13)
            return 0;
        /* getchar(); */
        i++;
    }
    i = 0;
    while(i <= 3)
    {
        nummern[i] = 1;
        i++;
    }
    i = 0;
    int z = 2;
    /* Schritt 2 */
    printf("Schleife2\n");
    while(1)
    {
        nummern[1] = z;
        if(teste_formel(nummern[0], nummern[1], nummern[2], nummern[3]) == 13)
            return 0;
        printf("nummern1: %i\n", nummern[1]);
        /* getchar(); */
        if((nummern[0] == 4) && (nummern[1] == 4))
            break;
        if(nummern[1] == 4)
        {
            z = 1;
            nummern[0]++;
            continue;
        }
        z++;
    }
    i = 0;
    while(i <= 3)
    {
        nummern[i] = 1;
        i++;
    }
    z = 2;
    /* Schritt 3 */
    printf("Schleife 3\n");
    while(1)
    {
        nummern[2] = z;
        if(teste_formel(nummern[0], nummern[1], nummern[2], nummern[3]) == 13)
            return 0;
        if((nummern[0] == 4) && (nummern[1] == 4) && (nummern[2] == 4))
            break;
        if(nummern[2] == 4 && nummern[1] != 4)
        {
            z = 1;
            nummern[1]++;
            continue;
        }
        if(nummern[1] == 4 && nummern[2] == 4)
        {
            z = 1;
            nummern[1] = 1;
            nummern[0]++;
            continue;
        }
        z++;
    }
    i = 0;
    while(i <= 3)
    {
        nummern[i] = 1;
        i++;
    }
    z = 2;
    /* Schritt 4 */
    printf("Schleife 4\n");
    while(1)
    {
        nummern[3] = z;
        if(teste_formel(nummern[0], nummern[1], nummern[2], nummern[3]) == 13)
            return 0;
        /* getchar(); */
        if((nummern[0] == 4) && (nummern[1] == 4) && (nummern[2] == 4) && (nummern[3] == 4))
            break;
        if(nummern[3] == 4 && nummern[2] != 4)
        {
            z = 1;
            nummern[2]++;
            continue;
        }
        if(nummern[2] == 4 && nummern[1] != 4)
        {
            nummern[2] = 1;
            nummern[1]++;
            continue;
        }
        if(nummern[1] == 4 && nummern[0] != 4)
        {
            nummern[1] = 1;
            nummern[0]++;
            continue;
        }
        z++;
    }
    return 0;
}

float teste_formel(int a, int b, int c, int d)
{
    /* Hier wird die Gleichung getestet */
    char gleichung[11];

    gleichung[0] = '(';
    gleichung[1] = '6';
    gleichung[2] = '_';
    gleichung[3] = '2';
    gleichung[4] = ')';
    gleichung[5] = '_';
    gleichung[6] = '8';
    gleichung[7] = '_';
    gleichung[8] = '9';
    gleichung[9] = '_';
    gleichung[10] = '1';

    if(a == 1)
        gleichung[2] = '+';
    if(a == 2)
        gleichung[2] = '-';
    if(a == 3)
        gleichung[2] = '*';
    if(a == 4)
        gleichung[2] = '/';

    if(b == 1)
        gleichung[5] = '+';
    if(b == 2)
        gleichung[5] = '-';
    if(b == 3)
        gleichung[5] = '*';
    if(b == 4)
        gleichung[5] = '/';

    if(c == 1)
        gleichung[7] = '+';
    if(c == 2)
        gleichung[7] = '-';
    if(c == 3)
        gleichung[7] = '*';
    if(c == 4)
        gleichung[7] = '/';

    if(d == 1)
        gleichung[9] = '+';
    if(d == 2)
        gleichung[9] = '-';
    if(d == 3)
        gleichung[9] = '*';
    if(d == 4)
        gleichung[9] = '/';
    printf("%s\n", gleichung);
    return berechne_gleichung(gleichung);
}

float berechne_gleichung(char gleichung[11])
{
    /* Hier wird das Ergebnis der Gleichung berechnet, indem zuerst die Gleichung in Teile zerlegt wird */
    /* Zuerst das INnere der Klammer ausrechnen */
    float inderklammer;

    if(gleichung[2] == '+')
        inderklammer = 6+2;
    else if(gleichung[2] == '-')
        inderklammer = 6-2;
    else if(gleichung[2] == '*')
        inderklammer = 6*2;
    else if(gleichung[2] == '/')
        inderklammer = 6/2.0;
    printf("Inhalt der Klammer: %f\n", inderklammer);
    /* Punkt vor Strich beachten */
    float naechstes;
    float mitte;
    if(gleichung[5] == '*' || gleichung[5] == '/') /* Wenn nach der Klammer Punkt kommt, dann sofort die Klammer zu der darauffolgenden Zahl rechnen */
    {
        if(gleichung[5] == '*')
            naechstes = inderklammer*8;
        else if(gleichung[5] == '/')
            naechstes = inderklammer/8.0;
        if(gleichung[7] == '+')
            naechstes += 9;
        else if(gleichung[7] == '-')
            naechstes -= 9;
        printf("%f\n", naechstes);
    }
    else if(gleichung[5] == '-' || gleichung[5] == '+') /* Wenn nach der Klammmer ein Strich kommt, dann schauen was als nächstes Rechenzeichen kommt */
    {
        if(gleichung[7] == '*' || gleichung[7] == '/')
        {
            if(gleichung[7] == '*')
                mitte = 8*9;
            else if(gleichung[7] == '/')
                mitte = 8/9.0;
        if(gleichung[5] == '-')
            naechstes = inderklammer-mitte;
        else if(gleichung[5] == '+')
            naechstes = inderklammer+mitte;
        }
        else if(gleichung[7] == '-' || gleichung[7] == '+')
        {
            if(gleichung[5] == '-')
            {
                if(gleichung[7] == '-')
                    naechstes = inderklammer-8-9;
                else if(gleichung[7] == '+')
                    naechstes = inderklammer-8+9;
            }
            else if(gleichung[5] == '+')
            {
                if(gleichung[7] == '-')
                    naechstes = inderklammer+8-9;
                else if(gleichung[7] == '+')
                    naechstes = inderklammer+8+9;
            }

        }
    }
    /* (6_2)_8_9_1  Notiz*/
    if(gleichung[9] == '+')
        naechstes += 1;
    else if(gleichung[9] == '-')
        naechstes -= 1;
    printf("Lösung der Gleichung: %f\n", naechstes);
    return naechstes;
}
 

ntor

Stammuser
#18
Hier auch mal meine C++-Lösung ;).
Hab jetzt leider Punkt-vor-Strich nicht beachtet und es nur für diese Gleichung gemacht, aber daran will ich mich später nochmal wagen (vll. auch mithilfe von Lua) ;)

Code:
#include <iostream>
#include <memory>
using namespace std;

//Für die Gleichung "(6_2)_8_9_1= 13 "

struct OP
{     virtual long Apply(long Opera1, long Opera2) = 0;
    virtual char OpIs(void) = 0;    };

struct Plus : public OP
{     virtual long Apply(long Opera1, long Opera2) { return Opera1 + Opera2; }
    virtual char OpIs(void) { return '+'; }    };

struct Minus : public OP
{     virtual long Apply(long Opera1, long Opera2) { return Opera1 - Opera2; }
    virtual char OpIs(void) { return '-'; }    };

struct Mul : public OP
{     virtual long Apply(long Opera1, long Opera2) { return Opera1 * Opera2; }
    virtual char OpIs(void) { return '*'; }    };

struct Div : public OP
{     virtual long Apply(long Opera1, long Opera2) { return Opera1 / Opera2; }
    virtual char OpIs(void) { return '/'; }    };

/**********************************
*** BEGIN OF MAIN******************
***********************************/

int main(void)
{
    cout << "Punkt-vor-Strich wird nicht beachtet!\n" << endl;
    OP * opTable[4] = {new Plus, new Minus, new Mul, new Div};
    for(int a=0; a < 4; ++a)
        for(int b=0; b < 4; ++b)
            for(int c=0; c < 4; ++c)
                for(int d=0; d < 4; ++d)
                    if(    opTable[d]->Apply( opTable[c]->Apply( opTable[b]->Apply( opTable[a]->Apply(6,2), 8), 9), 1) == 13)
                        cout << "(6" << opTable[a]->OpIs() << "2)" << opTable[b]->OpIs() << '8' << opTable[c]->OpIs() << '9' << opTable[d]->OpIs() << "1 = 13" << endl;

    for(int delCount=0; delCount < 4; ++delCount)
        delete opTable[delCount];
}
 
#19
Hier mal meine Lösung in C#.
Leider auch ohne Punkt vor Strich Rechnung, allerdings können auch andere Gleichungen mit 4 Operatoren berechnet werden.

public static List<int> SplitZahlen(string gleichung)
{
string[] split = gleichung.Split(new Char[] { '_', '=' });
List<int> zahlen = new List<int>();

foreach (string s in split)
zahlen.Add(Convert.ToInt32(s));

return zahlen;
}

public static string Rechne(string gleichung)
{
List<int> zahlen = SplitZahlen(gleichung);
char[] operatoren = new char[4] { '+', '-', '*', '/' };
int erg = zahlen.Last();
int zwischenerg = 0;

for (int i = 0; i < 4; i++)
{
for (int c = 0; c < 4; c++)
{
for (int z = 0; z < 4; z++)
{
for (int y = 0; y < 4; y++)
{
switch (operatoren) // 1. Operator
{
case '+':
zwischenerg = zahlen[0] + zahlen[1];
break;
case '-':
zwischenerg = zahlen[0] - zahlen[1];
break;
case '*':
zwischenerg = zahlen[0] * zahlen[1];
break;
case '/':
zwischenerg = zahlen[0] / zahlen[1];
break;
}
switch (operatoren[c]) // 2. Operator
{
case '+':
zwischenerg += zahlen[2];
break;
case '-':
zwischenerg -= zahlen[2];
break;
case '*':
zwischenerg *= zahlen[2];
break;
case '/':
zwischenerg /= zahlen[2];
break;
}
switch (operatoren[z]) // 3. Operator
{
case '+':
zwischenerg += zahlen[3];
break;
case '-':
zwischenerg -= zahlen[3];
break;
case '*':
zwischenerg *= zahlen[3];
break;
case '/':
zwischenerg /= zahlen[3];
break;
}
switch (operatoren[y]) // 4. Operator
{
case '+':
zwischenerg += zahlen[4];
break;
case '-':
zwischenerg -= zahlen[4];
break;
case '*':
zwischenerg *= zahlen[4];
break;
case '/':
zwischenerg /= zahlen[4];
break;
}
if ( zwischenerg == erg )
{
return (zahlen[0].ToString() + operatoren.ToString() + zahlen[1].ToString() +
operatoren[c].ToString() + zahlen[2].ToString() + operatoren[z].ToString() +
zahlen[3].ToString() + operatoren[y].ToString() + zahlen[4].ToString() + "=" + erg);
} zwischenerg = 0;
}
}
}
} return "Keine gültigen Operatoren gefunden!";
}
public static void Main(string[] args)
{
DateTime start = DateTime.Now;

Console.WriteLine(Rechne("6_2_8_9_1=13"));

DateTime ende = DateTime.Now;
TimeSpan diff = ende - start;
Console.WriteLine(diff.Milliseconds+" ms");
}
 
#20
Zum Ende hin wurde ich faul.
Böses Fluffy, eval zu benutzten -.-.
Hier mal ES6-Features mit Node v.0.11.14.

PHP:
var equation = "(6_2)_8_9_1=13",
    operators = ['+', '-', '*', '/'],
    result= [],
    solutions = [],
    equationResult = equation.split("=")[1];


    function *generator(elementCount) {
    var maxCombinations = Math.pow(operators.length, elementCount),
        currentCombination = -1;

    while(++currentCombination < maxCombinations) {
        result = [];

        var tmpCurrentCombination = currentCombination,
            modCurrentCombination = 0;

        do{
            modCurrentCombination = tmpCurrentCombination % operators.length;
            tmpCurrentCombination = parseInt(tmpCurrentCombination / operators.length);
            result.unshift(operators[modCurrentCombination]);
        } while(tmpCurrentCombination > 0);

        while(result.length < elementCount) {
            result.unshift(operators[0]);
        }

        yield result;
    }
}

gen = generator(4);

var data = gen.next();

while(!data.done) {
    var tmpEquation = equation.split("=")[0];
    for(var i in data.value){
        tmpEquation = tmpEquation.replace(new RegExp("_"), data.value[i]);
    }

    if(eval(tmpEquation + "==" + equationResult)) {
        solutions.unshift(tmpEquation + "=" + equationResult);
    }

    data = gen.next();
}

if(solutions.length === 0) {
    console.log("No result found")
} else {
    for(var i in solutions) {
        console.log(solutions[i]);
    }
}
 
Oben