diwt/matrix.go

// Copyright 2022 wanderer <wanderer at dotya.ml>
// SPDX-License-Identifier: GPL-3.0-or-later

package main

import (
	"log"
	"os"
	"strconv"
	"strings"
	"time"
)

type matrix struct {
	rows [][]int
}

// stoi attempts to convert a supposed int in string form to an actual int,
// fails loudly if it doesn't work.
func stoi(s string) int {
	val, err := strconv.Atoi(s)
	if err != nil {
		log.Fatalln("could not convert from string to int:", s, err)
	}

	return val
}

// rowtoi converts a row (a []string) to an []int and returns it.
func rowtoi(row []string) []int {
	cols := len(row)

	// prealloc, when the size is known, gosimple is wrong here.
	intRow := make([]int, cols, cols) //nolint:gosimple

	for i, v := range row {
		intRow[i] = stoi(v)
	}

	return intRow
}

// isNonEmptyMatrix checks the [][]string input and determines whether it is a
// non-empty matrix, since that is the kind we care about.
func isNonEmptyMatrix(strmatrix [][]string) bool {
	initCols := len(strmatrix[0])

	if initCols == 0 || len(strmatrix) == 0 {
		log.Printf("emptymatrix: we don't want those")
		return false
	}

	for i, v := range strmatrix {
		cols := len(v)

		if cols != initCols {
			log.Printf(
				"notamatrix: all rows until now were of '%d' columns\n"+
					"offending row: #%d, size: %d",
				initCols, i, cols,
			)

			return false
		}
	}

	return true
}

func initMatrix(strmatrix [][]string) matrix {
	m := &matrix{}
	// we can now safely do this because at this point we have already checked
	// that strmatrix is a "valid" matrix.
	cols := len(strmatrix[0])
	rows := len(strmatrix)

	// prealloc, when the size is known, gosimple is wrong here.
	m.rows = make([][]int, rows, rows) //nolint:gosimple
	for i := range strmatrix {
		// prealloc, when the size is known, gosimple is wrong here.
		m.rows[i] = make([]int, cols, cols) //nolint:gosimple
	}

	return *m
}

// convertMatrix attempts to convert the whole string matrix to an int matrix.
func convertMatrix(strmatrix [][]string) matrix {
	if !isNonEmptyMatrix(strmatrix) {
		log.Fatalln("bailing...")
		os.Exit(2)
	}

	m := initMatrix(strmatrix)

	for i, v := range strmatrix {
		m.rows[i] = rowtoi(v)
	}

	return m
}

// fmtPath efficiently formats positional values for printing.
func fmtPath(x, y, val int) string {
	s := "[" + strconv.Itoa(x) + "," + strconv.Itoa(y) + "] (" +
		strconv.Itoa(val) + ")"
	return s
}

// traverseMatrix traverses the given matrix in such a manner as to accumulate
// the smallest possible sum. allowed movements are down and to the right.
// it also prints a cute ascii path of traversal.
func traverseMatrixMinSumPath(m matrix) {
	start := time.Now()

	cols := len(m.rows[0])
	rows := len(m.rows)
	// current column.
	col := 0
	// current row index.
	i := 0
	sum := m.rows[i][col]
	traversing := true
	path := "init"
	graph := "x"

	log.Printf("matrix cols: %d, rows: %d\n", cols, rows)

	for traversing {
		path += ", " + fmtPath(i, col, m.rows[i][col])

		nextCol := col + 1
		nextRow := i + 1

		switch {
		case nextCol < cols && nextRow < rows:
			// can go either way.
			right := m.rows[i][col+1]
			down := m.rows[i+1][col]

			if right < down {
				col++

				sum += right
				graph += "x"
			} else {
				i++

				sum += down
				graph += "\n" + strings.Repeat(" ", col) + "x"
			}

		case nextRow == rows && nextCol < cols:
			// can only go right.
			col++
			sum += m.rows[i][col]
			graph += "x"

		case nextCol == cols && nextRow < rows:
			// can only go down.
			i++
			sum += m.rows[i][col]
			graph += "\n" + strings.Repeat(" ", col) + "x"

		default:
			path += ", finish"

			log.Printf(
				"traversal concluded with sum: %d\n"+
					"graph:\n%s\n"+
					"traversal path:\n%s\n\n",
				sum, graph, path,
			)

			traversing = false
		}
	}

	log.Printf("traversing the matrix took: %s\n", time.Since(start))
}