Skip to content

Instantly share code, notes, and snippets.

@joelsimonoff
Last active April 25, 2017 04:38
Show Gist options
  • Save joelsimonoff/543a3d89a6885d677c16e13614f5558e to your computer and use it in GitHub Desktop.
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.
//
// 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