Play a game of memory

Question

Playing the game of memory against a machine is highly unfair, because they play almost as good as small children. So let's make the machine play alone, but in a fair way:

• Input: 1...26 pairs of lowercase letters in random order like zz or gttg or abcdefghiabcdefghi. You can trust each letter appears exactly twice and no other characters show up.
• Lowercase letters represent unknown cards, uppercase letters are cards we already saw. Being a fair program, your code will not make knowledge of hidden cards.
• With each turn, you are allowed to uncover a pair of cards (making them uppercase). Start to uncover cards at the left side and continue to the right. If the first card was seen before, pick the match. If not, continue with the next unknown card. If you uncover a pair, remove it.
• Play the best you can: If you know an uppercase pair, uncover it. Otherwise never uncover a card you already know!
• Output: The number of turns you needed to remove all cards. With the given strategy, this is fixed for a given input. Output as binary, ASCII number or length of output string, whatever you like best.
• Goal: The shortest code wins, whatelse!

Let's illustrate this:

afzaxxzf | This is our input
AFzaxxzf | 1st turn, too bad: no pair
AFZAxxzf | 2nd turn was ZA, again no pair, but ...
 FZ xxzf | 3rd turn used to remove the AA pair
 FZ   zf | 4th turn uncovered XX, which can be immediately removed
 F     f | 5th turn started with z, so as second card we can pick the Z we already know
         | With the 6th turn we solved it, so output will be 6

Some more test data:

aa          --> 1
aabb        --> 2
abba        --> 3
ggijkikj    --> 6
qqwweerrtt  --> 5
cbxcxvbaav  --> 8
zyxzwyvxvw  --> 9
tbiaktyvnxcurczlgwmhjluoqpqkgspwsfidfedrzmhyeanxvboj --> 43

Hint:

You don't have to actually play memory, you don't need to actually turn anything uppercase! All that counts is the correct output with the lowest number of code bytes. Feel free to discover a hidden algorithm (but it's not as simple as it could appear on the first sight).

Answer 1

J, 35 bytes

[:#(#@]<.[+2-{.+./@e.~2{.}.)~^:a:&2

Attempt This Online!

A bit chonky as far as J code goes, but imo a nice simplification of the algorithm:

• We imagine a pointer, starting at index 2, pointing into our string:

  ggijkikj
    ^
  01234567
  

• On each iteration, we increment the pointer by 2 as a default

  • But: If the character at the pointer, or the character to the right of the pointer, exists within any of the previous characters (left of the pointer), we only increment by 1.

• We keep incrementing until the pointer exceeds the length of the string

• Our answer is the number of iterations that process took

This approach has the advantage of reducing the number of rules/cases down to just a single rule: increment by 2 or 1, depending on whether the next two characters have been seen. This avoids special-casing the aa case, or distinguishing between "1st character was already seen" and "2nd character was already seen".

Answer 2

Jelly, 10 bytes

ṪfṖƊƤŒɠHĊS

Try it online!

This alternate solution kinda grew alongside the one preserved below, for what it's worth. Ultimately derived from Jonah's description of his J solution, but whatever the actual code does I strongly suspect it isn't this.

   ƊƤ         For every prefix:
Ṫ             Pop the last element
 f            and filter it by membership in
  Ṗ           all but the last remaining (after the pop!) elements.
     Œɠ       Take the lengths of all runs of consecutive equal results,
       H      halve
        Ċ     and ceiling them,
         S    and sum.

Jelly, 16 13 12 11 bytes

ṪeṖƊƤœṣØ0KL

Try it online!

-1 kinda back-porting Neil's Retina solution since I don't actually have a clue why Jonah's pointer starts at 2 to begin with

-1 doing it again

Vague port of Jonah's J algorithm.

   ƊƤ          For each prefix:
Ṫ              Is the last element
 e             also found
Ṫ Ṗ            two or more indices earlier?
     œṣØ0      Split on all non-overlapping occurrences of the substring 0,0,
         K     join on spaces,
          L    and take the length of that result.

Answer 3

Implementing Jonah's smart trick

saved 10 bytes thanks to @DominicVanEssen

R 4.1, 82 bytes

a=\(v,x=1,j=duplicated(v))`if`(sum(j|1)>x,1+a(v,x+2-(v[x]!=v[x+1]&j[x]|j[x+1])),1)

Attempt this online!

---

Previous solution

R 4.1, 141 bytes

b=\(v,x){j=duplicated(v)
ifelse(is.na(v[3]),1,ifelse(j[x],1+b(v[v!=v[x]],x-1),ifelse(j[x+1],2+b(v[v!=v[x+1]],x)-(v[x]==v[x+1]),1+b(v,x+2))))}

Try it online!

Test:

w<-c("t","b","i","a","k","t","y","v","n","x","c","u","r","c","z","l","g","w","m","h","j","l","u","o","q","p","q","k","g","s","p","w","s","f","i","d","f","e","d","r","z","m","h","y","e","a","n","x","v","b","o","j")

b(w,1)

43

Brief explanation:

b is a recursive function with input:

• v a vector of characters
• x the position of the first unknown element of v

It proceeds :

• If v[x] is duplicated we use one move to remove that pair, and we continue with a shorter vector and one less known element.
• If v[x+1] is duplicated we use a second move to remove its pair (but if its twin is v[x]), and we continue with a shorter vector and as many known elements.
• Otherwise we use one move to see two more elements.

Answer 4

JavaScript (Node.js), 57 bytes

a=>a.map(c=>a[n+=!i|a[c]&i!=c,i=i||a[c]?0:c,c]=1,i=n=0)|n

Try it online!

We uncover cards from left to right and, for every next card c, with previous uncovered card in this turn i:

• Count an extra turn (++n) whenever:
  • This is the first card to uncover in this turn (!i): as a new turn;
  • This is the second card to uncover in this turn (i), AND the card just uncovered in the same turn does not equals to the current one (i!=c), AND the card just uncovered had already seen some time before (a[c]): as we need an extra turn to match these two cards;
• Leave this card uncovered for this turn (i=c) whenever:
  • This is the first card to uncover this turn (!i), AND this card is not ever seen before (!a[c]);
• Remember the card as a seen card (a[c]=1)

Answer 5

Retina 0.8.2, 25 20 bytes

(.)(?<!\1..+)
1
11|.

Try it online! Link includes test cases. Explanation: Port of @UnrelatedString's Jelly answer, as I don't see how it works, let alone ports @Jonah's J answer.

(.)(?<!\1..+)
1

Replace the first character of each pair with a 1, but also the second if it's adjacent.

11|.

Subtract the number of pairs of 1s from the length of the string.

Would be 22 bytes as a one-liner: ((.)(?<!\2..+)){1,2}|.

Answer 6

Charcoal, 25 15 bytes

Ｉ⁻Ｌθ№⭆θ№…θ⊖κι00

Try it online! Link is to verbose version of code. Explanation: Port of @UnrelatedString's Jelly answer, although I'm not entirely sure why it works.

   θ            Input string
  Ｌ             Take the length
 ⁻              Subtract
      θ         Input string
     ⭆          Map over characters and join
         θ      Input string
        …       Truncated to length
           κ    Current index
          ⊖     Decremented
       №        Count of
            ι   Current character
    №           Count of
             00 Literal string `00`
Ｉ               Cast to string
                Implicitly print

Previous 25-byte solution:

ＦＬθＭ⊕×⊕﹪ⅈ²№…θ⁻ι﹪ⅈ²§θι→Ｉ⊘ⅈ

Try it online! Link is to verbose version of code. Explanation:

ＦＬθ

Loop over the indices of the input.

Ｍ⊕×⊕﹪ⅈ²№…θ⁻ι﹪ⅈ²§θι→

Calculate how many cards get turned as a result of this card. This is 1 for the card itself and then a possible further 1 or 2 if this card has been seen before depending on whether an even or odd number of cards have been turned so far, except in the odd case where the previous card is the one seen before.

Ｉ⊘ⅈ

Output the number of turns (which is half of the number of cards turned).

Answer 7

JavaScript (Node.js), 54 bytes

a=>a.map(c=>a[i+=a[c]?i%2?i-a[c]?3:1:2:1,c]=i,i=0)|i/2
                 ^    ^   ^          ^
             seen?    |   | Flip the seen
               even-th?   |
  seen early? (abc[a] | bca[a])

Try it online!

Answer 8

Python3, 126 bytes:

def f(a):
 s,c=[],0
 while a:
  if(v:=a.pop(0))in s:s={*s}-{v}
  else:s={*s,*[v,(K:=a.pop(0))]*(v!=K)}
  c+=1
 return c+len(s)

Try it online!

Answer 9

Python 3.8 (pre-release), 101 bytes

This is a golfed version of Ajax1234 answer:

lambda a,s=set():(A:=iter(a),len([s!=(s:=s-{v})or(K:=next(A))!=v and(s:=s|{v,K})for v in A]+[*s]))[1]

Try it online!

This can be 85 bytes if we can take iterator as input, 95 bytes if you can accept "outputs as length of list containing weird random stuff", and 80 bytes if both are allowed:)

85 bytes iterator solution:

lambda A,s=set():len([s!=(s:=s-{v})or(K:=next(A))!=v and(s:=s|{v,K})for v in A]+[*s])

Try it online!

Answer 10

05AB1E, 14 bytes

ηεRõ1ǝćÃ}Åγ;îO

Port of @Unrelated String's Jelly answer, which is based on the explanation of @Jonah's J answer, so make sure to upvote both of those answers as well!
Will see if I can find something shorter using a similar approach, when I have a bit more time later on.

Try it online or verify all test cases.

Explanation:

η        # Get all prefixes of the (implicit) input-string
 ε       # Map over each prefix:
  R      #  Reverse it
   õ1ǝ   #  Remove the second character by inserting an empty string at index 1
      ć  #  Extract head; push remainder-string and first character separately
       Ã #  Keep all occurrences of this extracted head in the remainder-string
 }Åγ     # After the map: run-length encode the list of strings,
         # pushing a list of strings and list of counts of equal adjacent values
    ;    # Halve all counts
     î   # Ceil each
      O  # Sum those together
         # (which is output implicitly as result)

Answer 11

sed,  108  102 bytes

(97 bytes for buggy old GNU sed 4.2.2 by using empty label instead of 1)

I insert an underscore _ as marker up to where cards are known, then do backreference replacements for all possible cases. For each turn, H appends the pattern to the hold space, so in the end I output the number of turns as +:

s/^/_/
t2
:1
H
:2
s/(.)(.*)\1_/\2_/
t1
s/_(.)\1/_/
t1
s/(.)(.*_)\1/\2/
t1
s/_(..)/\1_/
t1
x
s/.\S*/+/g

The t2 at the beginning looks avoidable, but is needed to reset the t trigger after the first replacement.

Try it online!

Answer 12

X86_64/Linux Machine Code, 41 40 39 Bytes

Try it online!

Usage:

$> gcc -DIDEAL_BSS -Wl,-Tbss=0x10000000 -s -static -nostartfiles -nodefaultlibs -nostdlib -Wl,--build-id=none memory.S -o memory
$> echo -n "<Input>" | ./memory; echo $?

Program reads input from stdin (it is sensitive to the exact byte count of input, i.e stray spaces/new lines will change result).

The return value of the program is the number of rounds.

Notes:

• Size is measured in machine code (i.e 39 bytes of PROGBITS; .text, .data, etc...)
• The 39-byte size assumes the above compile command which sets the BSS address at an ideal value. With generic compile commands (no linker inputs), its 41-bytes.

Program:

/* Uncomment below if BSS was setup at 2^20.  */
/* #define IDEAL_BSS */

    .global _start
    .text
_start:
    /* Incoming registers are zero.  */

    movb    $60, %dl
#ifdef IDEAL_BSS
    btsl    %edx, %esi
#else
    movl    $G_mem + 0, %esi
#endif
    /* eax == 0 == SYS_read.  */
    /* edi == 0 == STDIN.  */
    syscall
    leal    (%rsi, %rax), %ecx
    movl    %esi, %eax
play:
    /* Load next character.  */
    lodsb
uncovered_already:
    /* Increment round number (returned at prog exit).  */
    incl    %edi

    /* (rax) is a byte-map of characters we have already seen.  */
    movb    (%rax), %bl
    /* Value zero indicates we haven't seen this character yet.  */
    testb   %bl, %bl
    jnz uncover_pair

    /* We haven't seen this character so update byte-map with its
       position + 1.  */
    movb    %dl, (%rax)

    /* Load assosiated character.  Compare first to check for back-
       to-back.  */
    cmpb    %al, (%rsi)
    lodsb

    /* If we uncovered the same character (by chance) then continue.  */
    je  uncovered_adjacent

    /* If the second uncover was an already uncovered character we
       reloop with it as the initial value.  */
    cmpb    %bl, (%rax)
    jne uncovered_already

    /* Update the second unique character's location then continue.  */
    movb    %dl, (%rax)
uncover_pair:
uncovered_adjacent:
    /* At end of buffer, this will always a final turn.  */
    cmpl    %esi, %ecx
    ja  play
done:
    /* Exit.  */
    xchgl   %eax, %edx
    syscall

    .section .bss
    .align  256
G_mem:  .space 4096

Examples/Tests:

$> for x in aa aabb abba ggijkikj qqwweerrtt cbxcxvbaav zyxzwyvxvw tbiaktyvnxcurczlgwmhjluoqpqkgspwsfidfedrzmhyeanxvboj; do echo -n "${x}" | ./memory; echo "${x} -> $?"; done
aa -> 1
aabb -> 2
abba -> 3
ggijkikj -> 6
qqwweerrtt -> 5
cbxcxvbaav -> 8
zyxzwyvxvw -> 9
tbiaktyvnxcurczlgwmhjluoqpqkgspwsfidfedrzmhyeanxvboj -> 43

Answer 13

C#, 132 bytes

Wanted to keep working on this (ideally finding a smarter algorithm) but never did, so here's where I got up to 3 weeks ago. I just started with a naïve algorithm and golfed it.

string d=args[0],s="";int t=0,i=0;for(;i<d.Length;t++)if(!s.Contains(d[i++])){if(s.Contains(d[i]))t++;s+=d[i-1];s+=d[i++];}return t;

Formatted

string d = args[0], // deck 
s = "";             // seen cards
int t = 0,          // turns taken
i = 0;              // current index
for (; i < d.Length; t++)
    if (!s.Contains(d[i++]))
    {
        if (s.Contains(d[i]))
            t++;
        s += d[i - 1];
        s += d[i++];
    }
return t;