beanz Magazine

Round Robin Algorithm

U.S. Army Corps of Engineers on Flickr

How I solved Math Pentathlon scheduling with the round robin algorithm!

The Problem

From grades kindergarten through seventh, I played Math Pentathlon, a group of math and critical thinking games that is practiced and later played at a final tournament. My school Math Pentathlon club met on weekends to practice games for the final tournament. During the meetings, we played games like the final tournament, in a mock/model tournament. To run smoothly, someone pairs the students up, assigns games, and assigns monitors. Usually, the person in charge of Math Pentathlon, the school lead, does this work.

I never realized how much work this involved until my dad was the school lead and had to schedule the mock tournaments.

There are some rules to pairing up players. Two students cannot be paired up more than once during competition. After every round, we check that the same students aren’t paired up together again. This sounds easy but it’s a tiring job. My dad worked long hours and stayed up late making schedules for the Math Pentathlon meetings.

One day, I saw him working on this pairing problem and thought, if a human can do this scheduling in 4 hours, can’t a computer do it in less time? So I started programming a website and, two years later, my website can schedule a mock tournament in 5 minutes. I hope this program will help many school Math Pentathlon leads.

How Math Pentathlons Work

Math pentathlon is a group of math and logical thinking related games. Students are grouped into divisions based on their grades. A division is made up of two grades. Each division has a set of five different games.

Divison Grades Games
1 – I K & 1 Calla, Hex-A-Gon, Kings & Quadraphages, Shape-Up, Star Track
2 – II 2 & 3 Fiar, Kwatro-Sinko, Par 55, Ramrod, Sum Dominoes & Dice
3 – III 4 & 5 Juggle, Contig 60, Stars & Bars, Fab-A-Diffy, Queens & Guards
4 – IV 6 & 7 Frac Fact, Pent ‘Em In, Fraction Pinball, Prime Gold, Remainder Islands

The games are practiced as a team or individually. At the end of the Math Pentathlon season, there is a final tournament. At the tournament, each kid plays each game with different people they have never met. They have a monitor who watches the games and clarifies rules. Kids gain points depending on their wins or losses.

What Happened Points
Win 3
Tie 2
Loss 1

At the end of the competition, all the points are added up and medals are awarded, depending on how many points each kid has collected.

Medal Points Needed
Hall of Fame 15
Gold 14
Silver 13
Bronze 12
Pentathlete Award 11 + under

The Round Robin Algorithm

The round robin tournament algorithm is an algorithm that pairs students up without repeating the same pair more than once. This algorithm is perfect for the scheduler that I have created. In Math Pentathlon, two players can not play against each other more than once. So with this algorithm, we can pair the players up without breaking this rule.

To pair a round robin tournament, draw a polygon and rotate the polygon. The number of sides is N-1, with N equal to the number of students. The number of students must be an even number to ensure pairs with no left over students.

For example, with 10 students there will be 9 sides to the polygon, N-1 or 10-1. Each point of the polygon will have a student number and the center of the polygon will have the first student.

For the first round, students are paired from across the polygon and the center student is paired with the highest point. So this pairs

(1, 10) (2, 9) (3, 8) (4, 7) and (5, 6)

For the second round, the players are rotated around the polygon leaving just one student in the center as a constant. Then, again, the players are paired across the polygon. So this pairs

(1, 9) (8, 10) (2, 7) (3, 6) and (4, 5)

This continues rotating for a total of 5 different rounds. At the end, the schedule would look like this.

Round Station 1 Station 2 Station 3 Station 4 Station 5
I 1, 10 2, 9 3, 8 4, 7 5, 6
II 1, 9 8, 10 2, 7 3, 6 4, 5
III 1, 8 7, 9 6, 10 2, 5 3, 4
IV 1, 7 6, 8 5, 9 4, 10 2, 3
V 1, 6 5, 7 4, 8 3, 9 2, 10

The same pairs will not repeat unless there are less than 6 students. With 6 students, there are 5 possible different pairs, but with anything less you can not make 5 different pairs. For example, with 4 students, the pairs are (1, 2) (1, 3) and (1, 4) which is only 3 pairs, whereas 5 pairs for 5 rounds are needed. So in this case, pairs must repeat.

ON PAPER

Before I started to code, here’s the round robin algorithm results for five rounds.

ROUND 1

ROUND 2

ROUND 3

ROUND 4

ROUND 5

Writing Code

To create a website that pairs students without repeats, I had to create this round robin process in code. It required a number of steps to code the round robin algorithm. Because I created a website, I used the PHP programming language.

Step 1

First, I needed to know the names of the students that will play in the Math Pentathlon. Names can be stored in an array called studentNames1. The 1 is added to the array name because each array name increments to reflect the order of the students as the round robin polygon rotates from the algorithm. Each rotation adds a number to the array name. For the studentNames1 array, the students are in the original order, also known as the imputed order. For this I used the code below:

Step 2

Second, I check if there are an even number of students. If there is an odd number of students, pairs with nobody leftover cannot be made. In this case, I added a student called Extra Player. In the tournament, a parent will play the game as the extra player. I used the modulus (%) operator to see if the array length leaves a remainder. No remainder means the number of students is even. Otherwise, the number of students is not even and I add the Extra Player to the array of student names.

Step 3

Third, I needed to know the names of the monitors. The monitors are parents who volunteer to supervise the games. These names are stored in an array called monitorNames. There is no specified number here because monitors do not change their order. They are assigned to a station and stay there the whole tournament.I also have to check if there are enough monitors. In the game, there needs to be one monitor for every two students. Monitors to students ratio should be 2:1. If there are not enough monitors for the number of students, I add a monitor called Extra Monitor. In the tournament, a parent who originally didn’t volunteer to be a monitor would supervise the game as the extra monitor.

Step 4

Next, I need to pair the students. On paper, I can draw the polygon and pair the students, but the computer can’t. So I needed to find a pattern. I drew it out on paper and paired the students. Notice the first student is paired with the last student and the second student is paired with the second-to-last student and so on.

I can pair studentName[i] and studentName[(studentNames1.length-1)-i]. If i starts as 0, studentName1[0] is paired with studentName1[9]. Next i will be 1, studentName1[1] is paired with studentName1[8], and so on. I put this incremental process in a for loop, since the line of code is repeated over and over again.

 

Step 5

Next, for the second round, I rotated the polygon and changed the order of the students. This new order for round 2 in an array called studentNames2.

Before

After

 

Step 6

For the second round, I take the first student of the original order, because this is the constant in the center of the polygon. Then I take the last student of the original order and then the rest of the students in the order they were in.

 

Step 7

Then again, I pair the students up and re-order the students for the next round. And I repeat these steps until all 5 rounds are done and students paired up without repetition.

My Final Code

Here’s my final code, as described above:

What I Learned About Programming

I want to share what I have learnt through the process of turning the round robin algorithm into software others can use to schedule Math Pentathlon students.

Code is frustrating

Code is hard, but if you want to create a program using code, you have to just push through whatever problems are frustrating.

Code is almost completely trial and error. During the project, I tried a piece of code out, and I had to go back and fix something, then checked it again and fixed something again and checked it again and again until I finally reached the right code. I wanted to give up, but I didn’t and I learned that I have to just keep persevering until I reach my goal and feel a sense of accomplishment.

Algorithms are work

This program included a lot of algorithms. To create these algorithms, I had to write out the start, which is the information I had, and the wanted end result. Then, find a pattern of how the start leads to the end. Then lastly, put it into code. After that, I ran through the code manually and fixed any small issues in my algorithm and after that, it worked by itself. This is a lot of work because the round robin algorithm is very tricky and there are a lot of steps to it. But after I put some effort in the beginning, I didn’t have to worry about it later.

You may lose interest along the way

At one point, It was getting challenging, it wasn’t working and I just felt like giving up. So I stopped. I came back to the code after a few months and I had new ideas and clearer thoughts. I used those ideas to move forward. I also learned that a few months of break is too long because you forget a few things while you are away from the code. So I had to go back and revisit the old code and understand what it is doing again and then write more code.

You can’t do it by yourself

There were many times during this project where I didn’t know how to solve the issue. I got help from 2 mentors. They would help me understand the problem, and teach me a line of code that could help me solve the issue, after that I could debug by myself. To make sure that I covered everything that the program needs to be able to do, I incorporated suggestions from the people who are going to use the program. With the help of others, I was able to complete the program to help everyone.

Don’t solve imaginary problems

I solved a real-world problem, a problem that is really happening and needs a solution. These types of problems are much better to solve than the problems you make up. Real world problems give you a reason to code a solution. Imaginary problems give you a reason, but nobody needs your solution. Real world problems motivate you to help the world. Imaginary problems don’t help. Solving an imaginary problem is actually more work for you that isn’t needed. When solving this real-world problem, I knew exactly what the output needed to be. With imaginary problems, you don’t know what the people want for a solution. Through these real-world problems, I got the satisfaction of people using my solution. In imaginary problems, no one needs your solution so no one will use it and your solution is useless.

Failure is essential to success

I made many mistakes during this project. Some were small coding mistakes, and some were bigger algorithm mistakes. When I took a break and went back to the code a few months later, I looked at my round robin algorithm and noticed that you can’t schedule that way properly without at least 10 students. So I restarted on all my algorithms and made new ones. Now using these new algorithms my program can schedule with only 6 students. Like this, with many other problems, I just figured out what I did wrong, and I fixed it. Even if I only fixed one problem a day, it was still progress.

You have to learn something along the way

If I knew how to code the whole thing, I wasn’t learning anything and part of the coding experience is learning! I had to stop along the way and complete two Udemy courses. I learned a lot from those courses. I didn’t incorporate all the code I learned, but lots of it I did. Those little bits of code made the program a lot better. I also used Stack Overflow and W3Schools to learn and sometimes I clarified a line or two of code with it.

Having fun is crucial

This took a long time and I had to present it to some people who will help me spread the word about this project. I had to present to them by some date, so sometimes I was stressed to finish before the deadline, but I just relaxed, and had fun while coding! Sometimes the code doesn’t work and it looks like I’m doing everything right so I get frustrated. Sometimes the code works perfectly on my first try so I am happy and enjoy it. But, the code doesn’t always work perfectly, so I just have to push through the times it doesn’t. I had to enjoy it or I would get stressed and frustrated and I would want to quit. It may be about the end result, but it’s also about the climb!

It was a challenging process, and I wasn’t sure if I would finish. I worked very hard for 2 years and wrote a lot of code. And now that I see the end result, I feel good that I completed a project to make people’s lives easier. Hopefully, my experience helps you in your coding journey. Good luck!

Learn More

Round Robin Scheduling

https://en.wikipedia.org/wiki/Round-robin_scheduling

Facts about Round Robin

https://plan2play.com/blog/uncategorized/what-you-never-knew-about-round-robin/

Coding for solving real life problems

https://www.youtube.com/watch?v=wM7v3HN14pY

Women’s Hackathon

https://news.csusm.edu/hackathon/

Coding and problem solving

https://medium.com/better-programming/how-coding-changed-the-way-i-look-at-problems-4e8d42676e2c

Kids Get Coding

https://www.amazon.com/Coding-Real-World-Kids-Get/dp/1512455865#reader_B073ZMSWZB

Why kids should learn to code

https://codewizardshq.com/kids-learn-to-code/

The code advantage

https://thecodewiz.com/teaching-kids-coding-the-code-advantage/

Coders solve real world problems

https://www.oakridge.in/achievers/young-coders-come-together-to-solve-real-world-problems/

Computer Science for Good

https://code.org/csforgood

(Visited 23 times, 1 visits today)

Also In The August 2020 Issue

Here's a fun way to identify plants, animals, birds, and more when you're outdoors!

With a new school year on the horizon and COVID-19 still ever present, students and teachers alike have question about what the future holds.

This month we will exploring the history of the first computer virus, and it is a creepy one!

Time to use your python coding skills to automate some of the more dull parts of your minecraft game!

How I solved Math Pentathlon scheduling with the round robin algorithm!

With the summer coming to an end, why not cap it off with a NFC enabled adventure?

No need to Google the origins of Google, we did the research for you!

Links from the bottom of all the August 2020 articles, collected in one place for you to print, share, or bookmark.

Interesting stories about computer science, software programming, and technology for February 2018.