How I react to algos
This is the third article in a series aiming to familiarize you with REACTO as a method of solving any algorithm problem. Today we are working on an algo found on AlgoExpert called tournamentWinner.
Check out the previous article in the series, Pig Latin
This is REACTO
REACTO is an acronym that represents the method we will use in solving this problem. As a reminder, these are the steps:
- R: Restate
- E: Example
- A: Approach
- C: Code
- T: Test
- O: Optimize
Let's stick to this order and get started!
The Prompt
A tournament just ended and you need to find the winner. Each round has a pair of teams facing off and only one team wins. The winning team is awarded 3 points. Create a function called
tournamentWinnerthat takes two arrays as input and return the winner of the tournament. The first array, calledcompetitions, consists of arrays of two team names that faced each other in the round and will be in the form["homeTeam", "awayTeam"]. The second argument is an array calledresultswhose elements will be either a1or a0. The same index at both arrays shows the teams that faced off and which of the teams won for that round. For example, at indexi, the teams atcompetitions[i]competed against each other and the team represented byresults[i]is the winner from that pair. Note thatresults[i]will be either a1or a0, with1representing a win for thehomeTeam, and a0representing a win for theawayTeam.
R: Restate the prompt
Now we will restate the prompt, which is important especially if you were given the prompt verbally.
/*
R: Restate
Given two arrays as input, one an array of team pairs
(each element is an array of two strings), and the other
an array of integers stating the winner of the pair, return
the team with the most points. The winning team in a pairing
is awarded 3 points while the other team in the pair is
awarded 0 points. The team with the most points after all
pairs are considered is the winner of the tournament. Each
team pairing from the first array has a home and an away
team. The second input array is the results array, contains
numbers of either 0 or 1, where 0 means the away team wins in
the pair and 1 means the home team wins for the pair.
*/
Now's a good time for questions and I happen to have one:
Q: Will a team face the same team twice?\
A: No, each pairing is unique.
That was probably a given, but better to not assume!
E: Examples
E is for examples and will usually be provided. If they are discussed verbally don't forget to write them down for reference because it could help guide in testing later.
Below we will see the two input arrays labeled competitions and results.
sample input
competitions = [
["Mice", "Pandas"],
["Pandas", "Pythons"],
["Pythons", "Mice"],
];
results = [1, 0, 0];
sample output
"Mice";
We can see why Mice is the winning team. Mice beats Pandas, Pythons beat Pandas, Mice beat Pythons. The score would look like this:
Mice - 6 points\
Pandas - 0 points\
Pythons - 3 points
So team Mice wins in this example!
A: Approach
Here is where we plan our approach. We should keep the code to a minimum and really think through the steps we will take to reach a solution.
On my first attempt this was my thought process:
- create an object to act as a score keeper.
- declare a variable to hold the index so it can be used on both input arrays simultaneously
- declare another variable to hold the current high score until iteration over the arrays ends, can be initiated with value of 0
- use a while loop to iterate over both the arrays
- declare a variable to hold the string name of the tournament winner, and update it while looping
That's a general view of how I will approach this problem. It will be more of a brute force tactic. Usually I want to get to a solution first before I think of optimization. Remember optimization is the last step of REACTO anyway. As skills develop we may start thinking about more efficient methods first, but I expect any beginner to feel more comofortable with this approach as I am.
So, if we are using a while loop what should we include inside of it?
- loop only while the index value is less than the length of either of the input arrays (the arrays have the same amount of elements)
- declare a home and away variable and assign to them the values from the competitions array (
const [home, away] = competitions[indexValue]) - declare variable for winner of the pair and assign it the integer value from the results array at the given index value
- create conditional statements:
- if winner is 0 (0 is the away team), then add entry to score keeper object with team name and value of 3... but if the already exists we just set value to += 3
- repeat for winner being 1
- increase the index value at the end of the loop
- after the while loop we can iterate over the score keeping object
- start with a conditional: if the value of current key is greater than the value of the high score variable, set the value of high score to the current key's value AND set the value of the tournament winner variable to the current key
- lastly, return the string value from the tournament winner variable
Okay!! That was quite verbose, but it helps to be detailed in this step. My preferred method of writing an approach is to write them in as a comment inside of the function and use them as a guide for the code. Let's add the above as a comment first and then we will copy it off and paste it into our function when we are ready to code.
/*
A: Approach
- create function tournamentWinner() that takes two arrays as args; competitions and results. <<-- forgot to add this
Inside of the function:
- create an object to act as a score keeper.
- declare a variable to hold the index so it can be used on both input arrays simultaneously, set initial val to 0
- declare another variable to hold the current high score until iteration over the arrays ends, can be initiated with value of 0
- declare a variable to hold the string name of the tournament winner, and update it while looping
- use a while loop to iterate over both the arrays
- loop only while the index value is less than the length of either of the input arrays (the arrays have the same amount of elements)
- declare a home and away variable and assign to them the values from the competitions array (`const [home, away] = competitions[indexValue]`)
- declare variable for winner of the pair and assign it the integer value from the results array at the given index value
- create conditional statements:
- if winner is 0 (0 is the away team), then add entry to score keeper object with team name and value of 3... but if the already exists we just set value to += 3
- repeat for winner being 1
- increase the index value at the end of the loop
- after the while loop we can iterate over the score keeping object
- start with a conditional: if the value of current key is greater than the value of the high score variable, set the value of high score to the current key's value AND set the value of the tournament winner variable to the current key
- lastly, return the string value from the tournament winner variable
*/
I added some more to those comments for clarity. And yeah, it looks rather clunky but we will get tp tidying later. Now it is time to code.
C: Code
Time to code! 🧑💻
If you've read my other articles in this series you'll know that I like to copy my Approach comments and paste them into my code as a guide.
// create function tournamentWinner() that takes two arrays as args; competitions and results. <<-- forgot to add this
/* Inside of the function: */
// create an object to act as a score keeper.
// declare a variable to hold the index so it can be used on both input arrays simultaneously, set initial val to 0
// declare another variable to hold the current high score until iteration over the arrays ends, can be initiated with value of 0
// declare a variable to hold the string name of the tournament winner, and update it while looping
// use a while loop to iterate over both the arrays
// loop only while the index value is less than the length of either of the input arrays (the arrays have the same amount of elements)
// declare a home and away variable and assign to them the values from the competitions array (`const [home, away] = competitions[indexValue]`)
// declare variable for winner of the pair and assign it the integer value from the results array at the given index value
// create conditional statements:
//// if winner is 0 (0 is the away team), then add entry to score keeper object with team name and value of 3... but if the already exists we just set value to += 3
//// repeat for winner being 1
// increase the index value at the end of the loop
// after the while loop we can iterate over the score keeping object
//// start with a conditional: if the value of current key is greater than the value of the high score variable, set the value of high score to the current key's value AND set the value of the tournament winner variable to the current key
// lastly, return the string value from the tournament winner variable
The comments have been reformatted into single line comments so that they may be moved around easily. Now that the approach is laid out in the coding environment of choice we can start writing JavaScript (or your language of choice). What you will see next are the comments and their translation into JavaScript.
// create function tournamentWinner() that takes two arrays as args; competitions and results.
function tournamentWinner(competitions, results) {
/* Inside of the function: */
// create an object to act as a score keeper.
let leaderboard = {};
// declare a variable to hold the index so it can be used on both input arrays simultaneously, set initial val to 0
let tournamentIdx = 0;
// declare another variable to hold the current high score until iteration over the arrays ends, can be initiated with value of 0
let highScore = 0;
// declare a variable to hold the string name of the tournament winner, and update it while looping
let champ;
// use a while loop to iterate over both the arrays
// loop only while the index value is less than the length of either of the input arrays (the arrays have the same amount of elements)
while (tournamentIdx > results.length) {
// declare a home and away variable and assign to them the values from the competitions array (`const [home, away] = competitions[indexValue]`)
const [home, away] = competitions[tournamentIdx];
// declare variable for winner of the pair and assign it the integer value from the results array at the given index value
const winner = results[tournamentIdx];
// create conditional statements:
// if winner is 0 (0 is the away team), then add entry to score keeper object with team name and value of 3... but if the already exists we just set value to += 3
if (winner === 0 && leaderboard[away]) {
leaderboard[away] += 3;
} else if (winner === 0) {
leaderboard[away] = 3;
}
// repeat for winner being 1
if (winner === 1 && leaderboard[home]) {
leaderboard[home] += 3;
} else if (winner === 1) {
leaderboard[home] = 3;
}
// increase the index value at the end of the loop
tournamentIdx++;
}
// after the while loop we can iterate over the score keeping object
for (let key in leaderboard) {
// start with a conditional: if the value of current key is greater than the value of the high score variable, set the value of high score to the current key's value AND set the value of the tournament winner variable to the current key
if (leaderboard[key] > highScore) {
highScore = leaderboard[key];
champ = key;
}
}
// lastly, return the string value from the tournament winner variable
return champ;
}
That should be everything! Now I am going to remove the comments for readability, but I would usually keep comments in if I am saving this to my local machine so that I may review the thought process in the future. Here's the code without the comments:
function tournamentWinner(competitions, results) {
let leaderboard = {};
let tournamentIdx = 0;
let highScore = 0;
let champ;
while (tournamentIdx < results.length) {
const [home, away] = competitions[tournamentIdx];
const winner = results[tournamentIdx];
if (winner === 0 && leaderboard[away]) {
leaderboard[away] += 3;
} else if (winner === 0) {
leaderboard[away] = 3;
}
if (winner === 1 && leaderboard[home]) {
leaderboard[home] += 3;
} else if (winner === 1) {
leaderboard[home] = 3;
}
tournamentIdx++;
}
for (let key in leaderboard) {
if (leaderboard[key] > highScore) {
highScore = leaderboard[key];
champ = key;
}
}
return champ;
}
Looking better! Let's test it out.
T: Test
Testing time is here again! Here is a Codepen with the function in the JS tab on the left and the results on the right. Feel free to play around with the code and explore.
O: Optimize
We passed our own tests! 🎉 Oh yeah! Now let's optimize it because you probably noticed we have two loops in the function. That means we loop over the arrays once, in one loop, and then we loop over the score keeping object. We don't need to do the latter, so let's look at a more optimized version below:
function tournamentWinner(competitions, results) {
let champ = "";
const leaderboard = { "": 0 };
for (let i = 0; i < results.length; i++) {
const result = results[i];
const [home, away] = competitions[i];
const winner = result === 1 ? home : away;
updateLeaderboard(winner, 3, leaderboard);
if (leaderboard[winner] > leaderboard[champ]) {
champ = winner;
}
}
return champ;
}
function updateLeaderboard(team, points, leaderboard) {
if (!leaderboard[team]) {
leaderboard[team] = 3;
} else {
leaderboard[team] += 3;
}
}
You can see how we made use of a helper function (thanks to AlgoExpert for the helpful guidance) and only make one loop. Let that optimized code sink in! You can see how some things done in the first attempt were unnecessary but did not hinder our progress to a valid solution. If you have any questions or suggestions, please leave a comment below!
Thank You
Once again. I would like to thank you for taking time out of your day to read this post. Follow me here on dev.to if you'd like to see more content like this as I post about my explorations into the world of web development. I'll see you around!
Oldest comments (0)