04/03/2017

[Java] Scorecard algorithm

Some time ago I took an online coding test which left me with an unfinished exercise; I played too long with the other one and had no time to finish this :(

However it seemed quite easy and interesting so I decided to finish it later, here is the description of the exercise as I remember it and my solution:

Bill plays some kind of game where the score is tracked on a scorecard; in addition to simple scoring moves, he can attempt (and possibly fail) more rewarding moves that will influence the score calculation.

Bill starts with a score of 0 and cannot earn negative points.

Bill can alter his total score by:

  • scoring a point (integer) - it will be added to the total score
  • doubling a previous score ("X") - the previous score will be doubled before adding it to the total score. If there is no previous score, it counts as 0
  • summing two previous scores ("+") - the two precedent scores will be summed together before adding the result to the total score. If there are no predecessors, it counts as 0; if there is only one predecessor, it will be added again to the total score
  • failing a move ("Z") - the previous score will be ignored from the total score and its value will also not be considered for subsequent special moves. If there is no previous score, this has no effects
The input scorecard is passed as a String array and the exercise requires to return an integer representing the total score. The tricky part was the "failing a move" bit because it basically deletes a position from the input array permanently.

First idea was to do only one pass over the input array and keep track of the current score plus two predecessors at all times, updating everything accordingly to the rules. However, if space is not an issue, tracking partial scores in a second array makes life easier and the run time is exactly the same O(n).

You can check the code and a sample JUnit test source on my Gist. The full project was developed with IntelliJ and Gradle using JDK 8.

No comments:

Post a Comment

With great power comes great responsibility.

Da grandi poteri derivano grandi responsabilità.