Last active
September 26, 2018 07:38
-
-
Save xealgo/db8ab63d6009fa6855db6c4150afc1b3 to your computer and use it in GitHub Desktop.
solution for withgoogle.com advanced challenge number 1
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
/////////////////////////////////////////////////////// | |
// solution for the With Google code challenge. | |
// https://techdevguide.withgoogle.com/paths/advanced/compress-decompression/#code-challenge | |
// by xealgo | |
// | |
// TODO: currently doesn't allow for numbers to be treated as string values, | |
// only to denote repetitions as per the rule: | |
// * Digits are only to represent amount of repetitions. | |
// but adding it would be pretty trivial though. | |
/////////////////////////////////////////////////////// | |
package main | |
import ( | |
"fmt" | |
"strconv" | |
"strings" | |
) | |
var ( | |
TestCases = map[string]string{ | |
"0[x]": "", | |
"10[a]": "aaaaaaaaaa", | |
"2[3[a]b]": "aaabaaab", | |
"1[4[1[a]bb]oo]": "abbabbabbabboo", | |
"2[3[b]4[d]z]": "bbbddddzbbbddddz", | |
"3[abc]4[ab]c": "abcabcabcababababc", | |
"2[3[2[b]a]4[c]d]": "bbabbabbaccccdbbabbabbaccccd", | |
"2[abc]3[a]15[2[b]z]": "abcabcaaabbzbbzbbzbbzbbzbbzbbzbbzbbzbbzbbzbbzbbzbbzbbz", | |
"1[1[g]1[2[o]g]1[le]2[!]!]": "google!!!", | |
} | |
) | |
// SubSequence holds a sequence such as 10[abc] | |
// and nested subsequences such as 10[2[a]bc] | |
type SubSequence struct { | |
Repeat int `json:"repeat"` | |
Value string `json:"value"` | |
Nested []SubSequence `json:"nested"` | |
} | |
// Sequence container for all subsequences. | |
type Sequence struct { | |
Sequences []SubSequence `json:"sequences"` | |
} | |
// Parse parses the entire "compressed" sequence. | |
func (seq *Sequence) Parse(data *string) error { | |
if data == nil { | |
return fmt.Errorf("expected a string sequence, nil given") | |
} | |
for i := 0; i < len(*data); i++ { | |
ns, j, e := seq.ParseSub(data, i) | |
if e != nil { | |
return e | |
} | |
seq.Sequences = append(seq.Sequences, *ns) | |
i = j | |
} | |
return nil | |
} | |
// ParseSub recursively parses subsequences and nest subsequences. | |
func (seq *Sequence) ParseSub(data *string, i int) (*SubSequence, int, error) { | |
d := *data | |
b := d[i] | |
ss := SubSequence{Repeat: 1, Nested: []SubSequence{}} | |
// the first character should be numeric. | |
if IsDigit(b) { | |
n, j, e := ReadDigits(data, i) | |
if e != nil { | |
return nil, j, fmt.Errorf("Failed to read digits at index %d (%s)", i, string(b)) | |
} | |
i = j | |
// the next character should be a [ | |
if d[i] != '[' { | |
return nil, j, fmt.Errorf("expected [ got %s", string(d[i])) | |
} | |
// begin parsing all nested subsequences | |
for { | |
i++ | |
if !IsDigit(d[i]) { | |
break | |
} | |
cs, j, e := seq.ParseSub(data, i) | |
if e != nil { | |
return nil, j, fmt.Errorf("Failed parsing nested subsequence: Error %s", e) | |
} | |
ss.Nested = append(ss.Nested, *cs) | |
i = j | |
} | |
j, str := ReadChars(data, i) | |
i = j | |
// the next character should be a ] | |
if d[i] != ']' { | |
return nil, i, fmt.Errorf("expected ] got %s", string(d[i])) | |
} | |
ss.Repeat = n | |
ss.Value = str | |
} else if IsRepeatable(b) { | |
j, str := ReadChars(data, i) | |
i = j | |
ss.Value = str | |
} | |
return &ss, i, nil | |
} | |
// Decompress returns the "decompressed" results of the given sequence. | |
func (seq *Sequence) Decompress(data string) (*string, error) { | |
buffer := []string{} | |
if err := seq.Parse(&data); err != nil { | |
return nil, err | |
} | |
for _, sub := range seq.Sequences { | |
buffer = append(buffer, sub.Build()) | |
} | |
results := strings.Join(buffer, "") | |
return &results, nil | |
} | |
// Build builds the string | |
func (sub *SubSequence) Build() string { | |
res := []string{} | |
// go over the nested sequences and build them recursively. | |
for _, n := range sub.Nested { | |
res = append(res, n.Build()) | |
} | |
return strings.Repeat(strings.Join(append(res, sub.Value), ""), sub.Repeat) | |
} | |
// IsDigit checks if a single byte is numeric. | |
// Why isn't this a regex? I'm only checking a single | |
// char at a time which means I just need to make sure | |
// the ascii value is within range. | |
func IsDigit(b byte) bool { | |
n := int(b) | |
// 48-57 are ASCII values for 0-9 | |
return (n > 47 && n < 58) | |
} | |
// IsRepeatable checks to see if a character is allowed to be | |
// repeated based on the challenge rules. Why isn't this a regex? | |
// I'm dealing with a single char at a time, a regex would be | |
// overkill for this. | |
func IsRepeatable(b byte) bool { | |
n := int(b) | |
// space - /, a-Z (ASCII values) | |
return (n > 31 && n < 47) || (n > 64 && n < 91) || (n > 96 && n < 123) | |
} | |
// ReadDigits reads the next n characters until a non numeric | |
// character is found. Returns the integer value. | |
func ReadDigits(data *string, i int) (int, int, error) { | |
d := *data | |
ln := len(d) | |
// keep reading the next characters until we encounter a non | |
// digit element. | |
n := []string{string(d[i])} | |
j := i + 1 | |
for j < ln { | |
if !IsDigit(d[j]) { | |
break | |
} | |
n = append(n, string(d[j])) | |
j++ | |
} | |
// convert the sequence into an integer | |
r, err := strconv.Atoi(strings.Join(n, "")) | |
return r, j, err | |
} | |
// ReadChars reads alphabet characters until non alphabet char is found. | |
// Returns the resulting string. | |
func ReadChars(data *string, i int) (int, string) { | |
d := *data | |
ln := len(d) | |
// character buffer | |
c := []string{} | |
j := i | |
for j < ln { | |
if !IsRepeatable(d[j]) { | |
break | |
} | |
c = append(c, string(d[j])) | |
j++ | |
} | |
return j, strings.Join(c, "") | |
} | |
// main | |
func main() { | |
for k, v := range TestCases { | |
fmt.Printf("TESTING SEQUENCE %s\n", k) | |
seq := Sequence{} | |
result, err := seq.Decompress(k) | |
if err != nil { | |
fmt.Printf("%s\nFAILED\n\n", err.Error()) | |
continue | |
} | |
fmt.Printf("EXPECTED: %s, GOT %s\n", v, *result) | |
if *result != v { | |
fmt.Printf("FAILED\n\n") | |
} else { | |
fmt.Printf("PASSED\n\n") | |
} | |
// b, _ := json.MarshalIndent(seq, "", "\t") | |
// fmt.Printf("TOKENS: %s\n", string(b)) | |
} | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
For cleanliness I would change your main loop to something akin to:
I would also document your magic numbers.