Plotting solution for https://leetcode.com/problems/number-of-islands

plot_matrix.go

package main

import (
	"image"
	"image/color"
	"image/png"
	"io"
	"math/rand"
	"net/http"
	"time"
)

const (
	Scale = 20
)

var matrix [][]byte = [][]byte{
	{1, 0, 0, 1, 1, 1, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
	{1, 0, 0, 1, 1, 0, 0, 1, 0, 0, 0, 1, 0, 1, 0, 1, 0, 0, 1, 0},
	{0, 0, 0, 1, 1, 1, 1, 0, 1, 0, 1, 1, 0, 0, 0, 0, 1, 0, 1, 0},
	{0, 0, 0, 1, 1, 0, 0, 1, 0, 0, 0, 1, 1, 1, 0, 0, 1, 0, 0, 1},
	{0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
	{1, 0, 0, 0, 0, 1, 0, 1, 0, 1, 1, 0, 0, 0, 0, 0, 0, 1, 0, 1},
	{0, 0, 0, 1, 0, 0, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1},
	{0, 0, 0, 1, 0, 1, 0, 0, 1, 1, 0, 1, 0, 1, 1, 0, 1, 1, 1, 0},
	{0, 0, 0, 0, 1, 0, 0, 1, 1, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 1},
	{0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 1, 0},
	{1, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 1, 0, 1, 0, 1, 0},
	{0, 1, 0, 0, 0, 1, 0, 1, 0, 1, 1, 0, 1, 1, 1, 0, 1, 1, 0, 0},
	{1, 1, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1},
	{0, 1, 0, 0, 1, 1, 1, 0, 0, 0, 1, 1, 1, 1, 1, 0, 1, 0, 0, 0},
	{0, 0, 1, 1, 1, 0, 0, 0, 1, 1, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0},
	{1, 0, 0, 1, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 1, 0, 1, 1},
	{1, 0, 1, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0},
	{0, 1, 1, 0, 0, 0, 1, 1, 1, 0, 1, 0, 1, 0, 1, 1, 1, 1, 0, 0},
	{0, 1, 0, 0, 0, 0, 1, 1, 0, 0, 1, 0, 1, 0, 0, 1, 0, 0, 1, 1},
	{0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 0, 1, 0, 0, 0, 1, 1, 0, 0, 0},
}

func main() {
	rand.Seed(time.Now().UTC().UnixNano())
	http.HandleFunc("/render", handleRender)
	http.ListenAndServe(":9090", nil)
}

func handleRender(w http.ResponseWriter, r *http.Request) {
	w.Header().Set("Content-Type", "image/png")
	colors := colorIslands(matrix)
	plotPNG(matrix, colors, w)
}

func RandUInt8() uint8 {
	return uint8(rand.Intn(0xFF))
}

func RandColor() color.Color {
	return color.NRGBA{RandUInt8(), RandUInt8(), RandUInt8(), 255}
}

func plotPNG(matrix [][]byte, colors map[uint64]color.Color, out io.Writer) {
	rect := image.Rect(0, 0, len(matrix[0])*Scale, len(matrix)*Scale)
	img := image.NewNRGBA(rect)
	for i, maxi := 0, len(matrix)-1; i <= maxi; i++ {
		for j, maxj := 0, len(matrix[0])-1; j <= maxj; j++ {
			var c color.Color
			if v, iscolored := colors[IndexToUInt64(i, j)]; iscolored {
				c = v
			} else {
				c = color.White
			}
			for y, maxy := i*Scale, i*Scale+Scale-1; y <= maxy; y++ {
				for x, maxx := j*Scale, j*Scale+Scale-1; x <= maxx; x++ {
					img.Set(x, y, c)
				}
			}

		}
	}

	if err := png.Encode(out, img); err != nil {
		panic(err.Error())
	}
}

func colorIslands(grid [][]byte) map[uint64]color.Color {
	if len(grid) == 0 {
		return nil
	}
	forest := make(map[uint64]uint64)
	for i, maxi := 0, len(grid)-1; i <= maxi; i++ {
		for j, maxj := 0, len(grid[i])-1; j <= maxj; j++ {
			if grid[i][j] == 0 {
				continue
			}
			p := IndexToUInt64(i, j)
			parents := make([]uint64, 0, 2)
			if i > 0 && grid[i-1][j] > 0 {
				parents = append(parents, forest[IndexToUInt64(i-1, j)])
			}
			if j > 0 && grid[i][j-1] > 0 {
				parents = append(parents, forest[IndexToUInt64(i, j-1)])
			}
			switch len(parents) {
			case 0:
				forest[p] = p
			case 1:
				forest[p] = parents[0]
			case 2:
				p1, p2 := parents[0], parents[1]
				forest[p2] = p1
				for k, v := range forest {
					if v == p2 {
						forest[k] = p1
					}
				}
				forest[p] = p1
			default:
				panic("should not happen")
			}
		}
	}
	parentColors := make(map[uint64]color.Color)
	colorForest := make(map[uint64]color.Color)
	for pixel, parent := range forest {
		if _, ok := parentColors[parent]; !ok {
			parentColors[parent] = RandColor()
		}
		colorForest[pixel] = parentColors[parent]
	}

	return colorForest
}

func IndexToUInt64(i, j int) uint64 {
	return uint64(i)<<32 | uint64(j)
}

func UInt64ToIndex(p uint64) (int, int) {
	return int(p >> 32), int(p & 0xFFFFFFFF)
}