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
java
groovy
Submit a new solution for erlang, java, or groovy
There are 3 other solutions in additional languages (clojure, fsharp, 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.
import java.util.concurrent.ExecutorService;
import java.util.concurrent.Executors;
import java.util.concurrent.TimeUnit;
public class Life {
private static final int K = 4;
private static final int ITERATIONS = 10;
private static final boolean ALIVE = true;
private static final boolean DEAD = false;
private static final Board SEED = new Board(new boolean[][] {
{ DEAD, DEAD, DEAD, DEAD, DEAD, ALIVE, DEAD, ALIVE },
{ DEAD, ALIVE, ALIVE, DEAD, DEAD, DEAD, ALIVE, ALIVE },
{ DEAD, ALIVE, ALIVE, DEAD, DEAD, DEAD, ALIVE, DEAD },
{ DEAD, DEAD, DEAD, DEAD, ALIVE, DEAD, DEAD, DEAD },
{ DEAD, DEAD, DEAD, DEAD, ALIVE, ALIVE, DEAD, DEAD },
{ DEAD, DEAD, DEAD, DEAD, DEAD, ALIVE, ALIVE, ALIVE },
{ DEAD, DEAD, DEAD, DEAD, ALIVE, ALIVE, DEAD, DEAD },
{ DEAD, DEAD, DEAD, DEAD, ALIVE, DEAD, DEAD, DEAD } });
public static void main(String[] args) {
Life life = new Life(K, SEED);
System.out.println(life);
for (int i = 0; i < ITERATIONS; i++) {
life.tick();
System.out.println(life);
}
}
private final Board board, oldBoard;
public Life(int k, Board seed) {
int width = 1 << k;
int height = 1 << k;
board = new Board(width, height);
oldBoard = new Board(width, height);
seed.copyTo(board);
}
private void tick() {
board.copyTo(oldBoard);
ExecutorService executor = Executors.newFixedThreadPool(Runtime.getRuntime().availableProcessors());
for (int y = 0; y < board.height; y++)
for (int x = 0; x < board.width; x++)
executor.execute(new Evaluator(x, y));
executor.shutdown();
try {
executor.awaitTermination(30, TimeUnit.SECONDS);
} catch (InterruptedException e) {
e.printStackTrace();
}
}
public Board getBoard() {
return board;
}
@Override
public String toString() {
return getBoard().toString();
}
private class Evaluator implements Runnable {
private final int x, y;
Evaluator(int x, int y) {
this.x = x;
this.y = y;
}
@Override
public void run() {
boolean state = DEAD;
int neighbors = oldBoard.countNeighbors(x, y);
switch (neighbors) {
case 2:
if (oldBoard.get(x, y) == DEAD)
break;
case 3:
state = ALIVE;
}
board.set(x, y, state);
}
}
public static class Board {
private final boolean[][] data;
private final int width, height;
public Board(boolean[][] data) {
this.data = data;
height = data.length;
width = data[0].length;
}
public Board(int width, int height) {
this.width = width;
this.height = height;
data = new boolean[height][width];
clear();
}
public void clear() {
for (int y = 0; y < height; y++)
for (int x = 0; x < width; x++)
set(x, y, DEAD);
}
public void copyTo(Board target) {
int yo = (target.height - height) / 2;
int xo = (target.width - width) / 2;
for (int y = 0; y < height; y++)
for (int x = 0; x < width; x++) {
int dx = x + xo;
int dy = y + yo;
if (0 <= dx && dx < target.width && 0 <= dy && dy < target.height)
target.set(dx, dy, get(x, y));
}
}
public void set(int x, int y, boolean state) {
data[y][x] = state;
}
public boolean get(int x, int y) {
return data[y][x];
}
public int countNeighbors(int x, int y) {
int count = 0;
for (int y1 = Math.max(y - 1, 0), y2 = Math.min(y + 1, height - 1); y1 <= y2; y1++)
for (int x1 = Math.max(x - 1, 0), x2 = Math.min(x + 1, width - 1); x1 <= x2; x1++)
if (((y1 != y) || (x1 != x)) && get(x1, y1) == ALIVE)
count++;
return count;
}
@Override
public String toString() {
StringBuilder sb = new StringBuilder();
for (int x = 0; x < width + 2; x++)
sb.append('#');
sb.append('\n');
for (int y = 0; y < height; y++) {
sb.append('#');
for (int x = 0; x < width; x++)
sb.append(get(x, y) == ALIVE ? '*' : ' ');
sb.append("#\n");
}
for (int x = 0; x < width + 2; x++)
sb.append('#');
return sb.toString();
}
public int getWidth() {
return width;
}
public int getHeight() {
return height;
}
}
}
import java.util.concurrent.Executors;
import java.util.concurrent.TimeUnit;
public class Life {
private static final int K = 4;
private static final int ITERATIONS = 10;
private static final boolean ALIVE = true;
private static final boolean DEAD = false;
private static final Board SEED = new Board(new boolean[][] {
{ DEAD, DEAD, DEAD, DEAD, DEAD, ALIVE, DEAD, ALIVE },
{ DEAD, ALIVE, ALIVE, DEAD, DEAD, DEAD, ALIVE, ALIVE },
{ DEAD, ALIVE, ALIVE, DEAD, DEAD, DEAD, ALIVE, DEAD },
{ DEAD, DEAD, DEAD, DEAD, ALIVE, DEAD, DEAD, DEAD },
{ DEAD, DEAD, DEAD, DEAD, ALIVE, ALIVE, DEAD, DEAD },
{ DEAD, DEAD, DEAD, DEAD, DEAD, ALIVE, ALIVE, ALIVE },
{ DEAD, DEAD, DEAD, DEAD, ALIVE, ALIVE, DEAD, DEAD },
{ DEAD, DEAD, DEAD, DEAD, ALIVE, DEAD, DEAD, DEAD } });
public static void main(String[] args) {
Life life = new Life(K, SEED);
System.out.println(life);
for (int i = 0; i < ITERATIONS; i++) {
life.tick();
System.out.println(life);
}
}
private final Board board, oldBoard;
public Life(int k, Board seed) {
int width = 1 << k;
int height = 1 << k;
board = new Board(width, height);
oldBoard = new Board(width, height);
seed.copyTo(board);
}
private void tick() {
board.copyTo(oldBoard);
ExecutorService executor = Executors.newFixedThreadPool(Runtime.getRuntime().availableProcessors());
for (int y = 0; y < board.height; y++)
for (int x = 0; x < board.width; x++)
executor.execute(new Evaluator(x, y));
executor.shutdown();
try {
executor.awaitTermination(30, TimeUnit.SECONDS);
} catch (InterruptedException e) {
e.printStackTrace();
}
}
public Board getBoard() {
return board;
}
@Override
public String toString() {
return getBoard().toString();
}
private class Evaluator implements Runnable {
private final int x, y;
Evaluator(int x, int y) {
this.x = x;
this.y = y;
}
@Override
public void run() {
boolean state = DEAD;
int neighbors = oldBoard.countNeighbors(x, y);
switch (neighbors) {
case 2:
if (oldBoard.get(x, y) == DEAD)
break;
case 3:
state = ALIVE;
}
board.set(x, y, state);
}
}
public static class Board {
private final boolean[][] data;
private final int width, height;
public Board(boolean[][] data) {
this.data = data;
height = data.length;
width = data[0].length;
}
public Board(int width, int height) {
this.width = width;
this.height = height;
data = new boolean[height][width];
clear();
}
public void clear() {
for (int y = 0; y < height; y++)
for (int x = 0; x < width; x++)
set(x, y, DEAD);
}
public void copyTo(Board target) {
int yo = (target.height - height) / 2;
int xo = (target.width - width) / 2;
for (int y = 0; y < height; y++)
for (int x = 0; x < width; x++) {
int dx = x + xo;
int dy = y + yo;
if (0 <= dx && dx < target.width && 0 <= dy && dy < target.height)
target.set(dx, dy, get(x, y));
}
}
public void set(int x, int y, boolean state) {
data[y][x] = state;
}
public boolean get(int x, int y) {
return data[y][x];
}
public int countNeighbors(int x, int y) {
int count = 0;
for (int y1 = Math.max(y - 1, 0), y2 = Math.min(y + 1, height - 1); y1 <= y2; y1++)
for (int x1 = Math.max(x - 1, 0), x2 = Math.min(x + 1, width - 1); x1 <= x2; x1++)
if (((y1 != y) || (x1 != x)) && get(x1, y1) == ALIVE)
count++;
return count;
}
@Override
public String toString() {
StringBuilder sb = new StringBuilder();
for (int x = 0; x < width + 2; x++)
sb.append('#');
sb.append('\n');
for (int y = 0; y < height; y++) {
sb.append('#');
for (int x = 0; x < width; x++)
sb.append(get(x, y) == ALIVE ? '*' : ' ');
sb.append("#\n");
}
for (int x = 0; x < width + 2; x++)
sb.append('#');
return sb.toString();
}
public int getWidth() {
return width;
}
public int getHeight() {
return height;
}
}
}
// 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 erlang, java, or groovy
There are 3 other solutions in additional languages (clojure, fsharp, or scala)
