Hilfe für den Amtsschimmel – Die Summerchallenge 2021

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

Hilfe für den Amtsschimmel – Die Summerchallenge 2021

Beitrag von black_adept (Top Expert / 3943 / 105 / 886 ) »
Moin allerseits,
es ist Sommer, die Fußball-EM vorbei und wahrscheinlich werdet ihr demnächst Urlaub haben und euch dort total langweilen. Um dem entgegenzuwirken habe ich die „Summerchallenge“ erstellt, die eure Gehirnzellen auch in so schwierigen Zeiten auf Trab halten sollte.
Diesmal ist der Wettbewerb ein wenig anders, denn es wird Teamwork gefordert sein, da ich annehme und hoffe, dass keiner von euch eine Lösung einfach so aus dem Ärmel schüttelt. Daher sollte erst das Zusammenspiel eurer aller Ideen, Umsetzungen und Verbesserungen bestehender Lösungen euch zum Ziel führen. Und auch das Diskutieren bestimmter Aspekte dieser Aufgabe wird hoffentlich die Lösungsansätze und -qualität beeinflussen. Und es herrscht auch kein Zeitdruck, da manche Ideen und Lösungen einfach "reifen" müssen und man manchmal erst nach ein paar Tagen neue Ideen bekommt.
Nun zur Ausgangslage:
In der Behörde hat sich im Laufe der Jahre folgende Arbeitsweise etabliert.
  • Die Behörde besteht aus n*m Büros, die in einem Rechteck angeordnet sind, wobei jedes Büro mit Türen mit jedem Nachbarbüro verbunden ist.
  • Den Bürgern wird bei Terminvergaben der Raum mitgeteilt, wo sie sich einzufinden haben sowie der Name des Sachbearbeiters, der für sie zuständig ist.
  • Da einige der Büros einfach schöner sind als andere und um keine Ungerechtigkeiten aufkommen zu lassen hat man sich entschieden, dass jedem Mitarbeiter morgens zufällig ein Büro zugewiesen wird, wo er an diesem Tag arbeiten wird.
  • Leider ist erst im Nachhinein aufgefallen, dass die Bürger dadurch zunächst meist in einem falschen Büro landen und sich nun erst auf den Weg zu ihrem Sachbearbeiter machen müssen
  • Weiterhin zeigt die Erfahrung, dass Sachbearbeiter von Büros, in welchen sich kein Bürger befindet in einen Büroschlaf verfallen und ihr Büro dafür abschließen, und dass Sachbearbeiter von Büros, wo sich mehr als ein Bürger aufhält von Panikattacken oder Burnout bedroht sind, so dass auch dies unter allen Umständen zu vermeiden ist.
Eine Beratungsgesellschaft wurde angefordert Lösungsvorschläge zu unterbreiten, wie man diese Situation verbessern könnte, da der Antragsstau inzwischen dazu geführt hat, dass an jedem Termin alle Büros belegt sind. Nach einigen Monaten wurde mitgeteilt, dass es sich hier lediglich um ein Optimierungsproblem handelt und dass es ausreichend ist, wenn am Morgen, nachdem den Sachbearbeitern ihre Büros zugewiesen wurden, ein Plan erstellt wird, wie sich die Bürger von Büro zu Büro bewegen müssen um bei ihrem Sachbearbeiter zu landen. Und das ist jetzt, wo das abapforum ins Spiel kommt.
Ihr seid gefordert solch einen Bewegungsplan zu erstellen, so dass nach möglichst wenigen Zügen jeder Bürger bei „seinem“ Sachbearbeiter angekommen ist, ohne dass die Sachbearbeiter zwischendurch in Tiefschlaf oder Panik verfallen sind ( also dass zu jedem Zeitpunkt in jedem Büro genau ein Bürger ist ).
live long and prosper
Stefan Schmöcker

email: stefan@schmoecker.de

gesponsert
Stellenangebote auf ABAPforum.com schalten
kostenfrei für Ausbildungsberufe und Werksstudenten


Re: Hilfe für den Amtsschimmel – Die Summerchallenge 2021

Beitrag von black_adept (Top Expert / 3943 / 105 / 886 ) »
Regeln und Hinweise,Scoring, Aufgabe, Rahmenprogramm,
Regeln und Hinweise:
  • Diese Aufgabe ist ursprünglich nicht von mir, sondern ich habe sie im Netz gefunden. Ich habe sie allerdings so umformuliert, dass ihr durch googeln hoffentlich nicht darauf stoßen werdet.
  • Wenn jemand diese Aufgabe kennt: Bitte (zunächst) keine Hinweise geben – ich würde mich aber über eine PM freuen, wie ihr darauf gestoßen seid. Ihr könnt auch gerne eine Lösung erstellen und mir via PM mitteilen. Mal sehen wann das Wissen der Massen euch überflügelt.
  • Ich habe wie üblich ein Rahmenprogramm vorgesehen – wenn ihr das mit der Defaultbelegung aufruft ( 10x10, Seed 0 ) gibt es eine vordefinierte Ausgangssituation, für die bekannt ist, dass es Lösungen mit 15 Bewegungsschritten gibt und dass es keinen Bewegunsplan mit weniger Schritten geben kann, der die Aufgabe löst.
Scoring:
Die Bürger benötigen 1 Minute um von einem Büro in ein angrenzendes zu gelangen. Wenn der Bewegungsplan x Schritte umfasst, vergehen also x Minuten, bevor alle Sachbearbeiter dann gleichzeitig die jeweiligen Bürgerbegehren bearbeiten können. Der Amtsleiter weiß – warum auch immer – dass ein optimaler Bewegungsplan Y Schritte benötigt und hieran werden wir gemessen.
Folgendes Scoring gilt, bei minimaler Schrittzahl Y
Scoring.png
Aufgabe:
Ihr könnt an 2 Stellschrauben arbeiten. Eure Lösungen können möglichst wenig Schritte benötigen und ihr könnt unabhängig davon Vorschläge unterbreiten, wie man den Schrittzahl Y abschätzen kann. Letzteres ist der deutlich leichtere Aufgabenteil und wird im Rahmenprogramm von mir angpasst werden - daher wird hier nur eine (einfache) Erläuterung oder erwartet und/oder das Posten einer veränderten Minimalschritterkennungsroutine. Momentan wird Y mit „1“ angesetzt, wenn nicht zufälligerweise tatsächlich schon im Anfangszustand schon alle Bürger zufällig bei „ihrem“ Sachbearbeiter sind. D.h. aber, dass aktuell selbst die optimale Lösung für die Beispielaufgabe mit 15 Schritten 14 Schritte über dem (aktuellen) Minimalziel 1 liegt, so dass diese aktuell nur als „befriedigend“ angesehen wird anstatt korrekt als „Optimal“.
Ziel ist, dass eine Lösung gefunden wird, die für die 10x10 Aufgaben mit Seeds 0-99 im Durchschnitt wenigstens „befriedigend“ ist, aber ich hoffe eigentlich, dass am Ende etwas deutlich besseres vorhanden ist.
Rahmenprogramm:
Ein paar technische Anmerkungen zum Rahmenprogramm, mit dem eure Lösung visualisiert werden kann und mit dem diverse Ausgangssituationen gelöst werden können.
  • Eure Lösung sollte die im Include Klasse lcl_your_solution implementieren, welche von der Klasse lcl erbt, und dort dann die in lcl abstrakte Methode solution redefinieren. Dort könnt ihr euch nach Belieben austoben. Damit das einfach zu posten ist, soll diese Klasse komplett in den Include ZKNOBEL_LONG_2021_SOLUTION ausgelagert werden.
  • Die Räume sind intern als (X/Y) Koordinate angelegt, aber zur Visualisierung wird die X-Koordinate nicht als Zahl sondern, wie aus Excel bekannt, als Buchstabe dargestellt. Desweiteren beginnt die Nummerierung mit 0 statt mit 1. Der Raum ganz oben links ist also intern als (0/0) bekannt, in der Visualisierung hingegen als (A0). Ihr könnt die Visualisierung aber auf dem Selektionsbild auf „00“ umstellen
  • Die Visualisierung ist nur auf Räume ausgelegt, bei denen die Spalte mit nur einem Buchstaben dargestellt werden kann ( also maximal 26x10, falls die Spalte als Buchstabe dargestellt wird ) und auch 26 wird nicht wirklich Freude machen, da dann gescrollt wird. Aber 10x10 ist eigentlich ein gutes Maß für die Aufgabe, welches hinreichend komplex ist aber trotzdem noch halbwegs visualisierbar. Und „brauchbare“ Lösungen kommen dann auch mit 2-stelligen Lösungen daher.
Rahmenprogramm

Code: Alles auswählen.

REPORT zknobel_long_2021 NO STANDARD PAGE HEADING line-size 800.

DATA: gv_step TYPE i." For HIDE

CLASS lcl DEFINITION ABSTRACT.
  PUBLIC SECTION.

* Definitions
    TYPES: mtv_movement_direction TYPE char1.
    CONSTANTS: mc_movement_direction_up    TYPE mtv_movement_direction VALUE 'U',
               mc_movement_direction_down  TYPE mtv_movement_direction VALUE 'D',
               mc_movement_direction_left  TYPE mtv_movement_direction VALUE 'L',
               mc_movement_direction_right TYPE mtv_movement_direction VALUE 'R',

               mc_navigate_previous_col    TYPE i VALUE 30,
               mc_navigate_next_col        TYPE i VALUE 50,

               mc_navigate_width           TYPE i VALUE 10.
* Various type to define the task

* The fields from selection screen
    TYPES: BEGIN OF mts_selections,
             dimension_x             TYPE i,
             dimension_y             TYPE i,
             random_seed_from        TYPE i,
             random_seed_to          TYPE i,
             visualize_even_if_error TYPE flag,
             column_2_alpha          TYPE flag,
           END OF mts_selections.


* Definition of (x,y) coordinates
    TYPES: BEGIN OF mts_coordinate,
             x TYPE i,
             y TYPE i,
           END OF mts_coordinate.
* Complete game state
    TYPES: BEGIN OF mts_state,
             coordinate    TYPE mts_coordinate,
             current_value TYPE mts_coordinate,
             color         TYPE i,
           END OF mts_state,
           mtt_state TYPE SORTED TABLE OF mts_state WITH UNIQUE KEY coordinate.
* Movements ( used to define the transition from one state to the next state )
    TYPES: BEGIN OF mts_movement,
             step       TYPE i,   " MUST start with 1 and for each step there must be at least one movment
             coordinate TYPE mts_coordinate,
             direction  TYPE mtv_movement_direction,
           END OF mts_movement,
           mtt_movements TYPE SORTED TABLE OF mts_movement WITH UNIQUE KEY step coordinate.
* Option to color output
    TYPES: BEGIN OF mts_color_state,
             step        TYPE i,   " MUST start with 1 and for each step there must be at least one movment
             coordinate  TYPE mts_coordinate,
             color       TYPE numc1,
             intensified TYPE numc1, " 0 = off, others = on
           END OF mts_color_state,
           mtt_color_state TYPE SORTED TABLE OF mts_color_state WITH UNIQUE KEY step coordinate.

    CLASS-METHODS:
      init_selscreen,
      top_of_page.

    METHODS:
      main FINAL IMPORTING is_selections TYPE mts_selections.

    CLASS-DATA:
      mo_instance TYPE REF TO lcl.

  PROTECTED SECTION.
    METHODS:
**********************************************************************

***                 Your solution in this method                 *****

**********************************************************************
      solution ABSTRACT IMPORTING it_state       TYPE mtt_state
                                  iv_dim_x       TYPE i
                                  iv_dim_y       TYPE i
                        EXPORTING et_movements   TYPE mtt_movements
                                  et_color_state TYPE mtt_color_state.
**********************************************************************
***                                                              *****
**********************************************************************



  PRIVATE SECTION.
    CONSTANTS: mc_state_entry_width  TYPE i VALUE 9,
               mc_state_entry_height TYPE i VALUE 5.

    TYPES: BEGIN OF mts_state_step,
             step    TYPE i,
             t_state TYPE mtt_state,
           END OF mts_state_step,
           mtt_state_steps TYPE SORTED TABLE OF mts_state_step WITH UNIQUE KEY step.
    TYPES: mtv_out(6)   TYPE p DECIMALS 6,
           mtv_grade(3) TYPE p DECIMALS 1.
    TYPES: BEGIN OF mts_solutions,
             seed              TYPE i,
             result            TYPE icon_d,
             runtime           TYPE mtv_out,
             steps_to_solution TYPE i,
             minimum           TYPE i,
             above_minimum     TYPE i,
             grade             TYPE mtv_grade,
             grade_text        TYPE string,
             errormessage      TYPE string,
           END OF mts_solutions,
           mtt_solutions TYPE STANDARD TABLE OF mts_solutions WITH NON-UNIQUE DEFAULT KEY.

    TYPES: BEGIN OF mts_top_of_page,
             steps   TYPE i,
             runtime TYPE mtv_out,
             grade   TYPE mtv_grade,
           END OF mts_top_of_page.

    METHODS:
      build_start           IMPORTING iv_dimx         TYPE i
                                      iv_dimy         TYPE i
                                      iv_seed         TYPE i
                            RETURNING VALUE(rt_state) TYPE mtt_state,
      get_lower_bound_for_solution IMPORTING it_state              TYPE mtt_state
                                   RETURNING VALUE(rv_lower_bound) TYPE i,
      build_special_start   RETURNING VALUE(rt_state) TYPE mtt_state,
      check_solution        IMPORTING it_state        TYPE mtt_state
                                      it_movements    TYPE mtt_movements
                                      is_selections   TYPE mts_selections
                            EXPORTING ev_errormessage TYPE string
                                      et_state_steps  TYPE mtt_state_steps,
      grade_solution CHANGING cs_solution TYPE mts_solutions,
      visualize_solution    IMPORTING it_state_steps TYPE mtt_state_steps
                                      it_movements   TYPE mtt_movements
                                      it_color_state TYPE mtt_color_state
                                      is_selections  TYPE mts_selections
                                      iv_runtime     TYPE numeric,
      visualize_transition IMPORTING iv_step         TYPE i
                                     is_selections   TYPE mts_selections
                                     it_state_before TYPE mtt_state
                                     it_state_after  TYPE mtt_state
                                     it_movements    TYPE mtt_movements
                                     it_color_state  TYPE mtt_color_state,
      visualize_state       IMPORTING iv_step        TYPE i
                                      is_selections  TYPE mts_selections
                                      it_state       TYPE mtt_state
                                      iv_offset_x    TYPE i
                                      it_movements   TYPE mtt_movements
                                      it_color_state TYPE mtt_color_state OPTIONAL,

      col_i_to_alpha        IMPORTING iv_i            TYPE i
                            RETURNING VALUE(rv_alpha) TYPE char1.

    CLASS-DATA: ms_top_of_page TYPE mts_solutions.
ENDCLASS.


**********************************************************************
**********************************************************************

*              Your solution goes here
INCLUDE zknobel_long_2021_solution.

**********************************************************************
**********************************************************************



SELECTION-SCREEN BEGIN OF BLOCK bl1 WITH FRAME.
PARAMETERS: dimx TYPE i OBLIGATORY DEFAULT 10,
            dimy TYPE i OBLIGATORY DEFAULT 10.
SELECTION-SCREEN END OF BLOCK bl1.

SELECTION-SCREEN BEGIN OF BLOCK bl2 WITH FRAME.
SELECT-OPTIONS: seed FOR sy-tabix NO-EXTENSION.
SELECTION-SCREEN END OF BLOCK bl2.

SELECTION-SCREEN BEGIN OF BLOCK bl3 WITH FRAME.
PARAMETERS: cb_errvi AS CHECKBOX DEFAULT space.
PARAMETERS: cb_alpha AS CHECKBOX DEFAULT 'X'.
SELECTION-SCREEN END OF BLOCK bl3.

INITIALIZATION.
  lcl=>init_selscreen( ).

END-OF-SELECTION.
  NEW lcl_your_solution( )->main( VALUE #( dimension_x             = dimx
                                           dimension_y             = dimy
                                           random_seed_from        = seed-low
                                           random_seed_to          = SWITCH #( seed-option WHEN 'EQ' THEN seed-low ELSE seed-high )
                                           visualize_even_if_error = cb_errvi
                                           column_2_alpha          = cb_alpha
                                         )
                                ).


TOP-OF-PAGE.
  lcl=>mo_instance->top_of_page( ).

AT LINE-SELECTION.
  gv_step = -1.
  READ CURRENT LINE.
  sy-lsind = 0.
  IF gv_step >= 0.
    IF     sy-cucol <= lcl=>mc_navigate_previous_col + 1 + lcl=>mc_navigate_width
       AND sy-cucol >= lcl=>mc_navigate_previous_col + 1.
      IF gv_step > 0.
        SCROLL LIST TO PAGE gv_step.
      ENDIF.
    ELSEIF sy-cucol <= lcl=>mc_navigate_next_col + 1 + lcl=>mc_navigate_width
       AND sy-cucol >= lcl=>mc_navigate_next_col + 1.
      gv_step = gv_step + 2.
      SCROLL LIST TO PAGE gv_step.
    ENDIF.
  ENDIF.




CLASS lcl IMPLEMENTATION.
  METHOD main.

    DATA: lv_at_least_one_error TYPE abap_bool VALUE abap_false,
          lt_state_steps        TYPE mtt_state_steps,
          lv_seed               TYPE i,
          lt_solutions          TYPE mtt_solutions,
          lt_movements          TYPE mtt_movements,
          lt_color_state        TYPE mtt_color_state.

    mo_instance = me.

* For each seed check the solution
    lv_seed = is_selections-random_seed_from.
    WHILE lv_seed <= is_selections-random_seed_to.
      CALL FUNCTION 'SAPGUI_PROGRESS_INDICATOR'
        EXPORTING
*         PERCENTAGE       = 0
          text = lv_seed.

      APPEND VALUE #( seed = lv_seed
                    ) TO lt_solutions ASSIGNING FIELD-SYMBOL(<ls_solution>).
* Build start state
      DATA(lt_original_state) = me->build_start( iv_seed = lv_seed
                                                 iv_dimx = is_selections-dimension_x
                                                 iv_dimy = is_selections-dimension_y ).
      <ls_solution>-minimum = me->get_lower_bound_for_solution( lt_original_state ).
* Ask for solution
      CLEAR:lt_movements,   " In case solution forgets its export parameters
            lt_color_state. " In case solution forgets its export parameters
      GET RUN TIME FIELD DATA(lv_runtime1).
      me->solution( EXPORTING
                      it_state       = lt_original_state
                      iv_dim_x       = is_selections-dimension_x
                      iv_dim_y       = is_selections-dimension_y
                    IMPORTING
                      et_movements   = lt_movements
                      et_color_state = lt_color_state ).
      GET RUN TIME FIELD DATA(lv_runtime2).
      <ls_solution>-runtime = ( lv_runtime2 - lv_runtime1 ) / 1000000. " From microseconds to seconds
* Check solution
      me->check_solution( EXPORTING
                            it_state      = lt_original_state
                            it_movements  = lt_movements
                            is_selections = is_selections
                          IMPORTING
                            ev_errormessage = <ls_solution>-errormessage
                            et_state_steps  = lt_state_steps
                        ).
      IF <ls_solution>-errormessage IS INITIAL.
        <ls_solution>-result = icon_led_green.
      ELSE.
        <ls_solution>-result = icon_led_red.
        MESSAGE <ls_solution>-errormessage TYPE 'S' DISPLAY LIKE 'E'.
        lv_at_least_one_error  = abap_true.
      ENDIF.
      <ls_solution>-steps_to_solution = lines( lt_state_steps ) - 1. " We start with initial state
      <ls_solution>-above_minimum = <ls_solution>-steps_to_solution - <ls_solution>-minimum.
      me->grade_solution( CHANGING cs_solution = <ls_solution> ).
      lv_seed = lv_seed + 1.
    ENDWHILE.



* Visualize solution(s)
    IF lines( lt_solutions ) = 1. " Only 1 seed --> visualize transitions
      IF   lv_at_least_one_error                 = abap_false
        OR is_selections-visualize_even_if_error = 'X'.
        me->ms_top_of_page = <ls_solution>.
        me->visualize_solution( it_state_steps = lt_state_steps
                                it_movements   = lt_movements
                                it_color_state = lt_color_state
                                is_selections  = is_selections
                                iv_runtime     = <ls_solution>-runtime )." yes - it's filled
      ENDIF.
    ELSE.
      TRY.
          cl_salv_table=>factory( IMPORTING
                                    r_salv_table   = DATA(lo_salv)
                                  CHANGING
                                    t_table        = lt_solutions
                                ).
          lo_salv->get_functions( )->set_all( ).
          lo_salv->display( ).
        CATCH cx_root ##CATCH_ALL.
          WRITE:/ |Internal error creating salv output| COLOR 6 INTENSIFIED ON.
      ENDTRY.
    ENDIF.
  ENDMETHOD.

  METHOD get_lower_bound_for_solution.
    rv_lower_bound = 0.
    LOOP AT it_state ASSIGNING FIELD-SYMBOL(<ls_state>).
      IF <ls_state>-coordinate <> <ls_state>-current_value.
        rv_lower_bound = 1.
        RETURN.
      ENDIF.
    ENDLOOP.
  ENDMETHOD.

  METHOD build_start.
    DATA: ls_coordinate TYPE mts_coordinate,
          lt_state      TYPE mtt_state,
          lo_rand       TYPE REF TO cl_abap_random,
          lv_tabix      TYPE sytabix,
          lv_lines      TYPE i.

    IF    iv_seed = 0
      AND iv_dimx = 10
      AND iv_dimy = 10 .
      rt_state = build_special_start( ). " Special setup
    ELSE.
* Fill with value = coordinate -- this is the expected end state
      DO iv_dimx TIMES.
        ls_coordinate-x = sy-index - 1.
        DO iv_dimy TIMES.
          ls_coordinate-y = sy-index - 1.
          INSERT VALUE #( coordinate      = ls_coordinate
                          current_value = ls_coordinate
                        ) INTO TABLE rt_state.
        ENDDO.
      ENDDO.

* Shuffle by grabbing a random coordinate from available coordinates
      lt_state = rt_state.
      lo_rand = cl_abap_random=>create( seed = iv_seed ).
      lv_lines = lines( rt_state ).
      LOOP AT rt_state ASSIGNING FIELD-SYMBOL(<ls_state>).
        lv_tabix = lo_rand->intinrange( low  = 1
                                        high = lv_lines ). " Get random entry in list of available coordinates
        lv_lines = lv_lines - 1.
        READ TABLE lt_state INDEX lv_tabix ASSIGNING FIELD-SYMBOL(<ls_state_source>). " Grab available coordinate
        <ls_state>-current_value = <ls_state_source>-current_value.
        DELETE lt_state INDEX lv_tabix. " coordinate used --> not available any more
      ENDLOOP.
    ENDIF.
  ENDMETHOD.

  METHOD build_special_start.
    DATA: lv_setup TYPE string,
          ls_state LIKE LINE OF rt_state.
* Special setup for those who know where the original exercise comes from
    lv_setup =  |40 87 34 33 75 43 65 35 57 27\n|
             && |05 70 23 88 00 48 08 13 73 01\n|
             && |79 30 94 61 80 62 04 39 28 38\n|
             && |16 85 46 58 66 17 41 60 52 99\n|
             && |72 29 42 11 98 50 53 67 97 84\n|
             && |12 45 56 95 69 19 81 96 21 07\n|
             && |09 68 49 64 82 31 92 44 77 91\n|
             && |55 15 26 54 83 14 37 18 74 71\n|
             && |32 10 93 47 03 78 86 89 24 36\n|
             && |76 25 02 51 59 63 90 20 22 06|.
    SPLIT lv_setup AT |\n| INTO TABLE DATA(lt_setup_rows).
    LOOP AT lt_setup_rows ASSIGNING FIELD-SYMBOL(<lv_setup_row>).
      ls_state-coordinate-y = sy-tabix - 1.
      SPLIT <lv_setup_row> AT ` ` INTO TABLE DATA(lt_setup_cols).
      LOOP AT lt_setup_cols ASSIGNING FIELD-SYMBOL(<lv_setup_col>).
        ls_state-coordinate-x = sy-tabix - 1.
        ls_state-current_value-y = <lv_setup_col>+0(1).
        ls_state-current_value-x = <lv_setup_col>+1(1).
        INSERT ls_state INTO TABLE rt_state.
      ENDLOOP.
    ENDLOOP.
  ENDMETHOD.

  METHOD check_solution.

    DATA: lt_state            TYPE mtt_state,
          lv_step             TYPE i,
          lt_next_state       TYPE mtt_state,
          lt_check_duplicates TYPE HASHED TABLE OF mts_coordinate WITH UNIQUE KEY table_line,
          errorflag           TYPE flag VALUE space.

    CLEAR: ev_errormessage,
           et_state_steps.


    lv_step = 0.
    lt_state = it_state.
    INSERT VALUE #( step    = lv_step
                    t_state = lt_state ) INTO TABLE et_state_steps.

    DO.
      lv_step = lv_step + 1.
      lt_next_state = lt_state.
      LOOP AT it_movements ASSIGNING FIELD-SYMBOL(<ls_movement>) WHERE step = lv_step.
* Find coordinate to be moved
        READ TABLE lt_state INTO DATA(ls_move) WITH TABLE KEY coordinate = <ls_movement>-coordinate.
        IF sy-subrc <> 0.
          ev_errormessage = |Internal error in step { lv_step }:  Coordinate { <ls_movement>-coordinate-x } / { <ls_movement>-coordinate-y } is not allowed|.
          RETURN.
        ENDIF.
* Move to direction
        CASE <ls_movement>-direction.
          WHEN mc_movement_direction_up.
            IF <ls_movement>-coordinate-y <= 0.
              ev_errormessage = |Internal error in step { lv_step }:  Coordinate { <ls_movement>-coordinate-x } / { <ls_movement>-coordinate-y } may not be moved up|.
              RETURN.
            ENDIF.
            ls_move-coordinate-y = ls_move-coordinate-y - 1.

          WHEN mc_movement_direction_down.
            IF <ls_movement>-coordinate-y + 1 >= is_selections-dimension_y.
              ev_errormessage = |Internal error in step { lv_step }:  Coordinate { <ls_movement>-coordinate-x } / { <ls_movement>-coordinate-y } may not be moved down|.
              RETURN.
            ENDIF.
            ls_move-coordinate-y = ls_move-coordinate-y + 1.

          WHEN mc_movement_direction_left.
            IF <ls_movement>-coordinate-x <= 0.
              ev_errormessage = |Internal error in step { lv_step }:  Coordinate { <ls_movement>-coordinate-x } / { <ls_movement>-coordinate-y } may not be moved left|.
              RETURN.
            ENDIF.
            ls_move-coordinate-x = ls_move-coordinate-x - 1.

          WHEN mc_movement_direction_right.
            IF <ls_movement>-coordinate-x + 1 >= is_selections-dimension_x.
              ev_errormessage = |Internal error in step { lv_step }:  Coordinate { <ls_movement>-coordinate-x } / { <ls_movement>-coordinate-y } may not be moved right|.
              RETURN.
            ENDIF.
            ls_move-coordinate-x = ls_move-coordinate-x + 1.

          WHEN OTHERS.
            ev_errormessage = |Internal error in step { lv_step }:  Unknown direction { <ls_movement>-direction }|.
            RETURN.
        ENDCASE.
* Move value to direction
        READ TABLE lt_next_state ASSIGNING FIELD-SYMBOL(<ls_modified>) WITH TABLE KEY coordinate = ls_move-coordinate.
        IF sy-subrc <> 0." Should not happen
          ev_errormessage = |Internal error in step { lv_step }:  Coordinate { ls_move-coordinate-x } / { ls_move-coordinate-y } not found in temporary table|."
          RETURN.
        ENDIF.
        <ls_modified>-current_value = ls_move-current_value.

      ENDLOOP.
      IF sy-subrc <> 0.
        EXIT.
      ENDIF.

*--------------------------------------------------------------------*
* If the movements were not consistent, we now have duplicates in the new state
*--------------------------------------------------------------------*
      CLEAR lt_check_duplicates.
      LOOP AT lt_next_state ASSIGNING FIELD-SYMBOL(<ls_state_check_duplicates>).
        INSERT <ls_state_check_duplicates>-current_value INTO TABLE lt_check_duplicates.
        IF sy-subrc <> 0.
          ev_errormessage = |Internal error in step { lv_step }:  Movements resulted in value { <ls_state_check_duplicates>-current_value-x } / { <ls_state_check_duplicates>-current_value-y } being found in multiple coordinates |."
          errorflag = 'X'. " Do not return but only exit loop and allow step to be shown
          EXIT.
        ENDIF.
      ENDLOOP.

      lt_state = lt_next_state.


      INSERT VALUE #( step    = lv_step
                      t_state = lt_state ) INTO TABLE et_state_steps.
      IF errorflag = 'X'. " Next step not consistent -> exit.
        RETURN.
      ENDIF.
    ENDDO.

*--------------------------------------------------------------------*
* Final check --> everything in right coordinate
*--------------------------------------------------------------------*
    LOOP AT lt_state ASSIGNING FIELD-SYMBOL(<ls_state_final_check>).
      IF <ls_state_final_check>-coordinate <> <ls_state_final_check>-current_value.
        ev_errormessage = |Final state not correct|.
        RETURN.
      ENDIF.
    ENDLOOP.

  ENDMETHOD.

  METHOD grade_solution.

    IF cs_solution-errormessage IS NOT INITIAL.
      cs_solution-grade = 6.
      cs_solution-grade_text = 'Ungenügend'.
    ELSEIF cs_solution-above_minimum <= 0.
      cs_solution-grade = '0.7'.
      cs_solution-grade_text = 'Optimal'.
    ELSEIF cs_solution-above_minimum <= 1.
      cs_solution-grade = 1.
      cs_solution-grade_text = 'Summa cum laude'.
    ELSEIF cs_solution-above_minimum <= 3.
      cs_solution-grade = '1.3'.
      cs_solution-grade_text = 'Sehr gut'.
    ELSEIF cs_solution-above_minimum <= 5.
      cs_solution-grade = '1.7'.
      cs_solution-grade_text = 'Gut'.
    ELSEIF cs_solution-above_minimum <= 7.
      cs_solution-grade = 2.
      cs_solution-grade_text = 'Gut'.
    ELSEIF cs_solution-above_minimum <= 9.
      cs_solution-grade = '2.3'.
      cs_solution-grade_text = 'Gut'.
    ELSEIF cs_solution-above_minimum <= 12.
      cs_solution-grade = '2.7'.
      cs_solution-grade_text = 'Befriedigend'.
    ELSEIF cs_solution-above_minimum <= 15.
      cs_solution-grade = 3.
      cs_solution-grade_text = 'Befriedigend'.
    ELSEIF cs_solution-above_minimum <= 18.
      cs_solution-grade = '3.3'.
      cs_solution-grade_text = 'Befriedigend'.
    ELSEIF cs_solution-above_minimum <= 22.
      cs_solution-grade = '3.7'.
      cs_solution-grade_text = 'Ausreichend'.
    ELSEIF cs_solution-above_minimum <= 26.
      cs_solution-grade = 4.
      cs_solution-grade_text = 'Ausreichend'.
    ELSEIF cs_solution-above_minimum <= 30.
      cs_solution-grade = '4.3'.
      cs_solution-grade_text = 'Ausreichend'.
    ELSEIF cs_solution-above_minimum <= 35.
      cs_solution-grade = '4.7'.
      cs_solution-grade_text = 'Mangelhaft'.
    ELSEIF cs_solution-above_minimum <= 40.
      cs_solution-grade = 5.
      cs_solution-grade_text = 'Mangelhaft'.
    ELSEIF cs_solution-above_minimum <= 45.
      cs_solution-grade = '5.3'.
      cs_solution-grade_text = 'Mangelhaft'.
    ELSE.
      cs_solution-grade = 6.
      cs_solution-grade_text = 'Ungenügend'.
    ENDIF.

  ENDMETHOD.

  METHOD visualize_solution.
    DATA: lt_state_before TYPE mtt_state.
    CALL FUNCTION 'SAPGUI_PROGRESS_INDICATOR'
      EXPORTING
        text = |Output solution|.

    LOOP AT it_state_steps INTO DATA(ls_state_step).
* Display state
      me->visualize_transition( iv_step         = ls_state_step-step
                                it_state_before = lt_state_before
                                it_state_after  = ls_state_step-t_state
                                it_movements    = it_movements
                                it_color_state  = it_color_state
                                is_selections   = is_selections ).
      lt_state_before = ls_state_step-t_state.

    ENDLOOP.

  ENDMETHOD.

  METHOD visualize_transition.

    CONSTANTS: lc_block_distance TYPE i VALUE 20.

    DATA: lv_lines_needed       TYPE i,
          lv_offset_before      TYPE i,
          lv_offset_after       TYPE i,
          lt_movements_for_step TYPE mtt_movements.


    lv_lines_needed = is_selections-dimension_y * mc_state_entry_height.
    lv_offset_before = 4.
    lv_offset_after  = lv_offset_before + is_selections-dimension_x * mc_state_entry_width + lc_block_distance.
    lt_movements_for_step = it_movements.
    DELETE lt_movements_for_step WHERE step <> iv_step.

    WRITE:/ |Step|  COLOR 3 INTENSIFIED OFF,
            iv_step COLOR 3,
            AT mc_navigate_previous_col(10) |< Previous| HOTSPOT ON COLOR 5 INTENSIFIED ON,
            AT mc_navigate_next_col(10)     |Next >|     HOTSPOT ON COLOR 5 INTENSIFIED ON.
    gv_step = iv_step.  " Prepare AT LINE SELECTION
    HIDE gv_step.

    RESERVE lv_lines_needed LINES.
    BACK.
    me->visualize_state( iv_step       = iv_step
                         it_state      = it_state_before
                         iv_offset_x   = lv_offset_before
                         is_selections = is_selections
                         it_movements  = lt_movements_for_step
                         it_color_state  = it_color_state
                       ).
    BACK.
    me->visualize_state( iv_step       = iv_step
                         it_state      = it_state_after
                         iv_offset_x   = lv_offset_after
                         is_selections = is_selections
                         it_movements  = VALUE #( )
                       ).
    BACK.
    SKIP lv_lines_needed.
    ULINE.
    NEW-PAGE.

  ENDMETHOD.

  METHOD visualize_state.

    DATA: lv_current_line   TYPE syindex,
          lv_current_column TYPE syindex,
          lv_data_offset_x  TYPE i,
          lv_data_skip_y    TYPE i,
          ls_state          LIKE LINE OF it_state,
          lv_offset_x       TYPE i,
          lv_direction_char TYPE char1,
          lv_color          TYPE i,
          lv_intensified    TYPE i,
          lv_value_x        TYPE char1.

    IF it_state IS INITIAL.
      RETURN.
    ENDIF.

*--------------------------------------------------------------------*
* Write data
*--------------------------------------------------------------------*
    SKIP.
    DO is_selections-dimension_y TIMES.
      lv_current_line = sy-index - 1.
      lv_data_skip_y = mc_state_entry_height * lv_current_line.
      DO is_selections-dimension_x TIMES.
        lv_current_column = sy-index - 1.
        lv_data_offset_x = iv_offset_x + lv_current_column * mc_state_entry_width.

        READ TABLE it_state INTO ls_state WITH TABLE KEY coordinate = VALUE #( x = lv_current_column
                                                                               y = lv_current_line ).
        IF sy-subrc <> 0.
          ls_state-current_value-x = -1.
        ENDIF.

        BACK.
        SKIP lv_data_skip_y.
* Define color
        lv_color = 0.               " Default standard color
        lv_intensified = 0        . " Default not intensified
        READ TABLE it_color_state ASSIGNING FIELD-SYMBOL(<ls_color_state>) WITH TABLE KEY step       = iv_step
                                                                                          coordinate = ls_state-coordinate.
        IF sy-subrc = 0.
          lv_color       = <ls_color_state>-color.
          lv_intensified = <ls_color_state>-intensified.
        ENDIF.
* top line
        WRITE: AT lv_data_offset_x(4)  sy-uline,
* data
               AT /lv_data_offset_x    sy-vline NO-GAP,
                                       '??'     NO-GAP COLOR 6 INTENSIFIED ON, " In case of error leave the question marks
                                       sy-vline NO-GAP,
* bottom line
               AT /lv_data_offset_x(4) sy-uline.
* Write the value
        IF ls_state-current_value-x <> -1.
          BACK.
          SKIP lv_data_skip_y.
          SKIP.
          lv_offset_x = lv_data_offset_x + 1.
          IF is_selections-column_2_alpha = 'X'.
            lv_value_x = me->col_i_to_alpha( ls_state-current_value-x ).
          ELSE.
            lv_value_x = ls_state-current_value-x.
          ENDIF.
          WRITE: AT lv_offset_x(1) lv_value_x               NO-GAP COLOR = lv_color INTENSIFIED = lv_intensified,
                    (1)            ls_state-current_value-y NO-GAP COLOR = lv_color INTENSIFIED = lv_intensified.
        ENDIF.
      ENDDO.
    ENDDO.

*--------------------------------------------------------------------*
* Write movements
*--------------------------------------------------------------------*
    LOOP AT it_movements ASSIGNING FIELD-SYMBOL(<ls_movement>).
      lv_data_offset_x = iv_offset_x + <ls_movement>-coordinate-x * mc_state_entry_width.
      lv_data_skip_y   = <ls_movement>-coordinate-y * mc_state_entry_height.
      CASE <ls_movement>-direction.
        WHEN mc_movement_direction_up.
          lv_direction_char = '↑'.
          lv_data_skip_y = lv_data_skip_y - 1.
          lv_data_offset_x = lv_data_offset_x + 1.

        WHEN mc_movement_direction_down.
          lv_direction_char = '↓'.
          lv_data_skip_y = lv_data_skip_y + 3.
          lv_data_offset_x = lv_data_offset_x + 2.

        WHEN mc_movement_direction_left.
          lv_direction_char = '←'.
          lv_data_offset_x = lv_data_offset_x - 3.

        WHEN mc_movement_direction_right.
          lv_direction_char = '→'.
          lv_data_skip_y    = lv_data_skip_y + 2.
          lv_data_offset_x  = lv_data_offset_x + 5.

      ENDCASE.

      BACK.
      SKIP lv_data_skip_y.
      WRITE AT lv_data_offset_x(2) lv_direction_char NO-GAP COLOR 7.

    ENDLOOP.

  ENDMETHOD.

  METHOD col_i_to_alpha.
    rv_alpha = sy-abcde+iv_i(1).
  ENDMETHOD.

  METHOD init_selscreen.
    %_dimx_%_app_%-text     = 'Dimension X ( horizontal )'.
    %_dimy_%_app_%-text     = 'Dimension Y ( vertical )'.
    %_seed_%_app_%-text     = 'Random seed'.
    %_cb_errvi_%_app_%-text = 'Show result if error occured'.
    %_cb_alpha_%_app_%-text = 'Use letters for columns'.
  ENDMETHOD.

  METHOD top_of_page.
    DATA: lv_above_par TYPE i.
    IF ms_top_of_page-errormessage IS INITIAL.
      FORMAT COLOR 3 INTENSIFIED OFF.
      WRITE:/ 'Solution needs', (12) ms_top_of_page-steps_to_solution RIGHT-JUSTIFIED INTENSIFIED ON NO-SIGN,
              AT 30 'steps to reach final state where all cells are on the correct coordinates'.
      WRITE:/ 'Solution needs', ms_top_of_page-runtime INTENSIFIED ON,
              AT 30 'seconds to reach this remarkable feat'.
      WRITE:/ 'This is', AT 16(12) ms_top_of_page-above_minimum  RIGHT-JUSTIFIED INTENSIFIED ON NO-SIGN,
              AT 30'steps above the expected minimum of ', (3) ms_top_of_page-minimum INTENSIFIED ON, 'steps',
              'resulting in grade', (3) ms_top_of_page-grade INTENSIFIED ON ,'(', ms_top_of_page-grade_text INTENSIFIED ON,')'.
    ELSE.
      FORMAT COLOR 6 INTENSIFIED OFF.
      WRITE:/ 'Solution needs', (12) ms_top_of_page-steps_to_solution RIGHT-JUSTIFIED INTENSIFIED ON NO-SIGN,
              AT 30 'steps to reach final state '.
      WRITE:/ 'Solution needs', ms_top_of_page-runtime INTENSIFIED ON,
              AT 30 'seconds to reach this'.
      WRITE:/ ms_top_of_page-errormessage COLOR 6 INTENSIFIED ON.
    ENDIF.

    ULINE.
    FORMAT COLOR OFF.

  ENDMETHOD.

ENDCLASS.
P.S. Ich bin auch Änderungen am Rahmenprogramm aufgeschlossen, wenn dadurch das Finden der Lösungen erleichtert wird und/oder wenn zusätzliche Informationen in die Visualisierungen oder Massenanalyse aufgenommen werden können.
Zuletzt geändert von black_adept am 11.07.2021 23:42, insgesamt 1-mal geändert.
live long and prosper
Stefan Schmöcker

email: stefan@schmoecker.de

Re: Hilfe für den Amtsschimmel – Die Summerchallenge 2021

Beitrag von black_adept (Top Expert / 3943 / 105 / 886 ) »
2 Beispiellösungen
Wie üblich biete ich auch (grottenschlechte) Lösungsvorschläge an, die euch ermuntern sollen, bessere zu erarbeiten. Ich werde das Verfahren jeweils nur ganz grob beschreiben. Wenn ihr die Demolösung bei euch installiert und visualisiert wird die Idee dahinter wahrscheinlich klarer als eine lange Erklärung.
Ich habe absichtlich 2 grundverschiedene Ansätze gewählt einfach um zu zeigen, dass viele Wege nach Rom führen. Diese hatten zudem den Vorteil, dass sie sehr einfach zu implementieren waren, was aber auf Kosten der Effizienz ging. Ich glaube zwar, dass ein grundsätzlich anderer Ansatz ist besser als die beiden Demolösungen, aber auch, dass man jede der Demolösungen mit Ideen aus der anderen verbessern kann und dabei schon nicht mehr ungenügende Lösungen findet.
Demolösung 1
  • Es wird zeilenweise, und dort von links nach rechts die dort hingehörende Zelle hinbewegt, ohne schon vorher korrekt abgelegte Zellen nochmals zu berühren
  • Dazu wird die Zelle gesucht und zunächst auf der X-Achse auf die richtige Position geschoben
  • Danach wird die Zelle auf der Y-Achse nach oben geschoben bis sie auf der richtigen Zeile angekommen wird
  • Das wird für alle Zellen wiederholt, bis alle auf ihrem Platz sind.
  • Ohne es jetzt genauer zu erläutern. Die Verschiebung auf der X-Achse benötigt im Schnitt 3,3 Verschiebungen und die Verschiebung auf der Y-Achse bei Anwendung des o.a. Verfahrens durchschnittlich weniger als 2,25, und wenn die vorletzte Zelle an der korrekten Stelle ist, ist es auch die letzte Zelle, so dass ein Bewegungsplan von 3,3 * 2,25 * 99 ~ 730 zu erwarten ist.

Code: Alles auswählen.

CLASS lcl_your_solution DEFINITION INHERITING FROM lcl.
  PROTECTED SECTION.
    METHODS:
      solution REDEFINITION.
  PRIVATE SECTION.
    TYPES: mtt_solution_state TYPE HASHED TABLE OF mts_state WITH UNIQUE KEY coordinate
                              WITH UNIQUE HASHED KEY val COMPONENTS current_value.
    METHODS:
      move_cell IMPORTING is_target_coordinate TYPE mts_coordinate
                          iv_step              TYPE i
                EXPORTING ev_done              TYPE abap_bool
                CHANGING  ct_state             TYPE mtt_solution_state
                          ct_movements         TYPE mtt_movements,
      switch_cells IMPORTING is_coordinate TYPE mts_coordinate
                             iv_direction  TYPE mtv_movement_direction
                             iv_step       TYPE i
                   CHANGING  ct_state      TYPE mtt_solution_state
                             ct_movements  TYPE mtt_movements.
    .
ENDCLASS.

CLASS lcl_your_solution IMPLEMENTATION.
  METHOD solution.

* Abarbeiten der Zielkoordinate zeilenweise von oben nach unten und links nach recht
* Jede Koordinate wird nunächst in die richtig X-coordinate und danach nach oben bis in die richtige Zeile geschoben
* Diese Vorgehensweise garantiert eine Lösung - wenn auch nicht sonderlich toll

    DATA:ls_cell_to_move  TYPE mts_coordinate,
         lt_current_state TYPE mtt_solution_state,
         lv_step          TYPE i,
         lv_done          TYPE abap_bool.

    lt_current_state = it_state. " Mit dem Anfangszustand loslegen
    lv_step = 1.

    DO iv_dim_y TIMES. " Zeilenweise
      ls_cell_to_move-y = sy-index - 1.
      DO iv_dim_x TIMES. " von links nach rechts
        ls_cell_to_move-x = sy-index - 1.
* Jetzt die aktuelle Zelle (x,y) in die gewünschte Position bringen
* Das Verfahren ist so einfach, dass hier keine weiteren Prüfungen nötig sind.
* Aber es ist halt auch grottenschlecht  :oP
        DO.
* zu bewegende Zelle farblich markieren
          READ TABLE lt_current_state ASSIGNING FIELD-SYMBOL(<ls_current>) WITH KEY current_value = ls_cell_to_move.
          INSERT VALUE #( step = lv_step
                          coordinate = <ls_current>-coordinate
                          color      = 3
                          intensified = 1
                        ) INTO TABLE et_color_state.
* Richtung Ziel bewegen, bis die Zelle da steht wo sie hin soll
          me->move_cell( EXPORTING
                           iv_step              = lv_step
                           is_target_coordinate = ls_cell_to_move
                         IMPORTING
                           ev_done              = lv_done
                         CHANGING
                           ct_state     = lt_current_state
                           ct_movements = et_movements
                       ).
* Wenn fertig mit der nächsten Zelle weitermachen
          IF lv_done = 'X'.
            EXIT.
          ENDIF.
          lv_step = lv_step + 1.
        ENDDO.
      ENDDO.
    ENDDO.


  ENDMETHOD.

  METHOD move_cell.
    ev_done = abap_false.  " worst case assumption

* Wo steht die zu bewegende Zelle denn gerade?
    READ TABLE ct_state ASSIGNING FIELD-SYMBOL(<ls_cell>) WITH TABLE KEY val COMPONENTS current_value = is_target_coordinate.
    IF <ls_cell>-coordinate = <ls_cell>-current_value. " Passt schon  :o)
      ev_done = abap_true.
      EXIT.
    ENDIF.

* Zunächst die X-Koordinate anpassen
    IF <ls_cell>-coordinate-x > <ls_cell>-current_value-x.  " Aktuell rechts von Zielposition --> nach links schieben
      me->switch_cells( EXPORTING
                          iv_step       = iv_step
                          is_coordinate = is_target_coordinate
                          iv_direction  = mc_movement_direction_left
                        CHANGING
                          ct_state      = ct_state
                          ct_movements  = ct_movements
                      ).
      RETURN.
    ENDIF.
    IF <ls_cell>-coordinate-x < <ls_cell>-current_value-x.  " Aktuell links von Zielposition --> nach rechts schieben
      me->switch_cells( EXPORTING
                          iv_step       = iv_step
                          is_coordinate = is_target_coordinate
                          iv_direction  = mc_movement_direction_right
                        CHANGING
                          ct_state      = ct_state
                          ct_movements  = ct_movements
                      ).
      RETURN.
    ENDIF.
* Falls X stimmt die Y-Koordinate anpassen ( in unserem Spezialfall immer nach oben )
    me->switch_cells( EXPORTING
                        iv_step       = iv_step
                        is_coordinate = is_target_coordinate
                        iv_direction  = mc_movement_direction_up
                      CHANGING
                        ct_state      = ct_state
                        ct_movements  = ct_movements
                    ).

  ENDMETHOD.


  METHOD switch_cells.

    DATA: lv_opposite_direction TYPE mtv_movement_direction.

    READ TABLE ct_state ASSIGNING FIELD-SYMBOL(<ls_state_cell_to_move>) WITH TABLE KEY val COMPONENTS current_value = is_coordinate.
    ASSERT sy-subrc = 0.
* Nachbarn bestimmen in der angegebenen Richtung
    DATA(ls_neighbour) = <ls_state_cell_to_move>-coordinate.
    CASE iv_direction.
      WHEN mc_movement_direction_up.
        ls_neighbour-y = ls_neighbour-y - 1.
        lv_opposite_direction = mc_movement_direction_down.

*      WHEN mc_movement_direction_down.                          " Not needed in this demo solution
*        ls_neighbour-y = ls_neighbour-y + 1.
*        lv_opposite_direction = mc_movement_direction_up.

      WHEN mc_movement_direction_left.
        ls_neighbour-x = ls_neighbour-x - 1.
        lv_opposite_direction = mc_movement_direction_right.

      WHEN mc_movement_direction_right.
        ls_neighbour-x = ls_neighbour-x + 1.
        lv_opposite_direction = mc_movement_direction_left.

    ENDCASE.

    READ TABLE ct_state ASSIGNING FIELD-SYMBOL(<ls_state_neighbour>) WITH TABLE KEY coordinate = ls_neighbour.
    ASSERT sy-subrc = 0.
* Bewegungen eintragen
    INSERT VALUE #( step       = iv_step
                    coordinate = <ls_state_cell_to_move>-coordinate
                    direction  = iv_direction
                  ) INTO TABLE ct_movements.
    INSERT VALUE #( step       = iv_step
                    coordinate = <ls_state_neighbour>-coordinate
                    direction  = lv_opposite_direction
                  ) INTO TABLE ct_movements.
* Werte der beiden Zellen austauschen ( Ringtausch )
    DATA(lv_save_current_value)           = <ls_state_cell_to_move>-current_value.
    <ls_state_cell_to_move>-current_value = <ls_state_neighbour>-current_value.
    <ls_state_neighbour>-current_value    = lv_save_current_value.

  ENDMETHOD.

ENDCLASS.
Demolösung 2
  • Das m*n-Raster wird durchnummeriert, wobei aufeinanderfolgende Zellen benachbart sind. Die Demolösung geht in der obersten Zeile von links nach rechts, dann am rechten Rand einen Schritt nach unten und dann innerhalb der 2. Zeile von rechts nach links, dann am linken Rand einen Schritt runter usw. Man kann auch eine andere Reihenfolge nehmen wie z.B. spiralförmig von außen nach innen oder völlig verwirrend, solange man halt jede Zelle genau 1x besucht.
  • Wenn man nun diese Anordnung betrachtet kann man erkennen, dass das Problem nun „nur noch“ eine Sortierung dieser Liste ist
  • Es wird jetzt eine Art „Bubblesort“ angewendet, aber da es hier nicht auf die Anzahl der Vertauschungen, sondern die Anzahl der Gesamtschritte geht, wird versucht möglichst viele Vertauschungen innerhalb eines Schritts der Liste auszuführen – eine Art „Schaumsortierung“ also.
  • Dazu wird die Liste pro Schritt von unten nach oben durchlaufen und geschaut, ob der Nachfolger eventuell weiter vorne in der Liste stehen sollte. Wenn ja werden die beiden Zellen vertauscht und danach mit der übernächsten Zelle weitergemacht. Wenn nicht wird direkt bei der nächsten Zelle weitergemacht.
  • So lange der Endzustand nicht erreicht ist, gibt es in der Liste immer mindestens zwei in der Liste benachbarte Zellen, die in der Anordnung in der falschen Reihenfolge stehen
  • Der vorherige Schritt wird so lange wiederholt, bis in einem Schritt keine Zelle mehr vertauscht wurde – dann ist der gewünschte Endzustand erreicht.
  • Auch hier ohne genauere Erläuterung. Der maximale Abstand einer Zelle von ihrem Zielort beträgt beim Weg durch die Liste ist mit mehr als 99%iger Wahrscheinlichkeit mehr als 80 Schritte. Das Verfahren kann auch nicht gewährleisten, dass diese maximal entfernte Zelle in jedem Schritt bewegt wird, so dass ich bei für die Lösungen etwa 100-120 Schritte erwarte. Besser als Demolösung 1, aber immer noch viel zu schlecht für die Behörde…

Code: Alles auswählen.

CLASS lcl_your_solution DEFINITION INHERITING FROM lcl.
  PROTECTED SECTION.
    METHODS:
      solution REDEFINITION.

  PRIVATE SECTION.
    TYPES: BEGIN OF mts_map_coordiante_to_list,
             index               TYPE i,
             coordinate          TYPE mts_coordinate,
             direction_successor TYPE mtv_movement_direction,
           END OF mts_map_coordiante_to_list,
           mtt_map_coordiante_to_list TYPE SORTED TABLE OF mts_map_coordiante_to_list WITH UNIQUE KEY index
                                      WITH UNIQUE HASHED KEY pos COMPONENTS coordinate.

    TYPES: mtt_solution_state TYPE HASHED TABLE OF mts_state WITH UNIQUE KEY coordinate
                              WITH UNIQUE HASHED KEY val COMPONENTS current_value.

    METHODS:
      build_map_state_to_list IMPORTING iv_dim_x TYPE i
                                        iv_dim_y TYPE i,
      my_sort   IMPORTING iv_step           TYPE i
                EXPORTING ev_count_switches TYPE i
                CHANGING  ct_state          TYPE mtt_solution_state
                          ct_movements      TYPE mtt_movements
                          ct_color_state    TYPE mtt_color_state,
      get_index IMPORTING is_coordinate   TYPE mts_coordinate
                RETURNING VALUE(rv_index) TYPE i,
      switch_cells IMPORTING is_coordinate  TYPE mts_coordinate
                             iv_direction   TYPE mtv_movement_direction
                             iv_step        TYPE i
                             iv_color       TYPE i OPTIONAL
                   CHANGING  ct_state       TYPE mtt_solution_state
                             ct_movements   TYPE mtt_movements
                             ct_color_state TYPE mtt_color_state.
    CLASS-DATA: mt_map_state_to_list TYPE mtt_map_coordiante_to_list.
ENDCLASS.

CLASS lcl_your_solution IMPLEMENTATION.

  METHOD solution.
    DATA: lt_state TYPE mtt_solution_state,
          lv_step  TYPE i.

    CLEAR: et_movements,
           et_color_state.

* Idee - Das Raster mit benachbarten Zellen durchnummerieren
*        Danach einen "erweiterten Bubblesort"
*        Die sortierte Liste von unten nach oben durchlaufen.   Wenn die Nachfolgeposition eine kleinere Nummer hat als die aktuelle, wird getaucht.
*        Damit sind diese beiden Zellen blockiert und es wird mit der übernächsten analog verfahren bis zum oberen Ende der Liste
*        Diese Vorgehensweise sorgt dafür, dass pro Durchlauf eine gültige Verschiebemenge erstellt wird und keine weiteren Kollisionsprüfungen sind nötig

* 1. Raster durchnummerieren und Zuordnungstabelle erstellen
    build_map_state_to_list( iv_dim_x = iv_dim_x
                             iv_dim_y = iv_dim_y ).
* 2. Bubblesort, bis keine Vertauschungen mehr nötig sind, dann fertig
    lt_state = it_state. " Auf Tabellentyp mit doppeltem Schlüssel casten.  Außerdem benötigt die Methode "bubblesort" den aktuellen Status als "Changing" Parameter
    DO.
      lv_step = lv_step + 1.
      DATA(lt_last_state) = lt_state.
      me->my_sort( EXPORTING
                     iv_step           = lv_step
                   IMPORTING
                     ev_count_switches = DATA(lv_count_switches)
                   CHANGING
                     ct_state          = lt_state
                     ct_movements      = et_movements
                     ct_color_state    = et_color_state ).
* Keine Tauschaktionen mehr --> fertisch
      IF lv_count_switches = 0.
        RETURN.
      ENDIF.
      IF lt_state = lt_last_state.
        BREAK-POINT.
      ENDIF.


    ENDDO.
  ENDMETHOD.


  METHOD my_sort.
    DATA: lv_index TYPE i VALUE 1,
          lv_next  TYPE i.
    CLEAR ev_count_switches.
    WHILE lv_index < lines( me->mt_map_state_to_list ).
      lv_next = lv_index + 1.
* Mapping lesen für aktuelle Zelle und Nachfolger
      READ TABLE me->mt_map_state_to_list ASSIGNING FIELD-SYMBOL(<ls_map_this>) WITH TABLE KEY index = lv_index.
      ASSERT sy-subrc = 0.
      READ TABLE me->mt_map_state_to_list ASSIGNING FIELD-SYMBOL(<ls_map_next>) WITH TABLE KEY index = lv_next.
      ASSERT sy-subrc = 0.
* Zugehörige Zellen der aktuellen Situation auslesen
      READ TABLE ct_state ASSIGNING FIELD-SYMBOL(<ls_state_this>) WITH TABLE KEY coordinate = <ls_map_this>-coordinate.
      ASSERT sy-subrc = 0.
      READ TABLE ct_state ASSIGNING FIELD-SYMBOL(<ls_state_next>) WITH TABLE KEY coordinate = <ls_map_next>-coordinate.
      ASSERT sy-subrc = 0.
* Schauen, ob die Relation der Zellen korrekt ist , sonst tauschen
      IF get_index( <ls_state_this>-current_value ) > get_index( <ls_state_next>-current_value ).
        me->switch_cells( EXPORTING
                            iv_step        = iv_step
                            is_coordinate  = <ls_map_this>-coordinate
                            iv_direction   = <ls_map_this>-direction_successor
                            iv_color       = 3
                          CHANGING
                            ct_state       = ct_state
                            ct_movements   = ct_movements
                            ct_color_state = ct_color_state
                        ).
        ev_count_switches = ev_count_switches + 1. " Ein Tausch
        lv_index = lv_index + 2. " Diese Zelle und die benachbarte, mit der getauscht wurde nicht mehr anfassen und mit übernächster weitermachen
      ELSE.
        lv_index = lv_index + 1.
      ENDIF.
    ENDWHILE.
  ENDMETHOD.

  METHOD get_index.
    READ TABLE me->mt_map_state_to_list ASSIGNING FIELD-SYMBOL(<ls_map>) WITH TABLE KEY pos COMPONENTS coordinate = is_coordinate.
    ASSERT sy-subrc = 0.
    rv_index = <ls_map>-index.
  ENDMETHOD.


  METHOD build_map_state_to_list.
* 1. Zeile links nach rechts, dann 1 nach unten, 2. Zeile rechts nach links, dann 1 Zeile nach unten,
* Grundsätzlich ungerade Zeilen von links nach rechts, gerade von rechts nach links, bei der letzten Zelle der Zeile 1 Schritt nach unten,
* Damit wird aus dem Rechteck eine sortierte Liste
* Beim Aufbau kann gleich die Nachbarschaftsbeziehung in der Originalliste mit angegeben werden, so dass später diese Informationen direkt
* zum Erstellen der Ausgabeliste mit verwendet werden können
    DATA: lv_index       TYPE i,
          lv_direction_x TYPE i VALUE 1,
          lv_pos_x       TYPE i VALUE 0,
          lv_pos_y       TYPE i VALUE 0.

    CLEAR me->mt_map_state_to_list.
    DO iv_dim_y * iv_dim_x TIMES.
      lv_index = lv_index + 1.
      INSERT VALUE #( index      = lv_index
                      coordinate = VALUE #( x = lv_pos_x
                                            y = lv_pos_y
                                          )
                    ) INTO TABLE me->mt_map_state_to_list ASSIGNING FIELD-SYMBOL(<ls_build_map>).
      lv_pos_x = lv_pos_x + lv_direction_x.
      CASE lv_pos_x.
        WHEN iv_dim_x. " Rechter Rand
          <ls_build_map>-direction_successor = mc_movement_direction_down.
          lv_pos_x = iv_dim_x - 1.
          lv_pos_y = lv_pos_y + 1.
          lv_direction_x = - 1.
        WHEN -1.
          <ls_build_map>-direction_successor = mc_movement_direction_down.
          lv_pos_x = 0.
          lv_pos_y = lv_pos_y + 1.
          lv_direction_x = + 1.

        WHEN OTHERS.
          IF lv_direction_x = 1. " Nachfolger rechts
            <ls_build_map>-direction_successor = mc_movement_direction_right.
          ELSE.
            <ls_build_map>-direction_successor = mc_movement_direction_left.
          ENDIF.
      ENDCASE.
    ENDDO.

  ENDMETHOD.



  METHOD switch_cells.

    DATA: lv_opposite_direction TYPE mtv_movement_direction.

*    READ TABLE ct_state ASSIGNING FIELD-SYMBOL(<ls_state_cell_to_move>) WITH TABLE KEY val COMPONENTS current_value = is_coordinate.
    READ TABLE ct_state ASSIGNING FIELD-SYMBOL(<ls_state_cell_to_move>) WITH TABLE KEY coordinate = is_coordinate.  " anders als in Demolösung 1 bekommen wir die echten Koordinaten geliefert
    ASSERT sy-subrc = 0.
* Nachbarn bestimmen in der angegebenen Richtung
    DATA(ls_neighbour) = <ls_state_cell_to_move>-coordinate.
    CASE iv_direction.
      WHEN mc_movement_direction_up.
        ls_neighbour-y = ls_neighbour-y - 1.
        lv_opposite_direction = mc_movement_direction_down.

      WHEN mc_movement_direction_down.
        ls_neighbour-y = ls_neighbour-y + 1.
        lv_opposite_direction = mc_movement_direction_up.

      WHEN mc_movement_direction_left.
        ls_neighbour-x = ls_neighbour-x - 1.
        lv_opposite_direction = mc_movement_direction_right.

      WHEN mc_movement_direction_right.
        ls_neighbour-x = ls_neighbour-x + 1.
        lv_opposite_direction = mc_movement_direction_left.

    ENDCASE.

    READ TABLE ct_state ASSIGNING FIELD-SYMBOL(<ls_state_neighbour>) WITH TABLE KEY coordinate = ls_neighbour.
    ASSERT sy-subrc = 0.
* Bewegungen eintragen
    INSERT VALUE #( step       = iv_step
                    coordinate = <ls_state_cell_to_move>-coordinate
                    direction  = iv_direction
                  ) INTO TABLE ct_movements.
    INSERT VALUE #( step       = iv_step
                    coordinate = <ls_state_neighbour>-coordinate
                    direction  = lv_opposite_direction
                  ) INTO TABLE ct_movements.
* Werte der beiden Zellen austauschen ( Ringtausch )
    DATA(lv_save_current_value)           = <ls_state_cell_to_move>-current_value.
    <ls_state_cell_to_move>-current_value = <ls_state_neighbour>-current_value.
    <ls_state_neighbour>-current_value    = lv_save_current_value.

    IF iv_color <> 0.
* This is the reason of the switch
      INSERT VALUE #( step        = iv_step
                      coordinate  = <ls_state_cell_to_move>-coordinate
                      color       = iv_color
                      intensified = 1 ) INTO TABLE ct_color_state.
    ENDIF.

  ENDMETHOD.

ENDCLASS.
Hinweis: Auch wenn es keine meiner Demolösungen macht. Wenn die Bürger gerne eine Polonäse durch mehrere Räume machen wollen, weil z.B. alle Bürger in Randräumen im Uhrzeigersinn in den Folgeraum gehen und quasi einen im einen erweiterten Ringtausch machen wollen, ist das durchaus erlaubt. Hauptsache, dass nach einem Schritt kein Büro leer und keins mit mehreren Leuten belegt ist.
live long and prosper
Stefan Schmöcker

email: stefan@schmoecker.de

Re: Hilfe für den Amtsschimmel – Die Summerchallenge 2021

Beitrag von black_adept (Top Expert / 3943 / 105 / 886 ) »
Aktueller Stand der Summer Challenge
Dieses Posting wird jeweils angepasst, wenn sich neue Lösungen einfinden.

Aktuelle Minimalschrittberechnung:
  • 0, wenn Ausgangszustand = Endzustand
  • 1 sonst
Ich hoffe, dass hier ein bald ein besserer Vorschlag eintrudelt, so dass auch für den Sonderfall "Randomseed = 0" eine Minimallösung auch gut oder besser bewertet wird


Aktuelle Lösungen:
  • 11.7.: Demmolösung1: ~ 558 Schritte , nach Abzug der aktuellen Minimalabschätzung ~ 557 Schritte über der Minimallösung, Gesamtnote: 6 - Ungenügend
  • 11.7.: Demmolösung2: ~99 Schritte , nach Abzug der aktuellen Minimalabschätzung ~ 98 Schritte über der Minimallösung, Gesamtnote: 6 - Ungenügend
Hier hoffe ich auf interessante Lösungsvorschläge von euch, mit denen die Bürger wieder die eine oder andere Aufgabe erledigt bekommen.

Mögen die Spiele beginnen.
live long and prosper
Stefan Schmöcker

email: stefan@schmoecker.de

Seite 1 von 1

Vergleichbare Themen

7
Antw.
8074
Views
Knobelaufgabe ( November 2021 ) 1983 Hirnschmalz vs. 2021 Rechenpower
von black_adept » 08.11.2021 18:03 • Verfasst in SAP - Allgemeines
6
Antw.
1459
Views
Knobelaufgabe ( August 2021 )
von black_adept » 13.08.2021 14:17 • Verfasst in SAP - Allgemeines
5
Antw.
1279
Views
Knobelaufgabe ( Oktober 2021 )
von black_adept » 19.10.2021 12:19 • Verfasst in SAP - Allgemeines
5
Antw.
1537
Views
Knobelaufgabe zum Wochenbeginn ( Mai 2021 )
von black_adept » 11.05.2021 16:21 • Verfasst in SAP - Allgemeines
22
Antw.
1778
Views
Knobelaufgabe - Advent 2021
von black_adept » 29.11.2021 12:58 • Verfasst in SAP - Allgemeines

Über diesen Beitrag

black_adept

Unterstütze die Community und teile den Beitrag für mehr Leser und Austausch

Newsletter Anmeldung

Keine Beiträge verpassen! Wöchentlich versenden wir lesenwerte Beiträge aus unserer Community.
Die letzte Ausgabe findest du hier.
Details zum Versandverfahren und zu Ihren Widerrufsmöglichkeiten findest du in unserer Datenschutzerklärung.

Unbeantwortete Forenbeiträge

Zwischensumme Adobe Forms
vor 4 Tagen von Lucyalison 1 / 71
Group Items auf einer Filterbar
vor einer Woche von Bright4.5 1 / 111
tRFC Transaktionen SM58
vor 4 Wochen von A6272 1 / 141