Building H2O

medium concurrency semaphore synchronization

Problem

There are hydrogen and oxygen threads calling hydrogen() and oxygen(). To form water molecules, atoms must bond in groups of exactly two hydrogen and one oxygen. Every group of three threads must release together before any thread from the next molecule proceeds. Given an input string of H and O with twice as many H as O, output any ordering where every consecutive group of three contains exactly two H and one O.

Inputwater = "HOH"

Output"HHO"

Two H and one O are gathered, then released together as one molecule. "HOH" or "OHH" are equally valid.

water (H and O only, 2× as many H as O)

from threading import Semaphore, Lock

class H2O:
    def __init__(self):
        self.h = Semaphore(2)   # up to 2 H may enter
        self.o = Semaphore(0)   # O blocked until 2 H ready
        self.barrier = 0        # H arrived in current molecule
        self.lock = Lock()      # guards the barrier counter

    def hydrogen(self, releaseHydrogen):
        self.h.acquire()
        releaseHydrogen()       # emit one "H"
        with self.lock:         # atomic increment-and-check
            self.barrier += 1
            if self.barrier == 2:   # second H signals O
                self.o.release()

    def oxygen(self, releaseOxygen):
        self.o.acquire()
        releaseOxygen()         # emit one "O"
        self.barrier = 0
        self.h.release()        # refill 2 H permits
        self.h.release()

// JS is single-threaded, so we model the semaphores with a
// Promise-based gate that actually blocks: acquire() resolves
// only once a permit is available, release() hands one out.
class Semaphore {
  constructor(permits) {
    this.permits = permits;
    this.waiters = [];
  }
  acquire() {
    if (this.permits > 0) { this.permits--; return Promise.resolve(); }
    return new Promise((resolve) => this.waiters.push(resolve));
  }
  release() {
    const next = this.waiters.shift();
    if (next) next();         // wake one waiter
    else this.permits++;
  }
}

class H2O {
  constructor() {
    this.h = new Semaphore(2);   // up to 2 H may enter
    this.o = new Semaphore(0);   // O blocked until 2 H ready
    this.barrier = 0;            // H arrived in current molecule
  }
  async hydrogen(releaseHydrogen) {
    await this.h.acquire();      // blocks until an H permit is free
    releaseHydrogen();           // emit one "H"
    this.barrier++;
    if (this.barrier === 2) this.o.release();  // second H signals O
  }
  async oxygen(releaseOxygen) {
    await this.o.acquire();      // blocks until two H have emitted
    releaseOxygen();             // emit one "O"
    this.barrier = 0;
    this.h.release();            // refill 2 H permits
    this.h.release();
  }
}

import java.util.concurrent.Semaphore;
import java.util.concurrent.atomic.AtomicInteger;

class H2O {
    private Semaphore h = new Semaphore(2); // up to 2 H may enter
    private Semaphore o = new Semaphore(0); // O blocked until 2 H
    private AtomicInteger barrier = new AtomicInteger(0); // H in current molecule

    public void hydrogen(Runnable releaseHydrogen) throws InterruptedException {
        h.acquire();
        releaseHydrogen.run();   // emit one "H"
        if (barrier.incrementAndGet() == 2) o.release();  // atomic second-H check
    }

    public void oxygen(Runnable releaseOxygen) throws InterruptedException {
        o.acquire();
        releaseOxygen.run();     // emit one "O"
        barrier.set(0);
        h.release(2);            // refill 2 H permits
    }
}

#include <semaphore.h>
#include <mutex>
#include <functional>

class H2O {
    sem_t h, o;     // h starts at 2, o starts at 0
    int barrier = 0;
    std::mutex bm;  // guards the barrier counter
public:
    H2O() { sem_init(&h, 0, 2); sem_init(&o, 0, 0); }

    void hydrogen(std::function<void()> releaseHydrogen) {
        sem_wait(&h);
        releaseHydrogen();       // emit one "H"
        {
            std::lock_guard<std::mutex> g(bm);  // atomic increment-and-check
            if (++barrier == 2) sem_post(&o);  // second H signals O
        }
    }

    void oxygen(std::function<void()> releaseOxygen) {
        sem_wait(&o);
        releaseOxygen();         // emit one "O"
        {
            std::lock_guard<std::mutex> g(bm);
            barrier = 0;
        }
        sem_post(&h); sem_post(&h);  // refill 2 H permits
    }
};

Explanation

Many threads call hydrogen() and oxygen() at once, but a water molecule needs exactly two H and one O. The job is to make threads wait for each other so they only proceed in valid groups of three. We do this with two semaphores, which are just permit-counters that block when they hit zero.

The H semaphore starts with 2 permits, so at most two hydrogen threads can enter at a time. The O semaphore starts at 0, so any oxygen thread is blocked immediately until something releases a permit to it.

Each hydrogen thread acquires an H permit, emits "H", and increments barrier. When the second H arrives (barrier == 2), it releases one O permit — the signal that two hydrogens are ready and an oxygen may now run.

The oxygen thread, once unblocked, emits "O", resets barrier to 0, and releases two H permits with self.h.release() twice. That refills the H semaphore so the next molecule's two hydrogens can enter, and the cycle repeats.

Example: with input "HOH", two H threads pass the Semaphore(2) and emit H, H; the second one releases O; the O thread then emits O and refills the permits — producing one valid molecule like "HHO".

Time: O(n) Space: O(1)