10

OK, here's a rather elaborate code golf challenge: Implement a game of Reversi (Othello).

  • The game should display the current state of the game-board and allow players at a single computer to alternately input moves.
  • Incorrect input and disallowed moves must be caught, but can be ignored silently.
  • The game must end when no more moves can be made (either because the board is full or because no move would flip any pieces).
  • The game must then announce who won, or if it was a draw.

Do this in as few characters as possible.

A session should look something like this:

 abcdefgh
1        
2        
3        
4   wb   
5   bw   
6        
7        
8        
b>d3
 abcdefgh
1        
2        
3   b    
4   bb   
5   bw   
6        
7        
8        
Zarkonnen
  • 22,200
  • 14
  • 65
  • 81
  • I'm sure you can, but I want to see... – Zarkonnen Oct 17 '09 at 14:55
  • 2
    You should post your answer as an answer. –  Oct 17 '09 at 14:58
  • 1
    Is the requirement "in as few characters as possible"? In that case, obfuscate your code with 1 char identifiers. Or is it "in as few tokens as possible"? In that case stick the whole source in a string, store it in a file, run javac on it and call it. As the string is 1 token, that will bring the number of tokens down :-) – rsp Oct 17 '09 at 15:01
  • Code golf is typically in as few characters as possible. Compiled code doesn't really count. – JesperE Oct 17 '09 at 15:11
  • As it says on the tin - in as few characters of code as possible. – Zarkonnen Oct 17 '09 at 15:14
  • 4
    http://meta.stackexchange.com/questions/24242/acceptable-level-of-code-golf-questions . Personally I find this problem a little on the long side, but I won't vote to close until we get some more community feedback. – dmckee --- ex-moderator kitten Oct 17 '09 at 15:18
  • 5
    Underspeced. What is the input format? what is the output format? Also, it's been said on mine, but this one really smells like homework – LiraNuna Oct 17 '09 at 18:29
  • 4
    This is definitely too broad, as @LiraNuna said. – strager Oct 17 '09 at 18:38
  • 3
    Homework?? But... I provided a solution, so how would this possibly be homework. – Zarkonnen Oct 17 '09 at 19:11
  • 9
    This is too long for code golf. – Rook Oct 17 '09 at 19:21
  • 1
    I wouldn't say it's bad due to the length, but the input and output formats _must_ be specified. – Chris Lutz Oct 17 '09 at 20:18
  • 3
    This is me being defensive - but, people do seem to be enjoying themselves and providing answers, so what's the issue? If people want, I can specify a much more rigorous spec about behaviour, input and output. – Zarkonnen Oct 17 '09 at 20:18
  • @Zarkonnen - I think you should. I think this is a good code gold, and I might try it if I wasn't swamped with school, but I think it is underspecified. – Chris Lutz Oct 17 '09 at 20:25
  • 3
    @dmckee: you comment on virtually EVERY code golf with your little link to meta and your code golf post there. Are you okay? Also people vote because of their own opinion, not because of 'community feedback'. It's getting extremely annoying to see your repetitive comments. If you have a problem with code golfs, skip them and make your own based on your recommendations. – Alex Oct 17 '09 at 20:26
  • 4
    This is a bad code golf for several reasons: It requires lengthy session with the user, testing is hard - and even have many aspect, such as the "all input must be validated". The intput is too simple as well as the output, so it makes it really easy to convert input to output. – LiraNuna Oct 17 '09 at 21:27
  • 1
    @LiraNuna, `cat input | ./program | cmp expected-output -`. I would much prefer a problem where input is given and the winner is announced, but that feels trivial. – strager Oct 18 '09 at 03:47
  • 1
    After having submitted an entry I agree with the people who said this problem was too involved. The logic of the game is fairly extensive and it is not a good problem for golf. I'm abandoning my entry. –  Oct 18 '09 at 09:41
  • Aaaaww... No Visual Basic implementation yet. – Arnis Lapsa Oct 21 '09 at 21:11

9 Answers9

7

Haskell, 821 characters, including newlines.

import Array
import List
import Maybe
import IO
a=((1,0),(8,7))
z=zip
x=range
y=repeat
o=putStr
i=['a'..'h']
r=[0,1,-1]
d b=' ':i++concatMap(\i->'\n':show(i+1)++map g(take 8$drop(i*8)$elems b))[0..7]++"\n"
e=array a(z(x a)$y 0)//z(x((4,3),(5,4)))[1,-1,-1,1]
f b p i|b!i/=0=Nothing|True=if b==v then Nothing else Just v where v=foldr u b(map(takeWhile(inRange a).($i).iterate.(\(i,j)(k,l)->(i+k,j+l)))$tail[(i,j)|i<-r,j<-r]);u r m=m//case(group$map(m!)r)of([_]:c@(m:_):(l:_):_)|m/=0&&l==p->z(take(1+length c)$r)(y p);_->[]
g=fromJust.(`lookup`z[-1..1]"b w")
h b p=do o$g p:">";hFlush stdout;c:r<-getLine;case f b p(read r,head$elemIndices c i)of;Nothing->h b p;Just m->o(d m)>>case filter(\s->mapMaybe(f m s)(x a)/=[])[-1*p,p]of(n:_)->h m n;_->print$if w==' 'then 'd'else w where w=g$signum$sum$elems m
main=o(d e)>>h e 1

The above is loosely based on this version:

import Data.Array
import Data.List
import Data.Maybe
import System.IO

type Index = (Int, Int)
type Player = Int -- (-1, 0, 1) for white, unclaimed and black, resp.
type Board = Array Index Player

-- Infix function which add two vectors
(|+|) :: Index -> Index -> Index
(i, j) |+| (k, l) = (i + k, j + l)

-- The functions dim, pieces and board2Str must be updated if one wishes to
-- alter the board's dimensions.

-- Board dimensions
dim :: (Index, Index)
dim = ((0, 0), (7, 7))

-- The pieces that will initially be on the board
pieces :: [(Index, Player)]
pieces = zip (range ((3, 3), (4, 4))) [1, -1, -1, 1]

-- Return a textual representation of the given board
board2Str :: Board -> String
board2Str b = ' ' : ['a'..'h'] ++                               -- column names
  concatMap (\i -> '\n' : show (i + 1) ++                       -- row names
    map player2Str (take 8 $ drop (i * 8) $ elems b)) [0..7] ++ "\n"  -- rows

-- The initial board, including the initial pieces
initial :: Board
initial = array dim (zip (range dim) $ repeat 0) // pieces -- the empty board

-- The directions in which pieces can be flipped.
deltas :: [(Int, Int)]
deltas = tail [(i, j) | i <- [0,1,-1], j <- [0,1,-1]]

-- All 'lines' in any direction starting from the given index
dirs :: Index -> [[Index]]
dirs c = map (takeWhile (inRange dim) . ($ c) . iterate . (|+|)) deltas

-- Attempt to perform a move
move :: Board -> Player -> Index -> Maybe Board
move b p i | b ! i /= 0 = Nothing
           | otherwise  = if b == updateAll then Nothing else Just updateAll
  where
    -- Attempt to swap pieces in all directions
    updateAll = foldr update b (dirs i)
    -- Attempt to swap pieces in the given direction
    update r b' = b' // case (group $ map (b' !) r) of
      ([_]:c@(m:_):(l:_):_) | m /= 0 && l == p ->     -- all conditions are met
        zip (take (1 + length c) $ r) (repeat p)      -- so swap the pieces
      _                                        -> []  -- nothing to swap

player2Str :: Player -> Char
player2Str = fromJust . (`lookup` zip [-1..1] "b w")

-- Test whether the given player can make a move
possible :: Board -> Player -> Bool
possible b p = mapMaybe (move b p) (range dim) /= []

-- Ask the players to make a move in turns, and update the board when required
mainLoop :: Board -> Player -> IO ()
mainLoop b p = do
  putStr $ player2Str p : "> "
  hFlush stdout
  c:r <- getLine  -- get user input (this is very fragile!)
  -- Attempt to perform the suggested move...
  case move b p (read r - 1, head $ elemIndices c ['a'..]) of
    Nothing -> mainLoop b p  -- ...try again if not possible
    Just b' -> do            -- ...accept if possible
      putStr $ board2Str b'  -- print the new board state
      case filter (possible b') [-1 * p, p] of  -- select next player to move
        (p':_) -> mainLoop b' p'   -- move if possible, otherwise game over
        _      -> print $ if winner == ' ' then 'd' else winner
                    where winner = player2Str $ signum $ sum $ elems b'

-- Let the games begin!
main :: IO()
main = putStr (board2Str initial) >> mainLoop initial 1

  : yes, I was at 756 characters, but noticed that the code didn't properly apply the rules of Reversi. Bummer.

Stephan202
  • 59,965
  • 13
  • 127
  • 133
4

Edit 2:
A bit more tweaking and tricks, and I managed to shave off another 124 characters down to 752 characters:

using C=System.Console;class O{static int[]b=new int[100];static int c=1;static void Main(){b[44]=b[55]=-1;b[45]=b[54]=1;var g=true;while(g){C.WriteLine(" abcdefgh");for(int i=10;i<90;i++){switch(i%10){case 0:C.Write(i/10);break;case 9:C.WriteLine();break;default:C.Write("w b"[b[i]+1]);break;}}C.Write("w b"[c+1]+">");var l=C.ReadLine();if(l.Length>1){int x=l[0]-96,y=l[1]-48;if(x>0&x<9&y>0&y<9&&b[y*10+x]<1)c*=f(y*10+x,1);}g=false;for(int y=10;y<90;y+=10)for(int x=y;x<y+8;)g|=b[++x]==0&&f(x,0)<0;}int s=0;foreach(int p in b)s+=p;C.WriteLine(s==0?"d":s<0?"w":"b");}static int f(int ofs,int y){var x=1;foreach(int d in new int[]{-11,-10,-9,-1,1,9,10,11}){int l=1,o=ofs;while(b[o+=d]==-c)l++;if(b[o]==c&l>1){x=-1;while(y>0&l-->0)b[o-=d]=c;}}return x;}}

Before compacting:

using Con = System.Console;

class O {

   // Initialise game board, made of ints - 0 is empty, 1 is a black piece, -1 a white.
   // Using a 10x10 board, with the outer ring of empties acting as sentinels.
   static int[] board = new int[100];

   // Color of the current player.
   static int currentColor = 1;

   static void Main() {
     // Set up the four pieces in the middle.
     board[44] = board[55] = -1;
     board[45] = board[54] = 1;
     var legal = true;
     while (legal) {
       // Print game board.
       Con.WriteLine(" abcdefgh");
       for (int i = 10; i < 90; i++) {
         switch (i % 10) {
           case 0: Con.Write(i / 10); break;
           case 9: Con.WriteLine(); break;
           default: Con.Write("w b"[board[i] + 1]); break;
         }
       }
       // Print input, indicating which color's turn it is.
       Con.Write("w b"[currentColor+1] + ">");
       // Parse input.
       var line = Con.ReadLine();
       if (line.Length > 1) {
         int x = line[0] - 96, y = line[1] - 48;
         // Discard malformed input.
         if (x > 0 & x < 9 & y > 0 & y < 9 && board[y * 10 + x] < 1)
           // Check if valid move and if so flip and switch players
           currentColor *= flip(y * 10 + x, 1);
       }
       // See if there are any legal moves by considering all possible ones.
       legal = false;
       for (int y = 10; y < 90; y += 10)
         for (int x = y; x < y + 8;)
           legal |= board[++x] == 0 && flip(x, 0) < 0;
     }
     // Calculate final score: negative is a win for white, positive one for black.
     int score = 0;
     foreach (int piece in board) score += piece;
     Con.WriteLine(score == 0 ? "d" : score < 0 ? "w" : "b");
   }

   // Flip pieces, or explore whether putting down a piece would cause any flips.
   static int flip(int ofs, int commitPutDown) {
     var causesFlips = 1;
     // Explore all straight and diagonal directions from the piece put down.
     foreach (int d in new int[] { -11, -10, -9, -1, 1, 9, 10, 11 }) {
       // Move along that direction - if there is at least one piece of the opposite color next
       // in line, and the pieces of the opposite color are followed by a piece of the same
       // color, do a flip.
       int distance = 1, o = ofs;
       while (board[o += d] == - currentColor) distance++;
       if (board[o] == currentColor & distance > 1) {
         causesFlips = -1;
         while (commitPutDown > 0 & distance-- > 0) board[o -= d] = currentColor;
       }
     }
     return causesFlips;
   }

}

876 character C# version:

using C=System.Console;class O{static void Main(){int[]b=new int[100];b[44]=b[55]=2;b[45]=b[54]=1;int c=1;while(true){C.WriteLine(" abcdefgh");for(int i=10;i<90;i++){switch(i%10){case 0:C.Write(i/10);break;case 9:C.WriteLine();break;default:C.Write(" bw"[b[i]]);break;}}bool g=false;for(int y=10;y<90;y+=10)for(int x=1;x<9;x++){g|=(b[x+y]==0&&f(x+y,b,c,false));}if(!g)break;C.Write(" bw"[c]+">");var l=C.ReadLine();if(l.Length>1){int x=l[0]-96,y=l[1]-48,ofs;if(x>0&x<9&y>0&y<9&&b[ofs=y*10+x]==0)if(f(ofs,b,c,true))b[ofs]=c;c=3-c;}}int s=0;for(int y=10;y<90;y+=10)for(int x=1;x<9;x++)switch(b[y+x]){case 1:s++;break;case 2:s--;break;}C.WriteLine(s==0?"d":s<0?"w":"b");}static bool f(int ofs,int[]b,int p,bool c){var x=false;foreach(int d in new int[]{-11,-10,-9,-1,1,9,10,11}){int l=1,o=ofs;while(b[o+=d]==3-p)l++;if(b[o]==p&l>1){x=true;if(c)while(l-->1)b[o-=d]=p;}}return x;}}

Before compacting:

using Con = System.Console;

class Othello {

  static void Main() {
    // Initialise game board, made of ints - 0 is empty, 1 is a black piece, 2 a white.
    // Using a 10x10 board, with the outer ring of empties acting as sentinels.
    int[] board = new int[100];
    // Set up the four pieces in the middle.
    board[44] = board[55] = 2;
    board[45] = board[54] = 1;
    // Color of the current player.
    int currentColor = 1;
    while (true) {
      // Print game board.
      Con.WriteLine(" abcdefgh");
      for (int i = 10; i < 90; i++) {
        switch (i % 10) {
          case 0: Con.Write(i / 10); break;
          case 9: Con.WriteLine(); break;
          default: Con.Write(" bw"[board[i]]); break;
        }
      }
      // See if there are any legal moves by considering all possible ones.
      bool legal = false;
      for (int y = 10; y < 90; y += 10) for (int x = 1; x < 9; x++) {
        legal |= (board[x + y] == 0 && flip(x + y, board, currentColor, false));
      }
      if (!legal) break;
      // Print input, indicating which color's turn it is.
      Con.Write(" bw"[currentColor] + ">");
      // Parse input.
      string l = Con.ReadLine();
      if (l.Length > 1) {
        int x = l[0] - 96, y = l[1] - 48;
        int ofs;
        // Discard malformed input.
        if (x > 0 & x < 9 & y > 0 & y < 9 && board[ofs = y * 10 + x] == 0)
          // Check if valid move & flip if it is - if not, continue.
          if (flip(ofs, board, currentColor, true))
            // Put down the piece itself.
            board[ofs] = currentColor;
        // Switch players.
        currentColor = 3 - currentColor;
      }
    }
    // Calculate final score: negative is a win for white, positive one for black.
    int score = 0;
    for (int y = 10; y < 90; y += 10) for (int x = 1; x < 9; x++)
      switch (board[y + x]) {
        case 1: score++; break;
        case 2: score--; break;
      }
    Con.WriteLine(score == 0 ? "d" : score < 0 ? "w" : "b");
  }

  /** Flip pieces, or explore whether putting down a piece would cause any flips. */
  static bool flip(int ofs, int[] board, int playerColor, bool commitPutDown) {
    bool causesFlips = false;
    // Explore all straight and diagonal directions from the piece put down.
    foreach (int d in new int[] { -11, -10, -9, -1, 1, 9, 10, 11 }) {
      // Move along that direction - if there is at least one piece of the opposite color next
      // in line, and the pieces of the opposite color are followed by a piece of the same
      // color, do a flip.
      int distance = 1, o = ofs;
      while (board[o += d] == 3 - playerColor) distance++;
      if (board[o] == playerColor & distance > 1) {
        causesFlips = true;
        if (commitPutDown) while (distance-- > 1) board[o -= d] = playerColor;
      }
    }
    return causesFlips;
  }

}

I use an int[100] instead of a char[10,10], to make some looping and comparisons simpler. There are a lot of small tricks in there, but other than that it's basically the same as the original Java code.

Edit:
The editor shows some strange "Col" value, but you should look at the "Ch" value... It's not 943 characters, it's 876...

Guffa
  • 687,336
  • 108
  • 737
  • 1,005
4

C++, 672 chars

Here's my version. It weighs in at 672 chars, including newlines:

#include <iostream>
#define F for
#define G F(i p=9;p<90;++p)
#define R return
#define C std::cout
typedef int i;i b[100];i f(i p, i s, i d){i t=0;i q[]={-11,-10,-9,-1,1,9,10,11};F(i o=0;o<8;++o){i c=p+q[o];F(;b[c]==-s;c+=q[o]);if(b[c]==s)F(--t;c!=p;c-=q[o],++t)if(d)b[c]=s;}R t;}i h(i s){G if(!b[p]&&f(p,s,0))R 1;R 0;}i main(){F(i p=0;p<100;++p)b[p]=p<10||p>89||!(p%10%9)?2:0;b[44]=b[55]=-1;b[45]=b[54]=1;i s=1;F(;;){C<<" abcdefgh";G C<<(char)(p%10?"w b\n"[b[p]+1]:'0'+p/10);s=h(s)?s:-s;if(!h(s)){s=-34;G s+=b[p];C<<(s<0?'s':s?'b':'d')<<'\n';R 0;}i p=0;F(;p<9||p>90||b[p]||!f(p,s,1);){C<<"w b"[s+1]<<">";std::string m;std::cin>>m;p=m[0]-'`'+(m[1]-'0')*10;}b[p]=s;s=-s;}}
Boojum
  • 6,592
  • 1
  • 30
  • 34
3

Perl, 408 char

This is Perl, now down to 408 characters. Could chop another 25 characters with a more minimal approach to declaring the winner (like saying "B" instead of "Winner: Black\n"). First two newlines are significant; the others are included for readability.

sub O{2&$B[$q+=$_]*$%}sub A{grep{$q=$=;$"=''while&O;$B[$q]*O$q=$=}$B[$=]?():@d}
sub F{$B[$q]=$%;O&&&F}sub D{print'
 ',a..h,$/,(map{($e="@B[$_*9+1..$_*9+8]
")=~y/012/ bw/;$_,$e}1..8),@_}
@d=map{$_,-$_}1,8..10;@B=(@z=(0)x40,$%=2,1,(0)x7,1,2,@z);
for$!(%!){$%^=3;for$=(9..80){$=%9*A&&do{{D$%-2?b:w,"> ";
$_=<>;$==(/./g)[1]*9-96+ord;A||redo}F$q=$=for A;last}}}
$X+=/1/-/2/for@B;D"Winner: ",$X<0?White:$X?Black:None,$/

@B holds the game board. $B[$i*9+$j] refers to row $i (1..8) and column $j (1..8)

@d is the list of 8 valid directions

O is a convenience method. It increments $q by $_ (the current direction) and returns non-zero if the piece at $B[$q] belongs to the current player's opponent

F handles flipping pieces in the current direction $_

A checks if the current player can make a legal move at $B[$=] and returns the set of directions that pieces can be flipped in

D(@_) draws the board and prints @_

The main loop toggles $% (the current player) and iterates through the positions on the board to find a legal move for that player. If any legal move is found, read a move from standard input (repeating until a valid move is entered) and update the board.

mob
  • 117,087
  • 18
  • 149
  • 283
2

I can do it in 1143 characters of Java:

import java.io.*;public class R{public static void main(String[]args)throws Exception{char[][]b=new char[10][10];for(inty=0;y<10;y++)for(int x=0;x<10;x++)b[y][x]=' ';b[4][4]='w';b[4][5]='b';b[5][4]='b';b[5][5]='w';char c='b';BufferedReader r=new BufferedReader(new InputStreamReader(System.in));while(true){System.out.println(" abcdefgh");boolean m=false;for(int y=1;y<9;y++){System.out.print(y);for(int x=1;x<9;x++){System.out.print(b[y][x]);m=m||(b[y][x]==' '&&f(x,y,b,c,false));}System.out.println();}if(!m)break;System.out.print(c+">");String l = r.readLine();if(l.length()<2)continue;int x=l.charAt(0)-'a'+1;int y=l.charAt(1)-'0';if(x<1||x>8||y<1||y>8||b[y][x]!=' '||!f(x, y, b, c, true))continue;b[y][x]=c;c=c=='b'?'w':'b';}int s=0;for(int y=1;y<9;y++)for(int x=1;x<9;x++)s+=b[y][x]=='b'?1:b[y][x]=='w'?-1:0;System.out.println(s==0?"d":s<0?"w":"b");}static boolean f(int x,int y,char[][]b,char c,boolean o){boolean p=false;for(int u=-1;u<2;u++)for(int v=-1;v<2;v++){if(u==0&&v==0)continue;int d=0;do d++;while(b[y+d*u][x+d*v]==(c=='b'?'w':'b'));if(b[y+d*u][x+d*v]==c&&d>1){p=true;if(o)for(int e=1;e<d;e++)b[y+e*u][x+e*v]=c;}}return p;}}

Here's a longhand version of (nearly) the same Java:

import java.io.*;

public class Reversi {
    public static void main(String[] args) throws Exception {
        // Initialise game board, made of chars - ' ' is empty, 'b' is a black piece, 'w' a white.
        // Using a 10x10 board, with the outer ring of empties acting as sentinels.
        char[][] board = new char[10][10];
        for (int y = 0; y < 10; y++) { for (int x = 0; x < 10; x++) { board[y][x] = ' '; } }
        // Set up the four pieces in the middle.
        board[4][4] = 'w'; board[4][5] = 'b'; board[5][4] = 'b'; board[5][5] = 'w';
        // Color of the current player.
        char currentColor = 'b';
        BufferedReader r = new BufferedReader(new InputStreamReader(System.in));
        while (true) {
            // Print game board.
            System.out.println(" abcdefgh");
            for (int y = 1; y < 9; y++) {
                System.out.print(y);
                for (int x = 1; x < 9; x++) { System.out.print(board[y][x]); }
                System.out.println();
            }
            // See if there are any legal moves by considering all possible ones.
            boolean legalMovesAvailable = false;
            for (int y = 1; y < 9; y++) { for (int x = 1; x < 9; x++) {
                legalMovesAvailable = legalMovesAvailable ||
                        (board[y][x] == ' ' && flip(x, y, board, currentColor, false));
            }}
            if (!legalMovesAvailable) { break; }
            // Print input, indicating which color's turn it is.
            System.out.print(currentColor + ">");
            // Parse input.
            String l = r.readLine();
            if (l.length() < 2) { continue; }
            int x = l.charAt(0) - 'a' + 1;
            int y = l.charAt(1) - '0';
            // Discard malformed input.
            if (x < 1 || x > 8 || y < 1 || y > 8 || board[y][x] != ' ') { continue; }
            // Check if valid move & flip if it is - if not, continue.
            if (!flip(x, y, board, currentColor, true)) { continue; }
            // Put down the piece itself.
            board[y][x] = currentColor;
            // Switch players.
            currentColor = currentColor == 'b' ? 'w' : 'b';
        }
        // Calculate final score: negative is a win for white, positive one for black.
        int score = 0;
        for (int y = 1; y < 9; y++) { for (int x = 1; x < 9; x++) {
            score += board[y][x] == 'b' ? 1 : board[y][x] == 'w' ? -1 : 0;
        }}
        System.out.println(score == 0 ? "d" : score < 0 ? "w" : "b");
    }

    /** Flip pieces, or explore whether putting down a piece would cause any flips. */
    static boolean flip(int pieceX, int pieceY, char[][] board, char playerColor, boolean commitPutDown) {
        boolean causesFlips = false;
        // Explore all straight and diagonal directions from the piece put down.
        for (int dY = -1; dY < 2; dY++) { for (int dX = -1; dX < 2; dX++) {
            if (dY == 0 && dX == 0) { continue; }
            // Move along that direction - if there is at least one piece of the opposite color next
            // in line, and the pieces of the opposite color are followed by a piece of the same
            // color, do a flip.
            int distance = 0;
            do {
                distance++;
            } while (board[pieceY + distance * dY][pieceX + distance * dX] == (playerColor == 'b' ? 'w' : 'b'));
            if (board[pieceY + distance * dY][pieceX + distance * dX] == playerColor && distance > 1) {
                causesFlips = true;
                if (commitPutDown) {
                    for (int distance2 = 1; distance2 < distance; distance2++) {
                        board[pieceY + distance2 * dY][pieceX + distance2 * dX] = playerColor;
                    }
                }
            }
        }}
        return causesFlips;
    }
}
Zarkonnen
  • 22,200
  • 14
  • 65
  • 81
  • 1
    Could you put the expected output back into the question? It's confusing having it here, and that will get worse when your Java solution moves down the page. –  Oct 17 '09 at 17:20
2

This doesn't quite solve the problem as stated but this implementation actually plays Othello (Reversi) at a reasonably strong level. This is one of the best IOCCC entries ever, in my opinion. You can find more information on it under "lievaart" at the Previous IOCCC Winners page.

(I have copied the implementation as published, but GCC didn't accept the whole idea of #define D define. With s/D/define/g, the program compiles and runs fine.)

#define D define
#D Y return
#D R for
#D e while
#D I printf
#D l int
#D W if
#D C y=v+111;H(x,v)*y++= *x
#D H(a,b)R(a=b+11;a<b+89;a++)
#D s(a)t=scanf("%d",&a)
#D U Z I
#D Z I("123\
45678\n");H(x,V){putchar(".XO"[*x]);W((x-V)%10==8){x+=2;I("%d\n",(x-V)/10-1);}}
l V[1600],u,r[]={-1,-11,-10,-9,1,11,10,9},h[]={11,18,81,88},ih[]={22,27,72,77},
bz,lv=60,*x,*y,m,t;S(d,v,f,_,a,b)l*v;{l c=0,*n=v+100,j=d<u-1?a:-9000,w,z,i,g,q=
3-f;W(d>u){R(w=i=0;i<4;i++)w+=(m=v[h[i]])==f?300:m==q?-300:(t=v[ih[i]])==f?-50:
t==q?50:0;Y w;}H(z,0){W(E(v,z,f,100)){c++;w= -S(d+1,n,q,0,-b,-j);W(w>j){g=bz=z;
j=w;W(w>=b||w>=8003)Y w;}}}W(!c){g=0;W(_){H(x,v)c+= *x==f?1:*x==3-f?-1:0;Y c>0?
8000+c:c-8000;}C;j= -S(d+1,n,q,1,-b,-j);}bz=g;Y d>=u-1?j+(c<<3):j;}main(){R(;t<
1600;t+=100)R(m=0;m<100;m++)V[t+m]=m<11||m>88||(m+1)%10<2?3:0;I("Level:");V[44]
=V[55]=1;V[45]=V[54]=2;s(u);e(lv>0){Z do{I("You:");s(m);}e(!E(V,m,2,0)&&m!=99);
W(m!=99)lv--;W(lv<15&&u<10)u+=2;U("Wait\n");I("Value:%d\n",S(0,V,1,0,-9000,9000
));I("move: %d\n",(lv-=E(V,bz,1,0),bz));}}E(v,z,f,o)l*v;{l*j,q=3-f,g=0,i,w,*k=v
+z;W(*k==0)R(i=7;i>=0;i--){j=k+(w=r[i]);e(*j==q)j+=w;W(*j==f&&j-w!=k){W(!g){g=1
;C;}e(j!=k)*((j-=w)+o)=f;}}Y g;}

You can find a modern reimplementation of this version at my Othello page.

Greg Hewgill
  • 951,095
  • 183
  • 1,149
  • 1,285
  • I'm guessing the `#D` construct was something used by some traditional pre-ANSI preprocessors. It's definitely not valid ANSI C. – Adam Rosenfield Oct 20 '09 at 20:00
  • Right, but the very first line defines `D`. If your preprocessor substitutes macros *before* looking for `#define`, then the above trick would work. – Greg Hewgill Oct 20 '09 at 21:16
1

Assuming your code works here a optimized version.

1081 characters

import java.util.*;import java.io.*;class R{public static void main(String[]a)throws Exception{PrintStream h=System.out;char[][]b=new char[10][10];for(int y=0;y<10;y++)for(int x=0;x<10;x++)b[y][x]=' ';b[4][4]='w';b[4][5]='b';b[5][4]='b';b[5][5]='w';char c='b';Scanner r=new Scanner(System.in);while(true){h.println(" abcdefgh");boolean m=false;for(int y=1;y<9;y++){h.print(y);for(int x=1;x<9;x++){h.print(b[y][x]);m=m||(b[y][x]==' '&&f(x,y,b,c,false));}h.println();}if(!m)break;h.print(c+">");String l=r.nextLine();if(l.length()<2)continue;int x=l.charAt(0)-'a'+1;int y=l.charAt(1)-'0';if(x<1||x>8||y<1||y>8||b[y][x]!=' '||!f(x,y,b,c,true))continue;b[y][x]=c;c=c=='b'?'w':'b';}int s=0;for(int y=1;y<9;y++)for(int x=1;x<9;x++)s+=b[y][x]=='b'?1:b[y][x]=='w'?-1:0;h.println(s==0?"d":s<0?"w":"b");}static boolean f(int x,int y,char[][]b,char c,boolean o){boolean p=false;for(int u=-1;u<2;u++)for(int v=-1;v<2;v++){if(u==0&&v==0)continue;int d=0;do d++;while(b[y+d*u][x+d*v]==(c=='b'?'w':'b'));if(b[y+d*u][x+d*v]==c&&d>1){p=true;if(o)for(int e=1;e<d;e++)b[y+e*u][x+e*v]=c;}}return p;}}
jitter
  • 53,475
  • 11
  • 111
  • 124
1

JavaScript/HTML 1419 characters (incomplete entry, abandoned)

Kinopiko is abandoning this entry. After working on the ungolfed version of this some more after submitting the entry, I realised that the problem is very much more complicated than it seems. For example, it is necessary to check for unplayable positions and declare a winner if both players are in unplayable positions. I don't know if the other answers actually do that, but the logic is complicated enough that this isn't really a fun problem any more. If anyone else wants to take over and finish this, feel free to do so.

This isn't finished yet (doesn't keep score). I've made it point and click rather than reading input.

<html>
<head>
<style>
.s{background-color:green;width:50;height:50;font-size:40}
.w{color:white;font-size:40}
.b{color:black;font-size:40}
.h{width:50;height:50;font-size:30}
</style>
<script>
b=new Array()
for(i=0;i<10;i++)b[i]=new Array(0,0,0,0,0,0,0,0,0);
function j(x,y,c){a=k("s"+x+y)
a.innerHTML=String.fromCharCode(parseInt("25CF",16))
a.className="s "+c}
z="b"
function v(x,y,c){
d=0
for(g=(x>1?x-1:1);g<=(x<8?x+1:8);g++){
for(h=(y>1?y-1:1);h<=(y<8?y+1:8);h++){
if(g==x&&h==y)continue
n=b[g][h]
if(n!=0&&n!=c){e=g-x
f=h-y
for(t=1;;t++){p=x+t*e
q=y+t*f
if(p<1||q<1||p>8||q>8)break
if(!b[p][q])break
if(b[p][q]==c){d=1
for(s=1;s<t;s++){r=x+s*e
u=y+s*f
b[r][u]=c
a=k("s"+r+u)
a.className="s "+c}break}}}}}return d}
function w(x,y){if(b[x][y])return
if(!v(x,y,z))return
b[x][y]=z
j(x,y,z)
z=(z=="b"?"w":"b")}

function create_b(){
b[4][4]=b[5][5]="w";b[4][5]=b[5][4]="b"
t=k("b");
r=o("tr",t)
for(x=0;x<9;x++){
if(x){
h=o("th",r)
h.innerHTML=x}
else 
h=o("th",r)
h.className="h"}
for(y=1;y<9;y++){
r=o("tr",t)
for(x=0;x<9;x++){
if(x){td=o("td",r)
td.className="s a"
td.id="s"+x+y;(function(x,y){td.onclick=function(){w(x,y)}}(x,y))
if(b[x][y])j(x,y,b[x][y])
}else{
h=o("th",r)
h.innerHTML=y
h.className="h"}}}}
function o(p,q){n=document.createElement(p);q.appendChild(n);return n}
function k(i){return document.getElementById(i)}
</script>
</head>
<body onload="create_b()">
<table id="b"></table>
</body>
</html>
  • Initially my code didn't meet all requirements, but I believe now it does. I agree that the game is not trivial. Note that some of the 'logic' can be reused. E.g. you can write a function which attempts to perform a move, and then use this method to (1) test the validity of a move (2) perform the actual move and (3) test whether there are any valid moves left. Similarly Guffa's idea to signify white and black using -1 and 1 is very smart, since it allows for (1) easy player switching and (2) an easy way to determine the winner (by summing the board values). Surely there are some other tricks. – Stephan202 Oct 18 '09 at 10:59
  • There are lots of things you can do, but the problem is big enough that golfing this is a test of patience rather than a test of ingenuity. In other words, it's a boring problem which I don't care to solve. –  Oct 19 '09 at 10:35
0

Here's a 1266 byte WinXP .COM file. That might seem a bit large, but it does exceed the requirements somewhat. OK, I got carried away a bit.

Controls:

w,s,a,d = move cursor
space = place piece
enter = exit program

It should be fairly intuitive to play.

P.S. Source code is here!

Skizz
  • 69,698
  • 10
  • 71
  • 108