Recursing For Bike Polo

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.

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!

You can use recursion in real life!

They make you learn recursion during first-year intro to programming courses. Some people get fed up at that point and drop out to become car salesmen or Liberal Arts majors instead. Some people never quite get it, but bodge their way through another four years of school anyway. For those who do get it, there’s a neat “aha!” moment where the entire world suddenly makes perfect sense, and it feels like the future of your brilliant programming career, and all the wealth that goes with it, is spread out before you. “The function calls itself! Of course! That’s what they were saying all along!”

My pseudocode
My pseudocode

Then they pile another dumptruck of homework on you and you forget about it for a while. Because honestly, you don’t use recursion that often in everyday programming. It’s a neat trick, but very rarely the most efficient solution to a problem. It’s also very easy to write a recursive function that goes out of control and brings down your entire office’s network and causes your boss to come your desk and raise his eyebrows at you.

So this week when I found a legitimate excuse to use recursion at work, I was pretty excited.

The Goal

We have a mailing list about real estate. Real estate agents write down some stuff about a property listing, give the date of an open house, upload some pics, and pay 70 bucks for us to send the email to everyone who is subscribed to the list. If you want to buy real estate in Victoria, it comes in handy, I guess.

The only thing is, each email has to be approved by our secretary before it goes out. Also, since we don’t want to spam the mailing list, we have to space them out a little, so the system isn’t fully automated. Nevertheless, when a customer asks for an email to be sent out on Monday morning, they expect it to be done or get an explanation.

The secretary needs some time in the morning to approve the scheduled emails and request changes if needed, so the following rules exist for the datepicker:

  • If it’s a weekend, the date is unavailable.
  • If it’s a holiday, the date is unavailable.
  • Today is unavailable.
  • If it’s after 1pm, tomorrow is unavailable.
  • If it’s after 1pm and tomorrow is a holiday or a weekend, the first business day following the holiday or weekend is unavailable.

Stop here and code up your own solution according to the following spec.

Okay, you ready? I look forward to being made a fool of by all the people who came up with better solutions than mine. Nevertheless, here’s my answer, which took a full work day to hammer out but made me very happy.

First, I’ve got three helper functions: one returns weekend dates. One returns holiday dates. And one returns the day after a given date.

Here’s the code.

Solution

I only brought down our office network once in the writing of this class.

The function is called like this:

You pass nextAvail() the current timestamp. It checks whether that time falls on an unavailable day. If it does, the time is incremented by one day by calling $this->tomorrow($today); then nextAvail() is called again with the incremented timestamp.

And so on, until we find a day that works.

 

***Edit: Since this is somehow one of my highest ranking posts, I might as well plug my company: Radar Hill Web Design in Victoria, BC.