View Problem
Subdivide A Problem To A Pool Of Workers (Shared Data)
Take a hard to compute problem and split it up between multiple worker threads. In your solution, try to fully utilize available cores or processors. (I'm looking at you, Python!)
Note: In this question, there should be a need for shared state between worker threads while the problem is being solved.
Example:
-Conway Game of Life-
From Wikipedia:
The universe of the Game of Life is an infinite two-dimensional orthogonal grid of square cells, each of which is in one of two possible states, live or dead. Every cell interacts with its eight neighbors, which are the cells that are directly horizontally, vertically, or diagonally adjacent. At each step in time, the following transitions occur:
1. Any live cell with fewer than two live neighbours dies, as if caused by underpopulation.
2. Any live cell with more than three live neighbours dies, as if by overcrowding.
3. Any live cell with two or three live neighbours lives on to the next generation.
4. Any dead cell with exactly three live neighbours becomes a live cell.
The initial pattern constitutes the seed of the system. The first generation is created by applying the above rules simultaneously to every cell in the seed—births and deaths happen simultaneously, and the discrete moment at which this happens is sometimes called a tick (in other words, each generation is a pure function of the one before). The rules continue to be applied repeatedly to create further generations.
--However, for our purposes, we will assign a size to the game
Notice that in this problem, at each step or
clojure
groovy
Submit a new solution for ruby, clojure, cpp, fantom ...
There are 3 other solutions in additional languages (fsharp, java, or scala)
Note: In this question, there should be a need for shared state between worker threads while the problem is being solved.
Example:
-Conway Game of Life-
From Wikipedia:
The universe of the Game of Life is an infinite two-dimensional orthogonal grid of square cells, each of which is in one of two possible states, live or dead. Every cell interacts with its eight neighbors, which are the cells that are directly horizontally, vertically, or diagonally adjacent. At each step in time, the following transitions occur:
1. Any live cell with fewer than two live neighbours dies, as if caused by underpopulation.
2. Any live cell with more than three live neighbours dies, as if by overcrowding.
3. Any live cell with two or three live neighbours lives on to the next generation.
4. Any dead cell with exactly three live neighbours becomes a live cell.
The initial pattern constitutes the seed of the system. The first generation is created by applying the above rules simultaneously to every cell in the seed—births and deaths happen simultaneously, and the discrete moment at which this happens is sometimes called a tick (in other words, each generation is a pure function of the one before). The rules continue to be applied repeatedly to create further generations.
--However, for our purposes, we will assign a size to the game
"board": 2^k * 2^k . That is, the board should be easy to subdivide.
Notice that in this problem, at each step or
"tick", each thread/process will need to share data with its neighborhood.
; This is a "glider"
(def *start*
[".O......"
"..O....."
"OOO....."
"........"
"........"
"........"
"........"])
(def *width* (count (first *start*)))
(def *height* (count *start*))
(def *live* \O)
(def *dead* \.)
(def *n-generations-to-show* 3)
(defn cell-at
([b coord]
(cell-at b coord {:col 0 :row 0}))
([b coord offset]
(let [x (mod (+ (:col coord) (:col offset)) *width*)
y (mod (+ (:row coord) (:row offset)) *height*)]
(nth (nth b y) x))))
(defn neighbor-count [b coord]
(->> (for [x (range -1 2) y (range -1 2)] {:col x :row y})
(filter #(not (= {:col 0 :row 0} %)))
(map (partial cell-at b coord))
(reduce (fn [sum n] (+ sum (if (= *live* n) 1 0))) 0)))
(defn next-generation-cell [b coord]
(let [nc (neighbor-count b coord)]
(cond (< nc 2) *dead*
(> nc 3) *dead*
(= nc 3) *live*
true (cell-at b coord))))
(defn next-generation-row [b row]
(->> (range *width*)
(map #(next-generation-cell b {:col % :row row}))
(apply str)))
(defn next-generation [b]
(->> (range *height*)
(pmap #(next-generation-row b %))))
(defn generation-seq [b]
(let [ng (next-generation b)]
(lazy-seq (cons ng (generation-seq ng)))))
(doseq [g (take *n-generations-to-show* (generation-seq *start*))]
(doseq [l g]
(println l))
(println))
(shutdown-agents)
; This version calculates each separate line on a separate thread (pmap in next-generation)
(def *start*
[".O......"
"..O....."
"OOO....."
"........"
"........"
"........"
"........"])
(def *width* (count (first *start*)))
(def *height* (count *start*))
(def *live* \O)
(def *dead* \.)
(def *n-generations-to-show* 3)
(defn cell-at
([b coord]
(cell-at b coord {:col 0 :row 0}))
([b coord offset]
(let [x (mod (+ (:col coord) (:col offset)) *width*)
y (mod (+ (:row coord) (:row offset)) *height*)]
(nth (nth b y) x))))
(defn neighbor-count [b coord]
(->> (for [x (range -1 2) y (range -1 2)] {:col x :row y})
(filter #(not (= {:col 0 :row 0} %)))
(map (partial cell-at b coord))
(reduce (fn [sum n] (+ sum (if (= *live* n) 1 0))) 0)))
(defn next-generation-cell [b coord]
(let [nc (neighbor-count b coord)]
(cond (< nc 2) *dead*
(> nc 3) *dead*
(= nc 3) *live*
true (cell-at b coord))))
(defn next-generation-row [b row]
(->> (range *width*)
(map #(next-generation-cell b {:col % :row row}))
(apply str)))
(defn next-generation [b]
(->> (range *height*)
(pmap #(next-generation-row b %))))
(defn generation-seq [b]
(let [ng (next-generation b)]
(lazy-seq (cons ng (generation-seq ng)))))
(doseq [g (take *n-generations-to-show* (generation-seq *start*))]
(doseq [l g]
(println l))
(println))
(shutdown-agents)
; This version calculates each separate line on a separate thread (pmap in next-generation)
// some crude assumptions made for size and amount of parallelism
enum State { ALIVE, DEAD }
import static State.*
seed = '''\
* *
** **
** *
*
**
***
**
* \
'''
def computeNextGen(inboard, outboard, n) {
// crudely split into 4 chunks but could be smarter if we wanted
int half = n/2
def t1 = Thread.start { computeNextGen(inboard, outboard, n, 0, half, 0, half) }
def t2 = Thread.start { computeNextGen(inboard, outboard, n, 0, half, half, n) }
def t3 = Thread.start { computeNextGen(inboard, outboard, n, half, n, 0, half) }
def t4 = Thread.start { computeNextGen(inboard, outboard, n, half, n, half, n) }
[t1, t2, t3, t4].each{ it.join() }
}
def computeNextGen(inboard, outboard, n, minx, maxx, miny, maxy) {
for (int i = minx; i < maxx; i++)
for (int j = 0; j < maxy; j++)
if (i == 0 || i == n-1 || j == 0 || j == n-1)
outboard[i][j] = DEAD
for (int i = minx; i < maxx; i++) {
for (int j = miny; j < maxy; j++) {
if (i == 0 || i == n-1 || j == 0 || j == n-1)
continue
int count = 0
[[-1, 0, 1], [-1, 0, 1]].combinations().each{ dx, dy ->
if ((dx || dy) && inboard[i+dx][j+dy] == ALIVE) count++
}
switch(count) {
case {count == 3}:
case {inboard[i][j] == ALIVE && count == 2}:
outboard[i][j] = ALIVE; break
default:
outboard[i][j] = DEAD
}
}
}
}
void printBoard(board) {
println '--------'
println board*.collect{ it == DEAD ? ' ' : '*' }*.join().join('\n')
}
void initBoard(seed, board) {
def row = 0
seed.readLines().each { line ->
def col = 0
line.each { ch ->
board[row][col++] = ch == '*' ? ALIVE : DEAD
}
row++
}
}
def N = 8
def NUM_CYCLES = 3
def board1 = new State[N][N]
def board2 = new State[N][N]
initBoard(seed, board1)
NUM_CYCLES.times {
computeNextGen board1, board2, N
printBoard board2
computeNextGen board2, board1, N
printBoard board1
}
enum State { ALIVE, DEAD }
import static State.*
seed = '''\
* *
** **
** *
*
**
***
**
* \
'''
def computeNextGen(inboard, outboard, n) {
// crudely split into 4 chunks but could be smarter if we wanted
int half = n/2
def t1 = Thread.start { computeNextGen(inboard, outboard, n, 0, half, 0, half) }
def t2 = Thread.start { computeNextGen(inboard, outboard, n, 0, half, half, n) }
def t3 = Thread.start { computeNextGen(inboard, outboard, n, half, n, 0, half) }
def t4 = Thread.start { computeNextGen(inboard, outboard, n, half, n, half, n) }
[t1, t2, t3, t4].each{ it.join() }
}
def computeNextGen(inboard, outboard, n, minx, maxx, miny, maxy) {
for (int i = minx; i < maxx; i++)
for (int j = 0; j < maxy; j++)
if (i == 0 || i == n-1 || j == 0 || j == n-1)
outboard[i][j] = DEAD
for (int i = minx; i < maxx; i++) {
for (int j = miny; j < maxy; j++) {
if (i == 0 || i == n-1 || j == 0 || j == n-1)
continue
int count = 0
[[-1, 0, 1], [-1, 0, 1]].combinations().each{ dx, dy ->
if ((dx || dy) && inboard[i+dx][j+dy] == ALIVE) count++
}
switch(count) {
case {count == 3}:
case {inboard[i][j] == ALIVE && count == 2}:
outboard[i][j] = ALIVE; break
default:
outboard[i][j] = DEAD
}
}
}
}
void printBoard(board) {
println '--------'
println board*.collect{ it == DEAD ? ' ' : '*' }*.join().join('\n')
}
void initBoard(seed, board) {
def row = 0
seed.readLines().each { line ->
def col = 0
line.each { ch ->
board[row][col++] = ch == '*' ? ALIVE : DEAD
}
row++
}
}
def N = 8
def NUM_CYCLES = 3
def board1 = new State[N][N]
def board2 = new State[N][N]
initBoard(seed, board1)
NUM_CYCLES.times {
computeNextGen board1, board2, N
printBoard board2
computeNextGen board2, board1, N
printBoard board1
}
Submit a new solution for ruby, clojure, cpp, fantom ...
There are 3 other solutions in additional languages (fsharp, java, or scala)
