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

Hallo Campac68,

folgende Eingabe:

                new int[9, 9] {
            {0,0,0,0,0,0,0,1,0},
            {4,0,0,0,0,0,0,0,0},
            {0,2,0,0,0,0,0,0,0},
            {0,0,0,0,5,0,4,0,7},
            {0,0,8,0,0,0,3,0,0},
            {0,0,1,0,9,0,0,0,0},
            {3,0,0,4,0,0,2,0,0},
            {0,5,0,1,0,0,0,0,0},
            {0,0,0,8,0,6,0,0,0}}

zur Kontrolle: Es soll dieses Sudoku aus der Wikipedia sein.

Ich habe dabei Deinen Algorithmus nach über 10 Minuten abgebrochen. Mein eigener Code löst das in 2m20s, mit reinem Backtracking, also gehe ich davon aus dass da noch etwas schiefläuft...

Gruß, MarsStein

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...

ne kein fehler dauert nur ewig:

lösung kam bei mir nach 6 1/2 minuten(2.5GHz) kann es sein das du es im Debug Modus ausgeführt hast? Das verlangsamt das ganze etwa um das doppelte^^

schade, dass ich anysudoku nicht einreichen kann.

habs grade überflogen, sieht schonmal ganz gut aus..
allerdings wünsche ich mir eine lösung die auch größere Sudokus akzeptiert..
bsp 12er statt 9er

wenn du diesen punkt noch umsetzt kannst du die nächste aufgabe stellen 😉

diesen punkt kannst du doch vernachlässigen^^
habe in den nächsten tagen seeehr wenig zeit um iwas nachzuprüfen.
akzeptiere deine lösung also 😃

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

Hallo,

hier noch nachträglich eine gültige Lösung für die Sudoku-Aufgabe.
Da herbivore das Spiel wieder freigegeben hat, erhebe ich aber keinen Anspruch auf die nächste Aufgabe.
Wenn jemand eine schöne Idee hat, biite sehr...

zum Sudoku-Code:
in der public-Methode muss 'values' die gültigen Werte enthalten.
Der erste Wert muss der Wert sein, der für leere Felder benutzt wird
'blocksInRow' gibt an, wieviel Blöcke in einer Reihe liegen, so kann ein 12x12-Feld z.B. als 4x3 Blöcke (dann wäre die 4 anzugeben) oder als 3x4 Blöcke (dann wäre 3 anzugeben) interpretiert werden.

public static class SudokuSolver
{
  static bool Solve<T>(T[,] sudoku, T[] values, int width, int height, int row, int col)
  {
    if(col == sudoku.GetLength(0))
    {
      col = 0;
      row ++;
    }
    bool? result = (row == width * height) ? true : (bool?)null;
    if((!result.HasValue) && sudoku[col,row].Equals(values[0]))
    {
      result = false;
      for(int field = 1; (!result.Value) && (field < values.Length); field++)
      {
        result = true;
        T val = values[field];
        for(int i = sudoku.GetLength(0) - 1; result.Value && (i >= 0); i--)
        {
          result = !(val.Equals(sudoku[col,i]) || val.Equals(sudoku[i,row]));
        }
        int rowStart = height * (row / height);
        int colStart = width * (col / width);
        for(int i =  rowStart; result.Value && (i < rowStart + height); i++)
        {
          for(int j =  colStart; result.Value && (j < colStart + width); j++)
          {
            result = !val.Equals(sudoku[j,i]);
          }
        }
        if(result.Value)
        {
          sudoku[col,row] = val;
          result = Solve(sudoku, values, width, height, row, col+1);
          sudoku[col,row] = result.Value ? val : values[0];
        }
      }
    }
    return result.HasValue ? result.Value : Solve(sudoku, values, width, height, row, col+1);
  }

  public static bool Solve<T>(T[,] sudoku, T[] values, int blocksInRow)
  {
    return Solve(sudoku, values, sudoku.GetLength(0) / blocksInRow, blocksInRow, 0, 0);
  }
}

Gruß, MarsStein
Edit: Ich hatte eine Version mit vertauschten Col/Row eingestellt -> korrigiert.

Hi @ All.

Gegeben ist folgendes Snippet:

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.

Hallo,

hier mal eine lebenserhaltende Maßnahme für diesen schönen Thread.

Ich hoffe der Code erfüllt die Anforderungen, Fälle wie Parameter mit '$' im Namen oder numerischen Namen habe ich jetzt nicht weiter berücksichgt 🤔

using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.Linq;
using System.Reflection;

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!
    string[] tokens = format.Split(new string[]{ "$$" }, StringSplitOptions.None);
    IEnumerable<Parameter> sorted = args.OrderByDescending((p) => p.Name);
    for(int tokenIdx = 0; tokenIdx < tokens.Length; tokenIdx++)
    {
      for(int i = args.Length; i >= 1; i--)
      {
        tokens[tokenIdx] = tokens[tokenIdx].Replace("$" + i, args[i-1].Value.ToString());
      }
      foreach(Parameter p in sorted)
      {
        if(!String.IsNullOrEmpty(p.Name))
        {
          tokens[tokenIdx] = tokens[tokenIdx].Replace("$" + p.Name, p.Value.ToString());
        }
      }
      int start = tokens[tokenIdx].IndexOf("${");
      while(start >= 0)
      {
        int stop = tokens[tokenIdx].IndexOf("}", start);
        if(stop < start)
        {
          break;
        }
        string orig = tokens[tokenIdx].Substring(start, stop - start + 1);
        string[] path = orig.Substring(2, orig.Length - 3)
                            .Split(new char[]{':'}, StringSplitOptions.None);
        Parameter param = args.First((p) => p.Name == path[0]);
        if(param != null)
        {
          object o = param.Value;
          for(int i = 1; i < path.Length; i++)
          {
            o = o.GetType().InvokeMember(path[i], System.Reflection.BindingFlags.GetProperty, null, o, null);
          }
          tokens[tokenIdx] = tokens[tokenIdx].Replace(orig, o.ToString());
          stop = start;
        }
        start = tokens[tokenIdx].IndexOf("${", stop);
      }
    }
    return tokens.Aggregate((left,right) => left + "$" + right);
  }
}

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")));
    }
}

Gruß, MarsStein

Hi, MarsStein.

Du bist dran!

Gruß, Christian.

Hallo,

hier die neue Aufgabe, mal was ganz kurzes:

mit der im Code gegeben Klasse sollen 10 Werte zwischen -31 und 31 über einen Indexer abgelegt und wieder ausgelesen werden können.
Ergänzt die Klasse ausschliesslich an den markierten Stellen um jeweils ein einziges Statement, damit der Indexer funktioniert.

Es dürfen nur die beiden Statements eingebaut werden, weiter Änderungen oder Ergänzungen sind nicht erlaubt.

Gruß, MarsStein

using System;

public class MultiValue31
{
  long val;
  
  public sbyte this[int idx]
  {
    get
    {
      if((idx < 0) || (idx > 9))
      {
        throw new IndexOutOfRangeException("index muss im Intervall [0;9] liegen");
      }
      
      return /* hier das Statement für den Getter */;
    }
    set
    {
      if((idx < 0) || (idx > 9))
      {
        throw new IndexOutOfRangeException("index muss im Intervall [0;9] liegen");
      }
      if(Math.Abs(value) > 31)
      {
        throw new ArgumentOutOfRangeException("value muss im Intervall [-31;31] liegen");
      }
      val = /* hier das Statement für den Setter */;
    }
  }
}

public class Program {
  public static void Main() {
    MultiValue31 values = new MultiValue31();
    values[0] = 0;
    values[1] = 1;
    values[2] = 31;
    values[3] = -31;
    values[4] = 16;
    values[5] = -16;
    values[6] = 8;
    values[7] = -8;
    values[8] = 4;
    values[9] = 2;
  
    for(int i = 0; i < 10; i++)
    {
      Console.WriteLine(values[i]);
    }
  }
}

Hi,

ich liebe Bit-Spielereien 😉

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

      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

Hallo Zommi,

perfekt, genau so war's gedacht 👍

Gruß, MarsStein

Na denn,

mal wieder was algorithmisches:

Gegeben sind 1000 Zahlen. (siehe Anhang)
Was ist die [B]größte[/B] Zahl aus dem Intervall [1 ; 10.000.000], die sich [B]nicht[/B] 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

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)?

gruß
sth_Weird

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.

hm... das ist ein np-hartes problem und die eingabemenge (n) ist gigantisch... die subsum ergebnissmenge (m) ist auch gigantisch. die gängigen algorithmen, die das in relativ annehmbarer zeit schaffen würden, würden nm4 bytes speicher nur für die lookup-tabelle verfressen... was so ziemlich jede .net anwendung überlastet. nicht jeder hat ~37 GB ram.

könnte man daher die aufgabenstellung auf ein realistisches maß herunterschrauben?

ps: für alle die es noch nciht wissen --> http://de.wikipedia.org/wiki/Untermengensumme

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

@ Jack:
sehr gut recherchiert! SubSetSum ist das richtige Stichwort. (Wobei "Inverse SubSetSum" evtl. passender wäre)

@ sth_Weird:
Das "Durchprobieren" ist als naiver Ansatz leider viel zu langsam. Die exponentielle Laufzeit macht dir da einen derben Strich durch die Rechnung.

Die Eingabe/Ergebnismengen wurden extra so gewählt, dass der naive Ansatz nicht zu unserer Lebzeit fertig wird 😃

Auch der von Jack zitierte gängige Algorithmus mit seiner m*n-Lookuptable schlägt hier fehl. Wie Jack korrekt bemerkt, würde dieser Gigabytes an Speicher benötigen.

Dennoch ist die Idee mit einer Lookuptable sehr gut und zielführend!
Nur muss man die Unterschiede zum Standard-SubSetSum finden. Dort ist nämlich auch die genaue Summation relevant (welche Teilmenge).
Hier ist das völlig egal! Nutzt es aus!

Daher:

könnte man daher die aufgabenstellung auf ein realistisches maß herunterschrauben?

Nein. Ziel soll es gerade sein, einen Algo zu suchen, der trotz der Komplexität dieses Problem knackt! (Und das ist schaffbar mit ein paar MB Ram und in ~ 10 Sekunden)

beste Grüße
zommi

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

aber es heißt doch:

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?

Die genaue Summation ist nicht relevant.
Man muss beim Bilden einer Summe natürlich aufpassen, dass jede Zahl nur höchstens einmal betrachtet wird.

Es reicht aus zu wissen, ob eine gewisse Summe aus gewissen Zahlen erreichbar ist oder nicht. Hierfür interessiert es niemanden, welche Zahlen genau verwendet wurden.

PS: Ich werd dann heute abend/morgen früh noch n Tipp in die Runde werfen. Aber ich will euch ja auch nicht das Grübeln vermiesen 😉

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.... 😦

Stimmt, Billiarden Jahre wollen wir hier nicht warten 😉
Skizzier doch kurz deine bisherige Idee. Das hilft dann auch anderen, die vielleicht mit ihren Ideen wieder dir helfen ?!

Und 10^{36 is schonmal besser als 10}301 (=2^1000) ! 🙂

beste Grüße
zommi

mein 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...

Ich würde mal dezent 400251 in die Runde werfen.
Falls es richtig sein sollte, gibt's auch Code 😉

Gruß,
dN!3L

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

400251 lässt sich zwar nach meinen Berechnungen ebenfalls nicht als Summe dieser Zahlen darstellen, ist jedoch nicht die größte (Aus dem Intervall bis 10 Mio) !

Insofern: Leider falsch ! (sofern ich keinen Fehler gemacht hab 🙂 )

Aber dass es geraten war, glaube ich mal nicht, da nur 6,18147% aller Zahlen aus [1; 10Mio] nicht als Summe dieser Zahlen darstellbar sind.

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

beste Grüße
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...

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

Neuer Vorschlag: 699188

Ne, noch größer.

Durchgang: 1000 / 1000
Suche Lösung....
Lösung:956176
Dauer: 84,95 sec.

Lösung: 956176 Also meine Testfunktion sagt mir, dass 956176 zerlegbar ist. Ich gucke mal, ob ich die Summanden rausbekomme. (EDIT: War wohl irgendwie eine Zahl falsch eingelesen.

public static void DoWork()
{
	List<int> test = Calculate(new int[]{ 2,2,3,5,7 },10).ToList();
	Debug.Assert(test.Count==2 && test.Contains(1) && test.Contains(6));
	
	var values = File.ReadAllLines("random.org.txt").Select(line => Int32.Parse(line));
	int result = Calculate(values,10000000).Last();

	Debug.Assert(!CanSubstitute(values.ToList(),result));
}

private static IEnumerable<int> Calculate(IEnumerable<int> values,int limit)
{
	bool[] map = new bool[limit*2];
	foreach (int value in values)
	{
		for (int i=limit;i>0;i--)
			if (map[i])
				map[i+value] = true;
		map[value] = true;
	}
	return Enumerable.Range(1,limit).Where(i => !map[i]);
}

private static bool CanSubstitute(IList<int> list,int value)
{
	return CanSubstitute(list.OrderByDescending(v => v).ToList(),0,value);
}

private static bool CanSubstitute(IList<int> list,int startIndex,int targetValue)
{
	if (startIndex>=list.Count || targetValue<=0)
		return false;
	else if (list[startIndex]==targetValue)
		return true;
	else if (CanSubstitute(list,startIndex+1,targetValue-list[startIndex]))
		return true;
	else if (CanSubstitute(list,startIndex+1,targetValue))
		return true;
	else
		return false;
}

Meine lösung sah so aus:

        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. 8o

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.

Soo, vom Halbfinalspiel zum Programmierspiel 🙂

956176 ist korrekt !!!! 🙂
Flotse hat den Pokal, auch wenn dN!3L dicht dran war. (könnt ja untereinander ausmachen, wer nächste Aufgabe stellt)

@Monstermaschine...
Flotses Code (84,95 sec) läuft bei mir in 7 sec durch 🤔 🙂. (intel Q9300)

Mein Referenz-Code sieht auch aus wie euer:

public static void Main() {
	int[] array = File.ReadAllLines("random.org.txt").Select(s => Int32.Parse(s)).ToArray();
	Stopwatch sw = Stopwatch.StartNew();	
	
	Console.WriteLine("MaxSum: {0}", MaxNonReachableSum(array, 10000000));
	
	sw.Stop();
	Console.WriteLine("Time: {0} ms", sw.ElapsedMilliseconds);	
}
	
public static int MaxNonReachableSum(int[] values, int maximumSum)
{
	bool[] reachable = new bool[maximumSum+1];
	reachable[0] = true;
	
	foreach(int value in values)
		for(int subSum = maximumSum; subSum >= value; subSum--)
			reachable[subSum] |= reachable[subSum - value];
							
	return Array.LastIndexOf(reachable, false);
}

Und auch hier wieder dieselbe Einleseroutine ^^

beste Grüße
zommi

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.

die aufgabe war wirklich interessant, kann vllt einer noch für nicht-mathematiker erklären was da passiert? aus

Im Prinzip funktioniert es ähnlich dem Sieb des Eratosthenes. Es werden alle Zahlen im Suchbereich markiert, die irgendwie über eine Summe erreichbar sind. werd ich nicht schlau. Ich kenn zwar das Sieb des Eratosthenes und verstehs auch, den transfer zu diesem problem bekomme ich aber leider nicht hin. Allgemein würde man sich über 2 oder 3 kommentare in den Lösungen immer freuen 😉

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

Hi fielding,

ich kommentier auch nochmal kurz meinen Code:

// Methode geht alle Zahlen von [0 .. maximumSum] durch und prüft,
// ob sich diese als Summe von Zahlen aus values darstellen lässt.
// Die Größte Zahl, die nicht als Summe darstellbar ist, wird zurückgegeben.
public static int  MaxNonReachableSum(int[] values, int maximumSum)
{
	// Array in dem wir nach und nach eintragen, ob eine Summe erreichbar ist
    bool[] reachable = new bool[maximumSum+1];
	// Die 0 ist stets erreichbar (indem wir keine Zahl nehmen)
    reachable[0] = true;

	// nun jede Zahl durchgehen und gucken, ob wir mit dieser neue Summen erreichen können
    foreach(int value in values)
	{
		// hier könnte man ALLE möglichen Summen durchgehen, 
		// spart sich aber etwas, wenn man nur die prüft, 
		// die größer als die aktuelle Zahl <value> sind,
		// denn nur bei denen kann <value> in der Summe enthalten sein!
        for(int subSum = maximumSum; subSum >= value; subSum--)
		{
			// Wenn eine Summe <subSum> bisher nicht erreichbar war, gucken, 
			// ob wir sie vielleicht jetzt bilden können
			if(!reachable[subSum])
			{
				// subSum ist dann erreichbar, wenn <subSum-Value> bisher erreichbar war
				// (da ich dann ja "(subSum-value) + value = subSum" bilden kann)
				reachable[subSum] = reachable[subSum - value];
			}
		}
	}

	// Nun die letzte Summe wählen, die nicht erreicht worden ist.
    return Array.LastIndexOf(reachable, false);
}

Nachtrag zur inneren For-Schleife:
Es ist etwas riskant die neu erreichbaren Summen im alten Array direkt zu markieren. Dies ist nämlich höchst sensitiv gegenüber der Zählrichtung. Wenn wir vorwärts (subSum++) laufen würden, könnte eine Zahl mehrfach zur Summe beitragen, die sie auch zu Summen dazuaddiert wird, die erst durch sie selbst darstellbar wären.
(Angenommen ich fange mit dem Ausgangsarray an und wähle die 2 als erste Zahl, dann wäre beim Vorwärtslaufen danach jede gerade Zahln erreichbar)

Beim Rückwärtslaufen hingegen erreicht man die andere Semantik, dass jede Zahl nur genau einmal verwendet werden darf.
(Angenommen ich fange mit dem Ausgangsarray an und wähle die 2 als erste Zahl, dann wäre beim Rückwärtslaufen runter von 10 Mio. danach nur noch die 2 erreichbar)

beste Grüße
zommi

Vielen Dank euch beiden, das macht das ganze einfach viel verständlicher (nicht nur für mich, sondern für jeden besucher dieses threads) und man muss nicht erst umständlich mit dem debugger durch den code gehen, um zu begreifen was passiert. Das ist meiner Meinung nach das bisschen Mehraufwand wert 😉

Nächste aufgabe:

Ein programm erstellen, in das man c#code eingibt, welcher dann ein bild generiert.
Der code den man eingibt soll eine klasse sein, die von folgendem interface ableitet:

interface ISharpPixelShader
{
    void Start(int width,height);
    int GetPixelColor(int x,int y,int width,height);//x und y sind die position des pixels. width und height sind die abmessungen des bildes.
    void End();
}

Das programm soll den code compilieren. Fehler sollten ausgegeben werden. Wenn das compilieren geklappt hat, eine instanz der compilieren klasse erstellen und mit dieser instanz soll ein bitmap (entweder fix 500x500 oder wählbare größe) befüllt werden. Das bitmap soll erst gespeichert und dann in einem fenster angezeigt werden.

Codeeingabe entweder als dateiname in einem argument der main oder über ein gui. (es reicht, wenn eine der beiden möglichkeiten implementiert wird.)

Tipp: man muss dem compiler mitteilen, dass auf typeof(ISharpPixelShader).Assembly verwiesen wird.

[ERG:]Bitte nicht getpixel, sondern lockbits verwenden!

Hast du mal so eine Eingabeklasse?

Ansonsten hier mal meine Quick'n'Dirty-Lösung:

using System;
using System.CodeDom.Compiler;
using System.Collections.Generic;
using System.Drawing;
using System.Drawing.Imaging;
using System.IO;
using System.Linq;
using System.Reflection;
using System.Windows.Forms;
using Microsoft.CSharp;

public class PictureGenerator
{
	public static void Main(string[] args)
	{
		try
		{
			string path = args[0];
			string source = File.ReadAllText(path);

			CSharpCodeProvider cSharpCodeProvider = new CSharpCodeProvider(new Dictionary<string,string>() { { "CompilerVersion","v3.5" } });
			CompilerParameters compilerParameters = new CompilerParameters { GenerateInMemory = true,GenerateExecutable = false };

			Action<string> addAssembly = (assemblyLocation) =>
			{
				if (!compilerParameters.ReferencedAssemblies.Contains(assemblyLocation))
					compilerParameters.ReferencedAssemblies.Add(assemblyLocation);
			};
			addAssembly(Assembly.GetExecutingAssembly().Location);
			foreach (AssemblyName referencedAssemblyName in Assembly.GetExecutingAssembly().GetReferencedAssemblies())
				try { addAssembly(Assembly.ReflectionOnlyLoad (referencedAssemblyName.FullName).Location); }
				catch (FileNotFoundException) { }

			CompilerResults compilerResults = cSharpCodeProvider.CompileAssemblyFromSource(compilerParameters,source);

			if (compilerResults.Errors.Count>0)
				throw new ArgumentException(String.Join("\r\n",compilerResults.Errors.Cast<CompilerError>().Select(ce => ce.ErrorText).ToArray()));
			else
			{
				Type generatedType = compilerResults.CompiledAssembly.GetTypes().First(t => t.GetInterface("ISharpPixelShader")!=null);
				ISharpPixelShader sharpPixelShader = (ISharpPixelShader)Activator.CreateInstance(generatedType);

				Bitmap bitmap = new Bitmap(500,500);
				sharpPixelShader.Start(bitmap.Width,bitmap.Height);
				for (int x=0;x<bitmap.Width;x++)
					for (int y=0;y<bitmap.Height;y++)
						bitmap.SetPixel(x, y ,sharpPixelShader.GetPixelColor (x, y, bitmap.Width, bitmap.Height));
				sharpPixelShader.End();

				bitmap.Save(path+".png",ImageFormat.Png);

				Form form = new Form();
				PictureBox pictureBox = new PictureBox { Dock = DockStyle.Fill,Image = bitmap };
				form.Controls.Add(pictureBox);
				Application.Run(form);
			}
		}
		catch (Exception exception)
		{
			MessageBox.Show(exception.Message);
		}
	}
	
	public interface ISharpPixelShader
	{
		void Start(int width,int height);
		Color GetPixelColor(int x,int y,int width,int height);
		void End();
	}
}

Ich war mal so frei und habe dein Interface etwas angepasst. Erstens so, dass es auch kompiliert, zweitens gibt GetPixelColor auch eine Farbe zurück.

Gruß,
dN!3L

Ein paar kleinigkeiten:

1. locken statt setpixel
2. zeilennummern in den fehlermeldungen?
3. out of range exception ist nicht sehr aufschlussreich, wenn man keine datei angibt.
   (4. den typ der fehlermeldung im titel anzeigen)

ansonsten ok.

Pff... Dann halt einmal in schöner: 😁

using System;
using System.CodeDom.Compiler;
using System.Collections.Generic;
using System.Drawing;
using System.Drawing.Imaging;
using System.IO;
using System.Linq;
using System.Reflection;
using System.Runtime.InteropServices;
using System.Windows.Forms;
using Microsoft.CSharp;

public static class PictureGenerator
{
	public interface ISharpPixelShader
	{
		void Start(int width,int height);
		Color GetPixelColor(int x,int y,int width,int height);
		void End();
	}

	public static void Main(string[] args)
	{
		try
		{
			if (args.Length==0)
				throw new ArgumentException("Kein Pfad zur Quelldatei angegeben");
			string path = args[0];

			File.ReadAllText(path)
				.CompileToAssembly()
				.GetPixelShader()
				.CreateBitmap()
				.SaveBitmapFor(path)
				.ShowBitmap();
		}
		catch (Exception exception)
		{
			MessageBox.Show (exception.Message,exception.GetType ().Name, MessageBoxButtons.OK, MessageBoxIcon.Error);
		}
	}

	private static Assembly CompileToAssembly(this string source)
	{
		CSharpCodeProvider cSharpCodeProvider = new CSharpCodeProvider(new Dictionary<string,string>() { { "CompilerVersion","v3.5" } });
		CompilerParameters compilerParameters = new CompilerParameters { GenerateInMemory = true,GenerateExecutable = false };
		compilerParameters.AddReferencedAssemblies();
		CompilerResults compilerResults = cSharpCodeProvider.CompileAssemblyFromSource(compilerParameters,source);
		if (compilerResults.Errors.Count>0)
			throw new ArgumentException (String.Join("\r\n", compilerResults.Errors.Cast<CompilerError>().Select(ce => ce.Line+": "+ce.ErrorText).ToArray()));
		else
			return compilerResults.CompiledAssembly;
	}

	private static void AddReferencedAssemblies(this CompilerParameters compilerParameters)
	{
		compilerParameters.ReferencedAssemblies.Add(Assembly.GetExecutingAssembly().Location);
		foreach (AssemblyName referencedAssemblyName in Assembly.GetExecutingAssembly().GetReferencedAssemblies())
			try
			{
				string assemblyLocation = Assembly.ReflectionOnlyLoad (referencedAssemblyName.FullName).Location;
				if (!compilerParameters.ReferencedAssemblies.Contains (assemblyLocation))
					compilerParameters.ReferencedAssemblies.Add (assemblyLocation);
			}
			catch (FileNotFoundException) { }
	}

	private static ISharpPixelShader GetPixelShader(this Assembly assembly)
	{
		Type generatedType = assembly.GetTypes().FirstOrDefault(t => t.GetInterface("ISharpPixelShader")!=null);
		if (generatedType==null)
			throw new ArgumentException("Assembly enthält keinen Typen, der die Schnittstelle 'ISharpPixelShader' implementiert.");
		else
			return (ISharpPixelShader)Activator.CreateInstance(generatedType);
	}

	private static Bitmap CreateBitmap(this ISharpPixelShader sharpPixelShader)
	{
		Bitmap bitmap = new Bitmap(500,500);
		sharpPixelShader.Start(bitmap.Width,bitmap.Height);
		BitmapData bitmapData = bitmap.LockBits(new Rectangle(0,0,bitmap.Width,bitmap.Height),ImageLockMode.ReadWrite,PixelFormat.Format32bppRgb);
		byte[] rgbValues = new byte[bitmapData.Stride*bitmap.Height];
		Marshal.Copy(bitmapData.Scan0,rgbValues,0,rgbValues.Length);
		for (int x=0;x<bitmap.Width;x++)
			for (int y=0;y<bitmap.Height;y++)
			{
				int i = x*4+y*bitmapData.Stride;
				Color color = sharpPixelShader.GetPixelColor(x,y,bitmap.Width,bitmap.Height);

				rgbValues[i+0] = color.B;
				rgbValues[i+1] = color.G;
				rgbValues[i+2] = color.R;
				rgbValues[i+3] = color.A;
			}
		Marshal.Copy(rgbValues,0,bitmapData.Scan0,rgbValues.Length);
		bitmap.UnlockBits(bitmapData);
		sharpPixelShader.End();
		return bitmap;
	}

	private static Bitmap SaveBitmapFor(this Bitmap bitmap,string sourcePath)
	{
		bitmap.Save(sourcePath+".png",ImageFormat.Png);
		return bitmap;
	}

	private static void ShowBitmap(this Bitmap bitmap)
	{
		Form form = new Form();
		PictureBox pictureBox = new PictureBox { Dock = DockStyle.Fill,Image = bitmap };
		form.Controls.Add(pictureBox);
		Application.Run(form);
	}
}

^. is ja gut, du bist dran.

Neue Aufgabe.

Erstmal etwas Vorgeplänkel: Gegeben sein beispielsweise folgende Auflistung

public class Container
{
	public DateTime Date { get; set; }
	public string Value { get; set; }
	public override string ToString() { return this.Value; }
}
//...
Container[] dataSource = new[]
{
    new Container { Date = new DateTime(2009,1,1),Value = "Januar '09" },
    new Container { Date = new DateTime(2009,2,1),Value = "Februar '09" },
    new Container { Date = new DateTime(2010,1,1),Value = "Januar '10" },
    new Container { Date = new DateTime(2010,2,1),Value = "Feburar '10" },
    new Container { Date = new DateTime(2010,3,1),Value = "März '10" },
};

Mit einem Left Outer Join kann man nun jedes Element der Auflistung mit dem Element des Montats des Vorjahres (falls vorhanden) zusammenführen:

var query = 
	from left in dataSource join right in dataSource 
	on left.Date equals right.Date.AddYears(1) into rightGroup
	from right in rightGroup.DefaultIfEmpty()
	select new { LeftValue = left.Value,RightValue = (right!=null) ? right.Value : null };

... ergibt dann für obiges Beispiel...

{ LeftValue = "Januar '09", RightValue = null }
{ LeftValue = "Februar '09", RightValue = null }
{ LeftValue = "Januar '10", RightValue = "Januar '09" }
{ LeftValue = "Feburar '10", RightValue = "Februar '09" }
{ LeftValue = "März '10", RightValue = null }

Es soll eine (Erweiterungs-)Methode erstellt werden, die genau das tut, allerdings mit folgenden Bedingungen:
[list]
[*]Die Eingabeauflistung (IEnumerable<T>) kann unendlich groß sein.
[*]Die Eingabeauflistung ist flüchtig, d.h. zwei Enumeratoren dieser Auflistung liefern [i]nicht[/i] die gleichen Elemente.
[*]Die Eingabeauflistung wird mit sich selbst zusammengeführt (vgl. Join mit sich selbst)
[/list]
Es kann vorrausgesetzt werden, dass die Eingabeauflistung bezüglich des Vergleichswertes geordnet vorliegt (d.h für das obige Beispiel, dass der Datumswert eines Elements immer größer[/gleich] seinen Vorgängern ist).

Und noch ein Beispiel für eine flüchtige unendliche Quellauflistung:

public IEnumerable<Container> GetValues()
{
	while (true)
	{
		yield return new Container { Date = dateTime,Value = dateTime.ToString("MMM yy") };
		dateTime = dateTime.AddMonths(1);
	}
}
private static DateTime dateTime = new DateTime(2001,5,1);

Gutes Gelingen,
dN!3L

Hallo,

den Punkt

Die Eingabeauflistung wird mit sich selbst zusammengeführt (vgl. Join mit sich selbst) habe ich nicht verstanden. Aber eine Lösung für die Aufgabe habe ich hoffentlich doch 😉

public static class ProgrammierSpiel
{
	public static IEnumerable<Result> Daniel(this IEnumerable<Container> dataSource)
	{
		Dictionary<DateTime, Container> memo = new Dictionary<DateTime, Container>();

		foreach (Container left in dataSource)
		{
			Container right = null;
			DateTime rightDate = left.Date.AddYears(-1);
			if (memo.ContainsKey(rightDate))
			{
				right = memo[rightDate];
				memo.Remove(rightDate);		// damit memo nicht sinnlos wächst
			}

			yield return new Result
			{
				LeftValue = left.Value,
				RightValue = (right != null) ? right.Value : null
			};

			memo[left.Date] = left;
		}
	}
}

public class Result
{
	public string LeftValue { get; set; }
	public string RightValue { get; set; }
}

Liefert das korrekte Ergebnis für das Referenzbeispiel und läuft solange bis AddMonth in der GetValues-Methode einen Fehler wirft.

mfG Gü

Liefert das korrekte Ergebnis für das Referenzbeispiel und läuft solange bis AddMonth in der GetValues-Methode einen Fehler wirft.

Gut, ganz so unendlich ist die Auflistung auch nicht. Aber im Prinzip... 😃
Ich guck mir deine Lösung morgen mal genauer an.

Zum Zeitvertreib kann ich ja noch wie Floste nachträglich die Bedingungen verschärfen 😉*Generisch, nicht nur auf Container beschränkt *Nicht nur auf Date und nicht nur auf AddYear(1) beschränkt *Nicht auf Result beschränkt

Hinweis: Signatur von Enumerable.Join

Nee, musst nicht. Bisherige Lösung reicht aus. Es sein denn, es will noch jemand eine Lösung mit einer Queue anbieten...

Bis morgennachher,
dN!3L