Find the optimal nim move

Question

The game

Nim is a mathematical strategy game, where 2 players take turns taking items from distinct heaps. On your turn, you must take at least one item, and you may take as many as you want, provided that you only take from one heap. The player that takes the last item wins! This is a solved game. Before I go into the strategy, you can try playing it online here.

The Strategy

The winning strategy is explained very clearly and simply here at this link. I will explain it using a little bit more technical terms. The way to win this game, is to always take as many items as possible so that the binary-digital-sum is always 0. Consider the following board:

         *
       * *
     * * *
   * * * *
 * * * * *
 1 2 3 4 5

To find the binary-digital-sum of this board, you must:

1. Convert the number in each row to binary. So we have 001, 010, 011, 100 and 101.

2. Add all the numbers together, and ignore any carrying.

    001
    010
    011
    100
   +101
   ----
    001
   

   You can also bitwise-xor each number, and this will achieve the same result.

Now, if the sum in this current configuration is 001, then this is not (yet) a winning board. But you can make it a winning board! If we take one item off of columns 1, 3 or 5, the sum will be 0. This is a winning board, which means that, provided you don't make a mistake, the next player to move will lose. So you must always end your turn with a winning board. Lets say you take one item off of column 5. Now the board looks like this:

       * *
     * * *
   * * * *
 * * * * *
 1 2 3 4 5

As long as you don't screw up, you have a guaranteed win. There is nothing your opponent can do to stop you. Lets say he takes all of the items from column 5.

       *
     * *
   * * *
 * * * *
 1 2 3 4 5

Where would you go next? Don't scroll down yet, and try to figure it out for yourself.

---

Right now, the sum is 100. The best move (and only winning move) would be to take everything from column 4. That would leave the board like this:

     * 
   * * 
 * * * 
 1 2 3 4 5

and the sum like this

 001
 010
+011
----
 000

that means that you are in a winning board! Yay!

The Challenge

You must write a program or function that, given a nim board, will return a winning move, or a falsey value if there is no winning move.

Your input:

• Will be your languages native list format, where each item in the list corresponds to the number of items in a given column. For example, the input {4, 2, 1, 0, 3} corresponds to the following nim board:

  *
  *           *
  *  *        *
  *  *  *     *
  1, 2, 3, 4, 5
  

• (optional) The number of rows. (For languages like C/C++ where this is not known from the list itself.)

Your output:

• Can go to STDOUT or be returned from the function

• Must be two numbers, 1) the column we are removing from (Remember that the columns are 0-indexed) and 2) the number of items to remove from that row. This could be a 2-item array, a string of the two numbers, etc. Keep in mind that the answer might be more than 2 digits long, so returning the string "111" is not valid because it isn't clear if this means "Remove one item from column eleven" or "Remove eleven items from column one". "1,11" or "11,1" would both be acceptable.

• If there is no answer, return or print a falsy value. If your langauge can only return one type of variable (again, like C/C++), a negative number for the column, or 0 or less for the number to remove would both be acceptable falsey values.

• If the column number or number to remove are too large, this is seen as an invalid output.

Sample Inputs/Outputs

[1, 2, 3, 4, 5] ---> [0, 1] or [4, 1] or [2, 1]

[1, 3, 5, 6] ---> [0, 1] or [1, 1] or [2, 1]

[1, 2, 0, 0, 5] ---> [4, 2]

[1, 2, 3] ---> ERROR

If you choose to do a function instead of full program, then you must write a full program to demonstrate the function in action. This will not count towards your full score. Also, programs are expected to run in a reasonable amount of time. I'm not planning to enter any excessively large inputs, so as long as your program isn't doing a brute force search over the entire game tree, you should be fine.

As usual, this is code-golf, so standard loop-holes apply, and answers are counted in bytes.

Leaderboard

Here is a Stack Snippet to generate both a regular leaderboard and an overview of winners by language.

To make sure that your answer shows up, please start your answer with a headline, using the following Markdown template:

# Language Name, N bytes

where N is the size of your submission. If you improve your score, you can keep old scores in the headline, by striking them through. For instance:

# Ruby, <s>104</s> <s>101</s> 96 bytes

var QUESTION_ID=52356;function answersUrl(e){return"http://api.stackexchange.com/2.2/questions/"+QUESTION_ID+"/answers?page="+e+"&pagesize=100&order=desc&sort=creation&site=codegolf&filter="+ANSWER_FILTER}function getAnswers(){jQuery.ajax({url:answersUrl(page++),method:"get",dataType:"jsonp",crossDomain:!0,success:function(e){answers.push.apply(answers,e.items),e.has_more?getAnswers():process()}})}function shouldHaveHeading(e){var a=!1,r=e.body_markdown.split("\n");try{a|=/^#/.test(e.body_markdown),a|=["-","="].indexOf(r[1][0])>-1,a&=LANGUAGE_REG.test(e.body_markdown)}catch(n){}return a}function shouldHaveScore(e){var a=!1;try{a|=SIZE_REG.test(e.body_markdown.split("\n")[0])}catch(r){}return a}function getAuthorName(e){return e.owner.display_name}function process(){answers=answers.filter(shouldHaveScore).filter(shouldHaveHeading),answers.sort(function(e,a){var r=+(e.body_markdown.split("\n")[0].match(SIZE_REG)||[1/0])[0],n=+(a.body_markdown.split("\n")[0].match(SIZE_REG)||[1/0])[0];return r-n});var e={},a=1,r=null,n=1;answers.forEach(function(s){var t=s.body_markdown.split("\n")[0],o=jQuery("#answer-template").html(),l=(t.match(NUMBER_REG)[0],(t.match(SIZE_REG)||[0])[0]),c=t.match(LANGUAGE_REG)[1],i=getAuthorName(s);l!=r&&(n=a),r=l,++a,o=o.replace("{{PLACE}}",n+".").replace("{{NAME}}",i).replace("{{LANGUAGE}}",c).replace("{{SIZE}}",l).replace("{{LINK}}",s.share_link),o=jQuery(o),jQuery("#answers").append(o),e[c]=e[c]||{lang:c,user:i,size:l,link:s.share_link}});var s=[];for(var t in e)e.hasOwnProperty(t)&&s.push(e[t]);s.sort(function(e,a){return e.lang>a.lang?1:e.lang<a.lang?-1:0});for(var o=0;o<s.length;++o){var l=jQuery("#language-template").html(),t=s[o];l=l.replace("{{LANGUAGE}}",t.lang).replace("{{NAME}}",t.user).replace("{{SIZE}}",t.size).replace("{{LINK}}",t.link),l=jQuery(l),jQuery("#languages").append(l)}}var ANSWER_FILTER="!t)IWYnsLAZle2tQ3KqrVveCRJfxcRLe",answers=[],page=1;getAnswers();var SIZE_REG=/\d+(?=[^\d&]*(?:&lt;(?:s&gt;[^&]*&lt;\/s&gt;|[^&]+&gt;)[^\d&]*)*$)/,NUMBER_REG=/\d+/,LANGUAGE_REG=/^#*\s*([^,]+)/;

body{text-align:left!important}#answer-list,#language-list{padding:10px;width:290px;float:left}table thead{font-weight:700}table td{padding:5px}

<script src="https://ajax.googleapis.com/ajax/libs/jquery/2.1.1/jquery.min.js"></script><link rel="stylesheet" type="text/css" href="//cdn.sstatic.net/codegolf/all.css?v=83c949450c8b"><div id="answer-list"> <h2>Leaderboard</h2> <table class="answer-list"> <thead> <tr><td></td><td>Author</td><td>Language</td><td>Size</td></tr></thead> <tbody id="answers"> </tbody> </table></div><div id="language-list"> <h2>Winners by Language</h2> <table class="language-list"> <thead> <tr><td>Language</td><td>User</td><td>Score</td></tr></thead> <tbody id="languages"> </tbody> </table></div><table style="display: none"> <tbody id="answer-template"> <tr><td>{{PLACE}}</td><td>{{NAME}}</td><td>{{LANGUAGE}}</td><td>{{SIZE}}</td><td><a href="{{LINK}}">Link</a></td></tr></tbody></table><table style="display: none"> <tbody id="language-template"> <tr><td>{{LANGUAGE}}</td><td>{{NAME}}</td><td>{{SIZE}}</td><td><a href="{{LINK}}">Link</a></td></tr></tbody></table>

Answer 1

Pyth, 33 22 21 20 19 bytes

eS.e*<JxxFQbb,k-bJQ

You can try it in the online compiler here.

Thank you to Jakube for removing 12 bytes and Maltysen for removing an additional byte!

This prints a winning move from the current position. If there are no winning moves, it doesn't print anything.

I used the algorithm on wikipedia. Here is the breakdown:

  .e              Q    While enumerating every element in the input:
      J                    Assign variable J to:
        xFQ                 Every element of the input bitwise xor'ed together,
       x   b                bitwise xor'ed with the current element of the input
             ,             Create a tuple containing:
              k             The index of the current element, and
               -bJ          the difference between the current element and J
    *<J     b              Put that tuple into a list if J < b, otherwise put an empty tuple
 S                     Sort the list
e                      Print the last element of the list

Answer 2

Pyth, 23 bytes

eSs.em*,kd!xxxFQb-bdSbQ

Try it online: Demonstration

This iterates over all possible moves and even does sorting. Therefore it has a time-complexity of O(N*log(N)) and a memory complexity of O(N), where N is the sum of the input list or the number of items.

Because of the bad time complexity, this might not be a valid answer. Though it solves all games, that you can play in real life with real objects, instantly.

Explanation:

                          implicit: Q = input list
   .e                 Q   map each (index k, item b) of Q to:
     m              Sb      map each d of [1, 2, ..., b] to:
       ,kd                      the pair (k, d)
      *                       multiplied by
             xFQ                xor of all numbers in Q
            x   b               xor with b
           x     -bd            xor with b-d
          !                     not (1 if xor==0 else 0)

So the input [1, 2, 0, 0, 5] gives [[[]], [[], []], [], [], [[], [4, 2], [], [], []]]

  s                       add all lists to one big list
 S                        sort

Now it looks like this: [[], [], [], [], [], [], [], [4, 2]]

e                         pick the last element and print

Answer 3

CJam, 21 20 bytes

Saved a byte compared to original version, and error handling also works now:

l~__:^f^.-_:g1#_@=S\

Try it online

Input is a CJam array, e.g.:

[1 2 3 4 5]

If no solution is found, it prints -1 0, which meets my understanding of the output requirements.

Explanation:

l~      Get input.
__      Make two copies for following operations.
:^      Reduce with xor operator, producing xor of all columns.
f^      xor all input values with the result. For each column, this calculates
        the value that the column would have to change to make the overall
        xor zero. Consider this the "target values".
.-      Subtract the target values from the input values.
_:g     Per element signum of difference between target value and input value.
1#      Find index with value 1, which is the first positive value.
_@=     Get the value at the index.
S\      Put a space between index and value.

Answer 4

Ruby, 95

->(a){r=[false,c=0]
a.each{|e|c^=e}
a.each_index{|i|(n=a[i]-(c^a[i]))>0&&n>r[1]?(r=[i,n]):0}
r}

I wrote 2 separate anonymous functions. The first, assigned to f in the program below, prints all solutions, and the second g (corresponding to the score above, as it is both shorter and more compliant with the spec) returns only the solution which requires removing the greatest number.

in both cases, the digit sum is totalized in c. Then the array is looped over and the expression n=a[i]-(c^a[i]) is used to calculate the number of counters to be removed (obviously this can only be done if it exceeds zero).

in f, all possible solutions are printed (if c is found to be 0, error is printed without looping.) I was surprised to see that the different piles can require quite different numbers of counters to be removed.

in g the output array r is only updated if the number of counters to be removed exceeds the previous number. the array r=[pile index, number to be removed] is returned. If there is no solution, the number of counters to be removed is always zero, r remains unchanged, and the initial value of r=[false,0] is returned.

Minor savings are possible if false can be changed to for example"!" and if any valid solution rather than the largest one can be returned (by deleting &&n>r[1].)

Formatted in test program

f=->(a){
  c=0
  a.each{|e|c^=e}
  c<1?(p "error"):(a.each_index{
     |i|(n=a[i]-(c^a[i]))>0?(p"#{i},#{n}"):0
   })
}

g=->(a){
  r=[false,c=0]
  a.each{|e|c^=e}
  a.each_index{
     |i|(n=a[i]-(c^a[i]))>0&&n>r[1]?(r=[i,n]):0
  }
  r
}

#Change the following two lines according to the number of values youj want to use for testing.
t=[rand(15),rand(15),rand(15),rand(15)] #Generate some random numbers for testing.
t=[gets.to_i,gets.to_i,gets.to_i]       #User input. Delete this line if you want to test with random numbers.
print t,"\n"

f.call(t)
puts g.call(t)

Answer 5

Mathematica, 73 bytes

{f=BitXor;p=Position[#,x_/;BitAnd[x,a=f@@#]==a][[1,1]],(n=#[[p]])-n~f~a}&

Answer 6

JavaScript (ES6), 54 bytes

Returns either the pair [column, number] or false

a=>a.some((n,i)=>r=(n-=n^eval(a.join`^`))>0&&[i,n])&&r

Try it online!

Commented

a =>                        // a[] = input array
  a.some((n, i) =>          // for each value n at position i in a[]:
    r = (                   //   save the result of the iteration in r
      n -=                  //   subtract from n:
        n ^ eval(a.join`^`) //     n XOR (all values in a[] XOR'ed together)
    ) > 0                   //   if the above value is positive:
    && [i, n]               //     yield the solution [i, n] and exit the some() loop
                            //   (otherwise: yield false and go on with the next value)
  ) && r                    // end of some(); return r