My Random Tech Stuff: August 2012

Tuesday, August 14, 2012

How to Solve 3-Sum Problem

Given a set S of n integers, are there elements a, b, c in S such that a + b + c = 0?

package main
 
import (
    "fmt"
    "sort"
)
 
func ThreeSum(numbers []int) {
    for i := 0; i < len(numbers); i++ {
        for j := 0; j < len(numbers); j++ {
            nSearch := -(numbers[i] + numbers[j])
            index := sort.SearchInts(numbers, nSearch)
            if index < len(numbers) && numbers[index] == nSearch {
                fmt.Println(numbers[i], numbers[j], numbers[index])
            }
        }
    }
}
 
func main() {
    numbers := []int{-40, 30, -10, 50, 20}
    sortedNumbers := sort.IntSlice(numbers)
    sort.Sort(sortedNumbers)
    ThreeSum(sortedNumbers)
}

Monday, August 13, 2012

A Tool to Escape HTML Characters in Go

I created a handy tool to escape HTML characters, especially for pasting code in a blog like this.

Usage: ./escapehtml  [dest_dir]

If the source is a directory, the tool will scan the whole directory and escape each file found and output the escaped string to stdout (if dest_dir isn't specified) or to a file (if dest_dir is specified).

escapehtml.go

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

package main
 
import (
    "fmt"
    "os"
    "errors"
    "path/filepath"
    "io/ioutil"
    "html"
    "strings"
)
 
func printUsage() {
    fmt.Println("Usage:", os.Args[0],
        "<source_file/source_dir>", "[dest_dir]")
}
 
func errorMessage(s string) string {
    return "Error: " + s
}
 
type fileType struct {
    directory bool
    regularFile bool
}
 
func fileExists(path string) (*fileType, error) {
    file, err := os.Open(path)
    if err != nil {
        if os.IsNotExist(err) {
            return nil, errors.New(
                errorMessage(path + " does not exist"))
        }
    }
    defer file.Close()
    fileInfo, err := file.Stat()
    if err != nil {
        return nil, err
    }
    if fileInfo.IsDir() {
        return &fileType{directory: true}, nil
    }
    return &fileType{regularFile: true}, nil
}
 
func validateArgs() (bool, error) {
    if len(os.Args) != 2 && len(os.Args) != 3 {
        return false, nil
    }
 
    if _, err := fileExists(os.Args[1]); err != nil {
        return false, err
    }
    if len(os.Args) == 3 {
        ft, _ := fileExists(os.Args[2])
        if ft != nil && !ft.directory {
            return false, errors.New(
                errorMessage(os.Args[2] + " must be a directory"))
        }
    }
    return true, nil
}
 
func printHeader(header string) {
    fmt.Println(strings.Repeat("=", 72))
    fmt.Println(header)
    fmt.Println(strings.Repeat("=", 72))
}
 
func escapeHTML(srcPath string, destPath string) {
    filepath.Walk(srcPath,
        func(path string, info os.FileInfo, err error) error {
            if info.IsDir() {
                return nil
            }
 
            b, err := ioutil.ReadFile(path)
            if err != nil {
                return nil
            }
 
            escapedString := html.EscapeString(string(b))
            if destPath == "" {
                printHeader(path)
                fmt.Println(escapedString)
            } else {
                if ft, _ := fileExists(destPath); ft == nil {
                    if e := os.MkdirAll(destPath, 0775); e != nil {
                        errors.New("Unable to create directory: " +
                            destPath)
                    } else {
                        fmt.Println("Creating directory: " + destPath)
                    }
                }
                newPath := filepath.Join(destPath,
                    filepath.Base(path) + ".txt")
                fmt.Println("Creating", newPath)
                e := ioutil.WriteFile(newPath, []byte(escapedString), 0644)
                if e != nil {
                    return e
                }
            }
            return nil
        })
}
 
func main() {
    if valid, err := validateArgs(); !valid {
        if err != nil {
            fmt.Println(err)
            os.Exit(1)
        } else {
            printUsage()
            os.Exit(1)
        }
    }
 
    srcPath := os.Args[1]
    destPath := ""
    if len(os.Args) == 3 {
        destPath = os.Args[2]
    }
    escapeHTML(srcPath, destPath)
}

To build it, just type

go build escapehtml.go

Sunday, August 12, 2012

How to Implement Union Find Algorithms

package unionfind
 
type UnionFind interface {
    Find(int, int) bool
    Union(int, int)
}
//================================================
type QuickFind struct {
    Nodes []int
}
 
func (qf *QuickFind) Find(x, y int) bool {
    return qf.Nodes[x] == qf.Nodes[y]
}
 
func (qf *QuickFind) Union(x, y int) {
    tmp := qf.Nodes[x]
    qf.Nodes[x] = qf.Nodes[y]
    for i := 0; i < len(qf.Nodes); i++ {
        if qf.Nodes[i] == tmp {
            qf.Nodes[i] = qf.Nodes[y]
        }
    }
}
//================================================
type QuickUnion struct {
    Nodes []int
}
 
func (qu *QuickUnion) Find(x, y int) bool {
    return qu.root(x) == qu.root(y)
}
 
func (qu *QuickUnion) Union(x, y int) {
    rootX := qu.root(x)
    rootY := qu.root(y)
    qu.Nodes[rootX] = qu.Nodes[rootY]
}
 
func (qu *QuickUnion) root(x int) int {
    for qu.Nodes[x] != x {
        x = qu.Nodes[x]
    }
    return x
}
//================================================
type WeightedQuickUnion struct {
    Nodes []int
    sizes []int
}
 
func (wqu *WeightedQuickUnion) Find(x, y int) bool {
    return wqu.root(x) == wqu.root(y)
}
 
func (wqu *WeightedQuickUnion) Union(x, y int) {
    rootX := wqu.root(x)
    rootY := wqu.root(y)
    if wqu.sizes[rootX] < wqu.sizes[rootY] {
        wqu.Nodes[rootX] = wqu.Nodes[rootY]
        wqu.sizes[rootY] += wqu.sizes[rootX]
    } else {
        wqu.Nodes[rootY] = wqu.Nodes[rootX]
        wqu.sizes[rootX] += wqu.sizes[rootY]
    }
}
 
func (wqu *WeightedQuickUnion) root(x int) int {
    for wqu.Nodes[x] != x {
        x = wqu.Nodes[x]
    }
    return x
}

My Random Tech Stuff