summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorDimitri Sokolyuk <demon@dim13.org>2016-08-22 21:38:03 +0200
committerDimitri Sokolyuk <demon@dim13.org>2016-08-22 21:38:03 +0200
commit62fe21882de2d65f529d81a5f283712bd5814c63 (patch)
treee81fba17dfe725cb85246eac13e3cd5880452188
Inital import
-rw-r--r--cmd/genset.go21
-rw-r--r--main.go101
-rw-r--r--main_test.go44
3 files changed, 166 insertions, 0 deletions
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)
+ }
+}