9
\$\begingroup\$

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:

nim with matchsticks

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:

balanced matchsticks

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.
\$\endgroup\$
  • 1
    \$\begingroup\$ Is there a limit to how many stones each pile may contain, or to how many distinct characters will be necessary for the visualization? (In the extreme case, what if, for example, more than the number of printable ASCII characters were needed, or more than 255 distinct characters?) \$\endgroup\$ – Doorknob Jun 19 '18 at 5:23
  • \$\begingroup\$ @Doorknob You can assume that won't happen. You could even assume the letters of the alphabet will be sufficient for any input. \$\endgroup\$ – Jonah Jun 19 '18 at 13:43
  • \$\begingroup\$ @Jonah would this be valid output for the second test case? ["H","EE","EEH","CCCC","CCCCI","DDDDFF","DDDDFFI","AAAAAAAA","AAAAAAAA-","----------"] \$\endgroup\$ – ngn Jun 19 '18 at 17:54
  • 1
    \$\begingroup\$ @Οurous I think the simple answer yes. Technically AAAABBBB is actually invalid, and ABB is not -- but it makes the output less readable so I think just making decreasing within a line an explicit rule is best. \$\endgroup\$ – Jonah Jun 20 '18 at 0:53
  • 1
    \$\begingroup\$ @JonathanAllan Yes, I am relying on the logic that all 3 steps must occur simultaneously. So if you perform steps 1 and 2 but cannot perform step 3, you must adjust your solution to steps 1 and 2. Which I can see being confusing. I've added your description below. \$\endgroup\$ – Jonah Jun 20 '18 at 19:24
2
\$\begingroup\$

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).

\$\endgroup\$
4
\$\begingroup\$

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!

\$\endgroup\$
  • \$\begingroup\$ I don't think this works for 4, 9, 10. \$\endgroup\$ – Neil Jun 19 '18 at 8:17
  • \$\begingroup\$ @Neil Nice catch, should be fixed now \$\endgroup\$ – TFeld Jun 19 '18 at 8:42
  • 1
    \$\begingroup\$ Sorry, I managed to fool it again, this time with 14, 21, 35. \$\endgroup\$ – Neil Jun 19 '18 at 9:19
  • \$\begingroup\$ It also fails for [1, 3, 4, 5], where it should remove the entire second pile. \$\endgroup\$ – Doorknob Jun 19 '18 at 13:57
  • \$\begingroup\$ @Doorknob, Is that required? The rules say There will be multiple ways to achieve a valid visualization, and all are valid \$\endgroup\$ – TFeld Jun 19 '18 at 14:04
1
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ Really nice. It's fun to play with it in real time. \$\endgroup\$ – Jonah Jun 19 '18 at 15:48
1
\$\begingroup\$

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
    ]
]
\$\endgroup\$
  • \$\begingroup\$ Just curious, Clean seems similar to haskell... what are its advantages over Haskell? \$\endgroup\$ – Jonah Jun 20 '18 at 18:40
  • 1
    \$\begingroup\$ @Jonah It is quite similar, yes. Off the top of my head, it has lower-level type manipulation, inline IL / Assembly, and interop with C all achieved easier than with Haskell. However, for actual use, due to the obscurity and experimental/academic nature of Clean, I would recommend Haskell (which also has more support in terms of libraries, and reference information). I just happen to like Clean is all. \$\endgroup\$ – Οurous Jun 22 '18 at 0:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.