Knobelaufgabe ( November 2021 ) 1983 Hirnschmalz vs. 2021 Rechenpower
8 Beiträge
•
Seite 1 von 1
8 Beiträge
Seite 1 von 1
Beitrag
von black_adept (Top Expert / 4087 / 126 /
940
)
»
Moin allerseits,
die Novemberknobelaufgabe ist etwas anders konzipiert als die früheren.
Es geht diesmal um ein "Spiel" - bzw. das was Informatiker so als Spiel ansehen.
Es wird eine natürliche Zahl (Divisor) von 1-20 vorgegeben. Danach müsst ihr wählen, ob ihr im Spiel anfangen wollt oder nicht.
Jetzt müsst ihr und euer Gegener abwechselnd die Ziffern einer 6-stelligen Zahl belegen. Ihr habt gewonnen, wenn die resultierende 6-stellige Zahl durch den Divisor ohne Rest teilbar ist.
Beispiel: Vorgegeben wird der Divisor 6.
Eure erste Entscheidung ist, dass ihr anfangen wollt und ihr belegt die 3. Ziffer mit einer 5. --> ??5???.
Euer Gegner setzt jetzt die 1 Ziffer auf 3. --> 3?5???.
Das wird fortgesetzt, bis am Ende die Zahl 315887 herauskommt. Leider ist diese nicht durch 6 teilbar, so das ihr nicht gewonnen habt.
Ich habe wie üblich ein Demoprogramm geschrieben, welches den Spielrahmen bereit stellt, sowie eine - wie ebenso üblich - schlechte Demolösung und auch einen guten Gegenspieler, der euch das Leben so schwer wie möglich macht.
Eure Aufgabe ist es nun, die beiden redefinierten Methoden der Klasse "solution" so abzuändern, dass ihr mehr Gewinne erzielt als die Demolösung. Das sollte eigentlich nicht schwer sein. Aber wie viele Gewinne könnt ihr insgesamt einfahren?
Die Methode "i_want_to_be_player_1" entscheidet lediglich, ob ihr anfangen wollt oder nicht bzw. ob ihr die erste oder die letzte Ziffer setzen wollt. Die Demolösung will stets anfangen.
Die Methode "set_digit" sagt, welche Position der 6-stelligen Zahl ihr mit welcher Ziffer besetzen wollt. Die Demolösung ist da auch recht einfach gestrickt und wird mit wenigen Siegen bestraft.
Das Demoprogramm ist etwas länger, aber der meiste Code hat mit der Spielumgebung zu tun - darum braucht ihr euch eigentlich nicht zu kümmern.
Da ich nächste Woche im Urlaub bin ist die Laufzeit dieser Aufgabe auf etwa 2 Wochen ausgelegt.
Das Schöne an dieser Aufgabe ist in meinen Augen, dass sie
die Novemberknobelaufgabe ist etwas anders konzipiert als die früheren.
Es geht diesmal um ein "Spiel" - bzw. das was Informatiker so als Spiel ansehen.
Es wird eine natürliche Zahl (Divisor) von 1-20 vorgegeben. Danach müsst ihr wählen, ob ihr im Spiel anfangen wollt oder nicht.
Jetzt müsst ihr und euer Gegener abwechselnd die Ziffern einer 6-stelligen Zahl belegen. Ihr habt gewonnen, wenn die resultierende 6-stellige Zahl durch den Divisor ohne Rest teilbar ist.
Beispiel: Vorgegeben wird der Divisor 6.
Eure erste Entscheidung ist, dass ihr anfangen wollt und ihr belegt die 3. Ziffer mit einer 5. --> ??5???.
Euer Gegner setzt jetzt die 1 Ziffer auf 3. --> 3?5???.
Das wird fortgesetzt, bis am Ende die Zahl 315887 herauskommt. Leider ist diese nicht durch 6 teilbar, so das ihr nicht gewonnen habt.
Ich habe wie üblich ein Demoprogramm geschrieben, welches den Spielrahmen bereit stellt, sowie eine - wie ebenso üblich - schlechte Demolösung und auch einen guten Gegenspieler, der euch das Leben so schwer wie möglich macht.
Eure Aufgabe ist es nun, die beiden redefinierten Methoden der Klasse "solution" so abzuändern, dass ihr mehr Gewinne erzielt als die Demolösung. Das sollte eigentlich nicht schwer sein. Aber wie viele Gewinne könnt ihr insgesamt einfahren?
Die Methode "i_want_to_be_player_1" entscheidet lediglich, ob ihr anfangen wollt oder nicht bzw. ob ihr die erste oder die letzte Ziffer setzen wollt. Die Demolösung will stets anfangen.
Die Methode "set_digit" sagt, welche Position der 6-stelligen Zahl ihr mit welcher Ziffer besetzen wollt. Die Demolösung ist da auch recht einfach gestrickt und wird mit wenigen Siegen bestraft.
Code: Alles auswählen.
REPORT zknobel_1983_vs_2021_publish.
CLASS lcx DEFINITION INHERITING FROM cx_static_check.
ENDCLASS.
CLASS lcl_game DEFINITION.
PUBLIC SECTION.
TYPES: mtv_divisor TYPE numc2,
mtv_player TYPE string.
TYPES: BEGIN OF mts_gamestate,
digit1 TYPE char1,
digit2 TYPE char1,
digit3 TYPE char1,
digit4 TYPE char1,
digit5 TYPE char1,
digit6 TYPE char1,
END OF mts_gamestate.
TYPES: BEGIN OF mts_set_digit,
position TYPE i, " 1-6
digit TYPE numc1,
END OF mts_set_digit .
CONSTANTS: mc_player_1 TYPE mtv_player VALUE `Spieler 1 - macht den ersten Zug`,
mc_player_2 TYPE mtv_player VALUE `Spieler 2 - macht den letzten Zug`,
mc_gamestate_not_set TYPE char1 VALUE '?'.
METHODS:
i_want_to_be_player_1 IMPORTING iv_divisor TYPE mtv_divisor
RETURNING VALUE(rv_player) TYPE mtv_player,
set_player IMPORTING iv_player TYPE mtv_player,
set_digit IMPORTING is_gamestate TYPE mts_gamestate
iv_divisor TYPE mtv_divisor
RETURNING VALUE(rs_set_digit) TYPE mts_set_digit
RAISING lcx.
DATA:
mv_player TYPE mtv_player.
ENDCLASS.
CLASS lcl_solution DEFINITION INHERITING FROM lcl_game.
PUBLIC SECTION.
METHODS: i_want_to_be_player_1 REDEFINITION,
set_digit REDEFINITION.
ENDCLASS.
CLASS lcl_opponent DEFINITION INHERITING FROM lcl_game.
PUBLIC SECTION.
METHODS: set_digit REDEFINITION.
ENDCLASS.
CLASS lcl_application DEFINITION FINAL.
PUBLIC SECTION.
CONSTANTS: mc_all_divisors TYPE lcl_game=>mtv_divisor VALUE 99.
METHODS:
initialization,
main IMPORTING iv_divisor TYPE lcl_game=>mtv_divisor.
PRIVATE SECTION.
METHODS:
play_game IMPORTING iv_divisor TYPE lcl_game=>mtv_divisor
CHANGING cv_choice TYPE lcl_game=>mtv_player
cv_won TYPE abap_bool
cv_gamestates TYPE string
RAISING lcx,
advance_game IMPORTING is_set_digit TYPE lcl_game=>mts_set_digit
RETURNING VALUE(rv_move_is_allowed) TYPE abap_bool
RAISING lcx.
DATA:
mo_player1 TYPE REF TO lcl_game,
mo_player2 TYPE REF TO lcl_game,
ms_gamestate TYPE lcl_game=>mts_gamestate.
ENDCLASS.
PARAMETERS: divisor TYPE lcl_game=>mtv_divisor AS LISTBOX VISIBLE LENGTH 40 OBLIGATORY.
INITIALIZATION.
NEW lcl_application( )->initialization( ).
END-OF-SELECTION.
NEW lcl_application( )->main( iv_divisor = divisor ).
CLASS lcl_solution IMPLEMENTATION.
METHOD i_want_to_be_player_1.
rv_player = mc_player_1.
ENDMETHOD.
METHOD set_digit.
*Freie Stelle wählen und dort eine Ziffer eintragen und hoffen, dass das ausreichen ist.
DO 6 TIMES.
ASSIGN COMPONENT sy-index OF STRUCTURE is_gamestate TO FIELD-SYMBOL(<lv_digit>).
IF <lv_digit> = mc_gamestate_not_set.
rs_set_digit = VALUE #( position = sy-index digit = sy-index ).
RETURN.
ENDIF.
ENDDO.
ENDMETHOD.
ENDCLASS.
CLASS lcl_opponent IMPLEMENTATION.
METHOD set_digit.
DATA: lv_count_unset TYPE i,
ls_last LIKE rs_set_digit,
lv_num TYPE char6,
lv_num2 TYPE char6,
lv_offset TYPE i.
*--------------------------------------------------------------------*
* Bei ungünstiger Wahl des Spielers Sonderbehandlung
*--------------------------------------------------------------------*
IF 720 MOD iv_divisor = 0.
IF is_gamestate-digit6 = mc_gamestate_not_set.
rs_set_digit = VALUE #( position = 6 digit = 7 ).
RETURN.
ENDIF.
IF is_gamestate-digit5 = mc_gamestate_not_set.
rs_set_digit = VALUE #( position = 5 digit = 1 ).
RETURN.
ENDIF.
IF is_gamestate-digit4 = mc_gamestate_not_set.
rs_set_digit = VALUE #( position = 4 digit = 3 ).
RETURN.
ENDIF.
ENDIF.
DATA: lt_results TYPE match_result_tab.
FIND ALL OCCURRENCES OF mc_gamestate_not_set IN is_gamestate RESULTS lt_results.
lv_count_unset = lines( lt_results ).
*--------------------------------------------------------------------*
* 1. und 2. Ziffer - irgendwas reinsetzen
*--------------------------------------------------------------------*
DO 6 TIMES.
ASSIGN COMPONENT sy-index OF STRUCTURE is_gamestate TO FIELD-SYMBOL(<lv_digit>).
IF <lv_digit> = mc_gamestate_not_set.
ls_last = rs_set_digit.
rs_set_digit = VALUE #( position = sy-index digit = sy-index ).
IF lv_count_unset > 2.
RETURN.
ENDIF.
ENDIF.
ENDDO.
*--------------------------------------------------------------------*
* das letzte Mal einfach die für den Spieler schlechteste Möglichkeit wählen
*--------------------------------------------------------------------*
IF lv_count_unset = 1.
DO 10 TIMES.
lv_num = is_gamestate.
REPLACE mc_gamestate_not_set IN lv_num WITH |{ sy-index - 1 }|.
IF lv_num MOD iv_divisor <> 0.
rs_set_digit-digit = sy-index - 1.
RETURN.
ENDIF.
ENDDO.
ELSEIF lv_count_unset = 2.
* Einfach 20 * 10 Möglichkeiten durchprobieren und die Schlechteste auswählen
DO 2 TIMES.
IF sy-index = 1.
lv_offset = rs_set_digit-position - 1.
ELSE.
lv_offset = ls_last-position - 1.
ENDIF.
DO 10 TIMES.
lv_num = is_gamestate.
lv_num+lv_offset(1) = |{ sy-index - 1 }|.
DO 10 TIMES.
lv_num2 = lv_num.
REPLACE mc_gamestate_not_set IN lv_num2 WITH |{ sy-index - 1 }|.
IF lv_num2 MOD iv_divisor = 0.
EXIT.
ENDIF.
ENDDO.
IF lv_num2 MOD iv_divisor <> 0.
rs_set_digit = VALUE #( position = lv_offset + 1 digit = lv_num+lv_offset(1) ).
RETURN.
ENDIF.
ENDDO.
ENDDO.
ENDIF.
ENDMETHOD.
ENDCLASS.
CLASS lcl_application IMPLEMENTATION.
METHOD main.
TYPES: BEGIN OF lts_results,
divisor TYPE lcl_game=>mtv_divisor,
choice TYPE lcl_game=>mtv_player,
result TYPE string,
won TYPE abap_bool,
exception TYPE abap_bool,
END OF lts_results.
FIELD-SYMBOLS: <ls_result> TYPE lts_results.
DATA: lt_results TYPE STANDARD TABLE OF lts_results WITH NON-UNIQUE DEFAULT KEY.
*--------------------------------------------------------------------*
* Spiel(e) spielen
*--------------------------------------------------------------------*
IF iv_divisor = mc_all_divisors. " Alle
DO 20 TIMES.
APPEND VALUE #( divisor = sy-index
exception = abap_false
won = abap_false
) TO lt_results ASSIGNING <ls_result>.
TRY.
me->play_game( EXPORTING iv_divisor = <ls_result>-divisor
CHANGING cv_choice = <ls_result>-choice
cv_won = <ls_result>-won
cv_gamestates = <ls_result>-result
).
CATCH lcx.
<ls_result>-exception = abap_true.
ENDTRY.
ENDDO.
ELSE.
TRY.
APPEND VALUE #( divisor = iv_divisor
exception = abap_false
won = abap_false
) TO lt_results ASSIGNING <ls_result>.
me->play_game( EXPORTING iv_divisor = <ls_result>-divisor
CHANGING cv_choice = <ls_result>-choice
cv_won = <ls_result>-won
cv_gamestates = <ls_result>-result
).
CATCH lcx.
<ls_result>-exception = abap_true.
ENDTRY.
ENDIF.
*--------------------------------------------------------------------*
* Ergebnis
*--------------------------------------------------------------------*
TRY.
cl_salv_table=>factory( IMPORTING
r_salv_table = DATA(lo_salv)
CHANGING
t_table = lt_results
).
lo_salv->get_columns( )->set_optimize( ).
LOOP AT lo_salv->get_columns( )->get( ) ASSIGNING FIELD-SYMBOL(<ls_col>).
<ls_col>-r_column->set_medium_text( CONV #( <ls_col>-columnname ) ).
ENDLOOP.
lo_salv->display( ).
CATCH cx_salv_msg.
ENDTRY.
ENDMETHOD.
METHOD play_game.
DATA: lo_winner TYPE REF TO lcl_game,
lv_gamestate TYPE char6.
*--------------------------------------------------------------------*
* Lösung und Gegner erzeugen
*--------------------------------------------------------------------*
DATA(lo_solution) = NEW lcl_solution( ).
DATA(lo_opponent) = NEW lcl_opponent( ).
*--------------------------------------------------------------------*
* Lösung fragen, ob sie anfange möchte oder nicht und dann
* dementsprechend Spiel initialisieren
*--------------------------------------------------------------------*
IF lo_solution->i_want_to_be_player_1( iv_divisor ) = lcl_game=>mc_player_1.
cv_choice = lcl_game=>mc_player_1.
mo_player1 = lo_solution.
mo_player2 = lo_opponent.
ELSE.
cv_choice = lcl_game=>mc_player_2.
mo_player1 = lo_opponent.
mo_player2 = lo_solution.
ENDIF.
mo_player1->set_player( lcl_game=>mc_player_1 ).
mo_player2->set_player( lcl_game=>mc_player_2 ).
CLEAR me->ms_gamestate WITH lcl_game=>mc_gamestate_not_set.
*--------------------------------------------------------------------*
* Spielen der 6 Züge
*--------------------------------------------------------------------*
DO 3 TIMES.
* Spieler 1 zieht
me->advance_game( mo_player1->set_digit( is_gamestate = me->ms_gamestate iv_divisor = iv_divisor ) ).
lv_gamestate = me->ms_gamestate.
cv_gamestates = |{ cv_gamestates } / { lv_gamestate }|.
* Spieler 2 zieht
me->advance_game( mo_player2->set_digit( is_gamestate = me->ms_gamestate iv_divisor = iv_divisor ) ).
lv_gamestate = me->ms_gamestate.
cv_gamestates = |{ cv_gamestates } / { lv_gamestate }|.
ENDDO.
REPLACE REGEX '^[/\s]*' IN cv_gamestates WITH ``.
* Prüfen ob gewonnen oder nicht
DATA: lv_num TYPE num6.
lv_num = lv_gamestate.
IF lv_num MOD iv_divisor = 0.
cv_won = abap_true.
ELSE.
cv_won = abap_false.
ENDIF.
ENDMETHOD.
METHOD advance_game.
ASSIGN COMPONENT is_set_digit-position OF STRUCTURE me->ms_gamestate TO FIELD-SYMBOL(<lv_digit>).
IF sy-subrc <> 0.
MESSAGE |Position { is_set_digit-position } darf nicht gesetzt werden| TYPE 'I' DISPLAY LIKE 'E'.
RAISE EXCEPTION TYPE lcx.
ENDIF.
IF <lv_digit> <> lcl_game=>mc_gamestate_not_set.
MESSAGE |Position { is_set_digit-position } dist schon belegt| TYPE 'I' DISPLAY LIKE 'E'.
RAISE EXCEPTION TYPE lcx.
ENDIF.
<lv_digit> = is_set_digit-digit.
ENDMETHOD.
METHOD initialization.
DATA lt_values TYPE vrm_values.
DO 20 TIMES.
APPEND VALUE #( key = sy-index ) TO lt_values.
ENDDO.
APPEND VALUE #( key = 99 text = 'Alle Divisoren von 1-20' ) TO lt_values.
CALL FUNCTION 'VRM_SET_VALUES'
EXPORTING
id = 'DIVISOR'
values = lt_values
EXCEPTIONS
id_illegal_name = 1
OTHERS = 2.
divisor = mc_all_divisors.
ENDMETHOD.
ENDCLASS.
CLASS lcl_game IMPLEMENTATION.
METHOD i_want_to_be_player_1.
rv_player = mc_player_1.
ENDMETHOD.
METHOD set_player.
mv_player = iv_player.
ENDMETHOD.
METHOD set_digit.
MESSAGE 'Method SET_DIGIT not redefined' TYPE 'I' DISPLAY LIKE 'E'.
RAISE EXCEPTION TYPE lcx.
ENDMETHOD.
ENDCLASS.Da ich nächste Woche im Urlaub bin ist die Laufzeit dieser Aufgabe auf etwa 2 Wochen ausgelegt.
Das Schöne an dieser Aufgabe ist in meinen Augen, dass sie
- Auf den ersten Blick total kompliziert klingt
- Auf den zweiten Blick eigentlich recht einfach
- Auf den 3. Blick ist das Resultat, wann man beginnen sollte und bei welchen Divisoren man gewinnen kann überraschend.
- Der 4. Blick, warum 3. so ist, ist für euch vielleicht von Interesse, aber für die Lösung nicht unbedingt wichtig. Wenn jemand eine Begründung haben will, warum sich 2 bestimmte Divisoren anders verhalten als 2 andere bestimmte Divisoren kann mich gerne nach Abschluss der Knobelaufgabe dahingehend anschreiben.
Folgende Benutzer bedankten sich beim Autor black_adept für den Beitrag (Insgesamt 3):
ewx • Thomas R. • DeathAndPain
gesponsert ⓘ
Stellenangebote auf ABAPforum.com schalten
kostenfrei für Ausbildungsberufe und Werksstudenten
kostenfrei für Ausbildungsberufe und Werksstudenten
Beitrag
von DeathAndPain (Top Expert / 1939 / 257 /
412
)
»
Brr, da braucht man ja erst mal etwas Zeit, um aus dem OO-Wasserkopf das eigentliche Coding zu extrahieren. 😁 Problematisch finde ich die Benamung der Methode I_WANT_TO_BE_PLAYER_1 . Wenn ich sie richtig verstehe, dann soll man darüber die Entscheidung zurückliefern, wer anfangen soll. Das widerspricht aber dem Namen der Methode, der besagt, dass man immer anfangen möchte. Allenfalls wenn der Rückgabewert ein BOOLEAN_FLG wäre, würde der Name Sinn ergeben.
Beitrag
von black_adept (Top Expert / 4087 / 126 /
940
)
»
Moin D&P,
da hast du leider recht. Ich hatte im Laufe der Aufgabenkonzeption diverse Attribute hin- und hergeändert. Am Anfang war das tatsächlich mal ein Boolean-Wert, aber - wie von dir richtig bemerkt - inzwischen ist das ein String, weil ich das in der Ausgabetabelle wiederverwenden wollte und dabei übersehen habe, dass der zugehörige Name dann ja gar nicht mehr passt...
Was den "OO-Wasserkopf" angeht: Ich hatte gehofft, dass ihr euch nur auf die Klasse lcl_solution konzentriert und den Rest als "nett, aber für mich unwichtig" ignoriert. Und so konnte ich die verschiedenen Teile des Spiels /halbwegs/ thematisch trennen. Ist tatsächlich nicht sonderlich gut geworden - aber es ist ausreichend für etwas, was in keinem Produktivsystem laufen soll . 😊
Viel Spaß beim Grübeln über der tatsächlichen Aufgabe...
da hast du leider recht. Ich hatte im Laufe der Aufgabenkonzeption diverse Attribute hin- und hergeändert. Am Anfang war das tatsächlich mal ein Boolean-Wert, aber - wie von dir richtig bemerkt - inzwischen ist das ein String, weil ich das in der Ausgabetabelle wiederverwenden wollte und dabei übersehen habe, dass der zugehörige Name dann ja gar nicht mehr passt...
Was den "OO-Wasserkopf" angeht: Ich hatte gehofft, dass ihr euch nur auf die Klasse lcl_solution konzentriert und den Rest als "nett, aber für mich unwichtig" ignoriert. Und so konnte ich die verschiedenen Teile des Spiels /halbwegs/ thematisch trennen. Ist tatsächlich nicht sonderlich gut geworden - aber es ist ausreichend für etwas, was in keinem Produktivsystem laufen soll . 😊
Viel Spaß beim Grübeln über der tatsächlichen Aufgabe...
Beitrag
von DeathAndPain (Top Expert / 1939 / 257 /
412
)
»
Kann ich grundsätzlich verstehen, aber dieses Ziel hättest Du mit abstrakten Klassen auch erreicht. Die Singleton-Instanziierung erhöht nur zusätzlich die Komplexität, ohne einen Gegenwert zu bieten. Du arbeitest ja nicht wirklich mit Objekten in diesem Programm, sondern willst bei der Objekterstellung einfach nur, dass der Code in der jeweiligen Methode ausgeführt wird. Das wäre mit statischen Methoden für den Leser leichter nachvollziehbar gewesen.
Je kleiner der Divisor, desto einfacher die Entscheidung ob man anfangen will. Bei größeren Primzahlendivisoren wird es haarig, wenn man das 1x1 nicht mehr im Kopf hat.
Eine Frage bezüglich der Logik:
Müsste es nicht heißen "Spieler 2 - macht den ersten Zug"? Wenn Spieler 1 den ersten Zug macht, macht Spieler 2 automatisch den letzten.
Eine Frage bezüglich der Logik:
Code: Alles auswählen.
CONSTANTS: mc_player_1 TYPE mtv_player VALUE `Spieler 1 - macht den ersten Zug`,
mc_player_2 TYPE mtv_player VALUE `Spieler 2 - macht den letzten Zug`,
mc_gamestate_not_set TYPE char1 VALUE '?'.
Publikationen:
Qualitätsmanagement in der ABAP-Entwicklung,
Why we should take care about clean code
ABAP, Java, JavaScript
GitHub
Qualitätsmanagement in der ABAP-Entwicklung,
Why we should take care about clean code
ABAP, Java, JavaScript
GitHub
Beitrag
von black_adept (Top Expert / 4087 / 126 /
940
)
»
Moin jcoder,
du hast genau wie D&P recht. Das habe ich ungünstig gelöst. Anfangs war dieses einfach eine boolean-Variable aber ich wollte das sprechender machen und habe das dann ungünstig gelöst, wie das häufig so ist, wenn man im letzten Moment noch was "verbessern" möchte.
Die Entscheidungsmethode heißt "i_want_to_be_player1" und müsste eigentlich jetzt heißen "Entscheide_player1_oder_player2"- dann passt auch die Beschriftung wieder, weil IMMER Spieler 1 den ersten Zug macht und man ja nur entscheidet, ob man Spieler1 oder Spieler2 sein möchte und der erklärende Text dann nochmal erklärt, was das Besondere an diesen beiden Spielern ist.
Was das "1x1 im Kopf" angeht. Ja - ein wenig Schulwissen ist schon hilfreich, denn ein vollständiger Brute-Force Ansatz dauert bei Einfachstimplementierung ( zumindest bei meiner ) ca. 1/2 - 1 Stunde um die Entscheidung zu treffen, wohingegen bei Anwendung von obigem Schulwissen das in akzeptable Größenordnungen kommt.
du hast genau wie D&P recht. Das habe ich ungünstig gelöst. Anfangs war dieses einfach eine boolean-Variable aber ich wollte das sprechender machen und habe das dann ungünstig gelöst, wie das häufig so ist, wenn man im letzten Moment noch was "verbessern" möchte.
Die Entscheidungsmethode heißt "i_want_to_be_player1" und müsste eigentlich jetzt heißen "Entscheide_player1_oder_player2"- dann passt auch die Beschriftung wieder, weil IMMER Spieler 1 den ersten Zug macht und man ja nur entscheidet, ob man Spieler1 oder Spieler2 sein möchte und der erklärende Text dann nochmal erklärt, was das Besondere an diesen beiden Spielern ist.
Was das "1x1 im Kopf" angeht. Ja - ein wenig Schulwissen ist schon hilfreich, denn ein vollständiger Brute-Force Ansatz dauert bei Einfachstimplementierung ( zumindest bei meiner ) ca. 1/2 - 1 Stunde um die Entscheidung zu treffen, wohingegen bei Anwendung von obigem Schulwissen das in akzeptable Größenordnungen kommt.
Beitrag
von black_adept (Top Expert / 4087 / 126 /
940
)
»
Dieser letzte Post von mir in diesem Thread hat sich erledigt.
Beitrag
von black_adept (Top Expert / 4087 / 126 /
940
)
»
Moin allerseits,
ich schulde nach meinem Urlaub ja noch eine "Auflösung" der Aufgabe. Leider hat mich nur eine einzige Einsendung erreicht, so dass ich zukünftig "kompliziertere" Aufgaben wohl nur noch sehr selten stellen werde.
Jetzt zur Aufgabe per se. Mein mitgelieferter "Opponent" war nicht optimal, da er für den Teiler "15" die Lösung nicht zielgerichtet verhindert, aber ansonsten macht er das Leben schon recht schwer.
Wie der Titel schon angedeutet hat, ist es heutzutage möglich ganz ohne mathematisches Hintergrundwissen eine Lösung zu programmieren und einen durch einen Brute-Force-Ansatz alles durchzuprobieren und dann jeweils den besten Zug zu machen.
Hier ist eine Implementierung eines solchen Brute Force Ansatzes, welcher beim Durchprobieren aller Möglichkeiten ( Teiler 1-20 ) ca. 15-30 Minuten braucht um folgendem Ergebnis zu gelangen: Man gewinnt, bei
Das Coding der wesentlichen Routine geht einfach alle Möglichkeiten zur Besetzung einer freien Position durch und ruft sich danach rekursiv selbst auf unter der Annahmen, man sei der andere Spieler, bis alle Positionen besetzt sind. Wenn der Gegner gewinnen kann verliert man und umgekehrt.
Das Coding ist noch etwas optimiert wurden durch die Einsendung von D&P, welche mir den mir bis dato unbekannten "COUNT"-Befehl für String-Operationen gezeigt hat. Man lernt halt nie aus und für mich selber zeigt das wieder, dass alleine das Beschäftigen mit einer Aufgabe ( oder deren Lösungen ) einen weiter bringt.
Vielleicht noch ein kurzer (mathematischer) Hintergrund, warum man in welchen Fällen gewinnen kann und wann nicht. Teile davon wurden von D&P in seiner Einsendung und von jocoder in seinem Beitrag ja schon korrekt angemerkt:
ich schulde nach meinem Urlaub ja noch eine "Auflösung" der Aufgabe. Leider hat mich nur eine einzige Einsendung erreicht, so dass ich zukünftig "kompliziertere" Aufgaben wohl nur noch sehr selten stellen werde.
Jetzt zur Aufgabe per se. Mein mitgelieferter "Opponent" war nicht optimal, da er für den Teiler "15" die Lösung nicht zielgerichtet verhindert, aber ansonsten macht er das Leben schon recht schwer.
Wie der Titel schon angedeutet hat, ist es heutzutage möglich ganz ohne mathematisches Hintergrundwissen eine Lösung zu programmieren und einen durch einen Brute-Force-Ansatz alles durchzuprobieren und dann jeweils den besten Zug zu machen.
Hier ist eine Implementierung eines solchen Brute Force Ansatzes, welcher beim Durchprobieren aller Möglichkeiten ( Teiler 1-20 ) ca. 15-30 Minuten braucht um folgendem Ergebnis zu gelangen: Man gewinnt, bei
- Teiler 1,2,5 und 10 wenn man anfängt,
- Teiler 15 wenn man anfängt, weil der mitgelieferte Opponent nicht optimal spielt. Bei einem optimal spielenden Gegner verliert man.
- Teiler 1,3,7,11 und 13 wenn man nicht anfängt und den letzten Zug macht
Code: Alles auswählen.
CLASS lcl_solution DEFINITION INHERITING FROM lcl_game.
PUBLIC SECTION.
TYPES: BEGIN OF mts_decision.
INCLUDE TYPE mts_set_digit AS set_digit.
TYPES:
i_win TYPE abap_bool,
END OF mts_decision.
METHODS:
i_want_to_be_player_1 REDEFINITION,
set_digit REDEFINITION,
can_win IMPORTING is_current_gamestate TYPE mts_gamestate
iv_divisor TYPE mtv_divisor
iv_win_if_divisible TYPE abap_bool
RETURNING VALUE(rs_decision) TYPE mts_decision.
ENDCLASS.
CLASS lcl_solution IMPLEMENTATION.
METHOD i_want_to_be_player_1.
DATA: ls_gamestate TYPE mts_gamestate.
* ls_gamestate = '00????'.
clear ls_gamestate with mc_gamestate_not_set.
DATA(ls_decision) = can_win( is_current_gamestate = ls_gamestate
iv_divisor = iv_divisor
iv_win_if_divisible = abap_true
).
IF ls_decision-i_win = abap_true.
rv_player = mc_player_1.
ELSE.
rv_player = mc_player_2.
ENDIF.
ENDMETHOD.
METHOD set_digit.
DATA(ls_decision) = can_win( is_current_gamestate = is_gamestate
iv_divisor = iv_divisor
iv_win_if_divisible = abap_true
).
rs_set_digit = ls_decision-set_digit.
ENDMETHOD.
METHOD can_win.
DATA: lv_num TYPE num6,
lv_is_divisible TYPE abap_bool,
ls_test_gamestate TYPE mts_gamestate,
ls_decision TYPE mts_decision.
IF count( val = CONV string( is_current_gamestate ) sub = mc_gamestate_not_set ) > 0. " Noch nciht alle Positionen belegt
* Alle Positionen durchprobieren
DO 6 TIMES. " Alle Positionen durchprobieren
data(lv_position) = sy-index.
ls_test_gamestate = is_current_gamestate.
ASSIGN COMPONENT sy-index OF STRUCTURE ls_test_gamestate TO FIELD-SYMBOL(<lv_digit>).
IF <lv_digit> = mc_gamestate_not_set.
DO 10 TIMES.
<lv_digit> = sy-index - 1. " Alle Ziffern von 0 - 9 an dieser Position durchprobieren
* Keine Win-Options --> Rückgabe des letzten Wertes
rs_decision = VALUE #( set_digit = VALUE #( position = lv_position
digit = <lv_digit>
)
i_win = abap_false ).
* Der Gegner gewinnt, wenn ich nicht gewinne --> switch iv_win_if_divisible
IF iv_win_if_divisible = abap_true.
ls_decision = can_win( is_current_gamestate = ls_test_gamestate
iv_divisor = iv_divisor
iv_win_if_divisible = abap_false
).
ELSE.
ls_decision = can_win( is_current_gamestate = ls_test_gamestate
iv_divisor = iv_divisor
iv_win_if_divisible = abap_true
).
ENDIF.
IF ls_decision-i_win = abap_false. " Wenn der Gegner nicht gewinnen kann gewinne ich
rs_decision-i_win = abap_true. " I win this way
RETURN.
ENDIF.
ENDDO.
ENDIF.
ENDDO.
ELSE.
lv_num = is_current_gamestate.
IF lv_num mod iv_divisor = 0.
lv_is_divisible = abap_true.
ELSE.
lv_is_divisible = abap_false.
ENDIF.
* Wenn teilbar Gewinn genau dann, wenn das auch so in Übergabeparameter steht
IF lv_is_divisible = iv_win_if_divisible.
rs_decision-i_win = abap_true.
ELSE.
rs_decision-i_win = abap_false.
ENDIF.
ENDIF.
ENDMETHOD.
ENDCLASS.
Das Coding ist noch etwas optimiert wurden durch die Einsendung von D&P, welche mir den mir bis dato unbekannten "COUNT"-Befehl für String-Operationen gezeigt hat. Man lernt halt nie aus und für mich selber zeigt das wieder, dass alleine das Beschäftigen mit einer Aufgabe ( oder deren Lösungen ) einen weiter bringt.
Vielleicht noch ein kurzer (mathematischer) Hintergrund, warum man in welchen Fällen gewinnen kann und wann nicht. Teile davon wurden von D&P in seiner Einsendung und von jocoder in seinem Beitrag ja schon korrekt angemerkt:
- Teiler 1: Das ist trivial - hier gewinnt man immer egal wie dumm man sich auch anstellt und egal ob man anfängt oder auch nicht
- Für die Teiler 2,5 und 10 gewinnt man, indem man einfach eine 0 an die letzte Stelle setzt, da die Zahl dann durch 10 und somit auch durch 2 und 5 teilbar ist. Das sollte aus der Schule noch bekannt sein.
- Für die Teiler 3 und 9 ist hoffentlich auch noch bekannt, dass es ausreichend ist, wenn die Quersumme der Zahl durch 3 bzw. 9 teilbar ist. Wenn man also den letzten Zug hat muss man einfach eine der Ziffern auswählen, so dass die Quersumme durch 3 bzw. 9 teilbar ist um zu gewinnen
- Die beiden vorherigen Punkte sagen, dass man bei einem geraden oder durch 5 teilbaren Teiler anfangen muss und dass derjenige gewinnt, der den letzten Zug macht, wenn die Zahl durch 3 teilbar sein muss. Daher kann der Gegner den Gewinn verhindern, wenn der Teiler 2*3, 4*3, 5*3, 6*3 = 6,12,15,18 ist
- Evtl. auch noch Schulwissen: Eine Zahl ist durch 4 teilbar, wenn die beiden letzten Ziffern durch 4 teilbar sind. Da man selber ( 4 ist grade ) ja den 1. Zug machen muss und die letzte Ziffer dann mit einer geraden Zahl belegen muss, ist des dem Gegner stets möglich mit geschickter Wahl der vorletzten Ziffer zu verhindern, dass die beiden letzten Ziffern durch 4 teilbar sind. Somit kann man den Sieg nicht für die Teiler 4,8,12,16 erzwingen.
- Der letzte gerade Teiler der oben noch nicht angesprochen wurde ist die 14 = 2*7. Da man um den Gewinn zu wahren den 1. Zug machen muss, kann der Gegner sich in der letzten Zug machen. Man kann für alle Positionen aufschreiben welche Reste auftauchen können und erkennt dabei, dass modulo 7 alle möglichen Werte durchlaufen werden, sodass der Gegner nur einen derjenigen 6 Werte auswählen muss, der den Sieg verhindert
- Jetzt bleiben nur noch die Teiler 7,11,13,17 und 19 übrig, welche oben noch nicht behandelt wurden. Das entspricht dem Kommentar von jocoder, wo er bemerkt, dass die "größeren Primzahldivisoren" das Hauptproblem sind. Offensichtlich ( siehe Teiler 14 ) ist es für den Gegner ein leichtes sich einen ungünstigen Wert auszusuchen von den 10 möglichen die er für die letzte Ziffer hat, so dass es so ist, dass wir selber den letzten Zug haben müssen um überhaupt noch eine Chance zu haben.
- Teiler 7,11,13: Hier gibt es eine überraschend einfach Strategie mit der man den Gewinn erzielen kann ( und welcher durch den BRUTE FORCE - Lösungsansatz gefunden wird ): Man bilde Päärchen von Ziffern - und zwar 1 und 4, 2 und 5 und 3 und 6. Wenn der Gegner eine Position mit einer beliebigen Ziffer belegt suchen wir uns das zugehörige Päärchen und belegen die zugeordnete Position mit der gleichen Ziffer wie der Gegner. Wenn also der Gegner die 3. Position mit "8" belegt, belegen wir die zugehörige 6. Position auch mit "8". Dann kommt eine Zahl der Form "abcabc" dabei heraus. Und abcabc = abc000 + abc = abc( 1000 + 1 ) = 1001 * abc. Netterweise ist 1001 = 7 * 11 * 13, so dass die resultierende Zahl tatsächlich durch all diese Teiler teilbar ist.
- Das kompizierteste sind die Teiler 17 und 19. Ohne jetzt allzu viel ins Detail zu gehen: Wenn man selber den letzten Zug hat kann man durch die Belegung mit 0-9
10 verschiedene Reste erreichen. Oder viel schlimmer - man kann eben 19-10 = 9 bzw. 17-10 = 7 Reste nicht erreichen oder gleichbedeutend: Es gibt 9 bzw. 7 Reste mit bei denen ich mit der Wahl der letzten Ziffer nicht mehr die rettende 0 erreichen kann. Der Gegner hat in seinem letzten Zug 2 nicht belegte Positionen und somit 20 Möglichkeiten eine dieser "schlimmen" Konstellationen zu erreichen. Und dies kann er, ohne dass ich hier einen Beweis dazu liefern werde wie vor ca. 40 Jahren...
Folgende Benutzer bedankten sich beim Autor black_adept für den Beitrag:
ewx
Seite 1 von 1
Vergleichbare Themen
5
Antw.
Antw.
2719
Views
Views
22
Antw.
Antw.
4315
Views
Views
5
Antw.
Antw.
2364
Views
Views
Knobelaufgabe zum Wochenbeginn ( Mai 2021 )
von black_adept » 11.05.2021 16:21 • Verfasst in SAP - Allgemeines
von black_adept » 11.05.2021 16:21 • Verfasst in SAP - Allgemeines
6
Antw.
Antw.
2846
Views
Views
10
Antw.
Antw.
3842
Views
Views
Knobelaufgabe zum Wochenbeginn ( Juni 2021 )
von black_adept » 21.06.2021 16:29 • Verfasst in SAP - Allgemeines
von black_adept » 21.06.2021 16:29 • Verfasst in SAP - Allgemeines
Frage die ABAP Experten
Über diesen Beitrag
Unterstütze die Community und teile den Beitrag für mehr Leser und Austausch
Aktuelle Forenbeiträge
Newsletter Anmeldung
Keine Beiträge verpassen! Wöchentlich versenden wir lesenwerte Beiträge aus unserer Community.Die letzte Ausgabe findest du hier.