14
\$\begingroup\$

Inspiration

This question is inspired by the cards Throne Room and King's Court from the popular deck-building card game Dominion.

Throne Room King's Court

As part of one's turn, one plays a sequence of actions. These two particular actions cause the next-played action to repeat two or three times*. Other "generic" actions cause specific game effects, but we won't be interested in the particulars, simply labelling them with letters.

The interesting case is when a Throne Room or King's Court affects another Throne Room of King's Court, causing the doubling or tripling effect to itself be doubled or tripled. Long chains of Throne Rooms, King Courts, and multiplied actions can confuse even experienced Dominion players.

Your goal is to write code that correctly resolves these chains, using as few bytes as possible. I'll describe the program requirements before explaining how the chains resolve in the Dominion rules.

*Technically, you choose the action affected as part of resolving Throne Room or King's Court, but this view is cleaner for this challenge.

Program Requirements

Write a program or named function. It should take in the chain of actions played (STDIN or function input), and output or print the resulting chain of actions from the effects of doubling and tripling. Fewest bytes wins.

Input

A string representing the sequence of actions played. Generic actions are represented by capital letters A through Z. The special doubling action Throne Room is represented by the character 2, and the tripling action King's Court by 3,

The number of characters (actions) will be between 1 and 30, inclusive. You may have the input end in a newline if you wish.

Example input: WA23G3GA

Output

A string of capital lettersA to Z. This should be the sequence of generic actions that results from resolving the doubling and tripling effects, in the order than they happen.

You may have the output end in a newline if you wish. There should be no additional characters otherwise.

Example output: WAGGGGGGAAA.

How doubling and tripling works in Dominion

Here, I'll go through how chains of Throne Rooms (2's) and King's Courts (3's) work as per the Dominion rules.

After you play a 2, the next action to be resolved happens twice. So, if you first play 2, then A, you get A happening twice.

2A -> AA

Similarly,

A2BC -> ABBC
3DE -> DDDE
3N2BC3XY2 -> NNNBBCXXXY

Note in the last example that the final 2 had nothing to double, so it had no effect.

The interesting thing happens when doubling or tripling effects are themselves doubled or tripled. For example,

22AB -> AABB

First, you play 2. Then, you play another 2, which is doubled from the previous 2. As a result, the next two actions are doubled. First, the two copies of A resolve. Then, the copies of B resolve.

Note that A is not quadrupled: after the first copy of 2 acts on the first A, the next copy acts on the next unresolved action, which is B. Without the B, we'd have

22A -> AA

where the second copy of 2 is waiting for the next action to double, but no action comes.

Finally, let's look at a complex example.

223BCDE -> BBBCCCDDE

As before, the first 2 causes the second 2 to be doubled. So, the next two actions will be doubled. The first copy of 2 doubles the next action 3, which must be resolved completely before resolving the next copy of 2. The first copy of 3 triples B, and the second copy triples C. Now, the still-waiting second copy of 2 doubles the next still-unresolved action, which is D. After this, no doubling or tripling effects remain, and the final action E simply happens.

Test cases

These are given as (input,output).

(FY, FY)
(A2BC, ABBC)
(3DE, DDDE)
(3N2BC3XY2, NNNBBCXXXY)
(WA23G3GA, WAGGGGGGAAA)
(32, )
(33RST, RRRSSSTTT)
(2A32B2CDEFG, AABBCCDDEEFG)
(A2A323AB2CD2D2E3ABC, AAAAAABBBCCDDDDEEAAABBBC)
(P22LL3Q2Q22T, PLLLLQQQQQTT)
(322322ABCDEFGHIJKLMN, AABBCCDDEEEFFGGHHIJKLMN)
\$\endgroup\$

4 Answers 4

5
\$\begingroup\$

GolfScript (29 26 bytes)

](1/{\1+(3&@*.23-\1$-@+}/;

Online demo

Dissection

This slightly abuses the loose typing of GolfScript. The stack of how many times to repeat subsequent actions starts out as an array and later turns into a string - but 1+ appends a 1 and (3& pops the first value and correctly puts it in the range 0 to 3 regardless of the type change.

](         # Push an empty array under the input string to serve as rep stack
1/{        # Loop over the input string as a series of 1-char strings
           #   Stack is ... reps ch
           #   where the ... covers zero or more strings which will be output
  \        #   Bring the rep stack to the top
  1+(      #   Push a `1` on the bottom of it to avoid underflow and then pop
  3&       #   Coerce to correct range, because if rep stack is a string then
           #   we just got an ASCII value
  @*       #   Apply repetition to the 1-char string: it's now an n-char string
  .23-     #   Duplicate it and remove chars '2' and '3': this becomes output
  \1$-     #   Get the original copy and remove the output string's chars
           #   So the stack is now ... reps output non-output
           #   where non-output is either an empty string or a string of '2's
           #   or '3's
  @+       #   Push non-output onto the repetition stack
}/         # Loop
;          # Pop whatever's left of the repetition stack
\$\endgroup\$
4
  • \$\begingroup\$ I like your trick of pushing 1's under the stack to treat un-multiplied actions the same as multiplied ones. Could you please explain more about how you juggle the various stacks? In particular, what does \ do to "bring the rep stack to the top"? \$\endgroup\$
    – xnor
    Commented Oct 2, 2014 at 4:06
  • \$\begingroup\$ @xnor, here's the builtins reference. \ swaps the top two items on the stack. \$\endgroup\$ Commented Oct 2, 2014 at 6:46
  • \$\begingroup\$ Thanks, I hadn't understood that each stack element was its own stack; I was imagining a single concatenated stack. \$\endgroup\$
    – xnor
    Commented Oct 2, 2014 at 6:59
  • \$\begingroup\$ @xnor, it's not that each stack item is its own stack; it's that the repetition stack is stored as an array or a string (which is still an array, but treated differently by some builtins). Debug demo which prints the GS stack contents just before the end of the main loop. \$\endgroup\$ Commented Oct 2, 2014 at 7:15
4
\$\begingroup\$

Javascript - 162 152 bytes

Minified:

F=I=>{L=c=>S.length;p=c=>L()?S.shift():d=>{};S=[(x=>/\d/.test(x)?(c,b)=>{for(c=p(),b=x;b--;)c();}:c=>s+=x)(m)for(m of I)];for(s='';L();)p()();return s;}

Expanded:

F = I => {
    L = c => S.length;
    p = c => L() ? S.shift() : d => {};
    S = [ (x => /\d/.test( x ) ?
        (c,b) => {
            for( c = p(), b = x; b--; )
                c();
        } : c =>
            s += x
        )(m) for( m of I ) ];

    for( s = ''; L(); )
        p()();

    return s;
}

I'm guessing the stack-based golf languages will kill on this one, since it's basically an exercise in function stacking. :P

Sample Outputs

F('3N2BC3XY2')
"NNNBBCXXXY"

F('WA23G3GA')
"WAGGGGGGAAA"

F('A2A323AB2CD2D2E3ABC')
"AAAAAABBBCCDDDDEEAAABBBC"

F('322322ABCDEFGHIJKLMN')
"AABBCCDDEEEFFGGHHIJKLMN"

F('FY')
"FY"

F('')
""
\$\endgroup\$
3
  • 1
    \$\begingroup\$ I'm surprised by how exact a parallel your interpretation of cards as functions is. I expected a stack, but not a literal call stack of functions! Is there not a more concise way to though call a function multiple times? Better yet, a variable number of times to handle the 2/3 cases together? \$\endgroup\$
    – xnor
    Commented Oct 2, 2014 at 4:04
  • \$\begingroup\$ @xnor: I thought it was clever. ;) As for your suggestion, your intuition was correct. I've combined the two cases for a savings of 10 bytes. It would ideally be 18 but I've stumbled on what I believe is a bug in Firefox. I should be able to manipulate x directly without first copying it into a variable b scoped to the inner lambda, but Firefox doesn't evaluate the loop condition properly. Specifically, x goes negative and the browser hangs. Try replacing , b = x; b--; with ; x--; and run the input A2A323AB2CD2D2E3ABC. If anyone reading this can figure out why, ... \$\endgroup\$
    – COTO
    Commented Oct 2, 2014 at 11:55
  • \$\begingroup\$ ...I'd be very interested to know. Maybe I'm missing something on how the closures are supposed to work. \$\endgroup\$
    – COTO
    Commented Oct 2, 2014 at 11:56
3
\$\begingroup\$

C, 115 111 bytes

Uses standard input/output.

Saved 4 by using memset and making the stack go in the other direction.

char*i,X[222],*s=X+99;main(){for(gets(i=X);*i;i++)*i<55?s=memset(s-*s,*i-49,*s+1):putchar(*i)**s?--*s,--i:++s;}

Ungolfed

#include <stdio.h>
#include <stdlib.h>
char I[99], S[99], *i = I, *s = S+66;
int n;
int main()
{
    gets(I);
    for(;*i;)
    {
        if(*i < '5') {
            n = *s;
            s[0] = s[1] = s[2] = *i - '1';
            s += n;
            i++;
        } else {
            putchar(*i);
            if(*s)
                --*s;
            else
                --s, ++i;
        }
    }
    return 0;
}
\$\endgroup\$
0
\$\begingroup\$

Python (84)

S='1'*99
R=''
for c in input():q=int(S[0])*c;S=q*(c<'A')+S[1:];R+=q*(c>'3')
print(R)

S is the stack of multipliers (top if front). It's initialized with enough 1's to handle unmultiplied actions.

Depending on whether the current action c is generic or not, we add its multiplied result either to the output R or to the stack of multipliers S.

Everything is represented as a string rather than a list of chars. Because strings are immutable, we unfortunately can't use pop or element assignment on them.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.