ProgrammieraufgabenHier wird regelmäßig eine neue Programmieraufgabe gestellt, die dann gelöst werden soll und in Zusammenarbeit mit den Moderatoren auch besprochen werden kann.
Operatoren für gegebene Gleichung finden (Bruteforce)
Diskussion: Operatoren für gegebene Gleichung finden (Bruteforce) im Forum Programmieraufgaben, in der Kategorie Code Kitchen; Anzeige
Folgende Programmieraufgabe wurde von IsNull eingereicht:
Folgende Gleichung ist gegeben: (6_2)_8_9_1= 13
Die Underlines stellen einen Operator dar, welchen ...
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..
Hier die Html-version
<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>
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)
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.)
100 Zeilen C++
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.
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.
Zitat:
Bei mir braucht der Code knapp 15ms für die beiden Lösungen der Beispielgleichung.
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..)
klick mich
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:
ich bin 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"}
könnte man den für einen bruteforcer, der eine eingegebene gleichung rausfinden soll denn nicht einen codegenerator schreiben?
ist das überhaupt erlaubt?
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*
*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.
py
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
1Likes
12.01.07, 18:46
Operatoren für gegebene Gleichung finden (Bruteforce) 
sry, dachte es wäre okay 
Linear-Darstellung
Ähnliche Themen 
