Overview

The Leap Year Detector problem involves identifying leap years from a given sequence. In general, a leap year is one that is divisible by 4. However, years divisible by 100 are not leap years unless they are also divisible by 400.

For instance, the year 2000 was a leap year because, even though it's divisible by 100, it's also divisible by 400. However, the year 1900 was not a leap year because, while it is divisible by 100, it is not divisible by 400.

In this multithreaded challenge, we aim to evaluate the sequence of years in two separate threads simultaneously:

1. Thread A will detect and print the leap years.
2. Thread B will detect and print the non-leap years.

A key challenge here is ensuring the years are printed in sequence. For instance, given the years [2000, 2001, 2002, 2003, 2004], the desired output might look like:

2000: Leap Year
2001: Non-Leap Year
2002: Non-Leap Year
2003: Non-Leap Year
2004: Leap Year

However, due to the concurrent nature of threads, without appropriate synchronization, we might end up with a jumbled output.

Concurrency (Pseudocode Explanation)

Given the concurrent nature of this task, we need to establish a synchronization mechanism to ensure that the years are evaluated and printed in sequence.

We can use two synchronization flags/signals:

1. leapYearTurn: Indicates whether it's Thread A's turn to check and print.
2. nonLeapYearTurn: Indicates whether it's Thread B's turn to check and print.

sqlCopy codesequence_of_years = [...]
leapYearTurn = true
nonLeapYearTurn = false

Function CheckLeapYear(year):
    IF year MOD 4 == 0 AND (year MOD 100 != 0 OR year MOD 400 == 0):
        return true
    ELSE:
        return false

Thread A:
    FOR each year in sequence_of_years:
        WAIT until leapYearTurn is true
        IF CheckLeapYear(year):
            print year + ": Leap Year"
            leapYearTurn = false
            nonLeapYearTurn = true

Thread B:
    FOR each year in sequence_of_years:
        WAIT until nonLeapYearTurn is true
        IF NOT CheckLeapYear(year):
            print year + ": Non-Leap Year"
            leapYearTurn = true
            nonLeapYearTurn = false

In the pseudocode above, the two threads evaluate each year in sequence. Thread A waits for its turn (leapYearTurn) to check for leap years, while Thread B waits for its turn (nonLeapYearTurn) to check for non-leap years. Once a thread completes its check for a specific year, it toggles the flags to signal the other thread. This mechanism ensures that the years are printed in sequence.

Algorithm Walkthrough

We have a list of years: [1999, 2000, 2001].

Initialization:

• We have two boolean flags, leapYearTurn and nonLeapYearTurn.
• Initially, leapYearTurn is set to true and nonLeapYearTurn to false.

Thread A (Leap Year Detector):

• Thread A starts and looks at the first year, 1999.
• It checks if it's its turn (leapYearTurn == true), which it is, so it proceeds.
• It applies the leap year check on 1999:
  • 1999 is not divisible by 4, so it’s not a leap year.
  • Thread A doesn't print anything since it's not a leap year, but it sets leapYearTurn to false and nonLeapYearTurn to true to pass the turn to Thread B.

Thread B (Non-Leap Year Detector):

• Thread B gets its turn because nonLeapYearTurn is now true.
• It looks at 1999, confirms it's not a leap year (which is its responsibility to print), and prints "1999: Non-Leap Year".
• It then sets leapYearTurn to true and nonLeapYearTurn to false to give the turn back to Thread A.

Thread A:

• Now it's 2000, and leapYearTurn is true again, so Thread A checks it.
• 2000 is divisible by 4 and also by 400, so it is a leap year.
• Thread A prints "2000: Leap Year" and toggles the flags for Thread B’s turn.

Thread B:

• Thread B sees nonLeapYearTurn is false and waits.

Thread A:

• Moves to 2001, sees that leapYearTurn is true.
• It checks 2001 and determines it's not a leap year.
• Again, Thread A does not print anything and passes the turn to Thread B by toggling the flags.

Thread B:

• Thread B wakes up with nonLeapYearTurn true, checks 2001, sees it's not a leap year, and prints "2001: Non-Leap Year".
• Toggles the flags for Thread A.The process continues in this manner, with each thread taking turns and only acting when it's their turn. This ensures that the years are printed in the correct order, alternating between leap years and non-leap years, even though two threads are operating concurrently.