The Dota2 senate consists of senators coming from two parties. Now the Senate wants to decide on a change in the Dota2 game. The voting for this change is a round-based procedure. In each round, each senator can exercise one of the two rights:
Given a string senate representing each senator's party belonging. The character 'R' and 'D' represent the Radiant party and the Dire party. Then if there are n senators, the size of the given string will be n.
The round-based procedure starts from the first senator to the last senator in the given order. This procedure will last until the end of voting. All the senators who have lost their rights will be skipped during the procedure.
Suppose every senator is smart enough and will play the best strategy for his own party. Predict which party will finally announce the victory and change the Dota2 game. The output should be "Radiant" or "Dire".
Example 1:
Input: senate = "RD"
Output: "Radiant"
Explanation:
The first senator comes from Radiant and he can just ban the next senator's right in round 1.
And the second senator can't exercise any rights anymore since his right has been banned.
And in round 2, the first senator can just announce the victory since he is the only guy in the senate who can vote.
Example 2:
Input: senate = "RDD"
Output: "Dire"
Explanation:
The first senator comes from Radiant and he can just ban the next senator's right in round 1.
And the second senator can't exercise any rights anymore since his right has been banned.
And the third senator comes from Dire and he can ban the first senator's right in round 1.
And in round 2, the third senator can just announce the victory since he is the only guy in the senate who can vote.
Constraints:
The key to solving this problem is to simulate the voting process using queues. Here’s a step-by-step breakdown:
🤖Initialization:
🤖Simulation Loop:
🤖Determine the Winner:
function predictPartyVictory(senate):
radiantQueue = empty queue
direQueue = empty queue
senateLength = length of senate
// Initialize queues
for i = 0 to senateLength - 1:
if senate[i] == 'R':
enqueue i into radiantQueue
else:
enqueue i into direQueue
// Simulate voting
while radiantQueue is not empty AND direQueue is not empty:
radiantIndex = front of radiantQueue
direIndex = front of direQueue
if radiantIndex < direIndex:
dequeue from direQueue
enqueue (radiantIndex + senateLength) into radiantQueue
dequeue from radiantQueue
else:
dequeue from radiantQueue
enqueue (direIndex + senateLength) into direQueue
dequeue from direQueue
// Determine winner
if radiantQueue is not empty:
return "Radiant"
else:
return "Dire"
class Solution:
def predictPartyVictory(self, senate: str) -> str:
"""
Predicts the winner of a senate vote based on the given rules.
Args:
senate: A string representing the senate, where 'R' denotes Radiant and 'D' denotes Dire.
Returns:
"Radiant" if Radiant wins, "Dire" if Dire wins.
"""
radiant = [] # Queue to store the indices of Radiant senators
dire = [] # Queue to store the indices of Dire senators
n = len(senate) # Length of the senate string
# Initialize the queues with the indices of each senator
for i, s in enumerate(senate):
if s == 'R':
radiant.append(i)
else:
dire.append(i)
# Simulate the voting process until one party has no senators left
while radiant and dire:
# Check which senator is next in line
if radiant[0] < dire[0]:
# Radiant senator bans the next Dire senator
dire.pop(0) # Remove the next Dire senator from the queue
# Radiant senator is added back to the queue, but with an updated index to simulate the circular nature
radiant.append(radiant[0] + n)
radiant.pop(0) #remove the current radiant senator
else:
# Dire senator bans the next Radiant senator
radiant.pop(0) #Remove the next radiant senator from the queue.
# Dire senator is added back to the queue, but with an updated index to simulate the circular nature
dire.append(dire[0] + n)
dire.pop(0) #remove the current dire senator.
# Determine the winner based on which queue is not empty
return "Radiant" if radiant else "Dire"
function predictPartyVictory(senate: string): string {
// Queues to store the indices of Radiant and Dire senators
const radiant: number[] = [];
const dire: number[] = [];
const n: number = senate.length; // Length of the senate string
// Populate the queues with senator indices
for (let i = 0; i < n; i++) {
if (senate[i] === 'R') {
radiant.push(i);
} else {
dire.push(i);
}
}
// Simulate the voting process
while (radiant.length > 0 && dire.length > 0) {
// Check which senator is next in line
if (radiant[0] < dire[0]) {
// Radiant senator bans the next Dire senator
dire.shift(); // Remove the next Dire senator
// Radiant senator is added back to the queue, with updated index
radiant.push(radiant.shift()! + n); //Add the radiant senator to the end of the queue.
} else {
// Dire senator bans the next Radiant senator
radiant.shift(); // Remove the next Radiant senator
// Dire senator is added back to the queue, with updated index
dire.push(dire.shift()! + n); //Add the dire senator to the end of the queue.
}
}
// Determine the winner based on which queue is not empty
return radiant.length > 0 ? "Radiant" : "Dire";
}
func predictPartyVictory(senate string) string {
// Queues to store the indices of Radiant and Dire senators
radiant := []int{}
dire := []int{}
n := len(senate) // Length of the senate string
// Populate the queues with senator indices
for i, s := range senate {
if s == 'R' {
radiant = append(radiant, i)
} else {
dire = append(dire, i)
}
}
// Simulate the voting process
for len(radiant) > 0 && len(dire) > 0 {
// Check which senator is next in line
if radiant[0] < dire[0] {
// Radiant senator bans the next Dire senator
dire = dire[1:] // Remove the next Dire senator
// Radiant senator is added back to the queue, with updated index
radiant = append(radiant, radiant[0]+n) // Add the radiant senator to the end of the queue.
radiant = radiant[1:] //remove the first radiant senator.
} else {
// Dire senator bans the next Radiant senator
radiant = radiant[1:] // Remove the next Radiant senator
// Dire senator is added back to the queue, with updated index
dire = append(dire, dire[0]+n) // Add the dire senator to the end of the queue.
dire = dire[1:] // remove the first dire senator.
}
}
// Determine the winner based on which queue is not empty
if len(radiant) > 0 {
return "Radiant"
}
return "Dire"
}
If you liked this article I’d appreciate an upvote or a comment. That helps me improve the quality of my posts as well as getting to know more about you, my dear reader.
Muchas gracias!
Follow me for more content like this.
X | PeakD | Rumble | YouTube | Linked In | GitHub | PayPal.me
Down below you can find other ways to tip my work.
BankTransfer: "710969000019398639", // CLABE
BAT: "0x33CD7770d3235F97e5A8a96D5F21766DbB08c875",
ETH: "0x33CD7770d3235F97e5A8a96D5F21766DbB08c875",
BTC: "33xxUWU5kjcPk1Kr9ucn9tQXd2DbQ1b9tE",
ADA: "addr1q9l3y73e82hhwfr49eu0fkjw34w9s406wnln7rk9m4ky5fag8akgnwf3y4r2uzqf00rw0pvsucql0pqkzag5n450facq8vwr5e",
DOT: "1rRDzfMLPi88RixTeVc2beA5h2Q3z1K1Uk3kqqyej7nWPNf",
DOGE: "DRph8GEwGccvBWCe4wEQsWsTvQvsEH4QKH",
DAI: "0x33CD7770d3235F97e5A8a96D5F21766DbB08c875"