// Week 6 – Solutions of the practice exercises
// Run: go run ./w06/exercises
package main

import (
	"fmt"
	"slices"
	"strings"
)

// E1. Removing duplicates by sorting
func distinct(a []int) []int {
	b := slices.Clone(a)
	slices.Sort(b)
	return slices.Compact(b) // merges neighbouring equal elements
}

// E2. Symmetric difference on sorted slices – O(n + m)
func symmetricDifference(a, b []int) []int {
	var c []int
	i, j := 0, 0
	for i < len(a) && j < len(b) {
		switch {
		case a[i] < b[j]:
			c = append(c, a[i])
			i++
		case a[i] > b[j]:
			c = append(c, b[j])
			j++
		default:
			i++
			j++
		}
	}
	c = append(c, a[i:]...)
	return append(c, b[j:]...)
}

// E3. Disjoint?
func disjoint(a, b []int) bool {
	i, j := 0, 0
	for i < len(a) && j < len(b) {
		if a[i] == b[j] {
			return false
		}
		if a[i] < b[j] {
			i++
		} else {
			j++
		}
	}
	return true
}

// E4. Power set with bit masks
func powerSet(u []string) []string {
	var res []string
	for mask := 0; mask < 1<<len(u); mask++ {
		var parts []string
		for i := range u {
			if mask&(1<<i) != 0 {
				parts = append(parts, u[i])
			}
		}
		res = append(res, "{"+strings.Join(parts, ", ")+"}")
	}
	return res
}

// E5. Number of distinct letters with a boolean vector
func distinctLetters(s string) int {
	var seen [26]bool
	c := 0
	for _, ch := range strings.ToLower(s) {
		if ch >= 'a' && ch <= 'z' && !seen[ch-'a'] {
			seen[ch-'a'] = true
			c++
		}
	}
	return c
}

// E6. Pangram
func isPangram(s string) bool { return distinctLetters(s) == 26 }

// E7. Common friends with a map
func commonFriends(a, b []string) []string {
	inB := map[string]bool{}
	for _, x := range b {
		inB[x] = true
	}
	var res []string
	for _, x := range a {
		if inB[x] {
			res = append(res, x)
		}
	}
	slices.Sort(res)
	return res
}

func main() {
	fmt.Println("E1. distinct([4 1 4 2 1]) =", distinct([]int{4, 1, 4, 2, 1}))
	fmt.Println("E2. {1,3,5,7} △ {3,4,5,6} =", symmetricDifference([]int{1, 3, 5, 7}, []int{3, 4, 5, 6}))
	fmt.Println("E3. disjoint({1,3,5},{2,4,6}) =", disjoint([]int{1, 3, 5}, []int{2, 4, 6}),
		", disjoint({1,3,5},{5,6}) =", disjoint([]int{1, 3, 5}, []int{5, 6}))
	fmt.Println("E4. P({a,b,c}) =", powerSet([]string{"a", "b", "c"}))
	fmt.Println(`E5. distinctLetters("Hello World") =`, distinctLetters("Hello World"))
	fmt.Println("E6. isPangram(...) =", isPangram("The quick brown fox jumps over the lazy dog"))
	fmt.Println("E7. common friends:", commonFriends([]string{"Li", "Wang", "Anna", "Chen"}, []string{"Chen", "Peter", "Li"}))
}