Visualize a Nim board like an expert

Question

Background

In the game of Nim, players alternate removing "stones" from "piles": on each turn, a player must remove between one and all stones from a single pile. The object of Nim is to take the last stone or, in the misere variant, to force your opponent to do so -- however, it turns out the strategies are nearly identical.

Nim makes a fun bar game. You can use matchsticks or coins for the "stones," and the "piles" are typically arranged in a line. Below is a classic setup with piles of 1, 3, 5, and 7:

If you've never played Nim before, you might try your hand at it before attempting this challenge. Here's a version called "Pearls Before Swine".

Strategy

Optimal strategy in Nim is tricky enough that most lay people lose consistently to an expert, but simple to describe with binary arithmetic.

Doing mental binary XOR operations, however, is tough, so luckily there is an equivalent way to visualize the correct strategy which is easier to implement in real time, even when drunk.

There are only three steps:

1. Mentally group the "stones" in each line into subgroups whose sizes are powers of 2, starting with the largest possible size: 8, 4, 2, and 1 are sufficient for most games.
2. Try to match each group with a twin in another line, so that every group has a pair.
3. If this isn't possible, remove unpaired "stones" from a single line (this will always be possible - see the Wikipedia link for why) so that step 2. becomes possible.

Or, said another way: "Remove some stone(s) from a single pile such that if you then group the piles into powers of 2 all groups may be paired with a group in some other pile." With the caveat that you cannot break up larger powers of 2 into smaller ones -- eg, you cannot group a line with 8 stones into two groups of 4.

For example here's how you'd visualize the board above:

This board is perfectly balanced, so you'd want your opponent to move first.

The Challenge

Given a list of positive integers representing the size of Nim "piles", return a plain text visualization of the Nim board as seen by an expert.

What constitutes a valid visualization is best explained by example, but you must:

1. Assign a distinct character to each "power-of-2 subgroup" and its pair (unpaired subgroups do not qualify), and use that character to represent the "stones" in both subgroup and pair.
2. Represent any unpaired "stones" (ie, the ones an expert would remove when playing normal -- not misere -- Nim) using a hyphen: -.

There will be multiple ways to achieve a valid visualization, and all are valid. Let's work through some test cases:

Test Cases

Input: 1, 3, 5, 7

Possible Output 1:

A
BBA
CCCCD
CCCCBBD

You may optionally include spaces between the characters, as well as blank lines between the rows:

Possible Output 2:

A

B B A

C C C C D

C C C C B B D

Input: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10

The order and choice of characters can be whatever you like:

Possible Output 1:

G
E E
E E G
C C C C
C C C C F
B B B B D D
B B B B D D F
H H I - - - - -
A A A A A A A A I
A A A A A A A A H H

Unicode symbols are ok too:

Possible Output 2:

◎
◈  ◈
◈  ◈  ◎
△  △  △  △
△  △  △  △  ◉
◐  ◐  ◐  ◐  ◀  ◀
◐  ◐  ◐  ◐  ◀  ◀  ◉
▽  ▽  ◒  -  -  -  -  -
▥  ▥  ▥  ▥  ▥  ▥  ▥  ▥  ◒ 
▥  ▥  ▥  ▥  ▥  ▥  ▥  ▥  ▽  ▽  

Input: 7

From the rules it follows that any "single pile" must be completely removed.

Possible Output 1:

-------

Possible Output 2:

- - - - - - -

Input: 5, 5

Possible Output:

A A A A B
A A A A B

Additional Rules

• This is code golf with standard rules. Shortest code wins.
• Input is flexible, and may be taken in whatever list-ish form is convenient to you.
• Output is flexible too, as the above examples illustrate. Most reasonable variations will be allowed. Ask if you're unsure about something.

Answer 1

Python 2, 150 196 206 bytes

def f(p):
 c=48;s=[l*'.'for l in p];m=2**len(bin(l))
 while m:
  if sum(m*'.'in l for l in s)>1:
   for i,l in enumerate(s):s[i]=l.replace('.'*m,chr(c)*m,`s`.count(chr(c)*m)<2)
   c+=1
  else:m/=2
 return s

Try it online!

Answer 2

Ruby, 169 164 148 bytes

->a{s=eval a*?^
c=?@
m={}
a.map{|x|z=x-(x^s);[$><<?-*z,x-=z,s=0]if z>0
n=1
eval'x&1>0?[$><<(m[n]||c.next!)*n,m[n]=!m[n]&&c*1]:0;n*=2;x/=2;'*x
puts}}

Try it online!

First, we initialize

• the nim-sum with s=eval a*?^ (which is shorter than a.reduce:^)
• the variable c, which stores the first unused unique character
• a map m that maps power-of-two lengths to characters used to represent them

Then, looping over each pile, we run the following:

z=x-(x^s);[$><<?-*z,x-=z,s=0]if z>0

Per Wikipedia's strategy, if nim-sum XOR pile is less than pile, we should remove stones from that pile such that its length becomes nim-sum XOR pile. By storing the difference in the variable z, we can test to see whether this difference is positive, and if so 1.) print that many dashes, 2.) subtract it from the pile, and 3.) set the nim-sum variable to zero to prevent further stone removal.

n=1
eval'[...];n*=2;x/=2;'*x

Now we "loop" over each bit and keep track of their values by repeatedly dividing x by 2 and multiplying the accumulator n by 2. The loop is actually a string evaluated x times, which is far greater than the log2(x) times it's necessary, but no harm is done (aside from inefficiency). For each bit, we run the following if the bit is 1 (x&1>0):

$><<(m[n]||c.next!)*n

Print a character n times. If we already printed an unpaired group of this many stones, use that character; otherwise, use the next unused character (advancing c in-place due to the !).

m[n]=!m[n]&&c*1

If m[n] existed (i.e. we just completed a pair), then m[n] is reset. Otherwise, we just started a new pair, so set m[n] to the character we used (*1 is a short way to make a copy of c).

Answer 3

JavaScript (ES6), 215 bytes

f=
(a,c=0,x=eval(a.join`^`),i=a.findIndex(e=>(e^x)<e),b=a.map(_=>``),g=e=>(d=e&-e)&&a.map((e,i)=>e&d&&(a[i]-=d,b[i]=(c++>>1).toString(36).repeat(d)+b[i]))&&g(e-d))=>g(eval(a.join`|`),b[i]='-'.repeat(a[i]-(a[i]^=x)))||b

<textarea oninput=o.textContent=/\d/.test(this.value)?f(this.value.match(/\d+/g)).join`\n`:``></textarea><pre id=o>

Only visualises up to 36 different characters. I'm relieved this works for 1, 3, 4, 5.

Answer 4

Clean, 454 bytes

still golfing

import StdEnv,Text,Data.List
$p=join"\n"[{#toChar c+'-'\\c<-e}\\e<-[take i(e++[0,0..])\\e<-r[[~c\\c<-reverse e,_<-[1..c]]\\e<-hd[q\\q<-foldr(\h t=[[a:b]\\a<-h,b<-t])[[]][[c\\c<-subsequences(takeWhile((>=)k)(iterate((*)2)1))|sum c<=k]\\k<-p]|sum[1\\a<-q&b<-p|sum a<>b]<2&&foldr(bitxor)0(flatten q)==0]]1&i<-p]]
r[]_=[]
r[h:t]n|all((<)0)h=[h:r t n]
#[m:_]=removeDup[e\\e<-h|e<0]
#(a,[x:b])=span(all((<>)m))t
=r([[if(e==m)n e\\e<-k]\\k<-[h:a]++[x]]++b)(n+1)

Try it online!

Defines the function $ :: [Int] -> String, taking the pile sizes and returning a string where - denote stones to be removed, and groups are represented by ASCII characters ascending from -. If enough groups are needed the characters will wrap back around eventually, and due to the foldr it requires more than a gigabyte of memory to run the second test-case.

Indented version of the giant comprehension:

$p=join"\n"[
    {#
        toChar c+'-'
        \\c<-j
    }
    \\j<-[
        take i(e++[0,0..])
        \\e<-r[
            [
                ~c
                \\c<-reverse e
                ,_<-[1..c]
            ]
            \\e<-hd[
                q
                \\q<-foldr(\h t=[
                    [a:b]
                    \\a<-h
                    ,b<-t
                ])[[]][
                    [
                        c
                        \\c<-subsequences(takeWhile((>=)k)(iterate((*)2)1))
                        |sum c<=k
                    ]
                    \\k<-p
                ]
                |sum[
                    1
                    \\a<-q
                    &b<-p
                    |sum a<>b
                ]<2&&foldr(bitxor)0(flatten q)==0
            ]
        ]1
        &i<-p
    ]
]