Memory in 2*n Schritten lösen…

Vorhin bin ich in den IT-Nachrichten über die internationale Informatik-Olympiade gestolpert - diese fand dieses Jahr zum 22sten Mal statt; dieses Mal in Ontario/Kanada. Eine Aufgabe hat mich besonders fasziniert: Wie löst man am besten eine Partie Memory?

In der Aufgabe war das Gerüst bereits vorgegeben - man musste nur noch die eigentliche Logik entwickeln. Dabei gab es zwei Teilaufgaben... bei der ersten musste man lediglich so weit kommen, dass alle Karten mindestens einmal aufgedeckt wurden. Um das zu Zählen, wurde für jedes aufgedeckte Paar - auch, wenn es nicht gleichzeitig aufgedeckt wurde - ein Bonbon verteilt. In einer vorgegebenen Zeit musste das selbstgeschriebene Programm alle 25 möglichen Bonbons erhalten.
Die nächste Schwierigkeitsstufe war dann, dass das gesamte Spiel in maximal 100 Kartenumdrehungen (bei 50 Karten im Spiel) gelöst werden musste. Natürlich ist die erste Aufgabe auch dann gelöst, wenn man auch direkt die zweite Aufgabe gelöst hat. 😉

Als ich das laß, kam mir folgende einfache Idee: Wieso nicht erstmal alle Karten umdrehen, die Werte merken und dann einfach nur noch die Paare abgrasen? Dann würde man genau 50 Umdrehungen benötigen, um alle Karten zu kennen und weitere 50 Umdrehungen, um die Karten paarweise aufzudecken. 🙂

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
program PasMemory;

uses
  CardGiver,
  Memory;

var
  Line : String;

begin
  PrepareCards;
  PlayGame;

  WriteLn();
  WriteLn('Moves: ', TurnCounter);
  WriteLn('Over : ', GameOver);
  ReadLn(Line);
end.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
unit CardGiver;

interface

function GameOver : Boolean;
function PrepareCards : Boolean;
function TurnCard(CardID : Byte) : Char;
function TurnCounter : Integer;

implementation

var
  CardStack : array [1..50] of Char;
  FirstCard : Byte;
  TurnCount : Integer;

function GameOver : Boolean;
var
  Index : Byte;
begin
  Result := true;

  for Index := Low(CardStack) to High(CardStack) do
  begin
    if (CardStack[Index] <> #0) then
      Result := false;
  end;
end;

function PrepareCards : Boolean;
const
  CardCount : Byte = 25;
var
  Cards : array [1..25] of Byte;
  Done  : Boolean;
  Index : Byte;
  Temp  : Byte;
begin
  FirstCard := 0;
  TurnCount := 0;

  for Index := Low(Cards) to High(Cards) do
    Cards[Index] := 2;

  for Index := Low(CardStack) to High(CardStack) do
  begin
    Done := false;
    repeat
       Temp := Succ(Random(CardCount));
       if (Cards[Temp] > 0) then
       begin
         Cards[Temp]      := Pred(Cards[Temp]);
         CardStack[Index] := Char(Pred(Temp+65));

         Done := true;
       end;
    until Done;
  end;

  Result := true;
end;

function TurnCard(CardID : Byte) : Char;
begin
  if ((CardID >= Low(CardStack)) and (CardID <= High(CardStack))) then
  begin
    if ((FirstCard = 0) and (CardStack[CardID] <> #0)) then
    begin
      Result    := CardStack[CardID];
      TurnCount := Succ(TurnCount);

      FirstCard := CardID;
    end
    else
    begin
      if ((FirstCard <> 0) and (FirstCard <> CardID) and (CardStack[CardID] <> #0)) then
      begin
        Result    := CardStack[CardID];
        TurnCount := Succ(TurnCount);

        if (CardStack[CardID] = CardStack[FirstCard]) then
        begin
          WriteLn('Pair : ', CardStack[CardID]);

          CardStack[CardID]    := #0;
          CardStack[FirstCard] := #0;
        end;

        FirstCard := 0;
      end
      else
      begin
        Result := #0;
      end;
    end;
  end
  else
    Result := #0;
end;

function TurnCounter : Integer;
begin
  Result := TurnCount;
end;

initialization
  Randomize;

end.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
unit Memory;

interface

function PlayGame : Boolean;

implementation

uses
  CardGiver;

function PlayGame : Boolean;
var
  CardStack : array [1..50] of Char;
  Index     : Byte;
  IndexB    : Byte;
begin
  for Index := 1 to 25 do
  begin
    CardStack[Pred(Index * 2)] := TurnCard(Pred(Index * 2));
    CardStack[(Index * 2)]     := TurnCard((Index * 2));

    if (CardStack[Pred(Index * 2)] = CardStack[(Index * 2)]) then
    begin
      CardStack[Pred(Index * 2)] := #0;
      CardStack[(Index * 2)]     := #0;
    end;
  end;

  Index := 1;
  repeat
    if (CardStack[Index] <> #0) then
    begin
      for IndexB := Succ(Index) to High(CardStack) do
      begin
        if (CardStack[Index] = CardStack[IndexB]) then
        begin
          TurnCard(Index);
          TurnCard(IndexB);

          CardStack[Index]  := #0;
          CardStack[IndexB] := #0;

          Break;
        end;
      end;
    end;

    Index := Succ(Index);
  until (Index > High(CardStack));

  Result := true;
end;

end.

Da ich den vorgegebenen Kartenumdreh-Mechanismus leider nicht zum Laufen gekriegt hatte, habe ich auch diesen einfach nochmal neu implementiert (inklusive automatischem Durchmischen der Karten und einer Überprüfung, ob das Spiel wirklich vorbei ist). Und was soll ich sagen? Meine Idee war genau die richtige - und dank einer kleinen Optimierung (falls ein gleiches Paar beim erstmaligen Aufdecken schon gefunden wird, muss es kein zweites Mal betrachtet werden) braucht man teilweise sogar weniger als 100 Kartenumdrehungen... 😉
Update:
Jan Hendrik Burdinski hatte die Idee geäußert, nicht einfach nur alle Karten einmal aufzudecken und dann abzuräumen, sondern schon beim Aufdecken vorher gefundene Partnerkarten mit zu berücksichtigen. Die Idee hat mir so gut gefallen, dass ich sie auch noch umsetzen wollte:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
unit Memory;

interface

function PlayGame : Boolean;

implementation

uses
  CardGiver;

function PlayGame : Boolean;
var
  CardA     : Char;
  CardB     : Char;
  CardStack : array ['A'..'Z'] of Byte;
  Index     : Char;
  IndexB    : Byte;
begin
  for Index := 'A' to 'Z' do
    CardStack[Index] := 0;

  IndexB := 1;
  while (IndexB <= 50) do
  begin
    CardA := TurnCard(IndexB);
    if (CardA <> #0) then // card is valid
    begin
      if ((CardStack[CardA] >= 1) and (CardStack[CardA] <= 50)) then // card value has been seen before
      begin
        // flip matching card
        TurnCard(CardStack[CardA]);
        CardStack[CardA] := 255;
      end
      else
      begin
        if (CardStack[CardA] = 0) then // card value has not been seen before
        begin
          // save card position
          CardStack[CardA] := IndexB;

          // flip second card
          IndexB := Succ(IndexB);
          if (IndexB <= 50) then
          begin
            CardB := TurnCard(IndexB);

            if (CardA = CardB) then // 1st and 2nd card are a pair
              CardStack[CardB] := 255
            else
            begin
              if ((CardStack[CardB] >= 1) and (CardStack[CardB] <= 50)) then // card value has been seen before
              begin
                // flip matching cards
                TurnCard(IndexB);
                TurnCard(CardStack[CardB]);
                CardStack[CardB] := 255;
              end
              else
              begin
                // save card position
                CardStack[CardB] := IndexB;
              end;
            end;
          end;
        end;
      end;
    end;

    // move to next card
    IndexB := Succ(IndexB);
  end;

  Result := true;
end;

end.

Wie man sieht, ist die Logik etwas umfangreicher, da nun mehrere Schritte gemacht werden müssen:

  • Die erste Karte wird aufgedeckt.
  • Es wird überprüft, ob das Symbol der ersten Karte schonmal gefunden wurde.
  • Falls ja, wird die Partnerkarte aufgedeckt und von vorne begonnen (ein Pärchen wurd gefunden).
  • Falls nein, wird die Position des Symbols der ersten Karte gespeichert und die zweite Karte aufgedeckt.
  • Es wird überprüft, ob beide Karten identisch sind.
  • Falls ja, wird von vorne begonnen (ein Pärchen wurde gefunden).
  • Falls nein, wird geprüft, ob das Symbol der zweiten Karten schonmal gefunden wurde.
  • Falls ja, wird die zweite Karte (nochmal) und ihre Partnerkarten aufgedeckt und von vorne begonnen (ein Pärchen wurde gefunden).
  • Falls nein, wird die Position des Symbols der zweiten Karte gespeichert und von vorne begonnen.

Der Algorithmus ist meiner Meinung ziemlich performant und benötigt im Schnitt ca. 80 Kartenumdrehungen. Des Best-Case ist, dass die Karten paarweise sortiert sind. Der Worst-Case liegt übrigens dann vor, wenn die Karten so angeordnet sind, dass die Paarfindung immer durch das Umdrehen der zweiten Karte der Runde ausgelöst wird. Also z.B. in diesem Fall: "AYBACBDCEDFEGFHGIHJIKJLKMLNMONPOQPRQSRTSUTVUWVXWYX"

Zum Schluss noch etwas Rechtliches:
Der Autor dieses Programms haftet nicht für Schäden an Soft- oder Hardware oder Vermögensschäden, die durch das Benutzen des Programms entstehen, es sei denn, diese beruhen auf einem grob fahrlässigen oder vorsätzlichen Handeln des Autors, seiner Erfüllungsgehilfen oder seiner gesetzlichen Vertreter.
Spielerische Grüße, Kenny

5 Kommentare » Schreibe einen Kommentar

  1. Du kannst einen Speicher von 25 Karten verwenden und nur die ersten Karten jedes Paares speichern. Außerdem brauchst du die jeweils gerade gedrehte Karte.
    Sobald du eine Karte findest, die du bereits gespeichert hast, kannst du das Paar als gefunden markieren. Wenn du also die erste Karte aufdeckst und den Partner bereits kennst, macht es keinen Sinn zunächst die nächste Karte zu Indizieren. Stattdessen kannst du direkt das Paar aufdecken.
    Wenn du in einem Zug mit der zweiten Karte ein Paar entdeckst, deckst du einfach die letzte Karte noch einmal auf und den zugehörigen Partner und verlierst zu deinem Ansatz nichts.
    Auch hier sollte man natürlich zufällig gefundene Paare vorher aussortieren...

        • Ja, da hast du natürlich Recht... hatte das doppelte Aufdecken nicht berücksichtigt... besonders schlimm ist es übrigens, wenn erst die zweite Karte der Runde ein Pärchen offenbart, denn dann müssen beide Karten des Pärchens 2x aufgedeckt werden.

          Habe den Algo jetzt übrigens ebenfalls mal implementiert - sieht ein bisschen komplexer aus, als der einfache, der jede Karte einfach einmal umdreht und danach nach Pärchen sucht... 😀

  2. Eigentlich braucht man immer weniger als 100, da man ja weiß, dass die letzte Karte nur zu der Karte passen kann, die bis jetzt noch keinen Partner hat.
    Wenn bei den letzten beiden nicht aufgedeckten Karten sogar gar keine einzelnen Karten verblieben sind, hat man sogar nur 98 aufgedeckt.

Schreibe einen Kommentar

Um Ihnen beim weiteren Kommentieren auf dieser Webseite die erneute Eingabe Ihrer Daten zu ersparen, wird beim Absenden Ihres Kommentars ein Cookie an Ihren Browser gesendet und von diesem gespeichert. Mit dem Absenden eines Kommentars auf dieser Webseite stimmen Sie der Speicherung und Übertragung dieses Cookies explizit zu.

Pflichtfelder sind mit * markiert.