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
fsharp
Submit a new solution for java, csharp, cpp, erlang ...
There are 3 other solutions in additional languages (clojure, groovy, 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;
}
}
}
/// Represents a single cell, along with the basic transition rule
type State =
| Alive
| Dead
member this.Transition numLiveNeighbors =
match this with
| Alive when numLiveNeighbors < 2 -> Dead
| Alive when numLiveNeighbors > 3 -> Dead
| Alive -> Alive
| Dead when numLiveNeighbors = 3 -> Alive
| _ -> Dead
member this.ToChar() =
match this with
| Alive -> '*'
| Dead -> ' '
static member OfChar = function
| ' ' -> Dead
| _ -> Alive
type Board (board: State[,]) =
member this.Item
with get(i,j) = board.[i,j]
and set (i,j) v = board.[i,j] <- v
member this.Length1 = Array2D.length1 board
member this.Length2 = Array2D.length2 board
member this.CountLiveNeighbors(i, j) =
[| (-1,-1); (-1,0); (-1,1); (0,-1); (0,1); (1,-1); (1,0); (1,1) |]
|> Array.sumBy (fun (di,dj) ->
if (i + di) > 0 && (i + di) < this.Length1 && (j+dj) > 0 && (j+dj) < this.Length2 then
match board.[i+di,j+dj] with
| Alive -> 1
| _ -> 0
else
0
)
member this.Clone() = Board(Array2D.copy board)
override this.ToString() =
[|
for i in 0 .. this.Length1 - 1 do
let l = [| for j in 0 .. this.Length2 - 1 do yield board.[i,j].ToChar() |]
yield new String(l)
|]
|> String.concat ("\n")
static member OfString (s: string) =
let states =
s.Split('\n')
|> Array.map (fun line -> line.ToCharArray() |> Array.map State.OfChar)
Board (Array2D.init states.Length states.[0].Length (fun i j -> states.[i].[j]))
static member Update (inboard: Board) =
let outboard = inboard.Clone()
let Worker (i1,i2,j1,j2) =
for i in i1 .. i2 do
for j in j1 .. j2 do
outboard.[i,j] <-
inboard.CountLiveNeighbors(i, j)
|> inboard.[i,j].Transition
let N1 = inboard.Length1 / 2
let N2 = inboard.Length2 / 2
[| (0,N1,0,N2); (N1+1,inboard.Length1-1,0,N2); (0,N1,N2+1,inboard.Length2-1); (N1+1,inboard.Length1-1,N2+1,inboard.Length2-1) |]
|> Array.map (fun bounds -> async { Worker bounds})
|> Async.Parallel
|> Async.RunSynchronously
|> ignore
outboard
let blinker = " \n * \n * \n * \n " |> Board.OfString
do
let after1cycles =
blinker
|> Board.Update
let after3cycles =
after1cycles
|> Board.Update
|> Board.Update
printfn "%s" (after3cycles.ToString())
type State =
| Alive
| Dead
member this.Transition numLiveNeighbors =
match this with
| Alive when numLiveNeighbors < 2 -> Dead
| Alive when numLiveNeighbors > 3 -> Dead
| Alive -> Alive
| Dead when numLiveNeighbors = 3 -> Alive
| _ -> Dead
member this.ToChar() =
match this with
| Alive -> '*'
| Dead -> ' '
static member OfChar = function
| ' ' -> Dead
| _ -> Alive
type Board (board: State[,]) =
member this.Item
with get(i,j) = board.[i,j]
and set (i,j) v = board.[i,j] <- v
member this.Length1 = Array2D.length1 board
member this.Length2 = Array2D.length2 board
member this.CountLiveNeighbors(i, j) =
[| (-1,-1); (-1,0); (-1,1); (0,-1); (0,1); (1,-1); (1,0); (1,1) |]
|> Array.sumBy (fun (di,dj) ->
if (i + di) > 0 && (i + di) < this.Length1 && (j+dj) > 0 && (j+dj) < this.Length2 then
match board.[i+di,j+dj] with
| Alive -> 1
| _ -> 0
else
0
)
member this.Clone() = Board(Array2D.copy board)
override this.ToString() =
[|
for i in 0 .. this.Length1 - 1 do
let l = [| for j in 0 .. this.Length2 - 1 do yield board.[i,j].ToChar() |]
yield new String(l)
|]
|> String.concat ("\n")
static member OfString (s: string) =
let states =
s.Split('\n')
|> Array.map (fun line -> line.ToCharArray() |> Array.map State.OfChar)
Board (Array2D.init states.Length states.[0].Length (fun i j -> states.[i].[j]))
static member Update (inboard: Board) =
let outboard = inboard.Clone()
let Worker (i1,i2,j1,j2) =
for i in i1 .. i2 do
for j in j1 .. j2 do
outboard.[i,j] <-
inboard.CountLiveNeighbors(i, j)
|> inboard.[i,j].Transition
let N1 = inboard.Length1 / 2
let N2 = inboard.Length2 / 2
[| (0,N1,0,N2); (N1+1,inboard.Length1-1,0,N2); (0,N1,N2+1,inboard.Length2-1); (N1+1,inboard.Length1-1,N2+1,inboard.Length2-1) |]
|> Array.map (fun bounds -> async { Worker bounds})
|> Async.Parallel
|> Async.RunSynchronously
|> ignore
outboard
let blinker = " \n * \n * \n * \n " |> Board.OfString
do
let after1cycles =
blinker
|> Board.Update
let after3cycles =
after1cycles
|> Board.Update
|> Board.Update
printfn "%s" (after3cycles.ToString())
Submit a new solution for java, csharp, cpp, erlang ...
There are 3 other solutions in additional languages (clojure, groovy, or scala)
