Last active
April 25, 2017 04:38
-
-
Save joelsimonoff/543a3d89a6885d677c16e13614f5558e to your computer and use it in GitHub Desktop.
Code that solves the problem of organizing an array (I used a golang slice) with a random distribution of red, green and blue values, into red values followed by blue values followed by green values, in O(n) time.
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
// | |
// Written By Joel Simonoff | |
// April 24, 2017 | |
// | |
package main | |
import ( | |
"fmt" | |
"math/rand" | |
"time" | |
) | |
func main() { | |
failCount := 0 | |
numRuns := 100 | |
numVals := 67 | |
for i := 0; i < numRuns; i++ { | |
s := generateData(numVals) | |
fmt.Printf("Run 1\nBefore: %v\n\n", s) | |
rgb(&s) | |
if validateResult(s) { | |
fmt.Printf("After: %v\nTest Passed!\n\n", s) | |
} else { | |
failCount++ | |
fmt.Printf("TEST FAILED 😐 After:%v\n\n", s) | |
} | |
} | |
fmt.Printf("Summary\nNum Fails: %v,\nNum Runs: %v,\nNum Vals Per Run: %v\n", failCount, numRuns, numVals) | |
} | |
// | |
// r = 0, g = 1, b = 2 | |
// | |
func rgb(p *([]int)) { | |
s := *p | |
g := -1 | |
b := -1 | |
for i := range s { | |
if s[i] == 2 { | |
handleBlue(s, i, &b) | |
continue | |
} | |
if s[i] == 1 { | |
handleGreen(s, i, &b, &g) | |
continue | |
} | |
handleRed(s, i, &b, &g) | |
} | |
*p = s | |
} | |
func handleBlue(s []int, i int, b *int) { | |
checkNotSetAndReplace(b, i) | |
} | |
func handleGreen(s []int, i int, b, g *int) { | |
if *b != -1 { | |
swap(s, i, *b) | |
*b++ | |
checkNotSetAndReplace(g, *b-1) | |
return | |
} | |
checkNotSetAndReplace(g, i) | |
} | |
func handleRed(s []int, i int, b, g *int) { | |
if *g != -1 { | |
swap(s, i, *g) | |
*g++ | |
} | |
if *b != -1 { | |
swap(s, i, *b) | |
*b++ | |
} | |
} | |
func validateResult(s []int) bool { | |
for i := 0; i < len(s)-1; i++ { | |
if s[i] > s[i+1] { | |
return false | |
} | |
} | |
return true | |
} | |
// checkNotSetAndReplace replaces the value at location v with i if *v == -1. | |
func checkNotSetAndReplace(v *int, i int) { | |
if *v == -1 { | |
*v = i | |
} | |
} | |
func swap(s []int, l int, r int) { | |
s[l], s[r] = s[r], s[l] | |
} | |
func generateData(n int) []int { | |
rand.Seed(time.Now().UnixNano()) | |
s := make([]int, n) | |
for i := 0; i < n; i++ { | |
s[i] = rand.Intn(3) | |
} | |
return s | |
} | |
func printSlice(s []int) { | |
for _, i := range s { | |
fmt.Print(i) | |
} | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment