Solving the Baseball Game in Go
Tags: go, algorithms, interview, challenges
Published: 2024-03-11 17:20:27

Below is an interpretation of how to solve the Baseball Game Challenge in Go. Below are the instructions:

You are keeping score for a baseball game with strange rules. The game consists of several rounds, where the scores of past rounds may affect future rounds' scores.
At the beginning of the game, you start with an empty record. You are given a list of strings ops, where ops[i] is the ith operation you must apply to the record and is one of the following:
0. An integer x - Record a new score of x.
0. "+" - Record a new score that is the sum of the previous two scores. It is guaranteed there will always be two previous scores.
0. "D" - Record a new score that is double the previous score. It is guaranteed there will always be a previous score.
0. "C" - Invalidate the previous score, removing it from the record. It is guaranteed there will always be a previous score.
Return the sum of all the scores on the record.

Here is how I solved the challenge in Go. Below are the test cases to help us check our answer.
1. Given input as `{"1"}` should return `1`
2. Input: `{"5", "2", "C", "D", "+"}`. Output: `30`
3. Input: `{"5", "-2", "4", "C", "D", "9", "+", "+"}`. Output: `27`

In the `main.go` file, we create a function that takes a string slice as a parameter and returns an int representing the sum of the resulting slice of scores.
```
package main

func main(){

}

func CalculatePoints(ops []string) int {
	var res int = 0

	return res
}
```
Second, we need to do the following:
* Loop through the slice
* For every operator, perform the necessary operation
* Append the result to a new slice of numbers
* From the resulting slice of numbers, return their sum

Let's take the first step. We declare a new slice to hold our numbers.

```
numbers := []int{}

for i, op := range ops {
	switch op {

        }
}
```
We check for each condition and then append the result to the numbers as shown below.
* If the operator is a `+`, the position will be held by a number that is the result of adding the previous two numbers
* If the operator is a `D`, we will double the previous number
* The default expectation is that this is a normal number which we will append to the list
```
case "+":
	numbers = append(numbers, numbers[i-1]+numbers[i-2])
case "D":
	numbers = append(numbers, numbers[i-1]*2)
default:
	num, _ := strconv.Atoi(op)
	numbers = append(numbers, num)
```
Notice that there is one condition missing. But for the three other conditions, this should work. Given an input for instance: `{"5", "2", "D", "+"}`, we get expect `17`.

Let's add the loop to sum, so we can test with the sample above:
```
for _, num := range numbers {
	res += num
}
```
In the **main** function, let's call our function with the above sample. Running the code with `go run .` should give `17`
```
func main() {
	ops := []string{"5", "2", "D", "+"}
	fmt.Println(CalculatePoints(ops))
}
```
Let's now consider the unimplemented condition where we have `C`, which should delete the previous number from the slice. Given the following sample `{"5", "2", "C", "D", "+"}`, we expect the output slice of numbers to look like this `{5, 10, 15}`:
* First, add the number 5 to the slice, resulting in `{5}`
* Add 2, resulting in `{5, 2}`
* "C" means we remove the previous number, hence, our slice now looks like `{5}`
* "D" means we double the previous number, resulting in `{5, 10}`
* "+" means we add the previous two numbers, resulting in `{5, 10, 15}`
* The sum of the elements in the resulting slice would give `30`
Now, note that the operation "C" actually reduces the length of the numbers slice, so that while the `ops` slice has `len` of 5, our slice of `numbers` has only 3. This means that the result of "C" actually deletes its own position, as well as the previous position, reducing the length by 2.

Below is the updated function:
```
numbers := []int{}
removed, j := 0, 0

for i, op := range ops {
	j = i - removed
	switch op {
	case "+":
		numbers = append(numbers, numbers[j-1]+numbers[j-2])
	case "D":
		numbers = append(numbers, numbers[j-1]*2)
	case "C":
		numbers = numbers[:j-1]
		removed += 2
	default:
		num, _ := strconv.Atoi(op)
		numbers = append(numbers, num)
	}
}
```
We add two int variables `removed` and `j` initialized to `0`. `removed` will hold how many positions have been removed by the "C" operation. For every "C" operation, two positions are removed from the `numbers` slice. `j` holds the current position of the numbers slice. The value of `j` is the result of subtracting the current value of `i` with the number of positions `removed`. If no position has been `removed`, `i` and `j` will have the same value.

Note that the other `case`s have also been updated to now use `j`, otherwise we would have an `out of bounds index` error.

Testing with the test cases now gives the correct results. The full code file `main.go` now looks like below:
```
package main

import (
	"fmt"
	"strconv"
)

func CalculatePoints(ops []string) int {
	var res int = 0

	numbers := []int{}
	removed, j := 0, 0

	for i, op := range ops {
		j = i - removed
		switch op {
		case "+":
			numbers = append(numbers, numbers[j-1]+numbers[j-2])
		case "D":
			numbers = append(numbers, numbers[j-1]*2)
		case "C":
			numbers = numbers[:j-1]
			removed += 2
		default:
			num, _ := strconv.Atoi(op)
			numbers = append(numbers, num)
		}
	}

	for _, num := range numbers {
		res += num
	}

	return res
}

func main() {
	ops := []string{"5", "2", "C", "D", "+"}
	fmt.Println(CalculatePoints(ops))
}
```

Let's add some tests. Create a file called `main_test.go` and paste the following code:

```
package main

import (
	"fmt"
	"testing"
)

func TestCalculatePoints(t *testing.T) {
	var tests = []struct {
		ops []string
		sum int
	}{
		{[]string{"5", "2", "C", "D", "+"}, 30},
		{[]string{"1"}, 1},
		{[]string{"5", "-2", "4", "C", "D", "9", "+", "+"}, 27},
	}

	for i, test := range tests {
		ops := test.ops
		sum := test.sum

		testname := fmt.Sprintf("running test %d", i)

		t.Run(testname, func(t *testing.T) {
			res := CalculatePoints(ops)

			if res != sum {
				t.Errorf(`Calculate Points(%s), expected result to be %d, got %d`, ops, sum, res)
			}
		})

	}
}
```

To execute the tests, run the following: `go test -v .` All the tests should pass.

The full source of the solution can be found on GitHub [Baseball Game](https://github.com/munenendereba/baseball-game-go). 

Thanks for reading. Leave a comment on any optimizations you suggest. Let's go!