[2016-02-17] Challenge #254 [Intermediate] Finding Legal Othello (Reversi) Moves

othello.R

#
# [2016-02-17] Challenge #254 [Intermediate] Finding Legal Reversi Moves
# https://www.reddit.com/r/dailyprogrammer/comments/468pvf/20160217_challenge_254_intermediate_finding_legal/
# Demo: http://www.r-fiddle.org/#/fiddle?id=qBVAmIPB&version=2
#
# Find all valid moves on a board in Othello (Reversi).
#
# Kory Becker 2/20/2016
# http://primaryobjects.com
#

input1 <- c(
'--------',
'--------',
'--------',
'---OX---',
'---XO---',
'--------',
'--------',
'--------'
)

input2 <- c(
'--------',
'--------',
'---O----',
'--XXOX--',
'---XOO--',
'----X---',
'--------',
'--------'
)

input3 <- c(
'--------',
'--------',
'---OX---',
'--XXXO--',
'--XOO---',
'---O----',
'--------',
'--------'
)

# Finds the next player location (row,col).
nextPiece <- function(board, player = 'O', row = 1, col = 1) {
  for(x in row:ncol(board)) {
    for (y in col:nrow(board)) {
      if (board[x, y] == player) {
        # Found next piece.
        return(c(x, y))
      }
    }
    
    # Reset back to 1st column at next row.
    col <- 1
  }
  
  NA
}

validMoves <- function(board, player, opponent, startRow, startCol) {
  # Clock-wise.
  validLocations <- data.frame(row = numeric(), col = numeric())
  
  if (startRow > 1) {
    col <- startCol
    row <- startRow - 1
    trig <- NA
    repeat {
      if (board[row, col] == '-' & !is.na(trig)) {
        validLocations <- rbind(validLocations, data.frame(row, col))
        break
      }
      else if (board[row, col] == opponent) {
        trig <- TRUE
      }
      else if (board[row, col] != opponent | row <= 1) {
        break
      }
      
      row <- row - 1
    }
    
    col <- startCol + 1
    row <- startRow - 1
    trig <- NA
    repeat {
      if (board[row, col] == '-' & !is.na(trig)) {
        validLocations <- rbind(validLocations, data.frame(row, col))
        break
      }
      else if (board[row, col] == opponent) {
        trig <- TRUE
      }
      else if (board[row, col] != opponent | row <= 1 | col > 8) {
        break
      }
      
      row <- row - 1
      col <- col + 1
    }

    col <- startCol + 1
    row <- startRow
    trig <- NA
    repeat {
      if (board[row, col] == '-' & !is.na(trig)) {
        validLocations <- rbind(validLocations, data.frame(row, col))
        break
      }
      else if (board[row, col] == opponent) {
        trig <- TRUE
      }
      else if (board[row, col] != opponent | col > 8) {
        break
      }
      
      col <- col + 1
    }

    col <- startCol + 1
    row <- startRow + 1
    trig <- NA
    repeat {
      if (board[row, col] == '-' & !is.na(trig)) {
        validLocations <- rbind(validLocations, data.frame(row, col))
        break
      }
      else if (board[row, col] == opponent) {
        trig <- TRUE
      }
      else if (board[row, col] != opponent | row > 8 | col > 8) {
        break
      }
      
      row <- row + 1
      col <- col + 1
    }

    col <- startCol
    row <- startRow + 1
    trig <- NA
    repeat {
      if (board[row, col] == '-' & !is.na(trig)) {
        validLocations <- rbind(validLocations, data.frame(row, col))
        break
      }
      else if (board[row, col] == opponent) {
        trig <- TRUE
      }
      else if (board[row, col] != opponent | row > 8) {
        break
      }
      
      row <- row + 1
    }
    
    col <- startCol - 1
    row <- startRow + 1
    trig <- NA
    repeat {
      if (board[row, col] == '-' & !is.na(trig)) {
        validLocations <- rbind(validLocations, data.frame(row, col))
        break
      }
      else if (board[row, col] == opponent) {
        trig <- TRUE
      }
      else if (board[row, col] != opponent | row > 8 | col <= 1) {
        break
      }
      
      row <- row + 1
      col <- col - 1
    }
    
    col <- startCol - 1
    row <- startRow
    trig <- NA
    repeat {
      if (board[row, col] == '-' & !is.na(trig)) {
        validLocations <- rbind(validLocations, data.frame(row, col))
        break
      }
      else if (board[row, col] == opponent) {
        trig <- TRUE
      }
      else if (board[row, col] != opponent | col <= 1) {
        break
      }
      
      col <- col - 1
    }

    col <- startCol - 1
    row <- startRow - 1
    trig <- NA
    repeat {
      if (board[row, col] == '-' & !is.na(trig)) {
        validLocations <- rbind(validLocations, data.frame(row, col))
        break
      }
      else if (board[row, col] == opponent) {
        trig <- TRUE
      }
      else if (board[row, col] != opponent | row <= 1 | col <= 1) {
        break
      }
      
      row <- row - 1
      col <- col - 1
    }
  }

  validLocations
}

formatBoard <- function(input) {
  # Read input into data.frame.
  t(as.data.frame(sapply(input, function(row) {
    unlist(strsplit(row, NULL))
  })))
}

search <- function(board, player, opponent) {
  # Find starting piece.
  loc <- nextPiece(board, player)

  # Initialize valid moves array.
  valid <- data.frame(row = numeric(), col = numeric())
  
  # Find valid moves.
  while (!is.na(loc)) {
    row <- loc[1]
    col <- loc[2]
    
    # Append valid moves to array.
    valid <- rbind(valid, validMoves(board, player, opponent, row, col))
  
    # If we're past the horizontal limit, wrap back around on the next row.
    if (col < 8) {
      col <- col + 1
    }
    else {
      # Wrap.
      col <- 1
    }
    
    # Find next piece.
    loc <- nextPiece(board, player, row, col)
  }
  
  # Remove duplicates.
  valid <- valid[!duplicated(valid),]
  
  valid
}

updateBoard <- function(board, validMoves) {
  # Place a * for each valid move.
  sapply(1:nrow(validMoves), function(index) {
    move <- validMoves[index,]
    board[move$row, move$col] <<- '*'
  })
  
  # Format output.
  result <- ''
  sapply(1:nrow(board), function(index) {
    result <<- paste(result, paste0(board[index,], '', collapse = ''), sep='\n')
  })
  
  result
}

run <- function(input, player, opponent) {
  # Setup input as data.frame.
  board <- formatBoard(input)
  moves <- search(board, player, opponent)
  
  print(paste(nrow(moves), 'legal moves for', player))
  updateBoard(board, moves)
}

cat(run(input1, 'X', 'O'))
cat(run(input2, 'O', 'X'))
cat(run(input3, 'X', 'O'))

output.txt

> cat(run(input1, 'O', 'X'))
[1] "4 legal moves for X"

--------
--------
---*----
--*OX---
---XO*--
----*---
--------
--------
> cat(run(input2, 'O', 'X'))
[1] "11 legal moves for O"

--------
--------
--*O-**-
-*XXOX*-
-**XOO--
--**X---
---**---
--------
> cat(run(input3, 'X', 'O'))
[1] "12 legal moves for X"

--------
--***---
--*OX---
--XXXO*-
--XOO**-
--*O**--
---**---
--------