Code-Challenge: Shut the Box

Es gibt 16 Antworten in diesem Thema. Der letzte Beitrag () ist von SeriTools.

    Code-Challenge: Shut the Box

    Falls jemand etwas Langeweile hat, hier eine kleine Code-Challenge:

    Es geht im Grunde um das Spiel Shut The Box, auch bekannt als Klappenspiel, allerdings in etwas abgewandelter Form:

    Input:
    Das Programm bekommt als Input (in welcher Form ist egal, kann auch direkt im Code stehen) eine Summe s, die Anzahl der Summanden n und eine Liste von möglichen Summanden i[].

    Alle Eingaben sind natürliche Zahlen.
    Die Liste i[] ist nicht sortiert.

    Output:
    Es sollen zwei Ausgaben getätigt werden:
    1.: Das Programm soll eine weitere Liste zurückgeben, in der sich n Summanden aus i[] befinden, deren Summe s beträgt. Jeder Summand aus i[] darf nur einmal benutzt werden. Gibt es mehrere Möglichkeiten, so muss nur eine zurückgegeben werden. Die Ausgabeliste muss nicht sortiert werden.
    2.: Gibt es keine Lösung - ob wegen zu kleiner Summandenliste oder unpassender Summanden -, so soll dies auch zurückgegeben werden. Zwischen den Fehlschlagsfällen muss nicht unterschieden werden. (Kurzum: ein Success-Boolean)
    Außerdem soll die zurückgegebene Liste leer sein/bleiben, wenn es keine Lösung gibt.

    Es muss keine Konsoleneingabe oder -ausgabe erfolgen, es geht allein um die Eingabe/Ausgabe im Code.

    Beispiel:
    Input:
    s=18, n=5, i[]={ 4, 11, 1, 7, 3, 5, 2 }

    Output:
    true, { 2, 5, 3, 7, 1 }


    Der Code muss in VB oder C# geschrieben werden.

    Es geht in dieser Challenge nicht ausschließlich um den kürzesten Code. Es kann jeder beliebige Code eingereicht werden, ob er nun zur Kategorie kürzester/längster, am leichtesten/schwersten lesbarer, schönster/hässlichster oder effizientester/ineffizientester Code oder sonst was passt, steht jedem natürlich frei, auch sind mehrere Codes von einem Ersteller natürlich erlaubt und erwünscht!

    Ich habe auch schon eine Lösung vorbereitet und werde sie später posten.

    Fragen bitte immer stellen!

    Viel Spaß an der Challenge!
    lg SeriTools
    | Keine Fragen per PN oder Skype.

    Dieser Beitrag wurde bereits 3 mal editiert, zuletzt von „SeriTools“ ()

    Done!
    Spoiler anzeigen

    C-Quellcode

    1. public static bool ShutTheBox(int sum, int count, int[] input, out int[] output)
    2. {
    3. var combinations = input.Permutate();
    4. foreach (var combination in combinations)
    5. {
    6. int s = 0;
    7. for (int i = 0; i < count; i++)
    8. s += combination[i];
    9. if (s == sum)
    10. {
    11. output = combination.Take(count).ToArray();
    12. return true;
    13. }
    14. }
    15. output = null;
    16. return false;
    17. }
    19. public static IEnumerable<List<T>> Permutate<T>(this IEnumerable<T> value)
    20. {
    21. var inputCount = value.Count();
    22. List<T>[] buffer = null;
    23. var oldBuffer = new List<T>[inputCount];
    24. for (int i = 0; i < inputCount; i++)
    25. oldBuffer[i] = new List<T>(new[] { value.ElementAt(i) });
    26. var bufferCount = inputCount;
    27. for (int count = 1; count < inputCount; count++)
    28. {
    29. buffer = new List<T>[bufferCount * (inputCount - count)];
    30. int index = 0;
    31. for (int i = 0; i < oldBuffer.Length; i++)
    32. foreach (var item in value)
    33. if (!oldBuffer[i].Contains(item))
    34. {
    35. var l = new List<T>(oldBuffer[i]);
    36. l.Add(item);
    37. buffer[index] = l;
    38. index++;
    39. }
    40. oldBuffer = buffer;
    41. bufferCount = oldBuffer.Count();
    42. }
    43. return buffer;
    44. }

    Ineffizientester Algo ever.

    Ich habe so verstanden, dass Fragen erlaubt sind.
    @Artentus
    Nachdem ich 10 Minuten mühsam durch deine "List" durchgestiegen bin :P , verstehe ich deinen Code so, dass du in "Permutate()" alle möglichen Kombinationen erstellst und dann n Elemente davon addierst?
    Warum übergibst du die Anzahl der Elemente in Kombinationen nicht gleich mit und hast du nur die Kombinationen mit der richtigen Anzahl der Elemente?

    @Artentus: Oh ja, in der Ineffizienz-Kategorie wäre das ziemlich weit vorne. :D

    Hier ist meine Lösung:
    Spoiler anzeigen

    C-Quellcode

    1. private static void Main(string[] args)
    2. {
    3. List<int> input = new List<int>(new int[] { 4, 11, 1, 7, 3, 5, 2 });
    4. List<int> result = new List<int>();
    5. ShutTheBox(result, 18, 5, input);
    6. }
    8. private static bool ShutTheBox(List<int> result, int s, int n, List<int> input, int nextindex = 0)
    9. {
    10. if (n == 0) return false;
    11. while (true) {
    12. if (n > input.Count - nextindex) return false;
    13. int i = input[nextindex];
    14. if (s - i < 0) {
    15. nextindex++;
    16. } else if (s - i == 0) {
    17. if (n == 1) {
    18. result.Add(i);
    19. break;
    20. } else {
    21. nextindex++;
    22. }
    23. } else {
    24. if (!ShutTheBox(result, s - i, n - 1, input, nextindex + 1)) {
    25. nextindex++;
    26. } else {
    27. result.Add(i);
    28. break;
    29. }
    30. }
    31. }
    32. return true;
    33. }

    Das Ergebnis gibt es in der result-Liste, obs geklappt hat wird von der Funktion selbst zurückgegeben.

    lg SeriTools
    | Keine Fragen per PN oder Skype.

    Ditto. Valide IEnumerable<T>
    Lang.

    C-Quellcode

    1. static void Main( string[] args ) {
    2. int[] val = new int[] { 4, 11, 1, 7, 3, 5, 2 };
    4. foreach ( var item in ShutTheBox( 18, 5, val ) ) {
    5. Console.WriteLine( "{0}; {1}", item.Sum( sum => (int) sum ), string.Join( ", ", item ) );
    6. }
    8. Console.ReadLine();
    9. }
    11. static IEnumerable<IEnumerable<int>> ShutTheBox( int sum, int count, int[] input ) {
    12. return Populate( input, count, count ).Select(
    13. item => item.Distinct()
    14. ).Where(
    15. item => item.Count() == count && item.Sum() == sum
    16. ).Select(
    17. item => item.OrderBy( order => order )
    18. ).Distinct( new IntArrayComparer() ).OrderBy(
    19. item => item.Sum()
    20. );
    21. }
    23. static IEnumerable<T> PopulateList<T>( T value, int count ) {
    24. for ( int i = 0; i < count; i++ )
    25. yield return value;
    26. }
    28. static IEnumerable<IEnumerable<T>> Populate<T>( T[] value, int min, int max ) {
    29. var digits = PopulateList( 0, min ).ToList();
    30. var rotatingDigit = 0;
    31. while ( rotatingDigit < max ) {
    32. List<T> tmp = new List<T>();
    34. if ( rotatingDigit == digits.Count )
    35. digits.Add( 0 );
    37. for ( int k = digits.Count - 1; k >= 0; k-- )
    38. tmp.Add( value[digits[k]] );
    40. yield return tmp;
    42. for ( rotatingDigit = 0; rotatingDigit < digits.Count; rotatingDigit++ ) {
    43. digits[rotatingDigit]++;
    44. if ( digits[rotatingDigit] < value.Length )
    45. break;
    46. digits[rotatingDigit] = 0;
    47. }
    48. }
    49. }
    51. public class IntArrayComparer : IEqualityComparer<IEnumerable<int>> {
    52. public bool Equals( IEnumerable<int> x, IEnumerable<int> y ) {
    53. if ( x == null || y == null )
    54. return x == y;
    55. return x.OrderBy( item => item ).SequenceEqual( y.OrderBy( item => item ) );
    56. }
    58. public int GetHashCode( IEnumerable<int> obj ) {
    59. if ( obj == null )
    60. throw new ArgumentNullException();
    61. int iHash = 0;
    62. for ( int i = 0; i < obj.Count(); ++i )
    63. iHash ^= ( obj.ElementAt( i ) << ( ( 0x03 & i ) << 3 ) );
    64. return iHash;
    65. }
    66. }

    Sollten Fehler enthalten sein: passiert. Bei deinem Beispiel funktioniert es bestens.

    Dieser Beitrag wurde bereits 2 mal editiert, zuletzt von „AliveDevil“ () aus folgendem Grund: Formatierung angepasst.

    @sonne75
    Nein, denn in diesem Fall wird später in der Liste noch einmal eine Liste vorhanden sein, bei der die gesuchte Kombination vorne steht. Das macht den Algo ja auch so ineffizient, weil wirklich alle Möglichen Permutationen berechnet werden und dann erst verglichen wird.

    Edit: Ich werde den Code mal etwas optimieren.

    Hier jetzt noch mal der überarbeitete Code:
    Spoiler anzeigen

    C-Quellcode

    1. public static bool ShutTheBox(int sum, int count, int[] input, out int[] output)
    2. {
    3. List<int>[] buffer = null;
    4. var oldBuffer = new List<int>[input.Length];
    5. for (int i = 0; i < input.Length; i++)
    6. oldBuffer[i] = new List<int>(new[] { input[i] });
    7. var bufferCount = input.Length;
    8. for (int c = 1; c < count; c++)
    9. {
    10. buffer = new List<int>[bufferCount * (input.Length - c)];
    11. int index = 0;
    12. for (int i = 0; i < oldBuffer.Length; i++)
    13. foreach (var item in input)
    14. if (!oldBuffer[i].Contains(item))
    15. {
    16. var l = new List<int>(oldBuffer[i]);
    17. l.Add(item);
    18. if (c + 1 == count && l.Sum() == sum)
    19. {
    20. output = l.ToArray();
    21. return true;
    22. }
    23. buffer[index] = l;
    24. index++;
    25. }
    26. oldBuffer = buffer;
    27. bufferCount = oldBuffer.Count();
    28. }
    29. output = null;
    30. return false;

    Die Funktion wird failen, wenn "count" < 2 ist oder wenn "count" > input.Length ist. Allerdings halte ich das auch für keine Eingabe, die man erhalten sollte.

    Na schön, du Halsabschneider. :P ;)
    Spoiler anzeigen

    C-Quellcode

    1. if (count < 1 || count > input.Length)
    2. {
    3. output = null;
    4. return false;
    5. }
    6. if (count == 1)
    7. {
    8. foreach (var item in input)
    9. if (item == sum)
    10. {
    11. output = new[] { item };
    12. return true;
    13. }
    14. output = null;
    15. return false;
    16. }
    17. List<int>[] buffer = null;
    18. var oldBuffer = new List<int>[input.Length];
    19. for (int i = 0; i < input.Length; i++)
    20. oldBuffer[i] = new List<int>(new[] { input[i] });
    21. var bufferCount = input.Length;
    22. for (int c = 1; c < count; c++)
    23. {
    24. buffer = new List<int>[bufferCount * (input.Length - c)];
    25. int index = 0;
    26. for (int i = 0; i < oldBuffer.Length; i++)
    27. foreach (var item in input)
    28. if (!oldBuffer[i].Contains(item))
    29. {
    30. var l = new List<int>(oldBuffer[i]);
    31. l.Add(item);
    32. if (c + 1 == count && l.Sum() == sum)
    33. {
    34. output = l.ToArray();
    35. return true;
    36. }
    37. buffer[index] = l;
    38. index++;
    39. }
    40. oldBuffer = buffer;
    41. bufferCount = oldBuffer.Count();
    42. }
    43. output = null;
    44. return false;
    45. }

    Ich habe den Code nochmal durch n eigenen Performance-Counter gejagt:

    C-Quellcode

    1. static IEnumerable<TimeSpan> performanceCounter( int iterations, TextWriter writer ) {
    2. int[] val = new int[] { 4, 11, 1, 7, 3, 5, 2 };
    4. DateTime start;
    5. for ( int i = 0; i < iterations; i++ ) {
    6. writer.WriteLine( "Iteration: {0}", i );
    7. var query = ShutTheBox( 18, 5, val );
    8. start = DateTime.Now;
    9. List<IEnumerable<int>> bytes = query.ToList();
    10. yield return DateTime.Now - start;
    11. }
    12. }

    ich glaube, dass Ergebnis kann sich sehen lassen:

    Quellcode

    1. Avg.: 00:00:00.0130000, Max.: 00:00:00.0350379, Min.: 00:00:00.0119579
    2. Time: 00:00:01.3110441, Iterations: 100

    Bei folgendem Code:

    C-Quellcode

    1. int iterations = 100;
    2. List<TimeSpan> times = performanceCounter( iterations, Console.Out ).ToList();
    4. Console.WriteLine( "Avg.: {0}, Max.: {1}, Min.: {2}", TimeSpan.FromMilliseconds( times.Average( item => item.Milliseconds ) ), times.Max( item => item ), times.Min( item => item ) );
    5. Console.WriteLine( "Time: {0}, Iterations: {1}", TimeSpan.FromTicks( times.Sum( item => item.Ticks ) ), iterations );

    Spoiler anzeigen

    C-Quellcode

    1. static void Main(string[] args)
    2. {
    3. var sum = 18;
    4. var num = 5;
    5. var input = new[] { 4, 11, 1, 7, 3, 5, 2 };
    6. int[] output = null;
    8. Console.WriteLine("Sum = " + sum + ", Num = " + num + ", Input = " + string.Join(", ", input));
    9. Console.Write("Result = " + ShutTheBoxFast(sum, num, input, out output));
    11. if (output != null)
    12. {
    13. Console.WriteLine(", " + string.Join(", ", output));
    14. }
    15. else
    16. {
    17. Console.WriteLine();
    18. }
    20. Console.ReadKey();
    21. }
    23. class LolNoException : Exception
    24. {
    26. }
    28. static bool ShutTheBoxFast(int sum, int num, int[] input, out int[] output)
    29. {
    30. if (input.Length < num)
    31. {
    32. throw new LolNoException();
    33. }
    35. var rnd = new Random();
    37. const long max = 4000000000;
    39. for (var k = 0; k < max; ++k)
    40. {
    41. var done = new bool[input.Length];
    42. output = new int[num];
    44. for (var i = 0; i < num; ++i)
    45. {
    46. var temp = rnd.Next(0, input.Length - 1);
    48. while (done[temp])
    49. {
    50. temp = rnd.Next(0, input.Length - 1);
    51. }
    53. output[i] = input[temp];
    54. done[temp] = true;
    55. }
    57. if (output.Sum() == sum)
    58. {
    59. return true;
    60. }
    61. }
    63. output = null;
    64. return false;
    65. }


    Spoiler anzeigen
    Mit n = 2 gehts sehr schnell :-)
    Laufzeit bei n >= 4: lim ∞


    Ich poste morgen mal eine ernsthafte Lösung :-D
    To make foobar2000 a real random music player, I figured out the only way to achieve this is to use Windows Media Player.

    “At some point in time, you recognize that knowing more does not necessarily make you more happy.”

    Dieser Beitrag wurde bereits 1 mal editiert, zuletzt von „Chrisber“ ()

    Also ~blaze~ hat mich ja gelehrt (;)), dass man immer eine bestimme Zeit festlegen und dann die Durchläufe, die darin möglich sind, zählen soll, da die Stopwatch sonst zu ungenau wird.
    Mein Code schafft z.B. ungefähr 2400 Durchlaufe in einer Sekunde. (@SeriTools: 8| )

    Ich habs so getestet:

    C-Quellcode

    1. List<int> input = new List<int>(new int[] { 4, 11, 1, 7, 3, 5, 2 });
    2. Stopwatch stop = new Stopwatch();
    3. stop.Start();
    4. for (int i = 0; i < 1000000; i++) {
    5. List<int> result = new List<int>();
    6. bool success = ShutTheBox(result, 18, 5, input);
    7. }
    8. stop.Stop();
    9. Console.Write(stop.ElapsedMilliseconds);


    Habe die Zeit und die Durchläufe übrigens nochmal angepasst, hatte nen Fehler im Aufruf drin.

    EDIT: Grad von Debug auf Release gestellt, jetzt sinds 480ms für 1mio Durchläufe :D
    Wenn man die List<T> nur Cleart und nicht immer neu erstellt bin ich bei 430ms.

    EDIT2: Von List<T> auf Array umgestellt:
    Spoiler anzeigen

    C-Quellcode

    1. private static void Main(string[] args)
    2. {
    3. List<int> input = new List<int>(new int[] { 4, 11, 1, 7, 3, 5, 2 });
    4. int[] input2 = new int[] { 4, 11, 1, 7, 3, 5, 2 };
    5. Stopwatch stop = new Stopwatch();
    6. stop.Start();
    7. List<int> result = new List<int>();
    8. for (int i = 0; i < 1000000; i++) {
    9. result.Clear();
    10. bool success = ShutTheBox(result, 18, 5, input);
    11. }
    12. stop.Stop();
    13. Console.WriteLine(stop.ElapsedMilliseconds);
    14. stop.Reset();
    15. stop.Start();
    16. for (int i = 0; i < 1000000; i++) {
    17. int[] result2 = new int[5];
    18. bool success = ShutTheBox2(result2, 18, 5, input2);
    19. }
    20. stop.Stop();
    21. Console.WriteLine(stop.ElapsedMilliseconds);
    22. Console.ReadKey(true);
    23. }
    25. private static bool ShutTheBox(List<int> result, int s, int n, List<int> input, int nextindex = 0)
    26. {
    27. if (n == 0) return false;
    28. while (true) {
    29. if (n > input.Count - nextindex) return false;
    30. int i = input[nextindex];
    31. if (s - i < 0) {
    32. nextindex++;
    33. } else if (s - i == 0) {
    34. if (n == 1) {
    35. result.Add(i);
    36. return true;
    37. } else {
    38. nextindex++;
    39. }
    40. } else {
    41. if (!ShutTheBox(result, s - i, n - 1, input, nextindex + 1)) {
    42. nextindex++;
    43. } else {
    44. result.Add(i);
    45. return true;
    46. }
    47. }
    48. }
    49. }
    51. private static bool ShutTheBox2(int[] result, int s, int n, int[] input, int nextindex = 0)
    52. {
    53. if (n == 0) return false;
    54. while (true) {
    55. if (n > input.Length - nextindex) return false;
    56. int i = input[nextindex];
    57. if (s - i < 0) {
    58. nextindex++;
    59. } else if (s - i == 0) {
    60. if (n == 1) {
    61. result[n - 1] = i;
    62. return true;
    63. } else {
    64. nextindex++;
    65. }
    66. } else {
    67. if (!ShutTheBox2(result, s - i, n - 1, input, nextindex + 1)) {
    68. nextindex++;
    69. } else {
    70. result[n - 1] = i;
    71. return true;
    72. }
    73. }
    74. }
    75. }


    ShutTheBox() ist List<T>, ShutTheBox2() ist Arraybasiert.

    1Mio. Durchläufe:
    ShutTheBox(): 430ms
    ShutTheBox2(): ~210ms

    EDIT3: Code noch einmal etwas verkürzt (Danke an @nikeee13:)
    EDIT4: Noch n bisschen optimiert.
    Spoiler anzeigen

    C-Quellcode

    1. private static bool ShutTheBox2(int[] result, int s, int n, int[] input, int nextindex = 0)
    2. {
    3. if (n == 0) return false;
    4. while (n <= input.Length - nextindex) {
    5. int i = input[nextindex];
    6. if (s == i) {
    7. if (n == 1) {
    8. result[n - 1] = i;
    9. return true;
    10. }
    11. nextindex++;
    12. } else {
    13. nextindex++;
    14. if (s >= i) {
    15. if (ShutTheBox2(result, s - i, n - 1, input, nextindex)) {
    16. result[n - 1] = i;
    17. return true;
    18. }
    19. }
    20. }
    21. }
    22. return false;
    23. }
    | Keine Fragen per PN oder Skype.

    Dieser Beitrag wurde bereits 10 mal editiert, zuletzt von „SeriTools“ ()