Data Structures and Algorithms

.PHONY: test solutions progress vet

# Test your exercises (every module). Expect failures until you implement them.
test:
	go test ./0* ./10*

# Test the reference solutions — should be all green.
solutions:
	go test -tags solutions ./...

# Show a per-module progress report.
progress:
	go run ./cmd/progress

# Vet both builds.
vet:
	go vet ./...
	go vet -tags solutions ./...

module github.com/bozcode/go-dsa-course

go 1.22

// Command progress runs the course tests and shows how far along you are.
//
//	go run ./cmd/progress                 # your exercises
//	go run ./cmd/progress -tags solutions # the reference solutions (all green)
//
// Any arguments are passed straight through to `go test`.
package main

import (
	"bufio"
	"bytes"
	"encoding/json"
	"fmt"
	"os"
	"os/exec"
	"path/filepath"
	"regexp"
	"sort"
	"strings"
)

type module struct {
	dir      string   // e.g. "01-arrays"
	title    string   // e.g. "Arrays"
	tests    []string // top-level test names, in file order
	passed   map[string]bool
	failed   map[string]bool
	buildErr bool
}

var testFunc = regexp.MustCompile(`(?m)^func (Test\w+)\(t \*testing\.T\)`)

func main() {
	root, err := findRoot()
	if err != nil {
		fmt.Fprintln(os.Stderr, err)
		os.Exit(1)
	}

	mods, err := discover(root)
	if err != nil {
		fmt.Fprintln(os.Stderr, err)
		os.Exit(1)
	}

	args := append([]string{"test", "-json", "-count=1"}, os.Args[1:]...)
	for _, m := range mods {
		args = append(args, "./"+m.dir+"/")
	}
	cmd := exec.Command("go", args...)
	cmd.Dir = root
	var out bytes.Buffer
	cmd.Stdout = &out
	cmd.Stderr = &out
	_ = cmd.Run() // a non-zero exit just means some tests fail

	byPkg := map[string]*module{}
	for _, m := range mods {
		byPkg[m.dir] = m
	}
	sc := bufio.NewScanner(&out)
	sc.Buffer(make([]byte, 1024*1024), 1024*1024)
	for sc.Scan() {
		var ev struct {
			Action  string
			Package string
			Test    string
			Output  string
		}
		if json.Unmarshal(sc.Bytes(), &ev) != nil {
			continue
		}
		m := byPkg[filepath.Base(ev.Package)]
		if m == nil {
			continue
		}
		if ev.Test == "" {
			if ev.Action == "output" && strings.Contains(ev.Output, "[build failed]") {
				m.buildErr = true
			}
			continue
		}
		if strings.Contains(ev.Test, "/") {
			continue // subtest
		}
		switch ev.Action {
		case "pass":
			m.passed[ev.Test] = true
		case "fail":
			m.failed[ev.Test] = true
		}
	}

	report(mods)
}

func report(mods []*module) {
	fmt.Println()
	fmt.Println("  Data Structures and Algorithms in Go — progress")
	fmt.Println()
	total, done := 0, 0
	var nextMod *module
	var nextTest string
	for i, m := range mods {
		n := len(m.tests)
		p := 0
		for _, t := range m.tests {
			if m.passed[t] {
				p++
			} else if nextMod == nil {
				nextMod, nextTest = m, t
			}
		}
		total += n
		done += p

		status := ""
		switch {
		case m.buildErr:
			status = "  ✗ doesn't compile — run: go vet ./" + m.dir + "/"
		case p == n:
			status = "  ✓ complete"
		}
		fmt.Printf("  %2d  %-20s %s  %2d/%-2d%s\n", i+1, m.title, bar(p, n, 12), p, n, status)
	}
	fmt.Println()
	fmt.Printf("  Overall: %d/%d tests passing (%d%%)\n", done, total, pct(done, total))
	if nextMod != nil {
		fmt.Printf("  Next up: %s → %s\n", nextMod.title, nextTest)
		fmt.Printf("           go test -run '^%s$' -v ./%s/\n", nextTest, nextMod.dir)
	} else {
		fmt.Println("  Every test passes. Nice work.")
	}
	fmt.Println()
}

func bar(p, n, width int) string {
	if n == 0 {
		return strings.Repeat("·", width)
	}
	filled := p * width / n
	return strings.Repeat("█", filled) + strings.Repeat("░", width-filled)
}

func pct(a, b int) int {
	if b == 0 {
		return 0
	}
	return a * 100 / b
}

// discover finds the numbered module directories and their test names.
func discover(root string) ([]*module, error) {
	entries, err := os.ReadDir(root)
	if err != nil {
		return nil, err
	}
	numbered := regexp.MustCompile(`^\d\d-`)
	var mods []*module
	for _, e := range entries {
		if !e.IsDir() || !numbered.MatchString(e.Name()) {
			continue
		}
		m := &module{
			dir:    e.Name(),
			title:  titleFor(e.Name()),
			passed: map[string]bool{},
			failed: map[string]bool{},
		}
		files, _ := filepath.Glob(filepath.Join(root, e.Name(), "*_test.go"))
		sort.Strings(files)
		for _, f := range files {
			src, err := os.ReadFile(f)
			if err != nil {
				return nil, err
			}
			for _, match := range testFunc.FindAllSubmatch(src, -1) {
				m.tests = append(m.tests, string(match[1]))
			}
		}
		mods = append(mods, m)
	}
	sort.Slice(mods, func(i, j int) bool { return mods[i].dir < mods[j].dir })
	if len(mods) == 0 {
		return nil, fmt.Errorf("no module directories found under %s", root)
	}
	return mods, nil
}

// titleFor turns "03-linked-lists" into "Linked Lists".
func titleFor(dir string) string {
	words := strings.Split(dir[3:], "-")
	for i, w := range words {
		words[i] = strings.ToUpper(w[:1]) + w[1:]
	}
	return strings.Join(words, " ")
}

// findRoot walks up from the working directory to the directory holding go.mod.
func findRoot() (string, error) {
	dir, err := os.Getwd()
	if err != nil {
		return "", err
	}
	for {
		if _, err := os.Stat(filepath.Join(dir, "go.mod")); err == nil {
			return dir, nil
		}
		parent := filepath.Dir(dir)
		if parent == dir {
			return "", fmt.Errorf("go.mod not found — run this from inside the course folder")
		}
		dir = parent
	}
}