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.
One thought on “Seles: Tennis coding challenge”
Comments are closed.