Problemansatz: "A Zero-Sum Game of Threes"



  • Problemstellung hier zu finden: https://www.reddit.com/r/dailyprogrammer/comments/3rhzdj/20151104_challenge_239_intermediate_a_zerosum/

    Ich nenne -2, -1, 0, 1, 2 "modifiers". Habe mir überlegt für jeden Schritt alle möglichen modifiers zu speichern, und separat davon den im Rechenschritt verwendeten.

    Wenn man nun bei 1 ankommt (man teilt die Anfangszahl immer wieder durch 3), und die Summe der modifiers nicht 0 ist, geht man so oft Rechenschritte zurück, bis man einen findet wo noch andere unverwendete modifiers übrig sind und probiert das Ganze mit dem anderen von neuem. Kommt man an den Anfang zurück und es gibt keine modifiers mehr, so ist es "impossible".

    Das lässt sich dann natürlich auch irgendwie optimieren, aber mir geht es um den Grundansatz. Außerdem, werden so trotzdem nicht alle möglichen Kombinationen abgedeckt. Meine "Lösung" kommt mir deshalb umso stärker als quatsch vor.

    Mir kommt dieses Problem nämlich unnötig kompliziert vor. Deshalb wollte ich mal euch fragen, wie ihr das lösen würdet. Ich hab das Gefühl ich sitz da ein bisschen auf dem Schlauch. Vielleicht fehlen mir auch einfach bestimmte logische Grundlagen...

    Würde mich sehr über Vorschläge freuen!

    LG
    HarteWare


  • Mod

    HarteWare schrieb:

    Außerdem, werden so trotzdem nicht alle möglichen Kombinationen abgedeckt.

    Welche werden denn ausgelassen?

    Deshalb wollte ich mal euch fragen, wie ihr das lösen würdet.

    Deine Idee klingt erst einmal ganz vernünftig. Was eventuell ein Problem werden könnte, ist, dass der Baum bei einem Anfangswert der Größenordnung 2^64 eine Tiefe von ~40 hat, was bedeutet, dass man sich eventuell ein paar Tricks einfallen lassen muss, um den Vorgang zu beschleunigen. Beispielsweise könnte man sich merken, welche Zahlen man bereits erforscht hat und was die Ergebnisse waren, so dass man diese nicht doppelt bearbeitet. Wenn das dann noch nicht reicht, dann denkt man über clevere Ansätze nach.



  • EIn Beispiel: 3 schritte:

    A: 1
    
    B: -1, 2
    
    C: -2 1
    
    D: -
    

    Summe ist nicht null, gehe zurück zu C, verwende -2, immernoch nicht 0, verwende C1, passt immer noch nicht, als verwende ich B-1 C1, passt nicht, also verwende ich B2 C1, passt auch nicht. Dabei wurden B-1 C-2 und B2 C-2 nicht ausprobiert. (Die Zahlen müssen jetzt erstmal keinen Sinn machen)

    Habe ich durch meine Beschreibung möglicherweise etwas impliziert, dass ich bisher nicht bewusst beachtet habe? Dass ich irgendwie mit einer Iteration über die jeweiligen modifier jeden möglichen Pfad abarbeiten lasse? Muss ich mir nochmal durch den Kopf gehen lassen.

    Mögliche Optimierungen die ich mir überlegt habe waren 1. wie erwähnt das Ergebnis für bestimmte "Pfade" zu speichern, damit ich mir das erneute rechnen spare. Außerdem, vielleicht kann man irgendwie "intelligent" den nächsten modifier auswählen, wenn man die momentane Summe bzw. die zuvor gewählten modifier in Betracht zieht.

    Jedenfalls vielen Dank für die schnelle Antwort find ich super.

    LG


  • Mod

    HarteWare schrieb:

    EIn Beispiel: 3 schritte:

    A: 1
    
    B: -1, 2
    
    C: -2 1
    
    D: -
    

    Summe ist nicht null, gehe zurück zu C, verwende -2, immernoch nicht 0, verwende C1, passt immer noch nicht, als verwende ich B-1 C1, passt nicht, also verwende ich B2 C1, passt auch nicht. Dabei wurden B-1 C-2 und B2 C-2 nicht ausprobiert. (Die Zahlen müssen jetzt erstmal keinen Sinn machen)

    😕 Ich verstehe dein Beispiel nicht. B-1 C-2 war doch dein zweiter Ast. und B+2 C-2 sollte dein letzter Ast sein, ich verstehe nicht, wieso du den nicht aufzählst. Außerdem werden B-1 und B+2 zu unterschiedlichen C führen!



  • Mein Tipp wäre hier erstmal kurz nachzudenken und zu überlegen welche Möglichen "Modifier"-Mengen überhaupt so auftreten (Tipp es sind nicht sehr viele) und inwiefern sich die zur Auswahl stehenden Werte eigentlich unterscheiden. Mein Lösungsvorschlag wäre sich mit der Summe greedy möglichst nah an der Null zu halten.



  • HarteWare schrieb:

    Problemstellung hier zu finden: https://www.reddit.com/r/dailyprogrammer/comments/3rhzdj/20151104_challenge_239_intermediate_a_zerosum/

    Wenn Du willst, dass ich die lese, dann poste sie hier.



  • Hallöchen,

    mit Freuden sehe ich, dass sich weitere Leute an meiner Frage beteiligen. Erstens mal entschuldigung an SeppJ, dass ich noch nicht geantwortet habe. Ich versuche irgendwie Code zusammen zu bekommen, aber es klappt noch nicht so ganz. Kann gut sein, dass mein Bsp. blöd war, ich kapiers ja selber nur halb.

    Zum Thema "welche Möglichen "Modifier"-Mengen überhaupt so auftreten" habe ich mal folgende Überlegung angestellt:

    +2
    +1
    +0
    -1 +2
    +1 -2
    +0
    -1 +2
    +1 -2
    +0
    -1 +2
    +1 -2
    +0
    -1 +2
    +1 -2
    +0
    .
    .
    .
    

    Wenn Du willst, dass ich die lese, dann poste sie hier

    Dürfte ich erfahren weshalb? Bin einfach neugierig :s
    Ich dachte man will nicht, dass ich den kompletten Inhalt hier kopiere. Also bitte, sogar formatiert:

    Challenge #239 [Intermediate] A Zero-Sum Game of Threes

    Description

    Let's pursue Monday's Game of Threes further!

    To make it more fun (and make it a 1-player instead of a 0-player game), let's change the rules a bit: You can now add any of [-2, -1, 1, 2] to reach a multiple of 3. This gives you two options at each step, instead of the original single option.

    With this modified rule, find a Threes sequence to get to 1, with this extra condition: The sum of all the numbers that were added must equal 0. If there is no possible correct solution, print Impossible.
    Sample Input:

    929

    Sample Output:

    `929 1

    310 -1

    103 -1

    34 2

    12 0

    4 -1

    1`

    Since 1 - 1 - 1 + 2 - 1 == 0 , this is a correct solution.
    Bonus points

    Make your solution work (and run reasonably fast) for numbers up to your operating system's maximum long int value, or its equivalent. For some concrete test cases, try:

    ` 18446744073709551615

    18446744073709551614`   
    

    Ich mach solang mal weiter das vermutlich einfache Problem in Teilprobleme zu zerlegen, bis ich ein Testprogramm hinbekomme. Naja ich arbeite jetzt auch nicht den ganzen Tag lang dran... Bin also nicht komplett blöd, nur beschäftigt 😛

    Bitte keine kompletten Lösungen posten (spoilern) !!!



  • Ist 0 deiner Meinung nach ein vielfaches von 3?





  • @Jester:
    Naja, irgendwie ist Null keine gültige Eingabe für diesen speziellen Fall... Das "Ende" ist ja 1. Bin mir jetzt nicht sicher, was die korrekte Definition von Vielfach ist. Aber vom Wort her würde ich 6, 9, 12, ... als Vielfache von 3 bezeichnen. Worauf zielt die Frage ab?



  • Ich würde bei einer Eingabe von 1 neben der 2 auch die -1 gelten lassen. Vielfaches von 3 heißt für mich: lässt sich schreiben in der Form x*3.


Log in to reply