Entwickler-Ecke

Ankündigungen - Lösung zu Paranuss 1


Kha - Fr 25.12.09 17:56
Titel: Lösung zu Paranuss 1
Auch wenn Bonuszahlungen dieses Jahr wirtschaftsbedingt ausfallen werden, darf sich der Weihnachtsmann immerhin über die Zahl 4304761169 auf seinem nächsten Gehaltszettel freuen :D .

Im Anhang findet sich das ausgefüllte Schema (txt, 8.03 KB) sowie eine Skizze (pdf, 87.27 KB) des angedachten Lösungsverfahrens. Anscheinend haben bei vielen aber auch simplere Ideen zum Ziel geführt, wie langweilig ;P .


BenBE - Fr 25.12.09 20:48
Also, meine Lösung ist so einfach, wie genial: Wie erschlagen die Aufgabe mit einem linearen Gleichungssystem :mrgreen:

Jetzt bleiben da noch die Fragen:
1. Wie sehen die Gleichungen aus?
2. Wie behandelt man die dabei auftretenden Faktoren?

Hier mal meine (zusammengehackte) PHP-Lösung:

Zusammengehackte PHP-Lösung: 
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:
62:
63:
64:
65:
66:
67:
68:
69:
70:
71:
72:
73:
74:
75:
76:
77:
78:
79:
80:
81:
82:
83:
84:
85:
86:
87:
88:
89:
90:
91:
92:
93:
94:
95:
96:
97:
98:
99:
100:
101:
102:
103:
104:
105:
106:
107:
108:
109:
110:
111:
112:
113:
114:
115:
116:
117:
118:
119:
120:
121:
122:
123:
124:
125:
126:
127:
128:
129:
130:
131:
132:
133:
134:
135:
136:
137:
138:
139:
140:
141:
142:
143:
144:
145:
146:
147:
148:
149:
150:
151:
152:
153:
154:
155:
156:
157:
158:
159:
160:
161:
162:
163:
164:
165:
166:
167:
168:
169:
170:
171:
172:
173:
174:
175:
176:
177:
178:
179:
180:
181:
182:
183:
184:
185:
186:
187:
188:
189:
190:
191:
192:
193:
194:
195:
196:
197:
198:
199:
200:
201:
202:
203:
204:
205:
206:
207:
208:
209:
210:
211:
212:
213:
214:
215:
216:
217:
218:
219:
220:
221:
222:
223:
224:
225:
226:
227:
228:
229:
230:
231:
232:
233:
234:
235:
236:
237:
238:
239:
240:
241:
242:
243:
244:
245:
246:
247:
248:
249:
250:
251:
252:
253:
254:
255:
256:
257:
258:
259:
260:
261:
262:
263:
264:
265:
266:
267:
268:
269:
270:
271:
272:
273:
274:
275:
276:
277:
278:
279:
280:
281:
282:
283:
284:
285:
286:
287:
288:
289:
290:
291:
292:
293:
294:
295:
296:
297:
298:
299:
300:
 
<?php

define('BLANK', '___________');

$Schema = <<<VERDIENST
___________
___________ ___________
___________ ___________ ___________
___________  542353018  ___________ ___________
___________ ___________  270488136   266170472  ___________
___________ ___________ ___________ ___________ ___________ ___________
___________ ___________ ___________ ___________ ___________ ___________ ___________
___________ ___________ ___________ ___________ ___________ ___________ ___________ ___________
___________ ___________ ___________ ___________ ___________ ___________ ___________ ___________ ___________
___________ ___________ ___________ ___________ ___________ ___________ ___________ ___________ ___________ ___________
___________ ___________ ___________ ___________ ___________   4263762   ___________ ___________ ___________ ___________ ___________
___________ ___________ ___________ ___________ ___________ ___________ ___________ ___________ ___________   1859824   ___________   1610467
___________ ___________ ___________ ___________ ___________ ___________ ___________ ___________ ___________ ___________ ___________ ___________ ___________
___________ ___________ ___________   532656    ___________ ___________ ___________ ___________ ___________ ___________   466095      424991    ___________ ___________
___________   267918    ___________ ___________   264672    ___________ ___________ ___________ ___________ ___________ ___________ ___________   202462    ___________ ___________
___________ ___________ ___________ ___________ ___________ ___________ ___________ ___________ ___________ ___________ ___________   116973    ___________ ___________ ___________ ___________
___________ ___________ ___________ ___________ ___________ ___________ ___________    66410    ___________ ___________ ___________ ___________ ___________ ___________ ___________    49254    ___________
___________ ___________ ___________ ___________    33843    ___________ ___________ ___________ ___________ ___________ ___________ ___________ ___________ ___________ ___________    23357    ___________ ___________
___________    15428       16330    ___________ ___________ ___________ ___________ ___________    16581    ___________ ___________ ___________ ___________    13956    ___________ ___________ ___________    13900    ___________
___________ ___________ ___________ ___________ ___________ ___________ ___________ ___________    8192     ___________ ___________    8407     ___________ ___________ ___________ ___________ ___________ ___________    7515     ___________
___________ ___________ ___________ ___________ ___________ ___________ ___________ ___________    4056     ___________ ___________ ___________ ___________ ___________ ___________ ___________ ___________ ___________ ___________ ___________ ___________
   2114     ___________ ___________ ___________ ___________ ___________ ___________ ___________ ___________ ___________ ___________ ___________ ___________ ___________ ___________ ___________ ___________ ___________ ___________ ___________ ___________ ___________
___________ ___________ ___________ ___________ ___________ ___________ ___________ ___________ ___________ ___________ ___________ ___________ ___________ ___________ ___________ ___________ ___________ ___________ ___________ ___________ ___________    1057     ___________
___________     526     ___________ ___________ ___________ ___________ ___________ ___________ ___________ ___________ ___________ ___________ ___________ ___________     510     ___________ ___________ ___________ ___________ ___________ ___________ ___________ ___________ ___________
___________ ___________ ___________ ___________ ___________ ___________ ___________ ___________ ___________ ___________ ___________ ___________ ___________ ___________ ___________ ___________ ___________ ___________ ___________ ___________ ___________ ___________ ___________ ___________ ___________
___________     152     ___________ ___________ ___________ ___________ ___________ ___________ ___________ ___________     124     ___________ ___________ ___________ ___________ ___________ ___________ ___________ ___________ ___________ ___________ ___________ ___________ ___________ ___________ ___________
___________ ___________ ___________     61      ___________ ___________ ___________ ___________ ___________ ___________ ___________ ___________ ___________     72      ___________ ___________ ___________ ___________ ___________ ___________ ___________ ___________ ___________ ___________ ___________ ___________ ___________
___________ ___________ ___________ ___________     28      ___________ ___________ ___________ ___________ ___________ ___________ ___________ ___________ ___________ ___________ ___________ ___________     29      ___________ ___________ ___________ ___________ ___________ ___________ ___________ ___________ ___________ ___________
___________ ___________ ___________ ___________ ___________ ___________ ___________ ___________ ___________ ___________ ___________ ___________ ___________ ___________     21      ___________ ___________ ___________ ___________ ___________ ___________ ___________ ___________ ___________ ___________     13      ___________ ___________ ___________
___________ ___________     16      ___________ ___________ ___________      9      ___________ ___________ ___________ ___________ ___________ ___________ ___________ ___________ ___________ ___________ ___________ ___________ ___________      4           3      ___________ ___________ ___________ ___________ ___________     10      ___________ ___________
VERDIENST;

echo "Daten einlesen ...\r\n";
$Schema = explode("\r\n", $Schema);

$data = array();
foreach($Schema as $Level) {
    $dataLevel = array();
    while(!empty($Level)){
        $dataLevel[] = trim(substr($Level, 0, 11));
        $Level = substr($Level, 12);
    } // while
    $data[] = $dataLevel;
}

$Schema = $data;

echo "Pre-Optimierung ...\r\n";
$blank = 0;
while($blank) {
    $blank--;

    $row = rand(0, count($Schema)-1);
    $col = rand(0, $row);
    
    $cell = $Schema[$row][$col];
    
    if(BLANK != $cell) {
        //Check if we can fill in below ...
        if($row < count($Schema)-1) {
            $c1 = $Schema[$row+1][$col];
            $c2 = $Schema[$row+1][$col+1];
        
            if(BLANK == $c1 && BLANK != $c2) {
                $c1 = $cell - $c2;
                $Schema[$row+1][$col] = $c1;
                $blank+=10;
            }

            if(BLANK != $c1 && BLANK == $c2) {
                $c2 = $cell - $c1;
                $Schema[$row+1][$col+1] = $c2;
                $blank+=10;
            }
        }
    } else {
        //Look if we can add from below ...
        if($row < count($Schema)-1) {
            $c1 = $Schema[$row+1][$col];
            $c2 = $Schema[$row+1][$col+1];
        
            if(BLANK != $c1 && BLANK != $c2) {
                $cell = $c1 + $c2;
                $Schema[$row][$col] = $cell;
                $blank+=10;
            }
        }

        //Look if we can conclude from above
        if(0 < $row) {
            //Left boundary check ...
            if(0 == $col) {
                $c1 = $Schema[$row-1][$col];
                $c2 = $Schema[$row][$col+1];
                if(BLANK != $c1 && BLANK != $c2) {
                    $cell = $c1 - $c2;
                    $Schema[$row][$col] = $cell;
                    $blank+=10;
                }
            } elseif ($col < $row) {
                $c1 = $Schema[$row-1][$col];
                $c2 = $Schema[$row][$col+1];
                if(BLANK != $c1 && BLANK != $c2) {
                    $cell = $c1 - $c2;
                    $Schema[$row][$col] = $cell;
                    $blank+=10;
                }

                $c1 = $Schema[$row-1][$col-1];
                $c2 = $Schema[$row][$col-1];
                if(BLANK != $c1 && BLANK != $c2) {
                    $cell = $c1 - $c2;
                    $Schema[$row][$col] = $cell;
                    $blank+=10;
                }
            } elseif ($col == $row) {
                $c1 = $Schema[$row-1][$col-1];
                $c2 = $Schema[$row][$col-1];
                if(BLANK != $c1 && BLANK != $c2) {
                    $cell = $c1 - $c2;
                    $Schema[$row][$col] = $cell;
                    $blank+=10;
                }
            }
            
        }
    }
    
}

echo "Optimierter Baum ...\r\n";

foreach($Schema as $Line) {
    foreach($Line as $Item) {
        printf('%11s ', $Item);
    }
    echo "\r\n";
}

echo "Gleichungssystem vorbereiten ...\r\n";

$vars = array();
$knowns = array();
$equ = array();
$maxline = count($Schema) - 1;

foreach($Schema as $row => $Line) {
    foreach($Line as $col => $Item) {
        $varid = count($vars);
        $vars[$varid] = array($row, $col);
        if (BLANK != $Item) {
            $knowns[$varid] = (int)$Item;
        }
        if($row < $maxline) {
            $c1 = ($row * ($row + 1)) / 2 + $col;
            $c2 = (($row + 1) * ($row + 2)) / 2 + $col;
            $c3 = (($row + 1) * ($row + 2)) / 2 + $col + 1;

            $equ[] = array($c1, $c2, $c3);
        }
    }
}

//Calc the size (number of knows + number of equations)
//Width = number of variables + 1

$equationLine = array_fill(0, count($vars) + 1, 0);
$eqSys = array_fill(0, count($knowns) + count($equ), $equationLine);
$i = 0;
foreach($knowns as $id => $val) {
    $eqSys[$i][$id] = 1;
    $eqSys[$i][count($vars)] = $val;
    $i++;
}
foreach($equ as $id => $cond) {
    $eqSys[$i][$cond[0]] = 1;
    $eqSys[$i][$cond[1]] = -1;
    $eqSys[$i][$cond[2]] = -1;
    $eqSys[$i][count($vars)] = 0;
    $i++;
}

//var_dump($eqSys);
showSys($eqSys);

echo "Gleichungssystem lösen ...\r\n";
$data = SolveLES($eqSys);

foreach($data as $i => $l) {
    foreach($l as $j => $c) {
        $data[$i][$j] = round($c, 1);
        if(abs($data[$i][$j]) < 1) $data[$i][$j] = 0;
    }

}

showSys($data);

foreach($vars as $i => $v) {
    $Schema[$v[0]][$v[1]] = $data[$i][count($vars)];
}
foreach($Schema as $Line) {
    foreach($Line as $Item) {
        printf('%11s ', $Item);
    }
    echo "\r\n";
}

function showSys($A) {
    echo "\r\n";
    foreach($A as $l) {
        foreach($l as $c) {
            echo $c . " ";
        }
        echo "\r\n";
    }
}

function SolveLES($A) {
    // DONE -oBenBE -cMaths, Matrix : SolveLES reorganized and rebuilt
    // DONE -oBenBE -cBug, Maths, Matrix : AV in Eliminationszyklus

    $SY = count($A);
    $SX = count($A[0]);

//    If (($SY <= 0) || (($SX <> $SY + 1) && ($SX <> $SY))) {
//        //RaiseInvalidDim;
//        return array(1337);
//    }

    $Result = $A;

    //Elimination Cycle:
    $ActRow = 0;
    For ($ActCol = 0; $ActCol < $SY; $ActCol++) {
        If (abs($Result[$ActRow][$ActCol]) < 1E-4) {
              $Swapped = False;
            For ($ActRow2Swap = $ActRow + 1; $ActRow2Swap < $SY; $ActRow2Swap++) {
                If (abs($Result[$ActRow2Swap][$ActCol]) >= 1E-4) {
                    $tmp = $Result[$ActRow2Swap];
                    $Result[$ActRow2Swap] = $Result[$ActRow];
                    $Result[$ActRow] = $tmp;
                    $Swapped = True;
                    Break;
                }
            }

            If(!$Swapped)
                Continue;
        }

        For( $ActRow2Work = $ActRow + 1; $ActRow2Work < $SY; $ActRow2Work++) {
            If (abs($Result[$ActRow2Work][$ActCol]) >= 1E-4) {
                //MatrixRowSub($Result, $ActRow2Work, $ActRow, $Result[$ActRow2Work][$ActCol] / $Result[$ActRow][$ActCol]);
                $tmp = $Result[$ActRow2Work][$ActCol] / $Result[$ActRow][$ActCol];
                for($MRSWork = 0; $MRSWork < $SX; $MRSWork++) {
                    $Result[$ActRow2Work][$MRSWork] -= $Result[$ActRow][$MRSWork] * $tmp;
                }
            }
        }
            
        $ActRow++;
    }

    //Back Substitution Cycle:
    For ($ActRow = $SY - 1; $ActRow >= 0; $ActRow--) {
        For ($ActCol = $ActRow; $ActCol < $SX; $ActCol++) {
            If (abs($Result[$ActRow][$ActCol]) > 1E-4) {
                //MatrixRowDiv($Result, $ActRow, $Result[$ActRow][$ActCol]);
                $tmp = $Result[$ActRow][$ActCol];
                for($MRDWork = 0; $MRDWork < $SX; $MRDWork++) {
                    $Result[$ActRow][$MRDWork] /= $tmp;
                }

                If ($ActCol <> $SX - 1) {
                    For ($ActRow2Work = 0; $ActRow2Work < $ActRow; $ActRow2Work++) {
                        If ($Result[$ActRow2Work][$ActCol] <> 0) {
                            //MatrixRowSub($Result, $ActRow2Work, $ActRow, $Result[$ActRow2Work][$ActCol]);
                            $tmp = $Result[$ActRow2Work][$ActCol];
                            for($MRSWork = 0; $MRSWork < $SX; $MRSWork++) {
                                $Result[$ActRow2Work][$MRSWork] -= $Result[$ActRow][$MRSWork] * $tmp;
                            }
                        }
                    }
                }

                Break;
            }
        }
    }

    return $Result;
}

?>


Das Verstehen sei dem geneigten Leser überlassen ;-)

Zur Erklärung aber vielleicht soviel:

Ich ordne jedem Wichtel\Weihnachtsmann eine Variable zu. Zusätzlich merke ich mir, wo dieser im Original-Array steht (Anzeige später)

Nun stelle ich Gleichungen mit den Abhängigkeiten auf:


Quelltext 
1:
2:
3:
4:
5:
6:
 
w[0] - w[1] - w[2] = 0;

w[1] - w[3] - w[4] = 0;
w[2] - w[4] - w[5] = 0;

...


Davor trage ich aber für alle Wichtel, deren Gehalt bekannt ist dies auch als Gleichungen ein:


Quelltext 
1:
 
w[7] = Gehalt;


Danach das Gleichungssystem linear erschlagen und die Lösungen zurück in die Gehaltsliste übertragen und den Kram ausgeben.

Auf Grund von Rundungsfehlern liefert PHP für die unteren Reihen ein wenig ungenaue Werte. Diese Rundungsfehler stören aber für die oberen Zahlen nicht, da diese auf Grund des frühen Auftauchens in den Gleichungen als erste ermittelt werden.

Um die genaue Lösung haben sich dann aber doch noch andere gekümmert: Wer etwas in der letzten Zeit aufgepasst hat, dürfte ggf. mitbekommen haben, dass Flamefire eine Erweiterung meiner BigNum2-Unit zum Verarbeiten von Vorzeichen geschrieben hat. Flamefire hat das entstandene Gleichungssystem nämlich mit BigNum2 erschlagen - einen Aufwand, den ich mir nicht antun wollte, da ich mit sehr hoher Wahrscheinlichkeit davon ausgehen konnte, das meine Lösung ausreichend genau war - für den Weihnachtsmann (Geizhals :mrgreen:)

Eine andere Lösung basiert auf linearer Optimierung. Das erklärt aber IMHO dessen Anwender am Besten ;-)

P.S.: SolveLES ist eine Portierung der gleichnamigen Funktion aus der Mathe-Bibliothek von Omorphia.


Xentar - Fr 25.12.09 22:56
Hm.. Gleichungen..
Hab mir einfach ne Software geschrieben, die den Baum durchrechnet, also lösbare Felder einträgt.
Danach hab ich einfach Werte in der unteren Reihe ausprobiert, und mir das Ergebnis angesehen ;)

Hatte nur leider keine Zeit mehr, das fertig zu machen :(


Oliver Marx - Sa 26.12.09 00:22


Kha - Sa 26.12.09 00:52
@user profile iconBenBE: :think:
Statt Koeffizienten für eine-Gleichung-pro-Gegebene auszurechnen, einfach die elementare Grundgleichung mehrmals aufzustellen, darauf bin ich nicht gekommen.
Mathematik ist dann leider ganz außen vor :mrgreen: und die Implementierung wird etwas komplexer, aber von der Idee her geht es wohl nicht mehr direkter und simpler.

@user profile iconOliver Marx:
Wow, ebenfalls eine äußerst interessante Lösung! Es muss eben nicht immer die direkte Lösung sein, wenn man das Problem stattdessen in ein bekanntes umformulieren kann und dadurch die Implementierung quasi geschenkt bekommt :D .


Noob23 - Sa 26.12.09 08:38
Hallo zusammen,

auf die Idee, für jede der gegebenen Werte eine Gleichung (Grundlage: Binomialkoeffizienten) aufzustellen, bin ich zwar anfangs gekommen ...da es aber an der Progammumsetzung fehlte, wurde eben mit teilweisem Bruteforce drangegangen ;)
Angeboten hat sich natürlich die linke Pyramidenseite, da hier schon relativ viele Zahlen bekannt waren und Lösung ist Lösung auch wenns eleganter ginge :)

Grüße
Noob23

PS: Der Weihnachtsmann wird wohl von den 4304761169 noch an jeden seiner Mitarbeiter ein Weihnachtsgeld auszahlen ;)


Flamefire - So 27.12.09 11:01
tja dann Mein Ansatz:
Der Baum ist vollständig durch die Variablen der untersten Reihe berechenbar.
Also habe ich jede vorgegebene Zahl als Gleichung von den Variablen der untersten Reihe ausdrücken lassen. Das geht mittels Binomialkoeffizienten
Am Ende das Gleichungssystem mittels Gauß hoch und runter rechnen und fertig.

Problem waren die episch großen Zahlen bei den Zwischenschritten. Daraus ist dann die Vorzeichen-BigNum-Lib entstanden ;-)


Hidden - So 27.12.09 11:56
Hi :)

Ich hatte Anfangs die gleichen Ansätze wie user profile iconFlamefire und user profile iconBenBE. Nach ein Paar Sekunden sind mir dann die episch großen Zahlen aufgefallen und user profile iconBenBE meinte in der SB, es ginge schöner als das was ich vorhatte(Matrizen).

Ironischerweise hat user profile iconBenBE mich falsch verstanden, und mein Ansatz war seiner. :nut: Nur hat er von schöner geredet, was ich als "Mathematiker-schön" und nicht "komplizierter aber schneller" verstanden habe und erstmal weitergesucht.

Aus Frustration dass ich nichts schöneres gefunden habe, hab' ich dann den Computer die Rosinen aufpicken lassen und triviale Teildreiecke ergänzen. Dann habe ich jeweils per Hand ein GLG auf Binomealkoeffizientenbasis gelöst(mit einer Unbekannten und 2 Gleichungen :lol:), um zwei Teildreicke zu vereinen und wieder die Rosinen ergänzen lassen. So kommt man innerhalb von 5-10min zu dem Punkt, wo noch 2 Variablen fehlen um das ganze Ding zu bestimmen(inclusive Codingzeit 8)). Hier sei es dem Geneigten Leser überlassen, ob er diese als X und Y einsetzt und ein finales GLG bildet, oder einen 5-Sekunden-Bruteforce macht. Jedenfalls bitte nicht so wie ich, mit oberen und unteren Schranken für alle Felder hab' ich's echt nochmal verkompliziert. War zwar schnell getippt, hat aber lange zu debuggen gebraucht.

lg


Kha - So 27.12.09 17:05
user profile iconHidden hat folgendes geschrieben Zum zitierten Posting springen:
Ich hatte Anfangs die gleichen Ansätze wie user profile iconFlamefire und user profile iconBenBE. Nach ein Paar Sekunden sind mir dann die episch großen Zahlen aufgefallen [...]
user profile iconFlamefire hat folgendes geschrieben Zum zitierten Posting springen:
Problem waren die episch großen Zahlen bei den Zwischenschritten.
Unendliche Genauigkeit ist natürlich immer schön, aber ich habe schon darauf geachtet, dass es auch problemlos mit Floats lösbar ist ;) (was user profile iconBenBEs Code ja auch schon gezeigt hat :) )...


F# 
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:
62:
63:
64:
65:
66:
67:
68:
69:
70:
71:
72:
73:
74:
75:
76:
77:
78:
79:
80:
81:
82:
83:
84:
85:
86:
87:
88:
89:
90:
91:
92:
93:
94:
95:
 
let isZero x = abs x < 1.e-8

let gaussRef (a:float[][]) =
    let m = Array.length a
    let n = Array.length a.[0]
    let mutable i,j = 0,0
    
    while i<m && j<n do
        let mutable maxI = i
        for k = i+1 to m-1 do
            if abs a.[k].[j] > abs a.[maxI].[j] then
                maxI <- k
        if not (isZero a.[maxI].[j]) then
            let temp = a.[i]
            a.[i] <- a.[maxI]
            a.[maxI] <- temp
            
            let x = a.[i].[j]
            for v = 0 to n-1 do
                a.[i].[v] <- a.[i].[v] / x
            for u = i+1 to m-1 do
                let x = a.[u].[j]
                for v = 0 to n-1 do
                    a.[u].[v] <- a.[u].[v] - a.[i].[v] * x
            i <- i+1
        j <- j+1

let backwardSubstitution (a:float[][]) =
    let n = Array.length a
    if Array.length a.[0] <> n+1 then failwith "lengths"
    
    let rec loop xs = function
    | -1 -> xs
    | i  ->
        loop (
         (a.[i].[n] - 
          (xs |> Seq.mapi (fun i' x -> a.[i].[i'+i+1] * x) |> Seq.sum)
        / a.[i].[i]) :: xs) (i-1)
    loop [a.[n-1].[n] / a.[n-1].[n-1]] (n-2)
    
let rec binomial n = function
    | 0 -> 1
    | k when 2 * k > n -> binomial n (n-k)
    | k -> {2..k} |> Seq.fold (fun acc i -> acc * (n+1-i) / i) n
      
let safeBin n k = if k < 0 || k > n then 0 else binomial n k

let apply f x = f x; x

open System
open System.IO
open Microsoft.FSharp.Math
open System.Text.RegularExpressions

let solve file =
    let lines = File.ReadAllLines file
    let n = lines.Length
    
    let given =
        lines
        |> Seq.mapi (fun i s -> 
            s.Split null
            |> Seq.filter (not << String.IsNullOrEmpty)
            |> Seq.mapi (fun j s ->
                let m = Regex.Match (s,@"(\d+)")
                if m.Success then Some (i,j,float m.Groups.[1].Value) else None)
            |> Seq.choose id
        )
        |> Seq.concat
        
    let baseRow =
        given
        |> Seq.map (fun (i,j,x) ->
            Array.init (n+1) (fun j' ->
                if j' = n then x
                else safeBin (n-i-1) (j'-j) |> float
        ))
        |> Seq.toArray
        |> apply gaussRef
        |> Array.filter (Seq.exists (not << isZero))
        |> backwardSubstitution

    let top =
        baseRow 
        |> Seq.mapi (fun i f -> f * float (safeBin (n-1) i))
        |> Seq.sum
        
    printfn "%f" top
    
[<EntryPoint>]
let main args =
    match args with
    | [|file|] -> solve file
    | _ -> printfn "Usage: Solve.exe file"
    0


Flamefire - So 27.12.09 17:27
Nunja bei BenBEs Code hätte ich trotzdem kalte Füße, da es falsche Zwischenlösungen gibt. Trotzdem stimmt es am Ende. Ist etwas ungewöhnlich ;-)

Bei deinem Code, steige ich grade etwas zäh durch.
Wenn ich das richtig sehe, löst du das LGS so:
Variablenweise+ZeilenWeise die Gleichungen durchgehen (Also für i.Zeile i.Variable(i.Spalte)) also normal.
Jetzt suchst du die Zeile, mit dem größten Koeffizienten für die aktuelle Variable und vertauschst sie mit der aktuellen Zeile. Jetzt diese Zeile auf 1 normieren.
und dann normal weiter.

Die backward verstehe ich gar nicht ;-)
Aber ich vermute, das ist dann ohne tricks, oder?


Kha - Mo 28.12.09 00:24
user profile iconFlamefire hat folgendes geschrieben Zum zitierten Posting springen:
Nunja bei BenBEs Code hätte ich trotzdem kalte Füße, da es falsche Zwischenlösungen gibt.
Gut, vielleicht hat er durch die höhere Anzahl von Gleichungen größere Abweichungen. Bei mir ist auch die unterste Reihe hinreichend genau:

Quelltext 
1:
2:
3:
4:
5:
 
[8.00000134; 8.999999777; 16.00000002; 3.999999995; 13.0; 3.0; 9.000000002;
 1.999999998; 15.99999999; 7.000000059; 3.999999852; 13.00000027; 7.999999587;
 1.00000053; 15.9999994; 5.000000596; 7.99999947; 11.00000041; 3.999999742;
 10.00000011; 4.0; 3.0; 1.99999982; 14.0000006; 6.999998775; 10.00000184;
 2.99999816; 10.0; 18.00000584; 0.9999808293]



user profile iconFlamefire hat folgendes geschrieben Zum zitierten Posting springen:
Bei deinem Code, steige ich grade etwas zäh durch.
Brauchst dich nicht dafür durch F# zu quälen, denn der Code ist wirklich "ohne Tricks" :) . gaussRef ist eine 1:1-Übersetzung hiervon [http://en.wikipedia.org/wiki/Gaussian_elimination#Pseudocode], backwardSubstitution eine davon [http://de.wikipedia.org/wiki/Gau%C3%9Fsches_Eliminationsverfahren#R.C3.BCckw.C3.A4rtseinsetzen].
Bei ersterer Funktion lässt sich leider nicht viel mit funktionaler Programmierung drehen, was die Lesbarkeit aber wohl eher erhöht hat ;) .


Martok - Mo 28.12.09 02:10
F# ist das was man dann nimmt, wenn man auch vor .NET-Reflection sicher sein will ;)

Meine Lösung ist noch etwas anders, und basiert auf der Tatsache dass jedes gegebene Feld die "rekursive Summe" aller Felder unter ihm ist. Man kann also ein Dreieck darunter aufspannen, so dass man einen Abschnitt der untersten Reihe bekommt.
Die Koeffizienten kriegt man aus (n k) für n=20 und k=Spalte.

Den Wust an Gleichungssystemen überführt man in eine Matrix und einen Vektor, übergibt das ganze in gewünschtem Format an den Kernel eines grade verfügbaren CAS, und hole sich das Ergebnis aus Stdout. Da hätte man dann auch direkt die Gleichung für den obersten Wert aufstellen können, ich hab aber nur die Werte eintragen lassen und dann iterativ nach oben addiert. Alle vorgegeben Werte haben reingepasst, musste also richtig sein.

Anders gesagt: der selbst geschriebe Anteil war lediglich eine Hilfe um das LGS aufzustellen und damit elegant an der beabsichtigten Aufgabe vorbeiprogrammiert ;)


Flamefire - Mo 28.12.09 10:59
Nunja am Ende war mir das mit der Bignum doch am liebsten, da man so wirklich sicher gehn konnte, dass alles stimmt

UND: Man hat die Aufgabe gelöst, wie man es sollte. Nicht was fertiges verwendet ;-)

Ne ok, bei der andren Aufgabe mit den Funken habe ich ja auch bei Narses abgeguckt also sollte ich da still sein ^^


ub60 - Mo 28.12.09 20:14
user profile iconFlamefire hat folgendes geschrieben Zum zitierten Posting springen:
Nunja am Ende war mir das mit der Bignum doch am liebsten, da man so wirklich sicher gehn konnte, dass alles stimmt

Also, ich habe Int64 verwendet, das ging auch ganz gut.
Und ich hab es auch SELBST programmiert :P :lol:

ub60


Hidden - Mo 28.12.09 22:41
Hi :)

Ich habe auch komplett mit Int64 gearbeitet. Selbst das Gehalt des Weihnachtsmanns war aber schon Int64 und nicht mehr Integer, und beim Gauß-Algorithmus werden ständig Zeilen miteinander multipliziert. Für höhere Genauigkeit bei Gauß-Jordan werden dann zu allem Überfluss noch jeweils extra die größten Zahlen ausgewählt.

Selbst bei geschickter Programmierung muss es hier doch bei Binomialkoeffizienten der untersten Zeile zum Überlauf kommen, wenn man immer nur multipliziert und nie ganze Zeilen mit 0<k<1 malnimmt, wie es der Gauß-Jordan tut?

Zwar ist Int64 mit High(Int64) = High(Integer)² = +9.223.372.036.854.775.808 schon sehr groß, aber mit dem Produkt zweier Zahlen im Bereich High(Integer) kommt man sehr schnell in den Bereich.

user profile iconFlamefire hat folgendes geschrieben:
Nunja am Ende war mir das mit der Bignum doch am liebsten, da man so wirklich sicher gehn konnte, dass alles stimmt
Wenn man es raushatte, konnte man sein Ergebnis doch sehr einfach durch Hochrechnen von der untersten Zeile und Vergleich mit allen gegebenen Zahlen überprüfen :nixweiss:


Nur schnell zusammengehackt, meine Überprüfung vom Abgabetag: 
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:
62:
63:
64:
65:
66:
67:
68:
69:
70:
71:
72:
73:
74:
75:
76:
77:
78:
79:
80:
81:
82:
83:
84:
85:
86:
87:
88:
89:
90:
91:
92:
93:
94:
95:
96:
97:
98:
99:
 
procedure TMainFrm.Button1Click(Sender: TObject);
begin
  self.ReadGalton;  //Unbearbeitete Version einlesen
end;

procedure TMainFrm.Button2Click(Sender: TObject);
var
  i, j: Integer;
  aGaltonCopy: Array of Array of Int64;
begin
  SetLength(aGaltonCopy, Length(FGalton));          //
  for i := 0 to Length(FGalton) - 1 do begin         //
    SetLength(aGaltonCopy[i], Length(FGalton[i]));  //Unbearbeitete Version in den Zwischenspeicher
    for j := 0 to Length(FGalton[i]) - 1 do          //
      aGaltonCopy[i, j] := FGalton[i, j];           //
  end;                                              //
  self.ReadGalton;  //vermeintlich fertige Kopie einlesen
  for i := 0 to Length(FGalton) - 1 do begin
    for j := 0 to Length(FGalton[i]) - 1 do  //alle Fehler durch Leerfelder ersetzen
      if (aGaltonCopy[i, j] <> -1) and (FGalton[i, j] <> aGaltonCopy[i, j]) then
        FGalton[i, j] := -1;
  end;
  self.PrintGalton;    
end;

////////////// oben benutzte Funktionen  /////////////////////////////////////////////////////

function FillTo(const S: String; aToLength: Integer; aFillWith: Char = ' '): String;
begin
  if aToLength <= Length(S) then
    result := S
  else begin
    aToLength := aToLength - Length(S);
    result := StringOfChar(aFillWith, aToLength div 2)
            + S + StringOfChar(aFillWith, aToLength - aToLength div 2);
  end;
end;

procedure TMainFrm.PrintGalton;
var
  i, j: Integer;
  S, L: String;
  aLen: Integer;
  aInt: String;
begin
  S := '';
  aLen := Length(FGalton);
  for i := 0 to aLen - 1 do begin
    L := StringOfChar(' ', 6 * (aLen - 1 - i));
    for j := 0 to Length(FGalton[i]) - 1 do begin
      if FGalton[i, j] = -1 then aInt := '___________'
      else aInt := IntToStr(FGalton[i, j]);
      L := L + FillTo(aInt, 11) + ' ';
    end;
    S := S + L + #13#10;
  end;
  RichEdit1.Lines.Append(S);
end;

procedure TMainFrm.ReadGalton;
var
  aLines: TStrings;
  L: String;
  i, j: Integer;
  aPos: Integer;
  aBuffer: String;
  aIsNum: Boolean;
begin
  aLines := RichEdit1.Lines;
  SetLength(FGalton, aLines.Count);
  for i := 0 to aLines.Count - 1 do begin
    L := aLines[i] + '#';
    SetLength(FGalton[i], i + 1);
    aIsNum := false;
    aBuffer := ' ';
    j := 0;
    for aPos := 0 to Length(L) do begin
      if L[aPos] in ['0'..'9'] then begin
        if aIsNum then aBuffer := aBuffer + L[aPos]
        else begin
          aIsNum := true;
          aBuffer := L[aPos];
        end;
      end else begin
        if aIsNum then begin
          FGalton[i, j] := StrToInt64(aBuffer);
          aIsNum := false;
          Inc(j);
        end;
        if (aBuffer = '_') and (L[aPos] <> '_') then begin
          FGalton[i, j] := -1;
          Inc(j);
        end;
        aBuffer := L[aPos];

      end;
    end;
  end;
end;


lg,


Entwickler-Ecke.de based on phpBB
Copyright 2002 - 2011 by Tino Teuber, Copyright 2011 - 2026 by Christian Stelzmann Alle Rechte vorbehalten.
Alle Beiträge stammen von dritten Personen und dürfen geltendes Recht nicht verletzen.
Entwickler-Ecke und die zugehörigen Webseiten distanzieren sich ausdrücklich von Fremdinhalten jeglicher Art!