Project Euler Problem 92: Erklärung eines Lösungsweges gesucht

Antoras

SeppJ schrieb:

Nein, 1 ist nur einer der bekannten Werte, mit denen man seine Rekursion abbrechen kann. Es wird die Gesamtzahl an Zahlen mit 7 oder weniger Ziffern zurückgegeben die äquivalent zu n sind in dem Sinne des ersten Teils des Beweises.

Ich kapier es noch immer nicht.
In welcher Reihenfolge werden die Additionen in f(n,k) den aufgerufen? Wird die komplette Gleichung mit

f(n-0^2,k-1) + f(n-1^2,k-1) + f(n-2^2,k-1) + .... + f(n-9^2,k-1)
f(n-0^2,k-2) + f(n-1^2,k-2) + f(n-2^2,k-2) + .... + f(n-9^2,k-2) 
f(n-0^2,k-3) + f(n-1^2,k-3) + f(n-2^2,k-3) + .... + f(n-9^2,k-3) 
...
f(n-0^2,k-1) + f(n-1^2,0) + f(n-2^2,0) + .... + f(n-9^2,0)

aufgerufen? Also, dass k so lange runter gezählt wird bis es 0 ist?

SeppJ schrieb:

edit2: Und natürlich hätte eine Bruteforce Lösung innerhalb von Sekunden (höchstens!) alle 7-Stelligen Zahlen durchprobiert, ohne dass man sich stundenlang Gedanken hätte machen müssen :p .

Ich weiß, meine jetzige Lösung braucht nicht mal eine Sekunde, aber ist Brute-force. Die Lösung interessiert mich an sich nicht, ich bin am Lösungsweg interessiert und Brute-force ist inakzeptabel.

Michael E.

Aus deinem Code-Block werde ich nicht schlau, weshalb ich dir nicht sagen kann, ob du es richtig verstanden hast.

n ist eine Zahl zwischen 2 und 567, das hast du schon richtig erkannt. k ist die Anzahl der Ziffern. f(n-x^2,k-1) bedeuet: Die aktuelle Ziffer, die ich mir gerade anschaue, ist x. Da ich als gesamte Summe n herausbekommen möchte, müssen sich die anderen k-1 Ziffern zusammen zu n-x^2 aufsummieren. Wenn man alle möglichen x durchgeht und aufsummiert, hat man alle Möglichkeiten durchprobiert und f(n, k) bestimmt.

Nun zu den Startwerten:

f(n, k) = 0, wenn n < 0. Diese Bedingung musst du reinnehmen für den Fall, dass x^2 > n ist bei einem deiner rekursiven Aufrufe. Denn es gibt keine Möglichkeit, auf die Gesamtsumme n zu kommen, wenn du mit den bisherigen Ziffern bereits mehr als n erreicht hast.

f(n, 0) = 0, wenn n > 0. Du bist alle dir zur Verfügung stehenden Ziffern durchgegangen, aber die Summe ist noch nicht n. Also wieder nicht das, was du haben willst.

f(0, 0) = 1. In diesem Fall summieren sich die k Ziffern zu n. Das ist genau der Fall, den du haben willst. Der Stack Trace repräsentiert genau eine Möglichkeit für die Ziffern 1,...,k, die Summe n zu erreichen. Deshalb ist der Zahlenwert 1.

SeppJ

In welcher Reihenfolge werden die Additionen in f(n,k) den aufgerufen?

In Code ausgedrückt:

int f(int n, int k)
{
 if (n < 0) return 0;
 if (k == 0 && n == 0) return 1;
 if (k == 0) return 0;

 return f(n - 0*0, k-1)
      + f(n - 1*1, k-1)
      + f(n - 2*2, k-1)
      + f(n - 3*3, k-1)
      + f(n - 4*4, k-1)
      + f(n - 5*5, k-1)
      + f(n - 6*6, k-1)
      + f(n - 7*7, k-1)
      + f(n - 8*8, k-1)
      + f(n - 9*9, k-1);
}

#include<iostream>
using namespace std;
int main()
{
  for (int n = 2; n <= 567; ++n)
  cout << "Die Anzahl siebenstelliger Zahlen deren Ziffernquadrate die Summe " << n << " ergeben ist " << f(n,7) << endl;
}

Ich weiß, meine jetzige Lösung braucht nicht mal eine Sekunde, aber ist Brute-force. Die Lösung interessiert mich an sich nicht, ich bin am Lösungsweg interessiert und Brute-force ist inakzeptabel.

Du wirst überrascht sein, wenn du siehst, wie lange die rekursive Lösung braucht . Brute-Force ist nicht unbedingt schlecht.

SeppJ schrieb:

Du wirst überrascht sein, wenn du siehst, wie lange die rekursive Lösung braucht . Brute-Force ist nicht unbedingt schlecht.

Die rekursive Lösung schreit aber förmlich danach, optimiert zu werden

Am gewinnbringendsten dürfte es wohl sein, ein 257x10-Array zu erstellen und iterativ für k = 0,...,9 mit der Rekursionsformel zu füllen. Dabei kann man sich sogar die Hälfte der Einträge sparen. Ich hab hier aber leidert keinen Compiler, sodass ich es nicht ausprobieren kann.

Antoras

Michael E. schrieb:

n ist eine Zahl zwischen 2 und 567, das hast du schon richtig erkannt. k ist die Anzahl der Ziffern. f(n-x^2,k-1) bedeuet: Die aktuelle Ziffer, die ich mir gerade anschaue, ist x. Da ich als gesamte Summe n herausbekommen möchte, müssen sich die anderen k-1 Ziffern zusammen zu n-x^2 aufsummieren. Wenn man alle möglichen x durchgeht und aufsummiert, hat man alle Möglichkeiten durchprobiert und f(n, k) bestimmt.

Ok, ich glaub ich hab es jetzt verstanden. Es werden einfach alle möglichen Kombinationsmöglichkeiten durchprobiert. Wenn eine Kombination n ergibt. dann wird eine 1 zurückgegeben sonst 0.
Aber ineffizient ist diese Lösung wirklich, d.h. ja, dass bei jeder Zahl immer wieder alle Kombinationen durchgegangen werden, oder?

SeppJ schrieb:

Du wirst überrascht sein, wenn du siehst, wie lange die rekursive Lösung braucht . Brute-Force ist nicht unbedingt schlecht.

Wenn ich den Code jetzt richtig verstanden habe, dann ist er ja auch Brute-force, nur eben über einen anderen Lösungsweg.

Michael E. logged out schrieb:

Am gewinnbringendsten dürfte es wohl sein, ein 257x10-Array zu erstellen und iterativ für k = 0,...,9 mit der Rekursionsformel zu füllen. Dabei kann man sich sogar die Hälfte der Einträge sparen. Ich hab hier aber leidert keinen Compiler, sodass ich es nicht ausprobieren kann.

Das mit dem Array wurde in dem Blog mit dem F#-Code glaube ich auch so gemacht.
Aber das hab ich auch wieder nicht verstanden.
Wie soll das Array genau gefüllt werden?

Michael E.

Antoras schrieb:

Das mit dem Array wurde in dem Blog mit dem F#-Code glaube ich auch so gemacht.
Aber das hab ich auch wieder nicht verstanden.
Wie soll das Array genau gefüllt werden?

Ich hab die Aufgabe vor Jahren auch mal gemacht. Das war meine Lösung (braucht auf meinem i3-330M ca. 335ms, Brute Force dauert glaub ich ca. 1,5s):

vector<int> table;
	table.reserve(600);
	table.push_back(-1);

	for(int i = 1; i < 568; ++i)
	{
		int foo = i;
		while(foo != 1 && foo != 89)
		{
			int bar = 0;
			while(foo > 0)
			{
				bar += (foo % 10) * (foo % 10);
				foo /= 10;
			}
			foo = bar;
		}
		if(foo == 89)
			table.push_back(1);
		else
			table.push_back(0);
	}

	int sum = 0;

	for(int i = 1; i < 10000000; ++i)
	{
		int foo = i;
		int bar = 0;
		while(foo > 0)
		{
			bar += (foo % 10) * (foo % 10);
			foo /= 10;
		}
		sum += table[bar];
	}
	return sum;

Ich versuch aber gerade, den Rekursionansatz schneller zu machen.

Michael E.

Nachdem ich gesehen habe, wie schnell die letzte Lösung im projecteuler-Thread (von Peteris, Seite 5) bei mir (3ms) ist, habe ich ehrlich gesagt die Lust verloren, einen minderwertigen Ansatz zu optimieren

Antoras

Stimmt, da hätte ich auch keine Lust mehr drauf. Ich hab den Post leider übersehen, sonst hätte ich mich ihm gleich zugewandt. Hast du zufällig herausgefunden wie der Code funktioniert?

Der erste Teil, in dem die Zahlen berechnet werden, die in 1 oder 89 enden ist klar, aber ich verstehe nicht wie man anhand der Quadratzahlen von 1-9 darauf schließen kann wie oft die Zahlen vorkommen.

Michael E.

Antoras schrieb:

Stimmt, da hätte ich auch keine Lust mehr drauf. Ich hab den Post leider übersehen, sonst hätte ich mich ihm gleich zugewandt. Hast du zufällig herausgefunden wie der Code funktioniert?

Der erste Teil, in dem die Zahlen berechnet werden, die in 1 oder 89 enden ist klar, aber ich verstehe nicht wie man anhand der Quadratzahlen von 1-9 darauf schließen kann wie oft die Zahlen vorkommen.

Die Idee ist wieder dieselbe wie bei der Rekursion, nach der du gefragt hast. Allerdings macht Peteris das Ganze iterativ und rückwärts. Im Set stehen alle Zahlen von 0 bis 257, die nach den ersten k Stellen auftreten können. Im Vektor stehen die dazugehörigen Häufigkeiten.

Antoras

Super, ich hab es verstanden! Vielen Dank an alle, die mir geholfen haben.

Hab diesen C/C++ Mischcode in Scala nachprogrammiert und ihn so weit optimiert bekommen, dass er anstatt 3ms nur noch 0.5ms benötigt.

Ich hab leider keinen Weg gefunden das ständige Umkopieren des Sets und das Neuanlegen des Arrays zu verhindern. Fällt da noch jemandem was ein wie man das in den Griff bekommen könnte? Andererseits ist jetzt auch schon genug optimiert. Nur schade, dass ich meinen Code bei Project Euler nicht mehr posten kann.

Michael E.

Antoras schrieb:

Ich hab leider keinen Weg gefunden das ständige Umkopieren des Sets und das Neuanlegen des Arrays zu verhindern.

Das wirst du IMHO auch nicht verhindern können.

Fällt da noch jemandem was ein wie man das in den Griff bekommen könnte?

Bedenke, dass die meisten keinen Zugriff auf den Code haben

Andererseits ist jetzt auch schon genug optimiert. Nur schade, dass ich meinen Code bei Project Euler nicht mehr posten kann.

Du kannst ihn ja hier posten. Dann seh ich mal, wie schön Scala ist.

Antoras

Michael E. schrieb:

Antoras schrieb:

Ich hab leider keinen Weg gefunden das ständige Umkopieren des Sets und das Neuanlegen des Arrays zu verhindern.

Das wirst du IMHO auch nicht verhindern können.

Hätte ja sein können, dass es einen speziellen Programmiertrick gibt mit dem man das in Griff bekommen könnte. Aber der läuft jetzt ja und das wichtigste: Ich hab ihn verstanden.

Michael E. schrieb:

Du kannst ihn ja hier posten. Dann seh ich mal, wie schön Scala ist.

Ich glaube nicht, dass der Code besonders geeignet ist um die Schönheit von Scala zu demonstrieren, aber urteile selbst:

object P92 extends App {

  bench (warmup = true) {
    1000.times {
      solution1
    }
  }

  def solution1 = {
    val end = 9*9*7
    val squares = (0 to 9) map toSquare
    val set = mutable.BitSet() ++ squares
    var count = new Array[Int](9*9+1)

    for (s <- set)
      count(s) = 1

    for (i <- (2 to 7)) {
      val newCount = new Array[Int](count.size+9*9)

      for (s <- set.clone; d <- squares) {
        newCount(s+d) += count(s)
        set += s+d
      }
      count = newCount
    }

    val chainEend = 0 +: ((1 to end) map findEnd)
    val occurrences = set.iterator map (s => chainEend(s)*count(s))
    occurrences.sum
  }

  def findEnd: Int => Int = {
    case 89 => 1
    case 1 => 0
    case n => n |> next |> findEnd
  }

  def toSquare(n: Int) = n*n

  def next(n: Int): Int = {
    def loop(n: Int, res: Int): Int =
      if (n == 0) res else loop(n/10, res + toSquare(n%10))
    loop(n, 0)
  }

  /*
   * More idiomatic, but slower
   */
//  def next(n: Int) = n.toString map (_-'0' |> toSquare) sum
}