Skip to content

Instantly share code, notes, and snippets.

@yosu yosu/celebrity.go
Last active Feb 3, 2016

Embed
What would you like to do?
5.5 Celebrity Problem - Introduction to Algorithms by Udi Manber
package main
import (
"bufio"
"flag"
"fmt"
"os"
"strconv"
"strings"
)
type Reader struct {
*bufio.Scanner
}
func NewReader() *Reader {
scanner := bufio.NewScanner(os.Stdin)
return &Reader{scanner}
}
func (r *Reader) scanInt() int {
r.Scan()
n, _ := strconv.Atoi(r.Text())
return n
}
func (r *Reader) scanIntArray() []int {
text := r.scanText()
strs := strings.Split(text, " ")
ints := make([]int, len(strs))
for i, v := range strs {
ints[i], _ = strconv.Atoi(v)
}
return ints
}
func (r *Reader) scanText() string {
r.Scan()
return r.Text()
}
func main() {
r := NewReader()
n := r.scanInt()
m := [][]int{}
for i := 0; i < n; i++ {
m = append(m, r.scanIntArray())
}
var algorithm = flag.Int("algorithm", 1, "select algorithm type: 1 - simple, 2 - fine")
flag.Parse()
fmt.Fprintf(os.Stderr, "Algorithm: %d\n", *algorithm)
celeb := findCelebrity(m, *algorithm)
if celeb != -1 {
fmt.Printf("%d\n", celeb+1)
} else {
fmt.Println("no celeb")
}
}
func knownByAll(m [][]int, j int) bool {
for i := 0; i < len(m); i++ {
if m[i][j] == 0 && i != j {
return false
}
}
return true
}
func knowAny(m [][]int, i int) bool {
for j := 0; j < len(m); j++ {
if m[i][j] == 1 && i != j {
return true
}
}
return false
}
func findCandidate(m [][]int) int {
i := 0
j := 1
next := 2
n := len(m)
for next <= n {
if m[i][j] == 1 {
i = next
} else {
j = next
}
next = next + 1
}
if i == n {
return j
}
return i
}
func findCelebrity(m [][]int, algorithm int) int {
if algorithm == 1 {
return findCelebrity1(m)
}
return findCelebrity2(m)
}
func findCelebrity1(m [][]int) int {
for i := 0; i < len(m); i++ {
if !knowAny(m, i) && knownByAll(m, i) {
return i
}
}
return -1
}
func findCelebrity2(m [][]int) int {
c := findCandidate(m)
if knownByAll(m, c) && !knowAny(m, c) {
return c
}
return -1
}
5
0 0 1 0 0
1 0 1 0 0
0 0 0 0 0
1 0 1 0 0
1 1 1 1 0
5
0 0 1 0 0
1 0 1 0 0
0 0 0 1 0
1 0 1 0 0
1 1 1 1 0
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.