Find list of valid continuing positions in a game

Question

My kids got a dice game for Christmas. I'm trying to mathematically analyze it. The first step is to come up with a list of all possible positions.

Each player in the game has a certain number of chips. A valid position is when more than one player has chips. If only one player has chips, they win and the game is over -- that's easy to identify.

I'm trying to come up with sensible code that uniquely lists all non-terminating positions. I use flatten() from more_itertools which is in PIP. Here's what I've got:

from more_itertools import flatten
from itertools import permutations
def all_nonzero_positions(num_players, num_chips, min_chips, max_chips):
 """ Returns all monotonically descending lists
 where num_chips are divided among num_players
 with each player having at least one chip, subject to the
 min_chips and max_chips constraints. Recursive. """ 
 if num_players==1:
 return [[num_chips]] if min_chips <= num_chips <= max_chips else []
 return [[p1] + y for p1 in range(min_chips,max_chips+1)
 for y in all_nonzero_positions(num_players-1, num_chips-p1,min_chips,p1)]
def all_positions_sorted(num_players, num_chips):
 """ Returns all monotonically descending lists
 where num_chips are divided among num_players
 where at least two players have one or more chips. 
 Works by repeatedly calling all_nonzero_positions()
 for smaller num_players and appending necessary zero elements. """ 
 return [position + [0]*zeroes for zeroes in range(0,num_players-1)
 for position in all_nonzero_positions(num_players-zeroes,num_chips,1,1000)]
def all_valid_positions(num_players, num_chips):
 return set(flatten(list(permutations(x))
 for x in all_positions_sorted(num_players,num_chips)))
def main():
 print(*all_valid_positions(3,3), sep='\n')
if __name__ == "__main__":
 main()

What I don't like:

• The lines are too long, but I don't see any place I can create temp variables or functions.
• Can I get rid of more_itertools.flatten() without lengthening the code?
• Can I get rid of list(), which I'm using to instantiate the generator?
• Can I get rid of set(), which I'm using to trim the duplicates?
• Is there a better way to permute than using itertools.permutations()?
• Can all_nonzero_positions() be written without recursion?
• I'm creating a ton of temporary lists here, can that be reduced?
• What other comments should I add? The code is really short, I don't know where to put them.

• 301_Moved_Permanently: An easy way to get rid of more_itertools is to understand that flatten = itertools.chain.from_iterable

Answer 1

Disclaimer: this is not a code review, but a suggestion for an alternative implementation.

First, there is not that many terminating positions (just num_players), so it seems easier to enumerate all positions, and filter the terminating ones out.

Second, given a position it is easy to generate lexicographically next one. In pseudocode,

 find the leftmost player holding non-zero amount of chips
 if it is the last player,
 we are done
 otherwise
 pass one chip to the next player, and
 give her remaining chips (if any) to player 0

• Snowbody: 400 -> 310 -> 220 -> 130 -> 040 -> 301 -> 211 -> 121 -> 031 -> 202 -> 112 -> 022 -> 103 -> 013 -> 004. Seems to work but I don't understand how this is a "lexicographic" ordering.
• vnp: @Snowbody Just spell them right to left (as in rightmost digit is most significant). A "true" lexicographic would be moving the token right to left, but I thought it is easier to move it left to right.

Answer 2

To build on @vnp's answer, you can enumerate all positions, and filter out the ones where a single player has all the chips. This only requires you to call all_nonzero_positions() with a min_chips argument of 0. But doing this, the function should be renamed, the min_chips parameter removed (changed to a constant in the code) and the range call simplified to omit it.

You can then use filter() in all_valid_positions() to check if the count of 0s in the current position is lower than its length minus 2.

Next, I didn't exactly understand the role of the max_chips parameter... We know that the amount of chips to split is num_chips so why try to pick up to max_chips ones and filter them in the next recursive call to return [] instead of [[num_chips]] if num_chips appears to be negative (since it won't grow)? Instead, it would be best to not (try to) pick more than num_chips chips and get rid of the max_chips parameter too.

Incidentally, doing so makes the new all_nonzero_positions() generate the same lexicographic order (moving the token right to left) that @vnp suggests in their answer, so you can use their pseudo-code to create a non-recursive version of the function.

Applying the changes and PEP8 to the code can yield:

import itertools
def all_positions(num_players, num_chips):
 """Returns all monotonically ascending lists
 where num_chips are divided among num_players.
 """
 less_players = num_players - 1
 if not less_players:
 return [[num_chips]]
 return [
 [picked] + others for picked in range(num_chips + 1)
 for others in all_positions(less_players, num_chips - picked)
 ]
def is_valid(position):
 """Check that a position is valid by counting
 the number of players having at least one chip.
 Two such players are needed for a valid position.
 """
 return position.count(0) < len(position) - 1
def all_valid_positions(num_players, num_chips):
 """Return all position where num_chips are divided
 among num_players where at least two players have
 one or more chip.
 """
 return set(itertools.chain.from_iterable(
 itertools.permutations(x)
 for x in filter(is_valid, all_positions(num_players, num_chips))
 ))
def main():
 print(*all_valid_positions(3, 3), sep='\n')
if __name__ == "__main__":
 main()

Note that:

• I used itertools.chain.from_iterable to flatten the results;
• I got rid of the list() call around permutations as it is absolutely not required;
• I changed the docstrings a bit to be more PEP257-compliant.

• Snowbody: Thanks! Instead of using set(permutations( I'm instead looking into more_itertools.distinct_permutations( What do you think?
• 301_Moved_Permanently: @Snowbody this could work if the various x were not already permutations of each others... Like in all_positions(3, 3) you already have [0, 1, 2], [0, 2, 1], [1, 0, 2], [1, 2, 0], [2, 0, 1], [2, 1, 0]... So you either convert the lists to tuples and use a set here as in set(map(tuple, filter(is_valid, all_positions(...)))) and then more_itertools.flatten(map(more_itertools.distinct_permutation, <previous_result>)); or stick to this approach...
• 301_Moved_Permanently: @Snowbody the previous set command won't even work as the tuples are not equals... you can try sorting them before adding them to the set... but I’m starting to think this is not worth the mental burden of understanding what's happening...

Answer 3

To get rid of flatten, consider:

return set(flatten(list(permutations(x))
 for x in all_positions_sorted(num_players,num_chips)))

In this code, flatten takes an iterable of iterables, and flattens away one level:

[[1, 2], [3, 4], [5], [6]] --> [1, 2, 3, 4, 5, 6]

So flatten is really just a form of writing:

[item for sublist in biglist for item in sublist]

So you can spell that out:

flat_list = [item for x in ... for item in permutations(x)]

You could pass that to the set() constructor, but why? Suddenly you remember that a function call is a valid spot for a generator expression, and merge that into your set:

return set(item for x in all_positions_sorted(num_players, num_chips)
 for item in permutations(x))

• Snowbody: Thanks! Instead of using set(... for item in permutations(x)) I'm instead looking into (... for item in more_itertools.distinct_permutations(x)) What do you think?
• aghast: As long as it matches the use case, go for it. It's more clear about what's happening.