Hilfe für den Amtsschimmel – Die Summerchallenge 2021
4 Beiträge
•
Seite 1 von 1
4 Beiträge
Seite 1 von 1
Beitrag
von black_adept (Top Expert / 4103 / 128 /
945
)
»
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.
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 ).
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.
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 ).
gesponsert ⓘ
Stellenangebote auf ABAPforum.com schalten
kostenfrei für Ausbildungsberufe und Werksstudenten
kostenfrei für Ausbildungsberufe und Werksstudenten
Beitrag
von black_adept (Top Expert / 4103 / 128 /
945
)
»
Regeln und Hinweise,Scoring, Aufgabe, Rahmenprogramm,
Regeln und Hinweise:
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 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.
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.
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.
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 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.
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.Du hast keine ausreichende Berechtigung, um die Dateianhänge dieses Beitrags anzusehen.
Zuletzt geändert von black_adept am 11.07.2021 23:42, insgesamt 1-mal geändert.
Beitrag
von black_adept (Top Expert / 4103 / 128 /
945
)
»
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
Demolösung 2
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.
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.- 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.
Beitrag
von black_adept (Top Expert / 4103 / 128 /
945
)
»
Aktueller Stand der Summer Challenge
Dieses Posting wird jeweils angepasst, wenn sich neue Lösungen einfinden.
Aktuelle Minimalschrittberechnung:
Aktuelle Lösungen:
Mögen die Spiele beginnen.
Dieses Posting wird jeweils angepasst, wenn sich neue Lösungen einfinden.
Aktuelle Minimalschrittberechnung:
- 0, wenn Ausgangszustand = Endzustand
- 1 sonst
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
Mögen die Spiele beginnen.
Seite 1 von 1
Vergleichbare Themen
7
Antw.
Antw.
9887
Views
Views
Knobelaufgabe ( November 2021 ) 1983 Hirnschmalz vs. 2021 Rechenpower
von black_adept » 08.11.2021 18:03 • Verfasst in SAP - Allgemeines
von black_adept » 08.11.2021 18:03 • Verfasst in SAP - Allgemeines
5
Antw.
Antw.
2444
Views
Views
Knobelaufgabe zum Wochenbeginn ( Mai 2021 )
von black_adept » 11.05.2021 16:21 • Verfasst in SAP - Allgemeines
von black_adept » 11.05.2021 16:21 • Verfasst in SAP - Allgemeines
6
Antw.
Antw.
2993
Views
Views
5
Antw.
Antw.
2896
Views
Views
22
Antw.
Antw.
4671
Views
Views
Frage die ABAP Experten
Über diesen Beitrag
black_adept
Unterstütze die Community und teile den Beitrag für mehr Leser und Austausch
Aktuelle Forenbeiträge
Newsletter Anmeldung
Keine Beiträge verpassen! Wöchentlich versenden wir lesenwerte Beiträge aus unserer Community.Die letzte Ausgabe findest du hier.