Seles: Tennis coding challenge

A colleague sent me a coding challenge. This is a short post to describe how I tackled it.

Edit: a follow-up post is here.

This is the challenge:

There is a tennis match between two players denoted 1, and 2. You are given a sequence of 1s and 2s whereby each number denotes a point won by player 1 or player 2 (e.g. 1,2,2,1,2,2 in this example player 2 wins the game to 30). Given the full sequence of the match and the assumption that you are aware of the rules and scoring of tennis, write a programme that determines the winner of the game, given any sequence, inclusive of all boundary cases. NB: The sequence is given in the form of a list called match. In the case above match = (1,2,2,1,2,2)
Points are awarded for a) code that successfully solves the challenge b) time to solve (time yourself) and c) lines of code for efficiency (shorter is better).

With an eye on b, and since I code fastest in Igor, I went with Igor over python or R. I knew this would lose me major points for c since Igor code is not very compact.

It took me 22 minutes to write a solution, slowed down a bit by helping a small person with their homework.

My solution

Function TennisMatches(nMatches)
	Variable nMatches
	Variable timerRefNum
	Variable microSeconds
	timerRefNum = StartMSTimer
	Variable nPoints, outcome, i
	Make/O/N=(nMatches) resultW
	
	for(i = 0; i < nMatches; i += 1)
		nPoints = 5 + round(abs(enoise(20)))
		Make/O/N=(nPoints)/FREE scoreW
		scoreW = floor(2 + enoise(0.1))
		outcome = TennisParser(scoreW)
		if(outcome > 2)
			resultW[i] = DeuceMatch(scoreW, outcome)
		else
			resultW[i] = outcome
		endif
	endfor
	microSeconds = StopMSTimer(timerRefNum)
	Print microSeconds / 1000000, "seconds"
End

Function TennisParser(w)
	Wave w
	Variable nRow = numpnts(w)
	Variable p1 = 0, p2 = 0
	
	Variable i
	
	for(i = 0; i < nRow; i += 1)
		if(w[i] == 1)
			p1 += 1
		elseif(w[i] == 2)
			p2 += 1
		endif
		
		if(p1 == 4 && p2 < 3)
			Print "Player 1 wins", w
			return 1
		elseif(p2 == 4 && p1 < 3)
			Print "Player 2 wins", w
			return 2
		elseif(p1==3 && p2 == 3)
			return i + 1 // deuce
		endif
	endfor
	Print "Game not finished", w
	return -1
End

Function DeuceMatch(w,ii)
	Wave w
	Variable ii
	
	Variable nRow = numpnts(w)
	Variable d1 = 0, d2 = 0
	
	Variable i
	
	for(i = ii; i < nRow; i += 1)
		if(w[i] == 1)
			if(d2 == 0)
				d1 += 1
			else
				d2 = 0
			endif
		elseif(w[i] == 2)
			if(d1 == 0)
				d2 += 1
			else
				d1 = 0
			endif
		endif
		
		if(d1 == 2)
			Print "Player 1 wins", w
			return 1
		elseif(d2 == 2)
			Print "Player 2 wins", w
			return 2
		endif
	endfor
	Print "Game not finished", w
	return -1
End

If we run the code by calling TennisMatches(10) we get the outcome of ten random matches. Like this:

•TennisMatches(10)
  Player 2 wins  
'_free_'[0]= {2,1,2,2,1,2,2,2,1,2,2,2,2,1,1,2,2,1,2,2,1,2,2}

  Player 1 wins  
'_free_'[0]= {1,1,1,1,1,2,1}

  Player 1 wins  
'_free_'[0]= {2,2,1,1,1,1,1,1}

  Player 2 wins  
'_free_'[0]= {2,2,2,2,2,1,1}

  Player 1 wins  
'_free_'[0]= {1,1,1,2,1,2,2,2,2,1,1,2,1,1,2,1,1,1,1,1}

  Player 2 wins  
'_free_'[0]= {1,2,1,2,2,2}

  Player 1 wins  
'_free_'[0]= {1,2,1,1,1,1,2,2,2,2,2,1,1,2}

  Player 2 wins  
'_free_'[0]= {2,2,2,1,2,2,1,1,1,1,2,1,1,2,1,2,2,1,1}

  Player 1 wins  
'_free_'[0]= {2,1,1,2,2,1,1,1,2}

  Player 2 wins  
'_free_'[0]= {1,2,1,1,2,2,2,2,1,2}

  0.00458757  seconds

An explainer

Igor doesn’t use numeric lists, the closest approximation is a numeric wave. I wrote the code for TennisParser() first assuming that it would be passed a wave with the scores as described in the challenge. The challenge only asks for us to be able to deduce the outcome and not to give the score. So this meant we can deal with everything using numeric values for outcomes and we don’t have to parse any strings.

The code sums 1s and 2s from the input in two separate variables (p1 and p2), working row by row.

When p1 is 4 and p2 is less than or equal to 2 (or vice versa) game goes to p1 (or p2). This is because the scoring system in tennis goes Love-15-30-40-Game. So Game would mean a player has reached 4. We ignore the fact that the list may actually have more points, which could be dealt with by printing a message.

The Deuce game is when either p1 or p2 get to 3 and the other player has 3. To handle this I returned the row number of the next point, to the calling function. Since this must be greater than 1 or 2 (my other return values), the calling function knows that we are now in a deuce game. I used a new function DeuceMatch() to handle the list, starting from the row we returned from TennisParser(). The rules are now that 1 in the list will increase d1 by 1, but only if d2 is at 0 (deuce). If not, player 2 was at advantage and therefore gets returned to deuce, and vice versa. The first player to reach 2 wins. We do not need to verify a score difference this time because of the way the addition is done.

It is possible the list that is parsed does not result in a win (due to insufficient points for either player). This is dealt with by the fact that the loops in both functions will terminate by return when a result is reached. So we can conclude that any code that executes after the loop is the result of a game not concluding.

I wrote a “wrapper” to generate as many match results as we need (TennisMatches()). A variable number of points are used and are shared randomly between player 1 and 2. This wrapper allows us to test how fast the code runs.

How did I do?

Well, my code works and gives the correct solution. It’s also fast. It can test 10,000 matches in 3.25 s on a 2.6 GHz 6-Core Intel i7 MBP. Most of this time comes from printing the results. Since the equivalent without printing is 0.039 s. Ten million matches can be processed in 2.82 s.

I thought my time to solve was OK, but with more time I could definitely make the code more compact (and efficient). For example, the DeuceMatch function could be rolled into the TennisParser function by using a variable to determine if we are in the regular game mode or deuce game mode. It would certainly take me longer to write a similar program in Python. I might try this to see how I can improve.

The code is over 80 lines long. So it does win any points for brevity.

Conclusion

I enjoyed the challenge and can see that this is a great way to learn programming techniques. I like the idea of speed coding too: prioritising results and minimising errors rather than aiming for elegance.

—

The post title is taken from “Seles” by Majesty Crush from their album Love 15. The lyrics are creepy but the song (and album) is fantastic. And it beats “Anyone For Tennis” by Cream.