Will Alice win in this Stick Bomber game?

Background

Stick Bomber is a two-player game I just made up. Initially, some sticks are placed in one or more groups, and the sticks in each group are laid out in a straight line. So a configuration with three groups of 3, 5, and 8 sticks each may look like the following. For conciseness, we can call it a (3,5,8) configuration.

|||  |||||  ||||||||


Let's call the two players Alice (the one who plays first) and Bob (second). At each turn, the player selects one stick anywhere on the board, and removes that stick along with the ones directly adjacent to it (left or right within the group).

For example, if Alice chooses the 3rd stick in the 5-stick group, the board becomes (3,1,1,8) (sticks removed in the middle split the group into two):

|||  |xXx|  ||||||||


Then, if Bob chooses the first stick in the 8-stick group, the board becomes (3,1,1,6):

|||  |  |  Xx||||||


Then if Alice chooses the 2nd stick in the 3-stick group, that group is entirely removed and the state becomes (1,1,6):

xXx  |  |  ||||||


The one who eliminates all the sticks from the board wins the game.

For single-pile initial states, Alice can win in 1 turn for (1) through (3), and (5) in three turns by removing the middle. However, Alice cannot win for (4) because any move will result in a (1) or (2), where Bob can win in 1 turn.

Challenge

Given an initial configuration of Stick Bomber, determine whether Alice can win the game. Assume that both Alice and Bob play perfectly, i.e. each player always plays a winning move whenever possible.

The input is guaranteed to be a non-empty sequence of positive integers, but it is not guaranteed to be sorted. For output, you can choose to

1. output truthy/falsy using your language's convention (swapping is allowed), or
2. use two distinct, fixed values to represent true (affirmative) or false (negative) respectively.

Standard rules apply. The shortest code in bytes wins.

Test cases

Single-group configurations

For n < 70, Alice wins for (n) unless n is one of the following. This result was generated using this Python code. This sequence and its inversion (the list of n's where Alice wins) are not yet part of the OEIS.

4, 8, 14, 20, 24, 28, 34, 38, 42, 54, 58, 62


Multi-group truthy

[2, 9] [3, 5] [3, 7] [3, 9] [7, 8]
[1, 2, 7] [1, 8, 9] [3, 8, 9] [6, 7, 9] [7, 8, 9]
[1, 3, 6, 6] [1, 4, 4, 9] [1, 5, 6, 7] [2, 5, 6, 7] [3, 4, 8, 9]


Multi-group falsy

[1, 6] [1, 7] [4, 4] [5, 5] [5, 9]
[1, 7, 8] [2, 3, 9] [3, 3, 4] [4, 5, 9] [8, 9, 9]
[1, 2, 4, 4] [1, 4, 4, 7] [2, 2, 5, 9] [2, 6, 6, 7] [3, 4, 7, 9]

• I think you have your multi-group test cases reversed. My code is showing exactly opposite results and [1,6] seems unwinnable by a manual exhaustive check. Jul 27, 2021 at 1:14
• @PurkkaKoodari Thanks, fixed. Jul 27, 2021 at 1:21
• May I take input as a string of ||| ||||| |||||||| or even 111 11111 11111111?
– tsh
Jul 27, 2021 at 1:37
• @Jonah No, I don't think there's any easy pattern (since the recursion involves potentially longer-length sequences). And I don't know if there's any previous literature (I suspect none since the sequence of winning numbers is not on the OEIS). Jul 29, 2021 at 4:32
• zeroes of A002187
– att
Jul 29, 2021 at 19:00

JavaScript (Node.js), 11010199 90 bytes

Thanks to @tsh for -9 bytes!

g=s=>s.some((a,i)=>!a&&!g(t=[...s],t.splice(i-1,3,1)))
i=>g(i.flatMap(n=>[1,...Array(n)]))


Try it online! (with test cases)

• 94 bytes: i=>g([0,...i.map(n=>'1'.repeat(n))+'']);g=s=>s.some((a,i)=>+a&&!g(t=[...s],t.splice(i-1,3,0))); and 90 bytes if we take input as array of BigInt i=>g([0,...i.map(n=>10n**n-1n)+'']);g=s=>s.some((a,i)=>+a&&!g(t=[...s],t.splice(i-1,3,0)))
– tsh
Jul 27, 2021 at 1:48
• @tsh Thanks, that's super clever with using ',' for 0. Jul 27, 2021 at 1:51
• 90 bytes: i=>g(i.flatMap(n=>[1,...Array(n)]));g=s=>s.some((a,i)=>!a&&!g(t=[...s],t.splice(i-1,3,1)))
– tsh
Jul 27, 2021 at 1:57

Python 2, 84 bytes

f=lambda a:0in[f(a[:i]+[v-1,x-v-2]+a[i+1:])for i,x in enumerate(a)for v in range(x)]


Try it online!

Jelly, 17 16 bytes

ḟⱮ’r‘Ɗß€Ạ¬
Rj0TÇ


Try it online!

Slow as hell.

Explanation

Rj0TÇ    Main link.
[1, 3, 5]
R          For each n in the array, create an array of n sticks.
[[1], [1, 2, 3], [1, 2, 3, 4, 5]]
j0        Join by 0 (non-sticks).
[1, 0, 1, 2, 3, 0, 1, 2, 3, 4, 5]
T       Indices of truthy values (sticks).
[1, 3, 4, 5, 7, 8, 9, 10, 11]

Ɱ     €        For each stick n in the array:
’               n-1
‘             n+1
r              Inclusive range [n-1,n,n+1]
ḟ                 Remove those three sticks if present
ß           Call this link recursively on the remainder
Ạ       See if there is nothing or only 1's in the list
(i.e. if the opponent won before this turn, or can
force a victory whatever we do)
¬      Invert to see if we can force a victory from here


JavaScript, 72 bytes

f=a=>a.some(g=(v,i,a)=>v-->0&&!f(b=[...a,v-1,a[i]-v-2],b[i]=0)+g(v,i,a))


Try it online!

A port of current Python answer by dingledooper.

Charcoal, 63 bytes

⊞υ⮌⌕Ａ⪫ＸχＡω0ＦυＦι⊞υ⁻ι…·⊖κ⊕κ≔⟦⟧ζＷ⁻υＥζ§κ⁰⊞ζ⟦⌊ι⊙⌊ι№ζ⟦⁻⌊ι…·⊖κ⊕κ⁰⟧⟧⊟⊟ζ


Try it online! Link is to verbose version of code. Outputs a Charcoal boolean, i.e. - for a winning position, nothing for a losing position. Explanation:

⊞υ⮌⌕Ａ⪫ＸχＡω0


Start enumerating all positions reachable from the starting position, which is calculated by taking 10 to the power of the input groups, concatenating the result, and taking the indices of the 0s from highest to lowest (i.e. reverse of the usual order).

ＦυＦι⊞υ⁻ι…·⊖κ⊕κ


For each position and stick, calculate the result of bombing that stick and add the result to the list of reachable positions.

≔⟦⟧ζＷ⁻υＥζ§κ⁰


Enumerate the list of reachable positions in ascending order, so that all positions reachable from a given position have been enumerated before that position. Additionally, the enumeration deduplicates the positions.

⊞ζ⟦⌊ι⊙⌊ι№ζ⟦⁻⌊ι…·⊖κ⊕κ⁰⟧⟧


For each position, check whether any play results in a losing position. Push that position plus the win flag to the enumeration.

⊟⊟ζ


Output the win flag for the original position.