5.5 Celebrity Problem - Introduction to Algorithms by Udi Manber

celebrity.go

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
}

input_celeb_3.txt

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

input_no_celeb.txt

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