User:DanBron/Game of Nim

From Rosetta Code
(Redirected from Game of Nim)

'''The suitability of this task for inclusion on Rosetta Code is being discussed on the talk page. This task may disappear in future.'''<br> '''You are welcome to join in the discussion on the [[Talk:Game of Nim|talk page]].'''<br> The task is to implement the core algorithm of the [[wp:Game of Nim|Game of Nim]]. But there's a twist. The primary task is to produce a program <tt>nim</tt> whose input and output are sequences of non-negative integers of arbitrary length. The input represents the current Nim game board: its length is the number of "heaps" and each integer represents the number of items in the corresponding heap. The output represents what moves the player could make to win the game. Since Nim is won by by reducing the nim-sum of the board to zero, then the output represents the choices available to the player to achieve that end. In particular, each element of the output represents how many items the player should remove from the corresponding heap in order to win the game (of course, the player can only choose one of these options, but they're all equally valid). For example, if the Nim board looks like this: <pre> * * * * * * * * * * * * * * * *</pre> Then it would be represented in your program as a sequence of five integers: 4 7 2 2 1, and your <tt>nim</tt> should consume it and produce 0 2 2 2 0 (that is, the player could choose to take 2 objects from the large pile of seven, or eliminate either of the small piles of two entirely). Note that while the sequence of the input is irrelevant, the sequence of the output must correspond 1:1 with the input. I/O to your program is up to you. The user must be able to type in a board like 4 7 2 2 1 or [4,7,2,2,1] or whatever's easiest for your language; it can come from a REPL or a command-line parameter or a file or wherever. The result must be printed in a way that a human could understand it as an instruction for play (literally "0 2 2 2 0" is fine, as is "[0,2,2,2,0]" or anything similar; but some non-readable binary output is not). The idea here is to not impose arbitrary strictures, but still allow a real human to interact with the program in a sensible way. Now for the twist. This task is a [[wp:Code golf|Code golf]] challenge. You must write <tt>nim</tt> in as little code as possible. Rules: * Code is measured in (8-bit) bytes. This is particularly relevant if you're considering using Unicode characters. * You may use any "out-of-the-box" features or libraries that ship with the default download of your compiler/interpreter or are so widespread within the community to be considered part of the language. Use of custom, obscure, or non-ubiquitous external libaries is barred. * Alternatively, you may use external libraries, but their source code is counted as part of your program, i.e. against you. * Similar remarks apply to custom make files, command line options, or other external elements which are required to make your program work. If the make file (or other dependency) is non-standard, or would be perceived as weird or tricky by an external auditor who didn't know the goals of this challenge, then the bytes used to composed it counts against your score. * It's fine to use a REPL (so long as the REPL ships with the language or is widespread in the community). Each entry should lead with a human-readable version of the code, the "compressed" version which counts as the entry for the purposes of golf scoring (comments and whitespace stripped, functions inlined, etc), an example of correctness, notes on execution (i.e. how the player interacts with the program), and the final golf score, measured in bytes (including program code and non-standard external dependencies). Note: ''Since all languages have different orthographies, rhematics, and other relevant characteristics, the task should be perceived as a contest _within a given language_. That is, write the shortest possible program _in your language_ to implement the task; mentally, you should be competing with other members of your programming community. It doesn't really make sense to compare program lengths across languages.'' =={{header|J}}== '''Solution''' (''human-readable''):<lang j> nim =: 0 >. ] - (~:"1 ~:/)&.#: NB. I/O is a sequence of numbers </lang> '''Compressed''' (''strip comments & whitespace''):<lang j> nim=:0>.]-(~:"1~:/)&.#:</lang> '''Example''':<lang j> nim 4 7 2 2 1 0 2 2 2 0</lang> '''Notes on execution''': Just define <tt>nim</tt> in the REPL and call it as per the example.<br/> '''Golf score''': 23 bytes (including the assigment, i.e. naming the function; 18 bytes for the function definition). =={{header|Javascript}}== Translation of J: <lang Javascript>function nim() { var x=0, a=arguments, l=a.length, r=[]; for (var j=0; j<l; j++) x^=a[j]; for (var j=0; j<l; j++) r[j]= Math.max(0,a[j]-(x^a[j])); return r; }</lang> Task example: <lang Javascipt>nim(4,7,2,2,1) [0, 2, 2, 2, 0]</lang> Ugly golf variant: <lang Javascript>function m(a){x=0 l=a.length r=[] for(j=0;j<l;j++)x^=a[j] for(j=0;j<l;j++)r[j]=Math.max(0,a[j]-(x^a[j])) return r}</lang> Golf example: <lang Javascript>m([4,7,2,2,1]) [0, 2, 2, 2, 0]</lang> =={{header|MATLAB}}== Full game implemented in standard method with two computer players <lang MATLAB>function GameOfNim board = [4 7 2 2 1]; fprintf('Board: [ %s]\n', sprintf('%d ', board)) turnA = true; while sum(board) if turnA  % Player A - uses strategy, makes first possible move nimMove = NextMoveNim(board); movePlace = find(nimMove, 1); if movePlace  % An optimal move is possible board(movePlace) = board(movePlace)-nimMove(movePlace); else  % No optimal move - move randomly possMoves = find(board); movePlace = possMoves(randi(length(possMoves))); board(movePlace) = board(movePlace)-randi(board(movePlace)); end fprintf('Player A: [ %s]\n', sprintf('%d ', board)) else  % Player B - moves randomly possMoves = find(board); movePlace = possMoves(randi(length(possMoves))); board(movePlace) = board(movePlace)-randi(board(movePlace)); fprintf('Player B: [ %s]\n', sprintf('%d ', board)) end turnA = ~turnA; end end function nimMove = NextMoveNim(board) boardNimSum = CalcNimSum(board); placeNimSums = zeros(size(board)); for k = 1:length(board) placeNimSums(k) = CalcNimSum([board(k) boardNimSum]); end movePlaces = placeNimSums < board; nimMove = zeros(size(board)); nimMove(movePlaces) = board(movePlaces)-placeNimSums(movePlaces); end function nimSum = CalcNimSum(board) boardBinary = dec2bin(board)==49;  % Shortcut to avoid using de2bi() nimBinary = boardBinary(1, :); for k = 2:length(board) nimBinary = xor(nimBinary, boardBinary(k, :)); end nimSum = bin2dec(char(nimBinary+48));  % Shortcut to avoid using bi2de() end</lang> {{out}} From a first-player advantage game (non-zero initial Nim-sum) <pre>Board: [ 4 7 2 2 1 ] Player A: [ 4 5 2 2 1 ] Player B: [ 3 5 2 2 1 ] Player A: [ 3 2 2 2 1 ] Player B: [ 3 2 2 0 1 ] Player A: [ 1 2 2 0 1 ] Player B: [ 1 2 2 0 0 ] Player A: [ 0 2 2 0 0 ] Player B: [ 0 2 0 0 0 ] Player A: [ 0 0 0 0 0 ]</pre> From a zero initial Nim-sum game <pre>Board: [ 3 4 7 ] Player A: [ 3 4 3 ] Player B: [ 3 0 3 ] Player A: [ 1 0 3 ] Player B: [ 1 0 1 ] Player A: [ 1 0 0 ] Player B: [ 0 0 0 ]</pre> Human-readable version of the "next move" function (with whitespace and descriptive variables) <lang MATLAB>function nim(decBoard) binBoard = de2bi(decBoard); allSum = mod(sum(binBoard), 2); for k = 1:numel(decBoard) placeSum(k) = bi2de(binBoard(k, :)+allSum == 1); end moves = decBoard-placeSum; moves(moves < 0) = 0; disp(moves) end</lang> Code golf version of "next move" function (104 characters, including newlines). Requires Communications System Toolbox for de2bi() and bi2de() functions. <lang MATLAB>function n(d) b=de2bi(d);a=mod(sum(b),2);for k=1:numel(d) p(k)=bi2de(b(k,:)+a==1);end m=d-p;m(m<0)=0</lang> No toolbox requirements (121 characters, including newlines) <lang MATLAB>function n(d) b=dec2bin(d)==49;a=mod(sum(b),2);for k=1:numel(d) p(k)=bin2dec(char(b(k,:)+a==1)+48);end m=d-p;m(m<0)=0</lang> {{out}} Usage <pre>>> n([4 7 2 2 1]) m = 0 2 2 2 0 >> n([3 4 5]) m = 2 0 0</pre> =={{header|Racket}}== '''See''' [[Tic-tac-toe#Racket]] for implementation of the general game engine. <lang racket> #lang racket (require "game.rkt" lazy/force) ;;-------------------------------------------------------------------- ;; The definition of the game (define initial-state '(3 5 7)) (define (move s m) (map - s m)) (define (win? s) (= 1 (apply + s))) (define (show-state s) (displayln (map (λ (n) (make-list n '●)) s))) (define (possible-moves S) (append-map (λ (heap n) (map (λ (x) (map (curry * x) heap)) (range 1 (+ 1 (min 3 n))))) '((1 0 0) (0 1 0) (0 0 1)) S)) ;;-------------------------------------------------------------------- ;; Creating the interactive players (define Nim% (class game% (super-new [draw-game? (const #f)] [possible-moves possible-moves] [show-state show-state]))) (define-partners Nim% (first% #:win win? #:move move) (second% #:win win? #:move move)) ;; players (define player-A (new (interactive-player first%) [name "A"] [look-ahead 4])) (define player-B (new (interactive-player second%) [name "B"] [look-ahead 4])) </lang> Computer plays with the computer: <pre> > (!(start-game player-A player-B initial-state)) A makes move (0 0 2) ((● ● ●) (● ● ● ● ●) (● ● ● ● ●)) B makes move (1 0 0) ((● ●) (● ● ● ● ●) (● ● ● ● ●)) A makes move (2 0 0) (() (● ● ● ● ●) (● ● ● ● ●)) B makes move (0 2 0) (() (● ● ●) (● ● ● ● ●)) A makes move (0 3 0) (() () (● ● ● ● ●)) B makes move (0 0 1) (() () (● ● ● ●)) A makes move (0 0 3) (() () (●)) A wins! </pre> [[Category:Handicap]]