This kata explores writing an AI for a two player, turn based game called *NIM*.

The Board
--------------

The board starts out with several piles of straw.  Each pile has a random number of straws.

```
Pile 0: ||||

Pile 1: ||

Pile 2: |||||

Pile 3: |

Pile 4: ||||||

...or more concisely: [4,2,5,1,6]
```

The Rules
--------------

- The players take turns picking a pile, and removing any number of straws from the pile they pick
- A player must pick at least one straw
- If a player picks the last straw, she wins!

The Task
------------

In this kata, you have to write an AI to play the straw picking game.

You have to encode an AI in a function `choose_move` (or `chooseMove`, or `choose-move`) that takes a board, represented as a list of positive integers, and returns

```python
(pile_index, number_of_straws)
```

Which refers to an index of a pile on the board, and some none-zero number of straws to draw from that pile.

The test suite is written so that your AI is expected to play 50 games and win every game it plays.

Difficulty: interview

Starter code:

def choose_move(game_state):
	

Solutions:
from operator import xor

def choose_move(game_state):
    """Chooses a move to play given a game state"""
    x = reduce(xor, game_state)
    for i, amt in enumerate(game_state):
        if amt ^ x < amt:
            return (i, amt - (amt ^ x))

from itertools import zip_longest
import random

def choose_move(game_state):
    def is_nim_sum_zero(nums):
        """
        Determines the "nim-sum" of the game. 
        First all the numbers are converted to binary, then 
        added following the rule that "if the binary column 
        has an even number of 1s, put a 0; else put a 1."
        
          1 1 0
        1 1 1 0
        1 1 0 1
        -------
        0 1 0 1
        
        If it sums to 0, we win!
        """
        to_add = []
        for num in nums:

            to_add.append(list(bin(num)[2:]))

        to_transpose = [b[::-1] for b in to_add]
        cols = [col for col in zip_longest(*to_transpose, fillvalue=0)]

        sum = 0

        for col in cols: 
            if col.count('1')%2 != 0:
                return False

        return True
    
    non_empty_piles = [i for i in range(len(game_state)) if game_state[i] != 0]

    if is_nim_sum_zero(game_state):
        # If nim-sum is 0 already, any move we do will give a non-zero nim-sum.
        # We will not be able to win if our opponent is a perfect player.
        # Return a random move.
        pile = random.choice(non_empty_piles)
        quant = random.choice(list(range(1, game_state[pile])) + 1)
        
    else:
        # Otherwise, let's systematically try EVERY MOVE until we get a zero
        # nim-sum!
        next_ply = list(game_state)
        pile_ind = 0
        pile = non_empty_piles[pile_ind]
        quant = 1
        
        next_ply[pile] = next_ply[pile] - quant
        
        while not is_nim_sum_zero(next_ply):
            next_ply = list(game_state)
            if quant < next_ply[pile]:
                quant += 1
            else:
                pile_ind += 1
                pile = non_empty_piles[pile_ind]
                quant = 1
                
            next_ply[pile] = next_ply[pile] - quant
            
    return (pile, quant)


def choose_move(game_state):
    nim = reduce(lambda x,y: x ^ y, game_state, 0)
    return [(i, x - (x ^ nim)) for i,x in enumerate(game_state) if x ^ nim < x][0]

# function to calculate whether everything is lost or not
def xor_all(game_state):
    result = 0
    for pile in game_state:
        result ^= pile
    return result


def choose_move(game_state):
    game_state_copy = list(game_state)
    # remove duplicate values (do not waste time on them, later on)
    for i, val in enumerate(game_state_copy):
        if val and game_state_copy.count(val) > 1:
            game_state_copy[i] = 0
            game_state_copy[game_state_copy.index(val)] = 0
    if xor_all(game_state):
        # check for each pile, whether it is possible to check apropriate number of piles
        for i, pile in enumerate(game_state_copy):
            # try with every possible number of straws
            for straws in range(0, pile+1):
                if xor_all(game_state_copy[:i] + [straws] + game_state_copy[i+1:]) == 0:
                    return [i, pile-straws]
    print "I have lost"
    return [0, 0]

from operator import xor
from functools import reduce
def choose_move(game_state):
    """Chooses a move to play given a game state"""
    nim_sum = reduce(xor, game_state)
    to_take = (s-(s^nim_sum) for s in game_state)
    return next((i,t) for i, t in enumerate(to_take) if t>0)


from operator import xor
from functools import reduce

def choose_move(game_state):
    """Chooses a move to play given a game state"""
    diffs = [amount ^ reduce(xor, game_state) for amount in game_state]
    offsets = [pile - diff for pile, diff in zip(game_state, diffs)]
    amount_of_straws = max(offsets)
    return (offsets.index(amount_of_straws), amount_of_straws)


def choose_move(game_state):
    """Chooses a move to play given a game state"""
    value = reduce(lambda x, y: x^y, game_state)
    i, v = [(i, v) for i, v in enumerate(game_state) if (v ^ value) < v][0]
    return i, v - (v ^ value)

from operator import xor
from itertools import imap

def choose_move(game_state):
    ns = reduce(xor, game_state)
    for i, p, s in imap(lambda (k, v): (k, v, ns ^ v), enumerate(game_state)):
        if s < p: return (i, p - s)

import operator

def choose_move(heaps):
    """Chooses a move to play given a game state."""
    x = reduce(operator.xor, heaps)
    return next((i, h-(x^h)) for i, h in enumerate(heaps) if (x^h) < h)

from functools import reduce
def choose_move(game_state):

  cond = reduce(lambda x,y: x^y, game_state)
  
  for idx, val in enumerate(game_state):
    if (val^cond < val):
      return (idx, val - (val^cond))