1195. Fizz Buzz Multithreaded

Description

You have the four functions:

printFizz that prints the word "fizz" to the console,
printBuzz that prints the word "buzz" to the console,
printFizzBuzz that prints the word "fizzbuzz" to the console, and
printNumber that prints a given integer to the console.

You are given an instance of the class FizzBuzz that has four functions: fizz, buzz, fizzbuzz and number. The same instance of FizzBuzz will be passed to four different threads:

Thread A: calls fizz() that should output the word "fizz".
Thread B: calls buzz() that should output the word "buzz".
Thread C: calls fizzbuzz() that should output the word "fizzbuzz".
Thread D: calls number() that should only output the integers.

Modify the given class to output the series [1, 2, "fizz", 4, "buzz", ...] where the i^th token (1-indexed) of the series is:

"fizzbuzz" if i is divisible by 3 and 5,
"fizz" if i is divisible by 3 and not 5,
"buzz" if i is divisible by 5 and not 3, or
i if i is not divisible by 3 or 5.

Implement the FizzBuzz class:

FizzBuzz(int n) Initializes the object with the number n that represents the length of the sequence that should be printed.
void fizz(printFizz) Calls printFizz to output "fizz".
void buzz(printBuzz) Calls printBuzz to output "buzz".
void fizzbuzz(printFizzBuzz) Calls printFizzBuzz to output "fizzbuzz".
void number(printNumber) Calls printnumber to output the numbers.

Example 1:

Input: n = 15
Output: [1,2,"fizz",4,"buzz","fizz",7,8,"fizz","buzz",11,"fizz",13,14,"fizzbuzz"]

Example 2:

Input: n = 5
Output: [1,2,"fizz",4,"buzz"]

Constraints:

1 <= n <= 50

Solutions

This problem is designed to be solved using multiple threads, where each thread is responsible for printing either numbers, “fizz”, “buzz”, or “fizzbuzz”. The main challenge is ensuring that the correct function is called for each number in sequence, despite the asynchronous nature of threads.

Code Explanation:

Initialization (__init__ method):
- self.n: The last number in the sequence that needs to be printed.
- self.fizzSemaphore, self.buzzSemaphore, self.fizzbuzzSemaphore, and self.numberSemaphore: Semaphores are used to control the execution flow of the threads. Each semaphore corresponds to one of the four possible print actions. The numberSemaphore is initially set to 1 to allow the sequence to start with the first number, while the others are set to 0 because they need to be triggered by the number sequence logic.
The fizz, buzz, fizzbuzz, and number methods: Each method is designed to be run in its own thread. They use semaphores to synchronize access to the shared resource (in this case, the console or standard output) to ensure that values are printed in the correct order.
- fizz method: Waits for the fizzSemaphore to be released (i.e., a number divisible by 3 but not by 5 is encountered) and then prints “fizz”. After printing, it releases the numberSemaphore to proceed with the sequence.
- buzz method: Similar to the fizz method but for numbers divisible by 5 but not by 3.
- fizzbuzz method: Waits for the fizzbuzzSemaphore to be released (i.e., a number divisible by both 3 and 5 is encountered) and then prints “fizzbuzz”. It then releases the numberSemaphore.
- number method: This is where the sequence logic is implemented. For each number from 1 to n, it first acquires the numberSemaphore to ensure orderly access. It then checks the divisibility of the current number to determine which semaphore to release next, allowing the corresponding method to print the appropriate value. If the number does not meet any special criteria (not divisible by 3 or 5), it prints the number itself and releases the numberSemaphore to continue the sequence.

How It Works Together:

The number method controls the flow of the program by releasing semaphores based on the divisibility of each number in the sequence. This ensures that only the correct thread is active at any given time for each number in the sequence.
The semaphores act as locks that prevent threads from proceeding until it’s their turn, ensuring the correct order of execution and preventing race conditions or incorrect output order.
This solution elegantly uses semaphores for synchronization between threads, allowing for a clear separation of logic and responsibilities among the threads.

class FizzBuzz {
    private int n;

    public FizzBuzz(int n) {
        this.n = n;
    }

    private Semaphore fSema = new Semaphore(0);
    private Semaphore bSema = new Semaphore(0);
    private Semaphore fbSema = new Semaphore(0);
    private Semaphore nSema = new Semaphore(1);

    // printFizz.run() outputs "fizz".
    public void fizz(Runnable printFizz) throws InterruptedException {
        for (int i = 3; i <= n; i = i + 3) {
            if (i % 5 != 0) {
                fSema.acquire();
                printFizz.run();
                nSema.release();
            }
        }
    }

    // printBuzz.run() outputs "buzz".
    public void buzz(Runnable printBuzz) throws InterruptedException {
        for (int i = 5; i <= n; i = i + 5) {
            if (i % 3 != 0) {
                bSema.acquire();
                printBuzz.run();
                nSema.release();
            }
        }
    }

    // printFizzBuzz.run() outputs "fizzbuzz".
    public void fizzbuzz(Runnable printFizzBuzz) throws InterruptedException {
        for (int i = 15; i <= n; i = i + 15) {
            fbSema.acquire();
            printFizzBuzz.run();
            nSema.release();
        }
    }

    // printNumber.accept(x) outputs "x", where x is an integer.
    public void number(IntConsumer printNumber) throws InterruptedException {
        for (int i = 1; i <= n; i++) {
            nSema.acquire();
            if (i % 3 == 0 && i % 5 == 0) {
                fbSema.release();
            } else if (i % 3 == 0) {
                fSema.release();
            } else if (i % 5 == 0) {
                bSema.release();
            } else {
                printNumber.accept(i);
                nSema.release();
            }
        }
    }
}

class FizzBuzz {
private:
    std::mutex mtx;
    atomic<int> index;
    int n;

    // 这里主要运用到了C++11中的RAII锁(lock_guard)的知识。
    // 需要强调的一点是，在进入循环后，要时刻不忘加入index <= n的逻辑
public:
    FizzBuzz(int n) {
        this->n = n;
        index = 1;
    }

    void fizz(function<void()> printFizz) {
        while (index <= n) {
            std::lock_guard<std::mutex> lk(mtx);
            if (0 == index % 3 && 0 != index % 5 && index <= n) {
                printFizz();
                index++;
            }
        }
    }

    void buzz(function<void()> printBuzz) {
        while (index <= n) {
            std::lock_guard<std::mutex> lk(mtx);
            if (0 == index % 5 && 0 != index % 3 && index <= n) {
                printBuzz();
                index++;
            }
        }
    }

    void fizzbuzz(function<void()> printFizzBuzz) {
        while (index <= n) {
            std::lock_guard<std::mutex> lk(mtx);
            if (0 == index % 15 && index <= n) {
                printFizzBuzz();
                index++;
            }
        }
    }

    void number(function<void(int)> printNumber) {
        while (index <= n) {
            std::lock_guard<std::mutex> lk(mtx);
            if (0 != index % 3 && 0 != index % 5 && index <= n) {
                printNumber(index);
                index++;
            }
        }
    }
};

from threading import Semaphore

class FizzBuzz: # semaphore
    def __init__(self, n: int):
        self.n = n
        self.fizzSemaphore = Semaphore(0)
        self.buzzSemaphore = Semaphore(0)
        self.fizzbuzzSemaphore = Semaphore(0)
        self.numberSemaphore = Semaphore(1)

    # printFizz() outputs "fizz"
    def fizz(self, printFizz: 'Callable[[], None]') -> None:
        for i in range(3, self.n + 1, 3):
            if i % 5 != 0:
                self.fizzSemaphore.acquire()
                printFizz()
                self.numberSemaphore.release()

    # printBuzz() outputs "buzz"
    def buzz(self, printBuzz: 'Callable[[], None]') -> None:
        for i in range(5, self.n + 1, 5):
            if i % 3 != 0:
                self.buzzSemaphore.acquire()
                printBuzz()
                self.numberSemaphore.release()

    # printFizzBuzz() outputs "fizzbuzz"
    def fizzbuzz(self, printFizzBuzz: 'Callable[[], None]') -> None:
        for i in range(15, self.n + 1, 15):
            self.fizzbuzzSemaphore.acquire()
            printFizzBuzz()
            self.numberSemaphore.release()

    # printNumber(x) outputs "x", where x is an integer.
    def number(self, printNumber: 'Callable[[int], None]') -> None:
        for i in range(1, self.n + 1):
            self.numberSemaphore.acquire()
            if i % 15 == 0:
                self.fizzbuzzSemaphore.release()
            elif i % 3 == 0:
                self.fizzSemaphore.release()
            elif i % 5 == 0:
                self.buzzSemaphore.release()
            else:
                printNumber(i)
                self.numberSemaphore.release()


##########

# ref: https://leetcode.com/problems/fizz-buzz-multithreaded/discuss/542960/python-greater99.28-a-standard-Lock()-based-solution-with-detailed-explanation

import threading

class FizzBuzz: # lock
    def __init__(self, n: int):
        self.n = n
        self.fizz_lock = threading.Lock()
        self.buzz_lock = threading.Lock()
        self.fizzbuzz_lock = threading.Lock()
        self.fizz_lock.acquire()
        self.buzz_lock.acquire()
        self.fizzbuzz_lock.acquire()
        self.main_lock = threading.Lock()

    def fizz(self, printFizz: 'Callable[[], None]') -> None:
        while True:
            self.fizz_lock.acquire()
            if self.n == 0 :
                return
            printFizz()
            self.main_lock.release()

    def buzz(self, printBuzz: 'Callable[[], None]') -> None:
        while True:
            self.buzz_lock.acquire()
            if self.n == 0:
                return
            printBuzz()
            self.main_lock.release()

    def fizzbuzz(self, printFizzBuzz: 'Callable[[], None]') -> None:
        while True:
            self.fizzbuzz_lock.acquire()
            if self.n == 0:
                return
            printFizzBuzz()
            self.main_lock.release()

    def number(self, printNumber: 'Callable[[int], None]') -> None:
        for i in range(1, self.n+1):
            self.main_lock.acquire()
            if i % 15 == 0:
                self.fizzbuzz_lock.release()
            elif i % 3 == 0:
                self.fizz_lock.release()
            elif i % 5 == 0:
                self.buzz_lock.release()
            else:
                printNumber(i)
                self.main_lock.release()

        self.main_lock.acquire()
        self.n = 0
        self.fizz_lock.release()
        self.buzz_lock.release()
        self.fizzbuzz_lock.release()
        return

1195 - Fizz Buzz Multithreaded

1195. Fizz Buzz Multithreaded

Description

Solutions

Code Explanation:

How It Works Together:

All Problems

All Solutions

Welcome to Subscribe On Youtube

1195. Fizz Buzz Multithreaded

Description

Solutions

Code Explanation:

How It Works Together:

All Problems

All Solutions