Codewars: Printer Errors

Page content

In a factory a printer prints labels for boxes. For one kind of boxes the printer has to use colors which, for the sake of simplicity, are named with letters from a to m.

The colors used by the printer are recorded in a control string. For example a “good” control string would be aaabbbbhaijjjm meaning that the printer used three times color a, four times color b, one time color h then one time color a…

Sometimes there are problems: lack of colors, technical malfunction and a “bad” control string is produced e.g. aaaxbbbbyyhwawiwjjjwwm with letters not from a to m.

You have to write a function printer_error which given a string will return the error rate of the printer as a string representing a rational whose numerator is the number of errors and the denominator the length of the control string. Don’t reduce this fraction to a simpler expression.

The string has a length greater or equal to one and contains only letters from ato z.

Examples

s="aaabbbbhaijjjm"
printer_error(s) => "0/14"

s="aaaxbbbbyyhwawiwjjjwwm"
printer_error(s) => "8/22"

Notes

First Thoughts

Iterating over the string and then iterating over the slice of valid characters would be a brute force solution, but I know it’d also be O(n^2) right off the bat which isn’t great. With the range of characters being consecutive without gaps there has to be an ASCII code solution where we look for something that’s >= a but <= m to pass validation.

Heading into Rune Land

Iterating over a string returns runes because strings can have more than just single byte characters if you’re using an encoding that supports them and Go defaults to UTF-8.

That turns our comparison (if we’re leaning toward the brute force loop route, at least initially) into a comparison of []rune instead of []string.

From what I’m reading on dot net perls this should be as easy as:

// a string value
value := "bird"

// convert the string to a slice of runes
runes := []rune(value)

Spinning in the Mud

So I’ve been trying to set a []rune at the top with the following for the last 5 minutes:

package kata

import fmt

var validRunes = []rune{"abcedfghijklm"}

Its complaint was that it was expecting a semicolon or a string. I finally googled how to import a package in Go and then it hit me that fmt needs quotes around it. This is what happens when we have nice things like gofmt to format our code and handle imports for us. Out of sight, out of mind I guess.

Casting, Not Initializing

After getting a bunch of errors about it not liking those curly braces, I googled (“create a slice of runes golang”) and headed down various rabbit holes:

https://stackoverflow.com/questions/65195938/how-to-convert-a-string-to-rune https://programming.guide/go/convert-string-to-rune-slice.html https://thedeveloperblog.com/go/convert-string-rune-slice-go https://www.dotnetperls.com/substring-go

Finally this one was the winner:

http://xahlee.info/golang/golang_char_sequence.html

Because I’m trying to leverage the conversion from string to []rune I needed to use parens and not curly braces to do it.

var validRunes = []rune("abcedfghijklm")

My Solution(s)

After renaming the isValidCharacter function to isValidRune I started getting green tests. YAY!

package kata

import "fmt"

var validRunes = []rune("abcedfghijklm")

func PrinterError(s string) string {
  errorCount := getErrorCount(s)
  result := fmt.Sprintf("%d/%d", errorCount, len(s))
  
  return result
}

func getErrorCount(s string) int {
  var totalErrors int
  for _, c := range s {
    if !isValidRune(c) {
      totalErrors++
    }
  }
  
  return totalErrors
}

func isValidRune(r rune) bool {
  for _, v := range validRunes {
    if r == v {
      return true
    }
  }
  
  return false
}

On to the revisions. I need to know how to get the integer value of the rune so I can use comparison operators on it. Back to google (“convert rune to ascii value golang”)!

And the winner was:

https://www.socketloop.com/tutorials/golang-how-to-convert-character-to-ascii-and-back

Since the characters are contiguous I’ll remove at least one loop by checking the int value of the rune (ASCII) to see if it’s between 97 (a) and 109 (m), inclusive.

I could have looked up an ASCII table to get those numbers, but instead I threw a fmt.Printf in there where it was iterating over the runes already:

func getErrorCount(s string) int {
  var totalErrors int
  for _, c := range s {
  fmt.Printf("%s:%d ", string(c), int(c))
    if !isValidRune(c) {
      totalErrors++
    }
  }
  
  return totalErrors
}

That gave me this output:

a:97 a:97 a:97 a:97 a:97 a:97 a:97 a:97 a:97 a:97 a:97 a:97 a:97 a:97 a:97 a:97 b:98 b:98 b:98 b:98 ... a:97 a:97 a:97 a:97 a:97 a:97 a:97 a:97 a:97 b:98 b:98 b:98 b:98 b:98 b:98 b:98 b:98 b:98 b:98 b:98 b:98 b:98 b:98 b:98 b:98 b:98 b:98 m:109 m:109 m:109 m:109

Adjusting that same function puts the complexity at O(n) which is a little more comfortable.

func getErrorCount(s string) int {
  var totalErrors int
  for _, c := range s {
    if int(c) < 97 || int(c) > 109 {
      totalErrors++
    }
  }
  
  return totalErrors
}

That allows me to remove the []rune global variable and isValidRune function entirely, leaving me with this solution, which passes the tests.

package kata

import "fmt"

func PrinterError(s string) string {
  errorCount := getErrorCount(s)
  result := fmt.Sprintf("%d/%d", errorCount, len(s))
  
  return result
}

func getErrorCount(s string) int {
  var totalErrors int
  for _, c := range s {
    if int(c) < 97 || int(c) > 109 {
      totalErrors++
    }
  }
  
  return totalErrors
}

Best Practice Solution(s)

package kata

import (
  "fmt"
)

func PrinterError(s string) string {
  e := 0
  for _, c := range s {
    if c >= 'a' && c <= 'm' {
      continue
    } else {
      e++
    }
  }
  
  return fmt.Sprintf("%d/%d", e, len(s))
}
  • Using var to initialize requires a working knowledge of the zero value of integers, so setting this to zero explicitly is a little smoother ride for the uninitiated.
  • I feel like var is the idiomatic way to go though - I’ll have to double check that.
  • Apparently the comparison operators work on runes to say that the range from a to m is what we want to avoid counting as errors.
  • I wonder if it works the same way for strings? I wouldn’t think so without some kind of sort because what’s to say apple is greater than austin without an assumption that we’re talking about alphabetical order.
package kata

import "fmt"

func PrinterError(s string) string {
  errors := 0
  for _, c := range s {
    if string(c) > "m" {
      errors++
    }
  }
  return fmt.Sprintf("%d/%d", errors, len(s))
}
  • It’s funny we were just talking about ranges of strings and here it is. It’s interesting that they aren’t accounting for characters less than a but now that I go back and read the problem description the last line says the letters are only a to z.
  • Search for boundaries & limits in the requirements and leverage them to reduce the scope of the solution.

Clever Solution(s)

package kata

import (
  "fmt"
  "regexp"
)

func PrinterError(s string) string {
  pt := regexp.MustCompile("[a-m]")
  a := pt.ReplaceAllString(s, "")
  return fmt.Sprintf("%v/%v", len(a), len(s))
}
  • Clever solutions are so darn clever.
  • Stripping out the characters we don’t want works here without a ton of extra text because we can use a character class ([a-m]) for the range.

Credit to g964 at Codewars for the kata.