Das Programmier-Spiel: nette Übungsaufgaben für zwischendurch

jo stimmt mal schauen

EDIT: Ich würde ehrlich gesagt behaupten das mein Code einfach nur relativ lahm ist. Ich hab nicht so auf Performance geachtet...

Hallo zusammen,

nachdem Campac68 - auch nach einer entsprechenden Aufforderung per PM - keine neue Aufgabe gestellt hat, gebe ich das Spiel wieder frei. Wer eine nette Aufgabe hat, möge diese bitte posten. Achtet dabei vor dem Absenden darauf, dass euch keiner zuvorgekommen ist. Nur die erste neue Aufgabe zählt.

herbivore

Hi @ All.

Gegeben ist folgendes Snippet:

C#-Code:

using System; using System.Diagnostics; public class Parameter {     private string m_Name;     private object m_Value;     public Parameter(string name, object value) {         m_Name = name;         m_Value = value;     }     public Parameter(object value) {         m_Name = null;         m_Value = value;     }     public string Name {         get { return m_Name; }     }     public object Value {         get { return m_Value; }     } } public static class StringEx {     public static string Format(string format, params Parameter[] args) {         // Hier eure Implementierung!         throw new NotImplementedException();     } } public class Program {     public static void Main() {         Debug.Assert("This is SPARTA!" == StringEx.Format("This is $what!", new Parameter("what", "SPARTA")));         Debug.Assert("This is SPARTA!" == StringEx.Format("This is $1!", new Parameter("SPARTA")));         DateTime date = new DateTime(2010, 06, 12, 17, 18, 32);         Debug.Assert("Date is: 12.6.2010, Time is: 17:18:32" == StringEx.Format("Date is: ${date:Day}.${date:Month}.${date:Year}, Time is: ${date:Hour}:${date:Minute}:${date:Second}", new Parameter("date", date)));         Debug.Assert("17:18:32" == StringEx.Format ("${date:TimeOfDay:Hours}:${date:TimeOfDay:Minutes}:${date:TimeOfDay:Seconds}", new Parameter("date", date)));         Debug.Assert("$test = TEST" == StringEx.Format("$$test = $test", new Parameter("test", "TEST")));     } }

Eure Aufgabe ist es nun, mal wieder eine Art von Parser zu entwickeln. Wie Ihr dabei vorgeht, bleibt diesmal euch überlassen.

Die unterstützten Formate sollen Folgende sein:

• $var wird durch den Wert des Parameters mit dem Namen var ersetzt
  
• $1 wird durch den Wert des ersten übergebenen Parameters ersetzt (ACHTUNG! das ist nicht 0-basiert!)
  
• ${var:Property1:Property2} wird durch den Wert von Property2 von Property1 des Parameters mit dem Namen var ersetzt
  
• $$ wird durch ein einzelnes $ ersetzt (--> Escaping)

Als Lösungen ausgeschlossen ist:
 String.Format(...) Extended

Gruß, Christian.

Hi, MarsStein.

Du bist dran!

Gruß, Christian.

Hi,

ich liebe Bit-Spielereien ;)

C#-Code (Statement 1):

return (sbyte)(((val >> (idx * 6)) & 63) - 32);

C#-Code (Statement 2):

val = (val & ~(63L << (idx*6))) | ((value + 32L) << (idx*6));

Der eingebaute UnitTest sagt bei mir zumindest, dass es korrekt sei, daher fang ich schonmal an eine neue Aufgabe auszugrübeln... :-)

beste Grüße
zommi

Na denn,

mal wieder was algorithmisches:

Gegeben sind 1000 Zahlen. (siehe Anhang) Was ist die größte Zahl aus dem Intervall [1 ; 10.000.000], die sich nicht als Summe von irgendeiner Teilmenge dieser Zahlen bilden lässt?

Die Zahlen sind übrigens frisch von random.org generiert ;)

Kleines Referenzbeispiel:
Gegeben: 2, 2, 3, 5, 7
Interval: [1; 10]
Lösung: 6 (1 und 6 lassen sich nicht darstellen)

Die Fragestellung schreibt hier keine Programmiersprache vor, oder ob iher überhaupt selbst was coden müsst. Die Lösung irgendwie zu bekommen, ist schon tricky genug! (glaube ich)
Aber am schönsten is natürlich ein kleines C#-Programm, dass diese Frage (und ähnliche) beantwortet.

beste Grüße
zommi

Zitat:

und jede Zahl die vorkommt darf maximal 1* verwendet werden (also es sei denn die Zahl käme in der Liste zweimal vor dann dürfte sie zweimal verwendet werden)?

Ja, exakt.

Hmm, weil du geschrieben hast von wegen Programmiersprache nicht vorgegeben und evtl garnichts schreiben müssen...

mein Ansatz wäre eine Wahrheitstabelle zu erstellen, wobei jede Spalte den Index auf die Zahlenliste darstellt. Also bei 3 Zahlen sähe die so aus:
000
001
010
011
100
101
110
111
und dann könnte man die zeilenweise durchlaufen und die Summe der Zahlen bilden, bei denen eine 1 steht, und das dann in einen Hash schreiben.
Danach müsste man nur noch von der Maximalzahl rückwärts runterzählen bis man eine Zahl findet, die nicht im Hash steht.

Bei 1000 Zahlen ist das tatsächlich ein Problem, denn die Tabelle hätte ja 2^1000 Zeilen.
Der nächste Ansatz ist, die 0en und 1en statt in Zahlenform in ein String-Array zu packen (also 1000 Strings im Array, jeder 2^1000 lang).
Und dann quasi durch die chars gehen und die Zahlen derart erzeugen.
Leider war die Pause zu kurz zum implementieren, musst dich also, wenn du auf ausprogrammierten Code bestehst, noch ein bissl gedulden, jetzt gehts zurück an die Arbeit

gruß
sth_Weird

Zitat:

Dort ist nämlich auch die genaue Summation relevant (welche Teilmenge). Hier ist das völlig egal!

aber es heißt doch:

Zitat:

und jede Zahl die vorkommt darf maximal 1* verwendet werden

und ob ich mir jetzt die verwendete zahl oder den index der verwendeten zahl merke ist egal. daher ist die gennaue summation schon relevant? oder habe ich da was falsch verstanden?

harter brocken... ich hab eine lösung, die schon perfomanter ist als der naive weg aber dennoch ~10^36 iterationen benötigt und daher nicht in einer annehmbarer zeit fertig ist.... :-(

mein code:

C#-Code:

main... { List<int> input = File.OpenText(Path.Combine(Environment.CurrentDirectory, "random.txt"))                 .ReadToEnd()                 .Split(new[] {Environment.NewLine}, StringSplitOptions.RemoveEmptyEntries)                 .Select(aString => int.Parse(aString))                 .ToList();             int max = 10000000;             List<int> selectedIndexList = new List<int>();             SearchMaxSubsetSum(ref max, input, selectedIndexList);             Console.WriteLine(max);             Console.ReadLine();   }         public static int stackCount = 0;         public static void SearchMaxSubsetSum(ref int max, List<int> inputValues, List<int> selectedIndexList)         {             Console.WriteLine(string.Format("{0,-20} {1}",StackCountString(stackCount),max));             int preselectedSum = selectedIndexList.Sum(index => inputValues[index]);             for (int i = 0; i < inputValues.Count; i++)             {                 int index = i;                 if(selectedIndexList.Any(item => item == index)) continue;                 int currentSelectedSum = preselectedSum + inputValues[i];                 if(currentSelectedSum < max)                 {                     selectedIndexList.Add(i);                     stackCount++;                     SearchMaxSubsetSum(ref max,inputValues,selectedIndexList);                     //if (selectedIndexList.Sum(selectedIndex => inputValues[selectedIndex]) >= max) return;                     selectedIndexList.Remove(i);                 }                 else if(currentSelectedSum == max)                 {                     max--;                     stackCount--;                     Console.WriteLine(max);                     return;                 }             }             stackCount--;         }         public static string StackCountString(int einrücker)         {             if (einrücker <= 0) einrücker = 1;             return string.Format("{0," + einrücker + "}", 0);         }

oh und ich habe mich geirrt, was die laufzeit angeht, da ich ja 10^36 iterationen bruache um eine zahl zu überprüfen aber ich muss ja alle 10.000.000 zahlen überprüfen (worst case) also wären das dann 10^43 und das auch nur deswegen, weil die input zahlen im schnitt so groß sind, das nciht mehr als 12 zahlen summiert werden müssen, um herauszufinden ,das man eigendlisch schon drüber ist...

Gemäß dem Fall der Wert ist richtig, würde mich schon interessieren wie du es ermittelt hast.

Zitat von zommi:

ist jedoch nicht die größte (Aus dem Intervall bis 10 Mio)

Ich habe ab 10 Mio abwärts prüfen lassen. 400251 war bei mir die erste, die nicht gepasst hat.
EDIT: Verdammt, das Caching/die Lookup-Tabelle klappt nicht ganz. Ohne werden mehr Zahlen als nicht darstellbar erkannt. Grml...

Zitat von zommi:

Aber die Zahl ist schonmal in einer "interessanten" Größenordnung, sodass du deinen Ansatz zumindest posten solltest

Ich muss nochmal drübergucken. Im Moment wird noch der Spezialfall behandelt, dass deine Testmenge keine doppelten Werte enthält. Mal sehen, ob ich das noch rausbekomme und vll. noch eine größere Zahl finde. Ich werd mich dann heute Abend nochmal genauer mit beschäftigen. :)

Neuer Vorschlag: 699188

Beste Grüße,
dN!3L

Meine lösung sah so aus:

C#-Code:

static void Main(string[] args)         {             Stopwatch sw = Stopwatch.StartNew();             const int max=10000000;             int[] numbers = File.ReadAllLines("random.org.txt").Select((line) => int.Parse(line)).ToArray();             //int[] numbers = { 2, 2, 3, 5, 7 };             bool[] reached = new bool[max+1];             reached[0] = true;             for (int i = 0; i < numbers.Length; i++)             {                 Console.Write("\rDurchgang: "+(i+1)+" / " +numbers.Length);                 int number = numbers[i];                 for (int i2 = max-number; i2>=0; i2--)                 {                     reached[i2+number]|=reached[i2];                 }             }             Console.WriteLine();             Console.WriteLine("Suche Lösung....");             for (int i = max; i >= 0; i--)             {                 if (!reached[i])                 {                     Console.WriteLine("Lösung:" + i);                     break;                 }             }             sw.Stop();             Console.WriteLine("Dauer: "+(sw.ElapsedTicks/(double)Stopwatch.Frequency).ToString("0#.00")+" sec.");             Console.ReadLine();         }

Mich würde mal interessieren, wie lange dein code braucht.
Mein code hate ein laufzeitverhalten von ca. suchbereichGröße*anzahlZahlen

irgendwie sind unsere einlesemethoden zeimlich identisch.

Zitat:

Aber an die "unter 15sec" von Zommi dürften wir noch weit weg sein...

vielleicht hat zommy einfach nur eine monstermaschine :-) oder nutzt parallel programming. so wie ich das sehe ließe sich der sieb gut parallelisieren.

Jaja, dass am Ende jemand das Bit-Array auspacken würde, das hatte ich schon befürchtet

beste Grüße
zommi


In C/C++ ließe sich diese schöne innere Schleife noch perfekt mittels SSE beschleunigen. Da wird dann nicht mehr 1 oder 32 Bit verarbeitet, sondern gleich 128 (bzw 64, weil man ja nur die hälfte hat)...mhh...wenn jemand nix zu tun hat? Da wär nochmal Faktor 2 zu holen ;-)


Ist schon herrlich, wie man mit n paar Zeilen Code (die sogar einfacher und kürzer als BruteForce sind - den BitQuatsch mal außen vor gelassen ;-)) die Laufzeit einer Problemlösung von grob 10^280 Jahren auf 1,5 Sekunden runterbrechen kann Das find ich echt faszinierend.

Beispiel: { 2,2,3,5 } im Bereich [1,10]. Man geht die Zahlen der Reihe nach durch:

• Mit der 2 kann man die 2 erreichen. (Zwischenergebnis erreichbare Zahlen: 2)
  
• Mit der nächsten 2 kann man wieder die 2 erreichen (haben wir schon), und von der vorhandenen 2 aus die 4. (ZE: 2,4)
  
• Mit der 3 kann man die 3 erreichen. Und über die vorhandene 2 und 4 die 5 und die 7. (ZE: 2,3,4,5,7).
  
• Mit der 5 kann man die 5 erreichen. Und über die vorhandene 2, 3, 4, 5 und 7 die 7 (haben wir schon), die 8, die 9, die 10 und die 12 (liegt aber nicht im Bereich). (ZE: 2,3,4,5,7,8,9,10)

Man kommt also über Summenbildung auf die Zahlen 2, 3, 4, 5, 7, 8, 9 und 10. Die 1 und die 6 können nicht erreicht werden.

Gruß,
dN!3L