The card gameWar is interesting in that the final outcome is entirely determined by the initial arrangement of the deck, so long as certain rules are followed for the order in which cards are picked up from the playing field and moved to decks. In this challenge, there will only be 2 players, simplifying things greatly.
The Game
- Each player is dealt a deck of 26 cards.
- Each player places the top card in their deck face-up. The player with the higher-ranking card (
Ace > King > Queen > Jack > 10 > 9 > 8 > 7 > 6 > 5 > 4 > 3 > 2) wins the round, and places their card on top of their opponent's card, flips them over, and adds them to the bottom of their deck (so their winning card is on the bottom of the deck, and the other player's losing card is just above it). This is done until one of the players runs out of cards.- If the cards are of equal rank, then each player places the top 2 cards of their deck face-up on top of their previous card (so that the card that was on top of the deck is the second card in the stack, and the card that was second-from-top is on top). Then, the ranks (of the top card of each stack) are compared again, and the winner places their entire stack on top of the loser's entire stack, turns the stack upside-down, and places it on the bottom of their deck. If there is another tie, more cards are played in the same way, until a winner is chosen or one player runs out of cards.
If at any point one of the players needs to draw a card from their deck, but their deck is empty, they immediately lose the game.
The Challenge
Given two lists of cards in the players' decks, in any convenient format, output a truthy value if Player 1 wins, and a falsey value if Player 2 wins.
For convenience, a 10 card will be represented with aT, and face cards will be abbreviated (Ace -> A, King -> K, Queen -> Q, Jack -> J), so that all cards are one character long. Alternatively, ranks may be represented with decimal integers 2-14 (Jack -> 11, Queen -> 12, King -> 13, Ace -> 14) or hex digits 2-E (10 -> A, Jack -> B, Queen -> C, King -> D, Ace -> E). Since suits don't matter, suit information will not be given.
- You may assume that all games will terminate at some point (though it may take a very long time), and one player will always run out of cards before the other.
- Each player places cards simultaneously, and one card at a time, so there is never any ambiguity about which player ran out of cards first.
Test Cases
The test cases use23456789ABCDE to represent the ranks (in ascending order).
D58B35926B92C7C4C7E8D3DAA2, 8E47C38A2DEA43467EB9566B95 -> False669D9D846D4B3BA52452C2EDEB, E747CA988CC76723935A3B8EA5 -> False5744B95ECDC6D325B28A782A72, 68394D9DA96EBBA8533EE7C6C4 -> True87DB6C7EBC6C8D722389923DC6, E28435DBEBEA543AA47956594A -> False589EAB9DCD43E9EC264A5726A8, 48DC2577BD68AB9335263B7EC4 -> TrueE3698D7C46A739AE5BE2C49286, BB54B7D78954ED526A83C3CDA2 -> True32298B5E785DC394467D5C9CB2, 5ED6AAD93E873EA628B6A4BC47 -> TrueB4AB985B34756C624C92DE5E97, 3EDD5BA2A68397C26CE837AD48 -> False9A6D9A5457BB6ACBC5E8D7D4A9, 73E658CE2C3E289B837422D463 -> True96E64D226BC8B7D6C5974BAE32, 58DC7A8C543E35978AEBA34D29 -> TrueC2978A35E74D7652BA9762C458, 9A9BB332BE8C8DD44CE3DE66A5 -> FalseBEDB44E947693CD284923CEA82, 8CC3B75756255A683A6AB9E7DD -> FalseEEDDCCBBAA8877665544332299, EEDDCCBBAA9988776655443322 -> FalseEEDDCCBBAA9988776655443322, DDCCBBAA9988776655443E3E22 -> TrueReference Implementation
This reference implementation is written in Python 3, and takes input in the same format as the test cases (except separated by a newline instead of a comma and a space).
#!/usr/bin/env python3from collections import dequep1, p2 = [deque(s) for s in (input(),input())]print(''.join(p1))print(''.join(p2))try: while p1 and p2: p1s = [p1.popleft()] p2s = [p2.popleft()] while p1s[-1] == p2s[-1]: p1s.append(p1.popleft()) p2s.append(p2.popleft()) p1s.append(p1.popleft()) p2s.append(p2.popleft()) if p1s[-1] > p2s[-1]: p1.extend(p2s+p1s) else: p2.extend(p1s+p2s)except IndexError: passfinally: print(len(p1) > 0)- 2\$\begingroup\$Related\$\endgroup\$Bassdrop Cumberwubwubwub– Bassdrop Cumberwubwubwub2016-06-06 11:10:39 +00:00CommentedJun 6, 2016 at 11:10
- 1\$\begingroup\$For a deck of cards
1, 2, 3the game has no end as you keep winning your opponent's1. Is that a quirk of having an odd number of cards?\$\endgroup\$Neil– Neil2016-06-06 12:28:05 +00:00CommentedJun 6, 2016 at 12:28 - \$\begingroup\$@Neil What deck of cards has a
1?\$\endgroup\$Suever– Suever2016-06-06 12:41:39 +00:00CommentedJun 6, 2016 at 12:41 - \$\begingroup\$@Suever Sorry, I didn't think too hard, I just picked the first three different numbers that came in to my head. Just pick any three cards where the first is the lowest.\$\endgroup\$Neil– Neil2016-06-06 12:45:40 +00:00CommentedJun 6, 2016 at 12:45
- 1\$\begingroup\$Actually I had confused this with a completely different game. Maybe I should post that game as a challenge!heads off to sandbox\$\endgroup\$Neil– Neil2016-06-07 08:58:37 +00:00CommentedJun 7, 2016 at 8:58
4 Answers4
JavaScript (ES6), 134 bytes
f=([p,...r],[q,...s],t=[],u=[],v)=>!q||p&&(v|p==q?f(r,s,[...t,p],[...u,q],!v):p>q?f([...r,...u,q,...t,p],s):f(r,[...s,...t,p,...u,q]))<div oninput=o.checked=f(p.value,q.value)>Player 1's cards: <input id=p><br>Player 2's cards: <input id=q><br><input id=o type="checkbox"> Player 2 losesReturnundefined if Player 2 wins,true otherwise. Accepts comparable iterators, usually arrays of integers or strings of hex characters. Answer is composed of over 22% of. characters, which I think must be a record for me.
- \$\begingroup\$I don't seem to get the right results when I try this with the test cases. Seejsfiddle.net/xbq5xzco\$\endgroup\$Chuck Morris– Chuck Morris2016-06-07 05:52:12 +00:00CommentedJun 7, 2016 at 5:52
- \$\begingroup\$@ChuckMorris Sorry about that, I'd overlooked one of the rules. Should be fixed now.\$\endgroup\$Neil– Neil2016-06-07 08:51:57 +00:00CommentedJun 7, 2016 at 8:51
- \$\begingroup\$@Mego Try again, I've just updated it.\$\endgroup\$Neil– Neil2016-06-07 08:53:11 +00:00CommentedJun 7, 2016 at 8:53
- \$\begingroup\$Everything seems to check out now.\$\endgroup\$user45941– user459412016-06-07 09:46:09 +00:00CommentedJun 7, 2016 at 9:46
- \$\begingroup\$OK, now I'm impressed!\$\endgroup\$Chuck Morris– Chuck Morris2016-06-07 22:51:15 +00:00CommentedJun 7, 2016 at 22:51
Python, 160 (155?) bytes
f=lambda x,y,z=1:f(*((x,y,z+2),(x[z:]+y[:z]+x[:z],y[z:]),(x[z:],y[z:]+x[:z]+y[:z]))[(x[z-1]>y[z-1])+(x[z-1]<y[z-1])*2])if len(y)>z<len(x)else len(x)>len(y)This solution is theoretically valid, but it require the default python maximum recursion depth to be increased for some of the test cases.
The second solution is 5 bytes longer, but work for all the test cases.
f=lambda x,y,z=1:(f(x,y,z+2)if x[z-1]==y[z-1]else f(x[z:]+y[:z]+x[:z],y[z:])if x[z-1]>y[z-1]else f(x[z:],y[z:]+x[:z]+y[:z]))if len(y)>z<len(x)else len(x)>len(y)Edit: Ungolfed solution 1:
def f(x,y,z=1): if len(y)<z>len(x): return len(x)>len(y) else: return f(*( (x,y,z+2), (x[z:],y[z:]+x[:z]+y[:z]), (x[z:]+y[:z]+x[:z],y[z:]) )[(x[z-1]>y[z-1])+(x[z-1]<y[z-1])*2])
- \$\begingroup\$SinceIronPython will run the first solution fine (the default recursion depth is unlimited), I'm going to say that the first solution is valid.\$\endgroup\$user45941– user459412016-07-07 14:10:31 +00:00CommentedJul 7, 2016 at 14:10
Python, 261 to 265 bytes
def f(a,b): if a==""or b=="":return b=="" p=a[0];q=b[0];a=a[1:];b=b[1:] if p>q:a+=q+p if p<q:b+=p+q while p[-1]==q[-1]: if len(a)<2 or len(b)<2:return len(b)<2 v=a[1];w=b[1];p+=a[0:2];q+=b[0:2];a=a[2:];b=b[2:] if v>w:a+=q+p if v<w:b+=p+q return f(a,b)As posted, this is 265 bytes and it works in both Python 2 and Python 3. You can save 4 bytes in Python 2 by replacing the spaces with a single tab in the while loop.
Haskell, 372
My first Haskell Program
(It's my first functional programming, too...)
w[]_=Falsew _[]=Truew a b=if length j==0 then a>b else w (drop(d$head j)a++fst(head j))(drop(d$head j)b++snd(head j))where j=p a bd(a,b)=quot(maximum[length a,length b])2f (Just a)=ap a b=map f$filter(/=Nothing)[t(a!!x,take(x+1)a,b!!x,take(x+1)b)|x<-[0,2..minimum[length a,length b]-1]]t(a,b,c,d)=if a==c then Nothing else if a>c then Just(d++b,[])else Just([],b++d)I'd love to have tips on how to improve.
Usage:
w "D58B35926B92C7C4C7E8D3DAA2" "8E47C38A2DEA43467EB9566B95"w "669D9D846D4B3BA52452C2EDEB" "E747CA988CC76723935A3B8EA5"w "5744B95ECDC6D325B28A782A72" "68394D9DA96EBBA8533EE7C6C4"w "87DB6C7EBC6C8D722389923DC6" "E28435DBEBEA543AA47956594A"w "589EAB9DCD43E9EC264A5726A8" "48DC2577BD68AB9335263B7EC4"w "E3698D7C46A739AE5BE2C49286" "BB54B7D78954ED526A83C3CDA2"w "32298B5E785DC394467D5C9CB2" "5ED6AAD93E873EA628B6A4BC47"w "B4AB985B34756C624C92DE5E97" "3EDD5BA2A68397C26CE837AD48"w "9A6D9A5457BB6ACBC5E8D7D4A9" "73E658CE2C3E289B837422D463"w "96E64D226BC8B7D6C5974BAE32" "58DC7A8C543E35978AEBA34D29"w "C2978A35E74D7652BA9762C458" "9A9BB332BE8C8DD44CE3DE66A5"w "BEDB44E947693CD284923CEA82" "8CC3B75756255A683A6AB9E7DD"w "EEDDCCBBAA8877665544332299" "EEDDCCBBAA9988776655443322"w "EEDDCCBBAA9988776655443322" "DDCCBBAA9988776655443E3E22"Haskell is quick... :)
real 0m0.039suser 0m0.022ssys 0m0.005s