This week I got to write a recursive function for the second time in my programming career. I’m always excited when this happens, and the event is so rare that it gets a blog post every time.
If you don’t know or care what recursion is, now’s the time to stop reading. Otherwise, we’re about to get technical, so pause your music and pay attention.
Recursion is a programming concept where a piece of code calls itself. It’s kinda hard to come up with a metaphor to explain this in non-programming terms – maybe think of a 3D printer that prints copies of itself. I dunno.
Anyway, I’ve been making a scoring application for my bike polo club. We’re having a tournament in January, and we’re not satisfied with the software options that are currently available.
Normal polo clubs use Podium. To use that, we have to get all our players to sign up for the League of Bike Polo and register themselves in our tournament with their teams, before the day of. The trouble is, our club hasn’t got its shit together. Hardly any of our players even know how to operate a computer, let alone sign up for LOBP. Besides that, our tournaments are traditionally mixers. That means you don’t choose your team – you throw your name in a hat and play with whoever you draw. We like it that way, because it keeps things low-key and egalitarian. The weakest player in the tournament still has a chance of scoring a few goals, and the winners are likely to be three strangers who have never played together before. It gives the Victoria players a chance to do okay, even though we’re playing against some of the best players in the world, who come over from Seattle and Vancouver.
So we don’t like Podium that much. (Though it is an excellent piece of software and a great contribution to the polo community!)
Jawn asked me to come up with something better last year. I think he asked me the year before as well. He asked a third time this year, with 4 months of run-up time, and this year I’m actually experienced enough to pull it off.
Instead of trying to master Javascript on the spot to create a fully browser-based application (that’s what I tried and choked on last time), I used the tools I’ve used on the job for the last three years – CakePHP and MySql. I use an older version of Cake, 1.3, at work, but my boss has been making noises about upgrading to 3.0 lately, and this was a good chance to learn how to use the newer version. So CakePHP 3.0 is the framework.
Setting up the framework on a borrowed server from work took a day or two. Figuring out how to create a plugin from the command line, then controllers, models, and views, took another week or so. Once the wiring was sorted out, I started on logic. Our user, in this case one Jawn Fawn, creates teams. Each team can have three players. They’re drawn out of a hat (in real life) then entered on a form (in the app). The teams are added to a tournament, and then you get a nice table with all your teams displaying.
Click a big plus sign to start a round, and you get… what?
Well, in the first version, you got a list of teams matched up at random. Winners get two points, ties get one point each, losers get nothing. So after a round, teams are sorted by how many points they’ve got, and then the teams with more points play each other and the teams with less points play each other. This makes sense to me, it’s a fair way of determining who the best player in a tournament is.
Except, that’s not really our goal. No one who plays polo in Victoria cares who the best player is. We’re here to get rowdy and drink in public. The weather is always terrible. Sometimes there’s soup, but the soup is usually cold. Showing each other up is the last thing on our minds.
No, the goal is to make sure that every team plays every other team, and that repeats happen as seldom as possible. Last week, I demoed the app to Jawn, and to my total shock, he didn’t care about my pretty ajax interface or the nice bubble display of complete matches. The first thing he asked was, “So if Big Country and the Beavers have the same score in round three…. they play each other again?”
And I’m like, “Yeah, I guess so?”
“Well that’s no good”, said Jawn. “The whole problem is that I don’t want to have to keep track of making sure teams don’t play each other too often.”
“Ok, I’ll give it another try.”
As usual in programming, the last 10% of the problem takes 80% of the development time. That’s basically what happened here, and it took another whole week to come up with an algorithm and an implementation that worked. Here it is, with lots of comments. It appears to be working, according to my tests, but I haven’t tested much. Still have to bug Jawn to kick it until it breaks. For some reason, he doesn’t drop what he’s doing and immediately start testing when I send him a demo, I have no idea what’s up with that.
Two things frustrated me for a whole day each. One was the part where the function calls itself. I was calling the function and then returning the array of matches. Instead, I need to return the function call within a conditional statement (if there are more unmatched teams, recurse…), and only return the matches when the condition is not met.
Second, I forgot the “break;” at the end of the foreach loop. It’s important. That was the “break”-through that let me finish it today.
Finally, the reason it had to be recursive in the first place. You grab the first item on the list of teams, then iterate the rest of the list until a match is found. What if no match is found? You have to iterate again. And so, you call the function again.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 |
<?php public function _createMatches($teams = array(), $matchedTeams = array(), $i = 0) { // If there is only one team left, it's the odd man out. // It gets a bye, if desired. Or it can play a team of irregulars. if(count($teams) == 1){ // Remove the one team from the array so it will be empty for the next "if" $team_a = array_pop($teams); // Make a subarray with that team $match = [$team_a]; // Add it to the return array. $matchedTeams[] = $match; } // If there are no teams left in the teams array if(!empty($teams)) { // Pop the last item off the array. $team_a = array_pop($teams); // Iterate the rest of the team. foreach($teams as $k => $team_b) { // Make two arrays out of the previous matches of the two teams, using only the ID field. $team_a_matches = array_column($team_a->matches, 'id'); $team_b_matches = array_column($team_b->matches, 'id'); // Do the two teams have any matches in common? $intersection = array_intersect($team_a_matches, $team_b_matches); // We start a counter at zero. if the teams have zero // or less matches in common, it's a valid match. if(count($intersection) <= $i) { // In that case, we make a subarray out of the id's of the // popped-off match, and the one we just found. $match = [$team_a, $team_b]; // Add the match to the return array. $matchedTeams[] = $match; // We take the other matched team off the list as well. unset($teams[$k]); // And we'll break the loop. Because this is a recursive function. // The loop doesn't continue, the function calls itself. break; } } // Reset the array keys... $teams = array_values($teams); // ... and call the function again. // pass the valid matches we've found so far, and increment the number of // allowed previous matches. return $this->_createMatches($teams, $matchedTeams, $i + 1); } return $matchedTeams; } // If you actually came here to learn about Cake, // here's how I call the function. pubic function ajaxAddMatch($tournamentId) { $teams = $this->Rounds->Tournaments->Teams->find('all', ['conditions' => ['tournament_id' => $tournamentId], 'contain' => ['Matches'] ]); $this->_createMatches($teams->toArray()); $this->set(compact('matches')); } ?> |
The tournament is set for January 21st. If you live anywhere near Victoria, I hope you can make it to see my work in action!