View Category

Subdivide A Problem To A Pool Of Workers (No 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 no need for shared state between worker threads while the problem is being solved. Only after every thread completes computation are the answers recombined into a single output.

Example:

-Input-

(In python syntax)

["ab", "we", "tfe", "aoj"]

In other words, a list of random strings.

-Output-

(In python syntax)

[ ["ab", "ba", "aa", "bb", "a", "b"], ["we", "ew", "ww", "ee", "w", "e"], ...

In other words, all possible permutations of each input string are computed.
ruby
array, threads, answers = ["ab", "we", "tfe", "aoj"], [], []
array.each { |word|
threads << Thread.new(word.split '' ) do |x|
answer = []
x.each { |a|
answer << a
x.each { |b| answer << [a, b].join }
}
answers << answer
end
}
threads.each {|thr| thr.join}
answers
java
public class ParallelPermutations {

final AtomicInteger cnt = new AtomicInteger(0);

final List<Set<String>> permutations = new ArrayList<Set<String>>();

public static void main(String[] args) {
new ParallelPermutations(Arrays.asList(args));
}

public ParallelPermutations(List<String> words) {
for (final String word : words) {
new Thread(new Runnable() {
public void run() {
cnt.incrementAndGet() ;
Set<String> permutationSet = new HashSet<String>();
for (int i = 0; i < word.length(); i++)
for (int j = i + 1; j <= word.length(); j++)
permutations("", word.substring(i, j),
permutationSet);
permutations.add(permutationSet);
if (cnt.decrementAndGet() == 0)
synchronized (ParallelPermutations.this) {
ParallelPermutations.this.notify();
}
}
private void permutations(String prefix, String word, Set<String> permutations) {
int N = word.length();
if (N == 0)
permutations.add(prefix);
else
for (int i = 0; i < N; i++)
permutations(
prefix + word.charAt(i),
word.substring(0, i) + word.substring(i + 1, N),
permutations);
}
}).start();
}

synchronized (this) {
try {
wait();
} catch (InterruptedException e) {
Thread.currentThread().isInterrupted();
}
}

System.out.println(permutations);
}

}
public class ParallelPermutations {
public static void main(String[] words) throws Exception {
if(words.length==0)
words = new String[] {"ab", "we", "tfe", "aoj"};

ParallelPermutations permutations = new ParallelPermutations();
Map<String,Set<String>> wordPermutationSet =
permutations.calculate(words);

for(Map.Entry<String,Set<String>> e : wordPermutationSet.entrySet())
System.out.println(e.getKey()+" > "+e.getValue());

System.out.println(permutations.getNumberOfJobSpawned ()+" job(s) have been spawned");
}

private AtomicInteger jobSpawnedCounter = new AtomicInteger();
private ExecutorService workers ;
private ConcurrentLinkedQueue<Future<PermutationTask>> jobSpawned = newQueue();

public ParallelPermutations () {
int availableProcessors = Runtime.getRuntime().availableProcessors();
// create a thread pool according to the number of proc.
workers = Executors.newFixedThreadPool(availableProcessors);
}

private void spawn(PermutationTask task) {
Future<PermutationTask> spawned = workers.submit(task);
jobSpawnedCounter.incrementAndGet();
jobSpawned.add(spawned);
}
public int getNumberOfJobSpawned () {
return jobSpawnedCounter.get();
}

public Map<String,Set<String>> calculate (String[] words)
throws InterruptedException, ExecutionException
{
// submit all tasks, they will spawn sub-tasks by themselves
for(String word:words)
spawn(new PermutationTask(word));

Map<String,Set<String>> wordPermutationSet = newMap ();
Future<PermutationTask> spawned;
while( (spawned=jobSpawned.poll()) != null) {
// this will wait until the result is available
// this should also handle the fact that a sub-task is spawn
// and then added in the 'jobSpawned' before its parent is done
PermutationTask task = spawned.get();

String word = task.getWord();
Set<String> founds = task.getPermutationSet();
Set<String> alreadyFounds = wordPermutationSet.get(word);
if(alreadyFounds!=null)
alreadyFounds.addAll(founds);
else
wordPermutationSet.put(word, founds);
}
return wordPermutationSet;
}

private class PermutationTask implements Callable<PermutationTask> {
private final Set<String> permutationSet = new HashSet<String>();
private final String word;
private final int initialPos;
private final Stack<Integer> indicesUsed;
public PermutationTask(String word) {
this(word, 0, new Stack<Integer>());
}

/** sub task entry point */
public PermutationTask(String word,
int initialPos,
Stack<Integer> indicesUsed) {
this.word = word;
this.initialPos = 0;
this.indicesUsed = indicesUsed;
}

/** the word this task is working on*/
public String getWord() {
return word;
}

/** permutations set of this task */
public Set<String> getPermutationSet() {
return permutationSet;
}

/**
* perform the task specific calculation
* @see Callable
*/
public PermutationTask call() throws Exception {
calculatePermutation(initialPos, indicesUsed);
return this;
}

/**
* The algorithm part of the problem. The main interest is the sub-task
* spawning. When Java 7 will be available there would be a better
* alternative with the built-in fork/join framework.
*/
private void calculatePermutation(int currentPos, Stack<Integer> indicesUsed) {
final int maxLetterPerWord = word.length();
if(indicesUsed.size()>=maxLetterPerWord) {
return;
}

final StringBuilder builder = new StringBuilder();
for (int i = 0, length = word.length(); i < length; i++) {
if(indicesUsed.contains(i) && distinctIndices)
continue;
indicesUsed.push(i);
if(indicesUsed.size()>=MIN_LETTER_PER_WORD) {
builder.setLength(0);
for(Integer index: indicesUsed)
builder.append(word.charAt(index));
permutationSet.add(builder.toString());
}
// spawn a sub task to perform the next pos. calculation
spawn(new PermutationTask(word, currentPos+1, copy(indicesUsed)));
indicesUsed.pop();
}
}
}

/* algorithm parameters : the minimum number of letter per word */
private static int MIN_LETTER_PER_WORD = 1;
/* allow duplicated letters in the word found */
private static boolean distinctIndices = true;

/* factory method */
private static <T> ConcurrentLinkedQueue<T> newQueue () {
return new ConcurrentLinkedQueue<T>();
}
/* factory method */
private static <K,V> Map<K,V> newMap () {
return new HashMap<K,V>();
}
/* factory method */
private static Stack<Integer> copy(Stack<Integer> stack) {
Stack<Integer> copy = new Stack<Integer>();
copy.addAll(stack);
return copy;
}
}
groovy
// as per Java answer, doesn't duplicate chars from input string, i.e. no 'aa'
def ans = [].asSynchronized()
def words = ["ab", "we", "tfe", "aoj"]
def threads = []

void permutations(String prefix, String w, Set<String> permSet) {
int n = w.size()
if (!n) permSet << prefix
else n.times { i ->
permutations(prefix + w[i], w[0..<i] + w[i+1..<n], permSet)
}
}

words.each { word ->
def t = Thread.start {
def wordAns = [] as Set
for (int i = 0; i < word.size(); i++)
for (int j = i + 1; j <= word.size(); j++)
permutations("", word[i..<j], wordAns)
ans << wordAns
}
threads << t
}

threads.each{ it.join() }
println ans
// as per Java answer, doesn't duplicate chars from input string, i.e. no 'aa'
def ans = [].asSynchronized()
def words = ["ab", "we", "tfe", "aoj"]

void permutations(String prefix, String w, Set<String> permSet) {
int n = w.size()
if (!n) permSet << prefix
else n.times { i ->
permutations(prefix + w[i], w[0..<i] + w[i+1..<n], permSet)
}
}

withParallelizer {
words.eachParallel { word ->
def wordAns = [] as Set
for (int i = 0; i < word.size(); i++)
for (int j = i + 1; j <= word.size(); j++)
permutations("", word[i..<j], wordAns)
ans << wordAns
}
}

println ans
scala
// as per Java answer, doesn't duplicate chars from input string, i.e. no 'aa'

// future detaches a computation whose result can
// be applied for at a later time
import scala.actors.Futures.future

def perm(s: String): IndexedSeq[String] =
if (s.length == 1)
IndexedSeq(s)
else
s map { c =>
future {
val subperms = perm(s filter (c !=))
(subperms map (c +)) ++ subperms
}
} flatMap (_ apply ())

def perms(l: Traversable[String]) =
l map (s => future(perm(s))) map (_ apply ())

val args = Seq("ab", "we", "tfe", "aoj")
println(perms(args))
python
import multiprocessing
import itertools

task_input = ["ab", "we", "tfe", "aoj"]

def all_subperms(s):
return set(reduce(
list.__add__,
([''.join(p) for p in itertools.product(s, repeat=r) if p]
for r in xrange(len(s) + 1))))

p = multiprocessing.Pool(len(task_input))
task_output = p.map(all_subperms, task_input)
print map(list, task_output)
cpp
vector<string> input;
input.push_back("ab");
input.push_back("we");
input.push_back("tfe");
input.push_back("aoj");

// Make the capacity for 'output' the same as 'input'
vector<set<string> > output(input.size());
#pragma omp parallel for
for (int i = 0; i < input.size(); ++i) {
set<string> perms;
generate_perms(input[i], perms);
#pragma omp critical
// Must use operator[]() and not push_back() since this line
// might be called in any order with respect to 'i'
output[i] = perms;
}

cout << output << endl;
fsharp
open System
let input = [| "ab"; "we"; "tfe"; "aoj" |]

/// Computes all permutations of an array
let rec permute = function
| [| |] -> [| [| |] |]
| a ->
a
|> Array.mapi (fun i ai ->
// Take all elements in the array apart from the i.th, compute
// their permutations, then attach element i at the front of each perm
Array.sub a 0 i
|> Array.append (Array.sub a (i + 1) (a.Length - i - 1))
|> permute
|> Array.map (fun perm -> Array.append [| ai |] perm)
)
|> Array.concat

/// Computes all permutations of a string
let permuteString (s: string) =
s.ToCharArray()
|> permute
|> Array.map (fun p -> new String(p))

let output =
input
|> Array.map (fun word -> async { return (permuteString word) })
|> Async.Parallel
|> Async.RunSynchronously
// like the Java and Groovy solutions, does not duplicate letters
open System
open System.Threading.Tasks

let input = [| "ab"; "we"; "tfe"; "aoj" |]

let factorial n =
seq { 1 .. n } |> Seq.reduce (*)

let swap (arr:'a[]) i j =
[| for k = 0 to arr.Length - 1 do
yield if k = i then arr.[j] elif k = j then arr.[i] else arr.[k] |]

let rec permutation (k:int,j:int) (r:'a[]) =
if j = (r.Length + 1) then r
else permutation (k/j+1, j+1) (swap r (j-1) (k%j))

let permutations (source:'a[]) = seq {
for k = 0 to (factorial source.Length) - 1 do
yield permutation (k,2) source
}

let permute (word:string) =
let letters = word.ToCharArray()
permutations letters
|> Seq.map (fun chars -> String(chars))
|> Array.ofSeq

let tasks =
input |> Array.map (fun word -> Task.Factory.StartNew(fun () -> permute word))

let taskResult (t:Task<_>) =
t.Result

let output = Task.Factory.ContinueWhenAll(tasks, fun ts -> Array.map taskResult ts).Result
haskell
import Control.Parallel
import Control.Parallel.Strategies

allPerms xs = do
x <- [1 .. length xs]
sequence (replicate x xs)

result = parMap rdeepseq allPerms ["ab", "we", "tfe", "aoj"]

main = print $ concat result

{-
Compile with -threaded
-}
clojure
(defn perm-chars [l]
"Returns a list of all possible permutations of strings with the
same size as the input string. This function will return duplicates
if the same character occurs multiple time in the string.
Ex: ab -> (aa ab ba ab)"
(if (string? l)
(recur (repeat (count l) l))
(let [s (first l)
r (rest l)]
(if (empty? r)
(map identity s)
(->> s
(map (fn [c] (map #(str c %) (perm-chars r))))
(flatten))))))

(defn perm-sz [s]
"Returns a list of all possible permutations of the input
string. May return duplicats.
Ex: ab -> (aa ab ba bb a b a b)"
(if-not (empty? s)
(let [r (perm-chars s)]
(if (= (count s) 1)
r
(->> r
(map #(perm-sz (apply str (rest %))))
(flatten)
(lazy-cat r))))))


(defn perm [s]
"Returns a list of all possible permutations of the input
string. The list of string is sorted and does not contain
duplicates.
Ex: ab -> (a aa ab b ba bb)"
(->> (reduce (fn [s e] (conj s e)) #{} (perm-sz s))
(map str)
(sort)))

(println (pmap perm ["ab" "we" "tfe" "aoj"]))
(require 'cojure.contrib.combinatorics)

(pmap (fn [str]
(apply concat (map #(selections str (inc %))
(range (count str)))))
["ab", "we", "tfe", "aoj"])
fantom
using concurrent

// as per Java answer, doesn't duplicate chars from input string, i.e. no 'aa'
const class PermGen : Actor
{
new make(ActorPool pool) : super(pool) {}

Void permutations(Str prefix, Str w, Str[] pset)
{
n := w.size
if (n == 0)
{
if (!pset.contains(prefix))
pset.add(prefix)
return
}
n.times { permutations(prefix + w[it..it], w[0..<it] + w[it+1..<n], pset) }
}

override Obj? receive(Obj? msg)
{
Str word := msg
wordSubPerm := Str[,]
for (Int i := 0; i < word.size; i++)
for (Int j := i; j < word.size; j++)
permutations("", word[i..j], wordSubPerm)
return wordSubPerm
}
}

class SolutionXX
{
static Void main()
{
pool := ActorPool() { maxThreads = 8 }
futures := Future[,]
["ab", "we", "tfe", "aoj"].each { futures.add(PermGen(pool).send(it)) }
futures.each { echo(it.get) }
}
}

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 "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.
java
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;
}
}
}
groovy
// 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
}
scala
import scala.actors.Futures.future

class Generation(gen: Array[String]) {
val width = gen(0).length
val hight = gen.length

override def toString = gen.reduceLeft(_ + "\n" + _)

def nextGen = {
// Calculate each row separately as a "future"
val ngFuture = (0 until hight).map(row => future(nextRow(row)))
// Wait for each row to finish
val ng = ngFuture.map(_ apply ())
new Generation(ng.toArray)
}

private def nextRow(row: Int): String =
(0 until width).map(nextCell(row, _)).foldLeft("")(_ + _)

private def nextCell(row: Int, col: Int) = {
liveNeighbors(row, col) match {
case 2 => cellAt(row, col)
case 3 => gameOfLife.liveCell
case _ => gameOfLife.deadCell
}
}

private def cellAt(row: Int, col: Int) =
gen((row + hight) % hight)((col + width) % width)

private def liveNeighbors(row: Int, col: Int) =
// Generate coordinate to all adjacent cells
((row-1) to (row+1)).flatMap(x => ((col-1) to (col+1)).map((x,_)))
// Remove our own cell and all dead neighbor cells
.filter(p => p != (row,col) && cellAt(p._1, p._2) == gameOfLife.liveCell)
// Get the number of cells we kept
.length
}


object gameOfLife {
val liveCell = 'O'
val deadCell = '.'
val firstGen = new Generation(Array(".O......",
"..O.....",
"OOO.....",
"........",
"........",
"........",
"........"))

def main(args: Array[String]) {
val numGens = if (args.length > 0) args(0).toInt else 3
var thisGen = firstGen
for (genNr <- 0 to numGens) {
println("Generation " + genNr)
println(thisGen)
thisGen = thisGen.nextGen
}
}
}
fsharp
/// 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())
clojure
; 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)

Create a multithreaded "Hello World"

Create a program which outputs the string "Hello World" to the console, multiple times, using separate threads or processes.

Example:

-Output-

Thread one says Hello World!
Thread two says Hello World!
Thread four says Hello World!
Thread three says Hello World!

-Notice that the threads can print in any order.
ruby
%w[one two three four].each do |number|
Thread.new(number) { |number|
puts "Thread #{number} says Hello World!"
}.join
end
java
for (int i = 0; i < 4; i++) {
final int nr = i ;
new Thread(new Runnable() {
public void run() {
System.out.println("Thread " + new String[] { "one", "two", "three", "four" }[nr] + " says Hello World!");
}
}).start();
}
perl
use threads;

foreach my $tid ("one","two","three","four") {
threads->create(
sub { print("Thread $tid says Hello World!\n"); }
)->join();
}
groovy
["one","two","three","four"].each { tid ->
Thread.start {
println "Thread $tid says Hello World!"
}
}
import static groovyx.gpars.Parallelizer.*
withParallelizer {
["one","two","three","four"].eachParallel {
println "Thread $it says Hello World!"
}
}
scala
import scala.actors.Actor

List("one", "two", "three", "four").foreach { name =>
new Actor { override def act() = { println("Thread " + name + " says Hello World!") } }.start
}
List("one", "two", "three", "four").foreach { name =>
new Thread { override def run() = { println("Thread " + name + " says Hello World!") } }.start
}
import scala.actors.Futures._
List("one", "two", "three", "four").foreach(name => future(println("Thread " + name + " says hi")))
python
#!/usr/bin/python
from threading import Thread
Nthread = ['one','two','three','four']
def ThreadSpeaks(number):
print "Thread", number, "says Hello World!"
if __name__ == "__main__":
for n in range(0,len(Nthread)):
th =Thread(target=ThreadSpeaks, args=(Nthread[n],))
th.start()
cpp
#include <iostream>
#include <string>

using namespace std;

int main(){
int pid;
string text[4]={"one","two","three","four"};
for (int i=0;i<4;i++){
pid=fork();
if (pid>0){
//cout << "Process("<<pid<<") - " << "Thread " << text[i] << " says Hello World!" << endl;
cout << "Thread " << text[i] << " says Hello World!" << endl;
exit(0);
}
}
return 0;
}
#include <iostream>
#include <string>

#include <omp.h>

int main() {
unsigned int const num_threads = 4;

std::string const names[] = { "one", "two", "three", "four" };

# pragma omp parallel num_threads(num_threads)
{
unsigned const id = omp_get_thread_num();
// Stream concatenation isn't thread-safe so we use a critical section.
# pragma omp critical
std::cout << "Thread " << names[id] << " says Hello World!" << std::endl;
}
}
fsharp
let mappedString =
["Thread one says Hello World!";
"Thread two says Hello World!";
"Thread four says Hello World!";
"Thread three says Hello World!"]
|> Seq.map (fun str -> async { printfn "%s" str })

Async.RunSynchronously (Async.Parallel mappedString)
erlang
-module(spam).
-export([spam/1]).

spam(N) when N<5 ->
spawn(fun() -> io:format("Hello World from thread ~p~n",[N]) end),
spam(N+1);
spam(_) -> void.
ocaml

(* Compilation (native):
$ ocamlopt -thread unix.cmxa threads.cmxa threads_hello.ml -o threads_hello
*)

let say_hello (i, msg) =
Printf.printf "Thread %d says %s\n" i msg
;;
let thread_ids = Array.init 4 (fun i ->
Thread.create say_hello (i, "Hello World!")) in
Array.iter Thread.join thread_ids;
flush_all ()
php
/*
The commented lines below can be used to verify new process are in use
*/
$text=array("one","two","three","four");
for ($i = 0; $i < 4; ++$i) {
$pid = pcntl_fork();
//$mypid=getmypid();
if (!$pid) {
//echo("Thread ".$text[$i]." says Hello World!(".$mypid.")\n");
echo("Thread ".$text[$i]." says Hello World!\n");
exit($i);
}
}
haskell
mapM_ (\x -> forkIO (putStrLn ("Thread " ++ x ++ " says Hello World!"))) ["one", "two", "three", "four"]
clojure
(doseq [msg ["one" "two" "three" "four"]]
(future (println "Thread" msg "says Hello World!")))
(dorun (pmap #(println (str "Thread " % " says Hello World!")) '("one" "two" "three" "four")))
(dorun (map (fn [n] (.start (Thread. #(println (str "Thread " n " says Hello World!")))))
'("one" "two" "three" "four")))
fantom
pool := ActorPool()
["one", "two", "three", "four"].each
{
a := Actor(pool) |Str name| { echo("Thread $name says Hello World!") }
a.send(it)
}

Create read/write lock on a shared resource.

Create multiple threads or processes who are either readers or writers. There should be more readers then writers.

(From Wikipedia):

Multiple readers can read the data in parallel but an exclusive lock is needed while writing the data. When a writer is writing the data, readers will be blocked until the writer is finished writing.

Example:

-Output-

Thread one says that the value is 8.
Thread three says that the value is 8.
Thread two is taking the lock.
Thread four tried to read the value, but could not.
Thread five tried to write to the value, but could not.
Thread two is changing the value to 9.
Thread two is releasing the lock.
Thread four says that the value is 9.
...

--Notice that when a needed resource is locked, a thread can set a timer and try again in the future, or wait to be notified that the resource is no longer locked.
java
public class ParallelPermutations {

Lock lock = new ReentrantLock();

Integer value = 8;

public static void main(String[] args) {
new ParallelPermutations(Arrays.asList(args));
}

public ParallelPermutations(List<String> words) {
for (int i = 0; i < 20; i++) {
final Integer cnt = i ;
if ( i % 3 == 0) {
new Thread(new Runnable() {
public void run() {
if ( ! lock.tryLock() ) {
System.out.println("Thread " + cnt + " tried to write the value, but could not.") ;
lock.lock();
}
value = (int) (Math.random() * 10);
System.out.println("Thread " + cnt + " is changing the value to " + value ) ;
lock.unlock();
System.out.println("Thread " + cnt + " is releasing the lock.") ;
}
}).start();
} else {
new Thread(new Runnable() {
public void run() {
if ( ! lock.tryLock() ) {
System.out.println("Thread " + cnt + " tried to read the value, but could not.") ;
lock.lock() ;
}
System.out.println("Thread " + cnt + " says that the value is " + value + ".") ;
lock.unlock();
}
}).start();
}
}
}
}
groovy
def lock = new ReentrantLock()
Integer value = 8

20.times { i ->
if (i % 3 == 0) {
Thread.start {
if (!lock.tryLock()) {
println "Thread " + i + " tried to write the value, but could not."
lock.lock()
}
value = (int) (Math.random() * 10)
println "Thread " + i + " is changing the value to " + value
lock.unlock()
println "Thread " + i + " is releasing the lock."
}
} else {
Thread.start {
if (!lock.tryLock()) {
println "Thread " + i + " tried to read the value, but could not."
lock.lock()
}
println "Thread " + i + " says that the value is " + value + "."
lock.unlock()
}
}
}
scala
import java.util.concurrent.locks.ReentrantReadWriteLock
import java.util.concurrent.locks.ReentrantReadWriteLock.ReadLock
import java.util.concurrent.locks.ReentrantReadWriteLock.WriteLock
import scala.util.Random

class Reader(name: String, lock: ReadLock) extends Thread {
override def run() = {
println(name)
while (true) {
if (!lock.tryLock)
{
println("Thread " + name + " tried to read the value, but could not.")
lock.lock
}
println("Thread " + name + " says that the value is " + rwLockOnSharedResource.value)
lock.unlock
Thread.sleep(3) // Generates output more similar to the problem description
}
}
}

class Writer(name: String, lock: WriteLock) extends Thread {
override def run() = {
while (true) {
if (!lock.tryLock) {
println("Thread " + name + " tried to write the value, but could not.")
lock.lock
}
println("Thread " + name + " is taking the lock.")
rwLockOnSharedResource.value = rwLockOnSharedResource.nextValue
println("Thread " + name + " is changing the value to " + rwLockOnSharedResource.value)
lock.unlock
println("Thread " + name + " is releasing the lock.")
Thread.sleep(3) // Generates output more similar to the problem description
}
}
}

object rwLockOnSharedResource {
private val maxValue = 10
private val randomVal = new Random
var value = nextValue

def nextValue = randomVal.nextInt(maxValue)

def main(args: Array[String]) = {
val rwLock = new ReentrantReadWriteLock(true)
val threadNames = List("one", "two", "three", "four", "five")
val readerCnt = threadNames.length * 2 / 3
val readerNames = threadNames.take(readerCnt)
val writerNames = threadNames.drop(readerCnt)

readerNames.foreach(new Reader(_, rwLock.readLock).start)
writerNames.foreach(new Writer(_, rwLock.writeLock).start)
}
}
python
#!/usr/bin/python
from threading import Thread, Lock
import time
thread_readers = ['one','two','three']
thread_writer = ['four','five']
lock = Lock()
value = 0

def Threadread(number):
global value
while True:
if lock.acquire(False):
print "Thread", number, "is taking the lock"
value += 1
print "Thread", number, "is changing the value to", value
print "Thread", number, "is releasing the lock."
lock.release()
else:
print "Thread", number, "tried to write to the value, but could not."
def Threadwrite(number):
global value
while True:
if lock.acquire(False):
print "Thread", number ,"four says that the value is", value
else:
print "Thread", number ,"tried to read the value, but could not."
if __name__ == "__main__":
for n in range(0,len(thread_readers)):
th =Thread(target=Threadread, args=(thread_readers[n],))
th.start()
for n in range(0,len(thread_writer)):
th =Thread(target=Threadwrite, args=(thread_writer[n],))
th.start()
cpp
class reader
{
string name_;
public:
reader(const string& name) : name_(name) {}

void operator()() {
for (;;this_thread::sleep(posix_time::milliseconds(1)))
{
shared_lock<shared_mutex> lock(m, try_to_lock);
lock_guard<mutex> cout_lock(io_m);
cout << "Thread " << name_;
if (lock)
cout << " says that the value is " << shared_value << "." << endl;
else
cout << " tried to read the value, but could not." << endl;
}
}
};

class writer
{
string name_;
public:
writer(const string& name) : name_(name) {}
void operator()() {
for (;;this_thread::sleep(posix_time::milliseconds(1)))
{
unique_lock<shared_mutex> lock(m, try_to_lock);
lock_guard<mutex> cout_lock(io_m);
cout << "Thread " << name_;
if (lock)
{
cout << " is taking the lock." << endl;
shared_value = rand() % 10;
cout << "Thread " << name_ << " is changing the value to " << shared_value << endl;
cout << "Thread " << name_ << " is releasing the lock. " << endl;
}
else
cout << " tried to write to the value, but could not." << endl;
}
}
};

int main()
{
thread t1 = thread(reader("one"));
thread t2 = thread(reader("two"));
thread t3 = thread(reader("three"));
thread t4 = thread(writer("four"));
writer("five")();
}
fsharp
open System.Threading
let lock = new ReaderWriterLock()
let mutable value = 0
let lockTimeout = 1

let ReaderThread t =
let random = new System.Random()
for i in 0 .. 100 do
try
lock.AcquireReaderLock(lockTimeout)
try
printfn "Thread %i says that the value is %i" t value
finally
lock.ReleaseReaderLock()
with _ ->
printfn "Thread %i tried to read the value, but could not (timeout)." t
Thread.Sleep(random.Next(50))

let WriterThread t =
let random = new System.Random()
for i in 0 .. 100 do
try
lock.AcquireWriterLock(lockTimeout)
try
value <- random.Next(10)
printfn "Thread %i is changing the value to %i" t value
Thread.MemoryBarrier()
finally
lock.ReleaseWriterLock()
printfn "Thread %i is releasing the lock." t
with _ ->
printfn "Thread %i tried to write the value, but could not (timeout)." t
Thread.Sleep(random.Next(50))

[| 0 .. 20 |]
|> Array.iter (fun t ->
async {
if t % 3 = 0 then
WriterThread t
else
ReaderThread t
}
|> Async.Start
)
ocaml

(* Compilation (native):
$ ocamlopt -thread unix.cmxa threads.cmxa threads_lock.ml -o threads_lock
*)

let value = ref 8
let mutex = Mutex.create ()

let create_writer i =
if not (Mutex.try_lock mutex) then begin
Printf.printf "Thread %d tried to write the value but could not.\n" i;
Mutex.lock mutex
end;
value := Random.int 10;
Printf.printf "Thread %d is changing the value to %d\n" i !value;
Mutex.unlock mutex;
Printf.printf "Thread %d is releasing the lock.\n" i

let create_reader i =
if not (Mutex.try_lock mutex) then begin
Printf.printf "Thread %d tried to read the value but could not.\n" i;
Mutex.lock mutex
end;
Printf.printf "Thread %d says that the value is %d\n" i !value;
Mutex.unlock mutex
;;

let thread_ids = Array.init 20 (fun i ->
Thread.create (if i mod 3 == 0 then create_writer else create_reader) i) in
Array.iter Thread.join thread_ids
clojure
; NOTE! Using explicit locking is NOT the Clojure way. It was done
; this way in order to comply exactly with the problem
; specification. Sharing data in Clojure would normally be done by
; using "atom", "agent" or "ref" depending on situation. None of those
; methods would ever result in the reader not being able to read (as
; required by the problem) since reading is wait-free in clojure.

(def *readers* (map #(agent %) '("one" "two" "three")))
(def *writers* (map #(agent %) '("four" "five")))
(def *mutex* (agent :unlocked))
(def *value* 0)

; mutex implementation
(defn lock [state who success-fn fail-fn]
(send who (if (= state :locked) fail-fn success-fn))
:locked)

(defn unlock [mutex]
:unlocked)

; Must be invoked with send-off since this handler blocks
(defn rand-sleep [state next-fn]
(Thread/sleep (rand-int 5))
(send *agent* next-fn)
state)

; Reader functions
(declare try-read)

(defn reader-got-lock [name]
(println (format "Thread %s says that the value is %d." name *value*))
(send *mutex* unlock)
(send-off *agent* rand-sleep try-read)
name)

(defn reader-did-not-get-lock [name]
(println (format "Thread %s tried to read the value, but could not." name))
(send-off *agent* rand-sleep try-read)
name)

(defn try-read [name]
(send *mutex* lock *agent* reader-got-lock reader-did-not-get-lock)
name)

; Writer functions
(declare try-write)

(defn writer-got-lock [name]
(println (format "Thread %s is taking the lock." name))
(def *value* (rand-int 10))
(println (format "Thread %s is changing the value to %d." name *value*))
(send *mutex* unlock)
(println (format "Thread %s is relasing the lock." name))
(send-off *agent* rand-sleep try-write)
name)

(defn writer-did-not-get-lock [name]
(println (format "Thread %s tried to write the value, but could not." name))
(send-off *agent* rand-sleep try-write)
name)

(defn try-write [name]
(send *mutex* lock *agent* writer-got-lock writer-did-not-get-lock)
name)

(dorun (map #(send % try-write) *writers*))
(dorun (map #(send % try-read) *readers*))

Separate user interaction and computation.

Allow your program to accept user interaction while conducting a long running computation.

Example:

Hello user! Please input a string to permute: (input thread)
abcdef
Passing on abcdef... (input thread)
Please input another string to permute: (input thread)
lol
Passing on lol... (input thread)
Done Work On abcdef! (worker thread)
["abcdef", "abcefd", ... ] (worker thread)
Please input another string to permute: (input thread)
EXIT
Quitting, I'll let my worker thread know... (input thread)
We'
re quitting! Alright! (worker thread)

--Notice, that this could be accomplished on the command line or within a GUI. The point is that computation and user interaction should take place on separate threads of control.
java
public class BackgroundComputation {

final protected Queue<Thread> threads = new ConcurrentLinkedQueue<Thread>() ;

public BackgroundComputation() {
BufferedReader r = new BufferedReader(new InputStreamReader(System.in));
try {
while (true) {
System.out.print("Enter string to permutate: ");
final String word = r.readLine();
if ("EXIT".equals(word) ) {
System.out.println("I'll let my worker thread know... (input thread)") ;
while (! threads.isEmpty())
threads.poll().stop(new ThreadDeath()) ;
break ;
}
Thread t = new Thread(new Runnable() {
public void run() {
try {
Set<String> permutationSet = new HashSet<String>();
for (int i = 0; i < word.length(); i++)
for (int j = i + 1; j <= word.length(); j++)
permutations("", word.substring(i, j), permutationSet);
System.out.println();
System.out.println("Received results: " + permutationSet);
System.out.print("Enter string to permutate: ");
} catch (ThreadDeath e) {
System.out.println("We're quitting! Alright!");
}
}

private void permutations(String prefix, String word, Set<String> permutations) {
int N = word.length();
if (N == 0)
permutations.add(prefix);
else
for (int i = 0; i < N; i++)
permutations(
prefix + word.charAt(i),
word.substring(0, i) + word.substring(i + 1, N),
permutations
);
}
});
t.start();
threads.add(t);
}
} catch (IOException ioe) {
System.out.println("IO error trying to read your name!");
System.exit(1);
}
}


public static void main(String[] args) {
new BackgroundComputation() ;
}
}
groovy
def threads = new ConcurrentLinkedQueue<Thread>()

void permutations(String prefix, String w, Set<String> permSet) {
int n = w.size()
if (!n) permSet << prefix
else n.times { i ->
permutations(prefix + w[i], w[0..<i] + w[i+1..<n], permSet)
}
}

println 'Welcome to the parallel permuter'
System.in.withReader { r ->
while (true) {
print 'Enter word:'
def word = r.readLine()
if (word == 'EXIT') {
while (!threads.isEmpty())
threads.poll().stop(new ThreadDeath())
break
} else
threads << Thread.start {
try {
def wordAns = [] as Set
for (int i = 0; i < word.size(); i++)
for (int j = i + 1; j <= word.size(); j++)
permutations("", word[i..<j], wordAns)
println '\nAnswer:' + wordAns
print 'Enter word:'
} catch (ThreadDeath td) {
println 'Thread aborted!'
}
}
}
}
scala
import scala.actors.Actor

object Worker extends Actor {
def perm(s: String): List[String] =
s.length match {
case 0 => Nil
case 1 => s :: Nil
case sLen => (0 to sLen-1).map(i => perm(s.take(i) + s.drop(i+1)).map(s(i) + _)).toList.flatten
}

def act() = react {
case "EXIT" =>
println("We're quitting! Alright!")
case (s: String) =>
val r = perm(s)
println("Done working on " + s + "!")
print("[ ")
r.foreach(s => print("\"" + s + "\", "))
println("]")
act()
}
}

object userInteractBackgroundCalc {
def main(args: Array[String]) {
print("Hello user! ")
Worker.start
var str = ""

do {
println("Please input a string to permute:")
str = readLine()
Worker ! str
} while (str != "EXIT")
}
}
cpp
class bg_worker
{
mutex bg_mutex_;
condition_variable work_present_;
deque<string> work_queue_;

result calc_perm(string s) {
result perms = result(new list<string>());

// sleep to simulate lots of work...
this_thread::sleep(posix_time::seconds(3));
sort(s.begin(), s.end());
do {
perms->push_back(s);
} while (next_permutation(s.begin(), s.end()));
return perms;
}

public:
void submit_work(const string &s) {
lock_guard<mutex> lock(bg_mutex_);
work_queue_.push_back(s);
work_present_.notify_one();
}

void operator()() {
for (;;) {
unique_lock<mutex> lock(bg_mutex_);
while (work_queue_.empty())
work_present_.wait(lock);
string s = work_queue_.front();
work_queue_.pop_front();
lock.unlock();

if (s == "EXIT") {
lock_guard<mutex> cout_lock(cout_mutex);
cout << "We're quitting! Alright!" << endl;
break;
}

result perm = calc_perm(s);
lock_guard<mutex> cout_lock(cout_mutex);
cout << "Done Work On " << s << "!" << endl;
cout << perm << endl;
}
}
};

int main()
{
bg_worker worker;
thread bg_thr(boost::ref(worker));
bool done = false;

{
lock_guard<mutex> cout_lock(cout_mutex);
cout << "Hello user! Please input a string to permute:" << endl;
}

while (!done)
{
string input;
cin >> input;
{
lock_guard<mutex> cout_lock(cout_mutex);
if (input == "EXIT") {
cout << "Quitting, I'll let my worker thread know..." << endl;
done = true;
} else {
cout << "Passing on " << input << "..." << endl;
cout << "Please input another string to permute:" << endl;
}
}
worker.submit_work(input);
}

bg_thr.join();
}
fsharp
open System

/// Computes all permutations of an array
let rec permute = function
| [| |] -> [| [| |] |]
| a ->
a
|> Array.mapi (fun i ai ->
Array.sub a 0 i
|> Array.append (Array.sub a (i + 1) (a.Length - i - 1))
|> permute
|> Array.map (fun perm -> Array.append [| ai |] perm)
)
|> Array.concat

/// Computes all permutations of a string
let permuteString (s: string) =
s.ToCharArray()
|> permute
|> Array.map (fun p -> new String(p))


type PermuteMessage =
| PermuteString of string
| Cancel

let mailbox = new MailboxProcessor<PermuteMessage>(fun inbox ->
let rec loop() =
async {
let! msg = inbox.Receive()
match msg with
| PermuteString s ->
printfn "[Worker] Starting to work on %s" s
let p = permuteString s
printfn "[Worker] Done my work on %s" s
let firstElems =
if s.Length > 4 then
let first = p |> Seq.truncate 4 |> Seq.toArray
String.Join(", ", first) + ", ..."
else
String.Join(", ", p)
printfn "[Worker] Result is %s" firstElems
return! loop()
| Cancel ->
printfn "[Worker] Nuff done, I'm quitting!"
return ()
}
loop()
)

do
printfn "[Input] Setting up worker."
mailbox.Start()
let loop = ref true
while !loop do
printfn "[Input] Please enter a word, or EXIT to exit"
let s = Console.ReadLine()
match s with
| "EXIT" ->
printfn "[Input] Sending worker the cancellation notice."
mailbox.Post(Cancel)
loop := false
| _ ->
printfn "[Input] Sending task to the worker."
mailbox.Post(PermuteString s)
ocaml
(* Compile (native):
$ ocamlopt -thread unix.cmxa threads.cmxa async_interface.ml -o async_interface
*)

module Mailbox =
struct

type 'a t = {
lock: Mutex.t;
notempty_condition: Condition.t;
queue: 'a Queue.t;
}

let create () = {
lock = Mutex.create ();
notempty_condition = Condition.create ();
queue = Queue.create ();
}

let add mb v =
Mutex.lock mb.lock;
Queue.add v mb.queue;
Condition.signal mb.notempty_condition;
Mutex.unlock mb.lock

let take mb =
Mutex.lock mb.lock;
while Queue.is_empty mb.queue do
Printf.printf "(waiting)\n%!";
Condition.wait mb.notempty_condition mb.lock
done;
let v = Queue.take mb.queue in
Mutex.unlock mb.lock;
v
end

type 'a orders =
Process of 'a
| Terminate

let permute_string s buf =
let len = String.length s in
let sep = ref "" in
let rec aux i =
if i = 0 then begin
Buffer.add_string buf !sep;
Buffer.add_char buf '"';
Buffer.add_string buf s;
Buffer.add_char buf '"';
sep := ","
end
else
let c = s.[i] in
for j = 0 to i - 1 do
s.[i] <- s.[j];
s.[j] <- c;
aux (i - 1);
s.[j] <- s.[i]
done;
s.[i] <- c;
aux (i - 1)
in
if len > 0 then
aux (len - 1)

let rec slave_loop mailbox =
match Mailbox.take mailbox with
| Process s ->
Printf.printf "Working on %s...%!" s;
let len = String.length s in
let fact n =
let rec aux i acc =
if i < 2 then acc
else aux (i - 1) (acc * i) in
aux n 1 in
(* Buffers reallocate as needed, but since we know the size beforehand... *)
let expected_output_size = (len + 3) * (fact len) + 2 in
let buf = Buffer.create expected_output_size in
Buffer.add_char buf '[';
permute_string s buf;
Buffer.add_string buf "]\n";
Printf.printf " Done Work On %s!\n" s;
Buffer.output_buffer stdout buf;
flush stdout;
slave_loop mailbox
| Terminate ->
Printf.printf "%s\n%!" "We're quitting! Alright!"


let rec master_loop mailbox article =
Printf.printf "Please input %s string to permute: %!" article;
let exit_string = "EXIT" in
let s =
try
read_line ()
with End_of_file -> exit_string in
if s = exit_string then begin
Printf.printf "%s\n%!" "Quitting, I'll let my worker thread know";
Mailbox.add mailbox Terminate
end
else begin
Printf.printf "Passing on %s...\n%!" s;
Mailbox.add mailbox (Process s);
master_loop mailbox "another"
end

let () =
let mailbox = Mailbox.create () in
let slave_thread_id = Thread.create slave_loop mailbox in

print_string "Hello user! ";
master_loop mailbox "a";

Thread.join slave_thread_id
clojure
(defn background-computation [_ s]
(let [res (permutations s)]
(println (format "Done Work On %s!" s))
(println res)))

(defn shutdown-app [_]
(println "We're quitting! Alright!")
(shutdown-agents))

(println "Hello user! Please input a string to permute: ")
(let [worker-agent (agent nil)]
(loop [input (str (read))]
(if (= input "EXIT")
(do (println "Quitting, I'll let my worker thread know...")
(send worker-agent shutdown-app))
(do (println (format "Passing on %s..." input))
(send worker-agent background-computation input)
(println "Please input another string to permute: ")
(recur (str (read)))))))
fantom
using concurrent
class Main
{
static Void main()
{
worker := Actor(ActorPool()) |Str s|
{
result := permute(s.chars).map { Str.fromChars(it) }
echo("Done Work On $s!")
echo(result)
}

Env.cur.out.writeChars("Hello, user! Please input a string to permute: ").flush
Env.cur.in.eachLine |line| {
echo("Passing on $line ...")
worker.send(line)
Env.cur.out.writeChars("Please input another string to permute: ").flush
}
}

static Obj[][] permute(Obj[] list, Obj[] prefix := [,])
{
list.isEmpty ?
[prefix] :
list.reduce([,]) |Obj[] r, Obj item, Int i -> Obj[]| {
r.addAll(permute(list.dup { removeAt(i) }, prefix.dup.add(item)))
}
}
}