Find the outcome of a game of War

Question

Find the outcome of a game of War

When I was in elementary school, there was a "Rock-Paper-Scissors"-ish game we'd play during assemblies, when waiting for our teacher, at recess etc. We called it "War". After some searching however, it turns out this is a much simpler variant of the "Shotgun Game" (according to WikiHow). I'm going to call it "War" since the rules are slightly different:

2 people sit across from each other. The goal of the game is to "kill" the other player. Each turn, you can play one of 3 moves:

• Reload: You have a gun that holds a single shot. It must be reloaded before it can be fired each time. Reloading when you already have ammo is legal, but does nothing. A reload was symbolized by tapping your temples with both hands. Each player starts with 0 ammo.

• Guard: The only safe move. If you're shot while guarding, you don't die. Guarding was symbolized by crossing your arms over your chest.

• Fire: Fire your gun. To successfully fire, you must have reloaded since the last shot. If your opponent is reloading, you win. If they also fire, and you both have ammo, it's a draw. If they're guarding, you wasted the ammo. While firing without ammo is a legal move, it does nothing and leaves you vulnerable like reloading. Firing was symbolized by pointing at the other player.

It was played similar to RPS, in that each player simultaneously throws down their choice (we tapped our legs twice in between turns to keep in rhythm with each other, but that's not important to the challenge).

The Challenge:

Your task is to find the outcome of a game of War. It can be a function or full program.

Input

• The option each player chose each turn will be represented by a character/string:

  • r: reload

  • g: guard

  • f: fire

• Input will be a list of pairs, a delimited/undelimited string, or anything else along these lines.

An example input in Python could be [("r", "g"), ("f", "r")], meaning on the first turn the first player reloaded, and the second player guarded. On the second turn, the first player fires, while the second player reloads. Player one wins this game. The same input could optionally be represented as "r g f r", "rgfr", "rg fr" "rg-fr"...

You can assume the following:

• Input will match your chosen format, and that it will only contain valid characters.

• Someone will die within 100 turns.

You cannot however assume that the turns end when someone dies.

Output

A value indicating who won (or, who won first*). You can chose what to output for each scenario, but must account for the following:

• Player 1 wins

• Player 2 wins

• They kill each other (draw)

Each outcome must have a district value, and must always be the same for each scenario.

As an example: you could output 1 when player 1 wins, 2 when player 2 wins, and 0 in the event of a draw. You must then always output 1 when player 1 wins, 2 when player 2 wins, and 0 in the event of a draw.

It can be returned, or printed to the stdout. Trailing whitespace is fine.

Just so it's clear, the only scenario that leads to a draw is if both players fire, and both have ammo.

* Since in this challenge, turns may continue after someone dies, it's possible more than 1 player may win eventually. You need to find who won first according to the input.

Test Cases (assuming 1 when P1 wins, 2 when P2 wins, and 0 for a draw):

"rg fr" => 1 (P1 shot P2 while they were reloading)

"rg ff" => 1 (They both shot, but only P1 had ammo)

"rr ff" => 0 (Both had ammo and shot each other)

"rr ff rr fg" => 0 (Both had ammo and shot each other. Everything after the first win is ignored)

"rr fg rf" => 2 (P2 shot P1 while they were reloading)

"rf gg rr fg rr fr" => 1
    (P2 tried to shoot but didn't have any ammo, then they both guarded, then they both reloaded, then P2 blocked a shot, then they both reloaded again [but P2 still only has 1 ammo!], then P1 shoots P2 while they're reloading.

"rr gf fr rf gg rg ff" => 1
       ^ Player 1 wins here. The rest to the right has no effect on the output

This is code golf, so the smallest number of bytes wins!

Note, as the test cases show, you must handle "dumb" moves. It's perfectly valid for a player to try to shoot when they don't have ammo, or reload 2 turns in a row (and only accumulate a single ammo).

Answer 1

Retina, 36 bytes

s`(?<=r..([^f]..)*)f
!
A`g
G1`!
\w
_

The input format should be linefeed separated pairs, e.g.

rr
fr

Output is !_ is player 1 wins, _! if player 2 wins and !! if there's a draw.

Try it online! (A test suite that uses space-separation for convenience.)

I must have completely overlooked this challenge. I'm sure I would have tried this in Retina earlier otherwise. :)

Explanation

s`(?<=r..([^f]..)*)f
!

We start by marking "valid" shots by turning the first f after each r into !. We do this by matching each f from which can find an r on the same player without crossing over another f. Limiting the search to rs on the same player is easy by always going three characters at a time.

A`g

Now we discard all turns in which someone guarded themselves, because the ending turn cannot be one of those.

G1`!

Now we keep only the first turn which contains an !. If a valid shot happens (and we know that no one guarded) the game ends.

\w
_

Finally, we need to consolidate the string to give consistent outputs, and we simply do this by turning the non-! characters (either r or f) into _.

Answer 2

Python, 139 Bytes

c=d=0
for i in input():
 b=(c&(i=='fr'))-(d&(i=='rf'));p,q=i
 if b|(i=='ff')&c&d:print b;break
 c,d=(p=='r',i!='fg')[c],(q=='r',i!='gf')[d]

Takes input on stdin in the form of a list of 2-character strings (eg. ['rf','rr','rg','ff']). Outputs 1 if player 1 wins, -1 if player 2 wins, and 0 for a draw.

Explanation: First checks if anyone fired a bullet, if so the game ends. Then we determine if the players have either reloaded their guns or wasted their ammo.

This is my first codegolf post :)

Answer 3

JavaScript (ES6), 108 107 93 91 89 85 bytes

Saved 4 bytes with the help of Titus

Takes input as an array of 2-character strings describing the moves played by each player.

b=>b.map(c=>w=w||b&'312'[b=(s='0210231')[m='ffrfgrrggf'.search(c)]|s[m-2]&b,m],w=0)|w

Returns:

• 1 if player 1 wins
• 2 if player 2 wins
• 3 for a draw

---

How it works

We maintain a bitmask b describing who has a loaded bullet:

• bit #0: player 1 has a bullet
• bit #1: player 2 has a bullet

We use the De Bruijn sequence 'ffrfgrrggf' to identify all 9 possible combinations of moves. We use OR and AND bitmasks to update b according to the move combination. We use a 3rd set of bitmasks which are AND'ed with b to determine the winner w. (The only three winning combinations being ff, fr and rf.)

It's worth noting that the OR and AND masks can be stored with the same pattern, shifted by two positions.

 Index in | Combination | Bullet   | Bullet  | Winner
 sequence |             | AND mask | OR mask | mask
----------+-------------+----------+---------+--------
    0     |     ff      |    0     |    0    |   3
    1     |     fr      |    0     |    2    |   1
    2     |     rf      |    0     |    1    |   2
    3     |     fg      |    2     |    0    |   0
    4     |     gr      |    1     |    2    |   0
    5     |     rr      |    0     |    3    |   0
    6     |     rg      |    2     |    1    |   0
    7     |     gg      |    3     |    0    |   0
    8     |     gf      |    1     |    0    |   0

---

Test cases

let f =

b=>b.map(c=>w=w||b&'312'[b=(s='0210231')[m='ffrfgrrggf'.search(c)]|s[m-2]&b,m],w=0)|w

console.log(f(["rg","fr"]));                            // 1
console.log(f(["rg","ff"]));                            // 1
console.log(f(["rr","ff"]));                            // 3
console.log(f(["rr","ff","rr","fg"]));                  // 3
console.log(f(["rr","fg","rf"]));                       // 2
console.log(f(["rf","gg","rr","fg","rr","fr"]));        // 1
console.log(f(["rr","gf","fr","rf","gg","rg","ff"]));   // 1

Answer 4

Perl 6, 71 62 bytes

{&[<=>](|map {m/r[..[r|g]]*.$^f/.to//∞},/[r|f]f/,/.f[r|f]/)}

Regex-based solution.

Takes input as a string in the form "rg fr".
The three possible outputs are the enum values More (player 1 won), Less ( player 2 won), Same (draw) – which turn into those words when printed, or into 1, -1, 0 when coerced to numbers.

Try it online!

How it works

• map { m/r[..[r|g]]*.$^f/.to // ∞ }, /[r|f]f/, /.f[r|f]/

  Performs two regex matches on the input. After interpolation, the two regexes are:

  • r[..[r|g]]*.[r|f]f – Matches the first successful shot by player 2.
  • r[..[r|g]]*..f[r|f] – Matches the first successful shot by player 1.

  In each case, it returns the end position of the match (.to), or infinity if there was no match.

• &[<=>](|   )

  Applies the <=> operator to the two match end positions. It returns a value from the Order enum (More, Less, or Same), depending on whether the first argument is greater, less, or equal to the second.

Answer 5

Haskell, 101 91 87 bytes

n!(c:r)|'g'>c=n:1!r|'g'<c=1:0!r|1<3=2:n!r
_!r=[]
a#b=[x|x@(y,z)<-zip(1!a)$1!b,2>y+z]!!0

Try it online! The infix function # takes two strings representing the actions of each of the two players and returns (0,1) if player 1 wins, (1,0) for player 2 and (0,0) for a draw.

Example usage:

Prelude> "rgrfrf" # "fgrgrr"
(0,1)

Explanation:

The infix function ! translates a sequence of actions 'r' (reload), 'f' (fire) and 'g' (guard) to a sequence of observable actions 0 (actual fire), 1 (no action) and 2 (guard), where a fire action is only counted as actual fire action if a bullet is loaded, and as no action otherwise. To achieve this the first argument n is 0 if a bullet is loaded and 1 if the gun is not loaded. This way each 'f' can simply be replaced with the current n. (n=0 -> loaded -> actual fire -> 0, n=1 -> unloaded -> no action -> 1)

n ! (c:r)                -- n is 0 or 1, c is 'f', 'g' or 'r' and r the rest of the string
    |'g'>c = n : (1 ! r) -- c is smaller 'g', so it must be 'f'. append n to the list
                         --  and set load status to 1 (unloaded)
    |'g'<c = 1 : (0 ! r) -- c is larger 'g', so it must be 'r'. append 1 (no action)
                         --  and set load status to 0 (loaded)
    |1<3   = 2 : (n ! r) -- c must be equal to 'g'. append 2 (guard)
                         --  and leave the load status unchanged
_ ! r = []               -- base case for recursion

The nine resulting possibilities are then

• (0,0): Both players shoot and die, game ends.
• (0,1) or (1,0): One player shoots the other, game ends.
• (0,2) or (2,0): One player shoots but the other guards, game continues.
• (1,1), (1,2), (2,1) or (2,2): No player shoots, game continues.

By design the sum of the game ending options is smaller then 2 and the sum of each game continuing possibility is larger or equal 2. The outcome of the game is then the first tuple with sum less then 2.

a#b=[x|         -- build the list of all x
    x@(y,z) <-  -- where x is an alias for the tuple (y,z) which is drawn from the list
    zip (1!a)   -- of tuples where the first component is from 1!a = eg. [1,2,1,0,1,0] 
        (1!b)   -- and the second from 1!b = eg. [1,2,1,2,1,1]
    , 2 > y+z]  -- and y+z are smaller 2.
    !!0         -- return the first element of this list

Answer 6

Batch, 249 bytes

@echo off
set g=goto gg
set/ax=y=0
:gg
shift&goto %1
:fg
set x=0
%g%
:gf
set y=0
%g%
:rr
set/ax=y=1
%g%
:fr
if %x%==1 exit/b1
:gr
set y=1
%g%
:rf
if %y%==1 exit/b2
:rg
set x=1
%g%
:ff
set/az=3-x-x-y
if %z%==3 %g%
exit/b%z%

Input is in the form of pairs of characters for each turn and outputs by error level (0 = draw, 1 = player 1, 2 = player 2). x and y keep track of whether the player has ammo, so when both fire, the result is 3-x-x-y, unless that is 3, in which case we keep going. On line 5 I abuse Batch's parser - %1 (which is the current move) is substituted before the shift statement executes and removes it, so we still go to the correct label.

Answer 7

Clojure, 168 bytes

#(reduce(fn[[l L r R][a A]](if(and l L)(let[M(fn[r a A](if(and(= a \f)r)[nil(= A \g)][(or(= a \r)r)1]))[r L](M r a A)[R l](M R A a)][l L r R])[l L r R]))[1 1 nil nil]%)

Less golfed (if both persons are alive we use M to update their ammo and enemy's life state, otherwise we return the current status):

(def f (fn[A] (reduce
                (fn [[l1 l2 r1 r2] [a1 a2]]
                  (if (and l1 l2)
                    (let[M (fn [r1 a1 a2]
                             (if (and(= a1 \f)r1)
                               [false (= a2 \g)]        ; we lost the ammo, a2 lives if he was guarding
                               [(or(= a1 \r)r1) true])) ; we might gain or keep ammo, a2 lives no matter what
                         [r1 l2] (M r1 a1 a2)
                         [r2 l1] (M r2 a2 a1)]
                      [l1 l2 r1 r2])
                    [l1 l2 r1 r2]))
                [true true false false] A)))

Example usage (first element tells if Player 1 is alive at the game end, second element tells if Player 2 is alive, 3rd and 4th tell the ammo status which isn't relevant when determining the winner):

(-> (for[[a b s] (partition 3 "rr fg rf fr ")][a b]) f (subvec 0 2))

Update: Well look at that, this loop has identical length! I find reduce version easier to develop as you can easily inspect intermediate states if you use reductions.

#(loop[l 1 L 1 r nil R nil[[a A]& I]%](if(and l L)(let[M(fn[r a A](if(and(= a \f)r)[nil(= A \g)][(or(= a \r)r)1]))[r L](M r a A)[R l](M R A a)](recur l L r R I))[l L]))

Answer 8

PHP, 107 101 90 bytes

using a bit mask $d for the loading status and a DeBruijn sequence for the firing moves.

for(;!$x=$d&strpos(_frff,$m=$argv[++$i]);)$d=$d&g<$m|h<$m|2*($d/2&f<$m[1]|g<$m[1]);echo$x;

takes input as 2-character command line arguments, run with -nr.

1 = Player 1 wins
2 = Player 2 wins
3 = draw

breakdown

for(;!$x=$d&strpos(_frff,       // 1. $x=someone dies, loop while not
    $m=$argv[++$i]          // loop throug moves
);)
    $d=
        $d&g<$m|h<$m            // 2. unload/reload Player 1 = bit 0
    |2*(
        $d/2&f<$m[1]|g<$m[1]    // 3. unload/reload Player 2 = bit 1
    );
echo$x;

• DeBruijn Sequence: fr:position=1=P1 fires; rf=position 2=P2 fires, ff=position 3=both fire
• g<$m <=> f<$m[0] (f<$m is always true, because there is a second character).

Answer 9

Clojure, 180 173 bytes

(fn[t](loop[z nil x nil[[c v]& r]t](let[k #(and %3(= %\f)(not= %2\g))h #(and(not= %\f)(or %2(= %\r)))q(k v c x)w(k c v z)](cond(and q w)0 q 2 w 1 1(recur(h c z)(h v x)r)))))

-7 bytes by changing the function to a full function instead of using a macro. That let me make the inner functions macros, which saves a bit.

This is a very literal solution. I'm kind of mind-locked since I just wrote a full version of the game, and this is basically a greatly stripped down version of the algorithm I used. There are probably many optimizations I could do, but I'm fairly happy with it. See pregolfed code for explanation.

(defn outcome [turns] ; Take input as ["rr" "ff"]
  (loop [p1-ammo? false ; Keep track of if each player has ammo
         p2-ammo? false
         [[p1-move p2-move] & rest-turns] turns] ; Deconstruct the turns out

    (let [killed? (fn [m m2 a] (and a (= m \f) (not= m2 \g))) ; Function that checks if one player killed the other
          has-ammo? (fn [m a] (and (not= m \f) (or a (= m \r)))) ; Function that decides if a player has ammo in the
                                                                 ;  next turn
          p1-killed? (killed? p2-move p1-move p2-ammo?) ; Check if each player was killed.
          p2-killed? (killed? p1-move p2-move p1-ammo?)]

      (cond ; Check who (if any) died. If no one died, recur to next turn.
        (and p1-killed? p2-killed?) 0
        p1-killed? 2
        p2-killed? 1
        :else (recur (has-ammo? p1-move p1-ammo?)
                     (has-ammo? p2-move p2-ammo?)
                     rest-turns)))))

Answer 10

Python, 200 bytes

def war_game(turns):
    turn=0
    player1=True
    player2=True
    ammo1=False
    ammo2=False
    while turn<len(turns):
        if turns[turn][0]=='f' and ammo1==True and turns[turn][1]!='g':
            player2=False
        elif turns[turn][0]=='f' and turns[turn][1]=='g':
            ammo1=False
        elif turns[turn][0]=='r':
            ammo1=True
        if turns[turn][1]=='f' and ammo1==True and turns[turn][0]!='g':
            player1=False
        elif turns[turn][1]=='f' and turns[turn][0]=='g':
            ammo2=False            
        elif turns[turn][1]=='r':
            ammo2=True
        if player2==False or player1==False:
            break
        turn+=1
    if player1==True and player2==False:
        print('Player 1 wins')
        return 1
    elif player1==False and player2==True:
        print('Player 2 wins')
        return 2
    print('Draw')
    return 0