Skip to content

Instantly share code, notes, and snippets.

@ex
Created October 29, 2012 03:50
Show Gist options
  • Save ex/3971406 to your computer and use it in GitHub Desktop.
Save ex/3971406 to your computer and use it in GitHub Desktop.
Dynamic Pragramming solution for Euler 393 in Killa
var USE_BC = true // Set this to false if you don't have bc library.
var one = (USE_BC)? require("bc").number(1) : 1
var IN = 1
var OUT = 2
// Insert board to state.
// If the board is already present just increase the board counter.
// Board data is stored as: [boardCount, boardArray]
function insertBoard(state, boardArray, boardCount) {
var boardKey = table.concat(boardArray, ',')
if (state[boardKey] == null) {
state[boardKey] = [boardCount, boardArray]
}
else {
state[boardKey][0] += boardCount
}
}
function clone(t) {
var out = []
for (var k = 0; k < $t; k += 1) {
out[k] = t[k]
}
return out
}
function euler_393(n) {
// Initial board has no ants moving IN or OUT (all zero)
var initBoard = []
for (var k = 0; k < n; k += 1) {
initBoard[k] = 0
}
// Initial state contains only the initial board
var state = {}
var init = table.concat(initBoard, ',')
// We are going to use a data type: [counter, board] for storing boards
state[init] = [one, initBoard];
// Columns
for (var col = 0; col < n; col += 1) {
// Rows
for (var row = 0; row < n; row += 1) {
var newState = {}
var newBoard
for each (var _,data in pairs(state)) {
var boardCount = data[0]
var board = data[1]
if (board[row] == 0) {
if ((row < n - 1) && (col < n - 1)) {
if (board[row + 1] != IN) {
newBoard = clone(board)
newBoard[row] = OUT
newBoard[row + 1] += IN
insertBoard(newState, newBoard, boardCount)
}
if (board[row + 1] != OUT) {
newBoard = clone(board)
newBoard[row] = IN
newBoard[row + 1] += OUT
insertBoard(newState, newBoard, boardCount)
}
}
}
else if (board[row] == IN) {
if ((row < n - 1) && (board[row + 1] != IN)) {
newBoard = clone(board)
newBoard[row] = 0
newBoard[row + 1] += IN
insertBoard(newState, newBoard, boardCount)
}
if (col < n - 1) {
insertBoard(newState, board, boardCount)
}
}
else if (board[row] == OUT) {
if ((row < n - 1) && (board[row + 1] != OUT)) {
newBoard = clone(board)
newBoard[row] = 0
newBoard[row + 1] += OUT
insertBoard(newState, newBoard, boardCount)
}
if (col < n - 1) {
insertBoard(newState, board, boardCount)
}
}
else {
// board[row] == IN + OUT
newBoard = clone(board)
newBoard[row] = 0
insertBoard(newState, newBoard, boardCount)
}
}
state = newState
}
}
return (state[init] != null)? state[init][0] : 0
}
var tm = os.clock()
print(euler_393(10))
print("Time: ", os.clock() - tm)
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment