Task Author: Gordon Cormack (CAN)

This was intended to be another very easy task, though slightly more difficult than the one on Day 1 when aiming for a full score.

Turning each possible pair of cards face up in some sequence is guaranteed to obtain all 25 candies. There are 50-choose-2 = 50 * 49 / 2 = 1225 such pairs. Hence, doing 2450 card turns (that is, calls to faceup) suffices. This can be programmed with two nested for-loops, and it solves Subtask 1

But it does not solve Subtask 2, where no more than 100 card turns are allowed. Note that the try-all-pairs solution does not look at what is on the cards that are turned face up. That is, it does not make use of the values returned by faceup. By using these returned values, you can gather information that can be used later to reduce the number of cards turned up.

In particular, taking this to an extreme, you can first turn all cards, in pairs, to discover and record where all the letters are, without caring about turning up equal pairs. In this first round, you might already obtain some candies by accident, but that is irrelevant. In the next round, you know where equal pairs are and you can flip them, in sequence, to obtain all remaining candies.

The first round requires 50 turns (calls to faceup), and the second round another 50 turns. Thus, altogether 100 times a card is turned, and thereby Subtask 2 is solved.

In the second round, you could skip equal pairs that were already identified in the first round. However, that will not improve the worst-case performance and it will complicate the coding.

Here is a Pascal solution that can readily be generalized (the constant and type definitions could be eliminated, but they document the relevant concepts nicely):

type
  TCard = 'A' .. 'Y'; { which letters appear on the cards }
  
const
  NLetters = Ord(High(TCard)) - Ord(Low(TCard)) + 1; { number of letters }
  NCardsPerLetter = 2; { number of cards per letter }
  NCards = NCardsPerLetter * NLetters; { number of cards }
  Unknown = 0; { when card index is unknown }

type
  TIndex = 1 .. NCards; { index of card }
  
procedure play;

  var
    index: array [ TCard, 1 .. NCardsPerLetter ] of Unknown .. NCards;
      { index[lt, k] = index of k-th card with letter lt }
    lt: TCard; { traverses index }
    k: 1 .. NCardsPerLetter; { traverses index }
    i: TIndex; { traverses cards }
    r: TCard; { result of faceup }

  begin

    { initialize index to Unknown }
    for lt := Low(TCard) to High(TCard) do begin
      for k := 1 to NCardsPerLetter do begin
        index[lt, k] := Unknown
      end { for k }
    end { for lt }
  ;
    { first round: don't care about candy; discover where all letter are }
    for i := 1 to NCards do begin
      r := faceup(i)
    ; k := 1
    ; while index[r, k] <> Unknown do k := k + 1
    ; index[r, k] := i
    end { for i }
  ;
    { second round: now collect all (remaining) candies }
    for lt := Low(TCard) to High(TCard) do begin
      for k := 1 to NCardsPerLetter do begin
        r := faceup( index[lt, k] ) { ignore result }
      end { for k }
    end { for lt }

  end;

void play() {
  // letters 'A' to 'Y' are converted to integers 0 to 24
  int index[50][2]; // locations of cards; 0 = unknown
  int lt, k; // traverses index
  int i; // traverses cards
  char r; // result of faceup

  // initialize index
  for (lt = 0; lt < 25; ++lt) {
    for (k = 0; k < 2; ++k) {
      index[lt][k] = 0;
    }
  }
  // first round
  for (i = 1; i <= 50; ++i) {
    r = faceup(i);
    lt = (int)(r) - (int)('A'); // int corresponding to char r
    k = (index[lt][0]) ? 1 : 0;
    index[lt][k] = i;
  }
  // second round
  for (lt = 0; lt < 25; ++lt) {
    faceup( index[lt][0] ); // result ignored
    faceup( index[lt][1] ); // result ignored
  }
}