Knobelaufgabe ( November 2021 ) 1983 Hirnschmalz vs. 2021 Rechenpower

Alles Rund um SAP®.
8 Beiträge • Seite 1 von 1
8 Beiträge Seite 1 von 1

Knobelaufgabe ( November 2021 ) 1983 Hirnschmalz vs. 2021 Rechenpower

Beitrag von black_adept (Top Expert / 3701 / 78 / 771 ) »
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.

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.
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
  • 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.
Noch ein Nachtrag zum Titel diese Knobelaufgabe "1983 Hirnschmalz vs. 2021 Rechenpower": Diese Aufgabe kam mir 1983 in meiner Schulzeit unter und mit den damaligen Rechnern wäre kein Brute-Force Ansatz realistisch gewesen , aber ich denke, dass das Problem heutzutage tatsächlich mit reiner Rechenleistung machbar sein sollte. Aber im damaligen Umfeld dieser Aufgabe war diese ganz ohne Rechner zu lösen und es sollte de facto nur gezeigt werden, bei welchen Teilern man sich entscheiden sollte als Spieler 1 oder 2 zu agieren und zu erklären, für welche Teiler ein Sieg überhaupt möglich ist.

Folgende Benutzer bedankten sich beim Autor black_adept für den Beitrag (Insgesamt 3):
ewxThomas R.DeathAndPain

live long and prosper
Stefan Schmöcker

email: stefan@schmoecker.de


Re: Knobelaufgabe ( November 2021 ) 1983 Hirnschmalz vs. 2021 Rechenpower

Beitrag von DeathAndPain (Top Expert / 1603 / 189 / 346 ) »
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.

Re: Knobelaufgabe ( November 2021 ) 1983 Hirnschmalz vs. 2021 Rechenpower

Beitrag von black_adept (Top Expert / 3701 / 78 / 771 ) »
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...
live long and prosper
Stefan Schmöcker

email: stefan@schmoecker.de

Re: Knobelaufgabe ( November 2021 ) 1983 Hirnschmalz vs. 2021 Rechenpower

Beitrag von DeathAndPain (Top Expert / 1603 / 189 / 346 ) »
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.

Re: Knobelaufgabe ( November 2021 ) 1983 Hirnschmalz vs. 2021 Rechenpower

Beitrag von jocoder (Specialist / 286 / 3 / 84 ) »
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:

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

Re: Knobelaufgabe ( November 2021 ) 1983 Hirnschmalz vs. 2021 Rechenpower

Beitrag von black_adept (Top Expert / 3701 / 78 / 771 ) »
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.
live long and prosper
Stefan Schmöcker

email: stefan@schmoecker.de

Re: Knobelaufgabe ( November 2021 ) 1983 Hirnschmalz vs. 2021 Rechenpower

Beitrag von black_adept (Top Expert / 3701 / 78 / 771 ) »
Dieser letzte Post von mir in diesem Thread hat sich erledigt.
live long and prosper
Stefan Schmöcker

email: stefan@schmoecker.de

Re: Knobelaufgabe ( November 2021 ) 1983 Hirnschmalz vs. 2021 Rechenpower

Beitrag von black_adept (Top Expert / 3701 / 78 / 771 ) »
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
  • 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 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:
  • 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

live long and prosper
Stefan Schmöcker

email: stefan@schmoecker.de

Seite 1 von 1

Über diesen Beitrag



ABAP & SAP eBook Flatrate von Espresso Tutorials Sponsorlink
Unterstütze die Community und teile den Beitrag für mehr Leser und Austausch

Aktuelle Forenbeiträge

Texte im Rechnungskopf
Gestern von JHM 7 / 65
CO01 BADI
Gestern von L0w-RiDer 13 / 150
Dynpro Eingabe von Zahl mit Komma
Gestern von ewx 17 / 181
Probleme mit CORRESPONDING itab
vor 2 Tagen von ewx gelöst 7 / 87

Vergleichbare Themen

Knobelaufgabe - Advent 2021
von black_adept » 29.11.2021 12:58
Knobelaufgabe ( Oktober 2021 )
von black_adept » 19.10.2021 12:19
Knobelaufgabe ( August 2021 )
von black_adept » 13.08.2021 14:17
Knobelaufgabe zum Wochenbeginn ( Mai 2021 )
von black_adept » 11.05.2021 16:21
Knobelaufgabe zum Wochenbeginn ( Juni 2021 )
von black_adept » 21.06.2021 16:29