From 62fe21882de2d65f529d81a5f283712bd5814c63 Mon Sep 17 00:00:00 2001 From: Dimitri Sokolyuk Date: Mon, 22 Aug 2016 21:38:03 +0200 Subject: Inital import --- cmd/genset.go | 21 ++++++++++++ main.go | 101 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ main_test.go | 44 +++++++++++++++++++++++++ 3 files changed, 166 insertions(+) create mode 100644 cmd/genset.go create mode 100644 main.go create mode 100644 main_test.go diff --git a/cmd/genset.go b/cmd/genset.go new file mode 100644 index 0000000..4138c62 --- /dev/null +++ b/cmd/genset.go @@ -0,0 +1,21 @@ +package main + +import ( + "fmt" + "math/rand" + "time" +) + +func main() { + rand.Seed(time.Now().UnixNano()) + n := 100000 + fmt.Println(n) + for i := 0; i < n; i++ { + k := 1e9 - rand.Intn(1e10) + if rand.Intn(2)%2 == 0 { + fmt.Println("insert", k) + } else { + fmt.Println("delete", k) + } + } +} diff --git a/main.go b/main.go new file mode 100644 index 0000000..bfbdc7c --- /dev/null +++ b/main.go @@ -0,0 +1,101 @@ +// http://www.spoj.com/problems/HOMO/ + +package main + +import ( + "bufio" + "io" + "os" + "runtime/pprof" + "strconv" + "strings" +) + +type List struct { + Data []int + Map map[int]int +} + +func (l *List) Insert(n int) { + l.Data = append(l.Data, n) + l.Map[n]++ +} + +func (l *List) Delete(n int) { + for i, v := range l.Data { + if v == n { + l.Data = append(l.Data[:i], l.Data[i+1:]...) + switch l.Map[n] { + case 1: + delete(l.Map, n) + default: + l.Map[n]-- + } + return + } + } +} + +func (l List) IsHomo() bool { + var top int + for _, v := range l.Map { + if v > top { + top = v + } + } + return top > 1 +} + +func (l List) IsHetero() bool { + return len(l.Map) > 1 +} + +func Split(s string) (string, int) { + i := strings.Index(s, " ") + n, _ := strconv.Atoi(s[i+1:]) + return s[:i], n +} + +func (l List) String() string { + homo, hetero := l.IsHomo(), l.IsHetero() + switch { + case homo && hetero: + return "both" + case hetero: + return "hetero" + case homo: + return "homo" + default: + return "neither" + } +} + +func Homo(r io.Reader, w io.Writer) { + scanner := bufio.NewScanner(r) + scanner.Scan() + n, _ := strconv.Atoi(scanner.Text()) + + l := List{ + Data: make([]int, 0, n), + Map: make(map[int]int), + } + + for scanner.Scan() { + s, n := Split(scanner.Text()) + switch s { + case "insert": + l.Insert(n) + case "delete": + l.Delete(n) + } + io.WriteString(w, l.String()) + io.WriteString(w, "\n") + } +} + +func main() { + f, _ := os.Create("cpu.out") + pprof.StartCPUProfile(f) + defer pprof.StopCPUProfile() + Homo(os.Stdin, os.Stdout) +} diff --git a/main_test.go b/main_test.go new file mode 100644 index 0000000..b969b40 --- /dev/null +++ b/main_test.go @@ -0,0 +1,44 @@ +package main + +import ( + "io/ioutil" + "os" + "strings" + "testing" +) + +const input = `11 +insert 1 +insert 2 +insert 1 +insert 4 +delete 1 +delete 3 +delete 2 +delete 1 +insert 4 +delete 4 +delete 4 +` + +func ExampleHomo() { + Homo(strings.NewReader(input), os.Stdout) + // Output: + // neither + // hetero + // both + // both + // hetero + // hetero + // hetero + // neither + // homo + // neither + // neither +} + +func BenchmarkHomo(b *testing.B) { + for i := 0; i < b.N; i++ { + Homo(strings.NewReader(input), ioutil.Discard) + } +} -- cgit v1.2.3