Find length of the largest region in Boolean Matrix

largest-region.go

// https://www.geeksforgeeks.org/find-length-largest-region-boolean-matrix/
package main

import (
	"container/ring"
	"fmt"
	"sort"
	"strconv"
	"strings"
	"sync"
)

/**
0,0,1,1,0
1,0,1,1,0
0,1,0,0,0
0,0,0,0,1
**/

type direction int

func (d direction) all() []direction {
	return []direction{
		north,
		south,
		east,
		west,
		northeast,
		northwest,
		southeast,
		southwest,
	}
}

func (d direction) others() []direction {
	for i, cDir := range d.all() {
		if d == cDir {
			return append(d.all()[:i], d.all()[i+1:]...)
		}
	}

	return d.all()
}

const (
	nodir direction = iota
	north
	south
	east
	west
	northeast
	northwest
	southeast
	southwest
)

type point struct {
	I, J int
}

func (p *point) String() string {
	return fmt.Sprintf("(%d,%d)", p.I, p.J)
}

type pointToPoint struct {
	from point
	to   point
}

type pointAndDirection struct {
	current point
	dir     direction
}

type walker struct {
	from      point
	current   point
	direction direction
}

func (w *walker) walk(matrix [][]int) chan pointToPoint {
	visited := make(chan pointToPoint)
	go func() {
		defer close(visited)
		for {
			for _, p := range w.surroundings() {
				if (p.I >= 0 && p.J >= 0) && (p.I < len(matrix) && p.J < len(matrix[p.I])) {
					if matrix[p.I][p.J] == 1 {
						p2p := pointToPoint{
							from: w.current,
							to:   p,
						}

						visited <- p2p
					}
				}
			}

			nextPoint := w.nextPointIn(w.direction)
			if nextPoint.I < 0 || nextPoint.J < 0 || nextPoint.I >= len(matrix) || nextPoint.J >= len(matrix[nextPoint.I]) || matrix[nextPoint.I][nextPoint.J] == 0 {
				break
			}

			w.current = nextPoint
		}
	}()

	return visited
}

func (w *walker) surroundings() []point {
	var allDirectionPoints []point

	for _, dir := range w.direction.all() {
		allDirectionPoints = append(allDirectionPoints, w.nextPointIn(dir))
	}

	return allDirectionPoints
}

func (w *walker) nextPointIn(dir direction) point {
	switch dir {
	case north:
		return point{
			I: w.current.I - 1,
			J: w.current.J,
		}
	case south:
		return point{
			I: w.current.I + 1,
			J: w.current.J,
		}
	case east:
		return point{
			I: w.current.I,
			J: w.current.J + 1,
		}
	case west:
		return point{
			I: w.current.I,
			J: w.current.J - 1,
		}
	case northeast:
		return point{
			I: w.current.I - 1,
			J: w.current.J + 1,
		}
	case northwest:
		return point{
			I: w.current.I - 1,
			J: w.current.J - 1,
		}
	case southeast:
		return point{
			I: w.current.I + 1,
			J: w.current.J + 1,
		}
	case southwest:
		return point{
			I: w.current.I + 1,
			J: w.current.J - 1,
		}
	default:
		return w.current
	}
}

type paths struct {
	sync.Mutex
	z map[point][]point
}

var pathz paths

func main() {
	pathz = paths{
		z: make(map[point][]point),
	}
	input := "{0,0,1,1,0},{1,0,1,1,0},{0,1,0,0,0},{0,0,0,0,1}"
	var matrix [][]int
	// reader := bufio.NewReader(os.Stdin)
	// line, _ := reader.ReadString(byte('\n'))
	// convert line to array
	parts := strings.Split(input, "},")
	replacer := strings.NewReplacer("{", "", "}", "")
	for _, part := range parts {
		txt := replacer.Replace(part)
		nums := strings.Split(txt, ",")
		var nstr []int
		for _, num := range nums {
			n, _ := strconv.Atoi(num)
			nstr = append(nstr, n)
		}

		matrix = append(matrix, nstr)
	}

	r := ring.New(len(nodir.all()))
	all := nodir.all()
	for i := 0; i < r.Len(); i++ {
		r.Value = all[i]
		r = r.Next()
	}

	var waiter sync.WaitGroup

	look := func(i, j int, waiter *sync.WaitGroup) {
		defer waiter.Done()
		d, _ := r.Value.(direction)
		w := &walker{
			direction: d,
			from: point{
				I: i,
				J: j,
			},
			current: point{
				I: i,
				J: j,
			},
		}

		r = r.Next()

		for p := range w.walk(matrix) {
			if !(w.from.I == p.to.I && w.from.J == p.to.J) {
				there := false
				pathz.Lock()
				for _, v := range pathz.z[w.from] {
					if p.to.I == v.I && p.to.J == v.J {
						there = true
						break
					}
				}
				if !there {
					pathz.z[w.from] = append(pathz.z[w.from], p.to)
				}
				pathz.Unlock()
			}
		}
	}

	for i, row := range matrix {
		for j, _ := range row {
			if matrix[i][j] == 1 {
				waiter.Add(1)
				go look(i, j, &waiter)
			}
		}
	}

	waiter.Wait()

	// check for longest chain
	maxLen := 0
	var largestChain point
	for p, ps := range pathz.z {
		if len(ps) > maxLen {
			maxLen = len(ps)
			largestChain = p
		}
	}

	var group []point
	group = append(group, pathz.z[largestChain]...)
	for _, p := range group {
		for _, pt := range pathz.z[p] {
			found := false
			for _, pi := range group {
				if pi.I == pt.I && pi.J == pt.J {
					found = true
					break
				}
			}
			if !found {
				group = append(group, pt)
			}
		}
	}

	sort.Slice(group, func(i, j int) bool {
		return group[i].J < group[j].J
	})

	sort.Slice(group, func(i, j int) bool {
		return group[i].I < group[j].I
	})

	fmt.Println(group)
	fmt.Printf("Max Count: %d\n", len(group))
}