package main

import (
	"cmp"
	"container/heap"
	"container/list"
	"fmt"
	"io"
	"os"
	"slices"
	"sort"
)

func lowerBound(a []int, x int) int {
	l, r := 0, len(a)
	for l < r {
		m := l + (r-l)/2
		if a[m] < x {
			l = m + 1
		} else {
			r = m
		}
	}
	return l
}

// The teaching input keeps sums inside int range.
func pairSum(a []int, target int) (int, int, bool) {
	l, r := 0, len(a)-1
	for l < r {
		s := a[l] + a[r]
		if s == target {
			return a[l], a[r], true
		}
		if s < target {
			l++
		} else {
			r--
		}
	}
	return 0, 0, false
}
func minCoins(coins []int, amount int) int {
	if amount < 0 {
		return -1
	}
	for _, c := range coins {
		if c <= 0 {
			panic("coin must be positive")
		}
	}
	d := make([]int, amount+1)
	for v := 1; v <= amount; v++ {
		d[v] = amount + 1
		for _, c := range coins {
			if c <= v {
				d[v] = min(d[v], d[v-c]+1)
			}
		}
	}
	if d[amount] > amount {
		return -1
	}
	return d[amount]
}
func subsets(a []int) [][]int {
	result := [][]int{}
	path := []int{}
	var visit func(int)
	visit = func(i int) {
		if i == len(a) {
			result = append(result, slices.Clone(path))
			return
		}
		visit(i + 1)
		path = append(path, a[i])
		visit(i + 1)
		path = path[:len(path)-1]
	}
	visit(0)
	return result
}
func bfs(g [][]int, start int) []int {
	d := make([]int, len(g))
	for i := range d {
		d[i] = -1
	}
	d[start] = 0
	q := []int{start}
	for head := 0; head < len(q); head++ {
		u := q[head]
		for _, v := range g[u] {
			if d[v] < 0 {
				d[v] = d[u] + 1
				q = append(q, v)
			}
		}
	}
	return d
}
func mergeSort(a []int) []int {
	if len(a) < 2 {
		return slices.Clone(a)
	}
	m := len(a) / 2
	l, r := mergeSort(a[:m]), mergeSort(a[m:])
	out := make([]int, 0, len(a))
	i, j := 0, 0
	for i < len(l) && j < len(r) {
		if l[i] <= r[j] {
			out = append(out, l[i])
			i++
		} else {
			out = append(out, r[j])
			j++
		}
	}
	out = append(out, l[i:]...)
	return append(out, r[j:]...)
}

// growDemo uses a deliberately fixed doubling rule, not Go append's growth policy.
func growDemo(n int) (int, []int) {
	a := []int{}
	copies := 0
	events := []int{}
	for i := 0; i < n; i++ {
		if len(a) == cap(a) {
			capacity := max(1, 2*cap(a))
			b := make([]int, len(a), capacity)
			copies += copy(b, a)
			a = b
			events = append(events, capacity)
		}
		a = append(a, i)
	}
	return copies, events
}

type intHeap []int

func (h intHeap) Len() int           { return len(h) }
func (h intHeap) Less(i, j int) bool { return h[i] < h[j] }
func (h intHeap) Swap(i, j int)      { h[i], h[j] = h[j], h[i] }
func (h *intHeap) Push(v any)        { *h = append(*h, v.(int)) }
func (h *intHeap) Pop() any          { a := *h; n := len(a); v := a[n-1]; *h = a[:n-1]; return v }

type entry struct {
	key   string
	value int
}
type lru struct {
	capacity int
	order    *list.List
	items    map[string]*list.Element
}

func newLRU(capacity int) *lru {
	if capacity < 0 {
		panic("negative capacity")
	}
	return &lru{capacity, list.New(), make(map[string]*list.Element)}
}
func (c *lru) get(k string) (int, bool) {
	e, ok := c.items[k]
	if !ok {
		return 0, false
	}
	c.order.MoveToFront(e)
	return e.Value.(entry).value, true
}
func (c *lru) put(k string, v int) {
	if c.capacity == 0 {
		return
	}
	if e := c.items[k]; e != nil {
		e.Value = entry{k, v}
		c.order.MoveToFront(e)
		return
	}
	c.items[k] = c.order.PushFront(entry{k, v})
	if c.order.Len() > c.capacity {
		e := c.order.Back()
		delete(c.items, e.Value.(entry).key)
		c.order.Remove(e)
	}
}
func (c *lru) keys() []string {
	out := []string{}
	for e := c.order.Front(); e != nil; e = e.Next() {
		out = append(out, e.Value.(entry).key)
	}
	return out
}

// This LFU reference simulator scans all entries at eviction: O(n), intentionally.
// It gives the policy a simple executable oracle, not an O(1) implementation.
type lfEntry struct{ value, freq, tick int }
type lfu struct {
	capacity, tick int
	items          map[string]lfEntry
}

func newLFU(n int) *lfu {
	if n < 0 {
		panic("negative capacity")
	}
	return &lfu{capacity: n, items: map[string]lfEntry{}}
}
func (c *lfu) get(k string) (int, bool) {
	v, ok := c.items[k]
	if !ok {
		return 0, false
	}
	c.tick++
	v.freq++
	v.tick = c.tick
	c.items[k] = v
	return v.value, true
}
func (c *lfu) put(k string, value int) {
	if c.capacity == 0 {
		return
	}
	if v, ok := c.items[k]; ok {
		c.tick++
		v.value = value
		v.freq++
		v.tick = c.tick
		c.items[k] = v
		return
	}
	if len(c.items) == c.capacity {
		victim := ""
		first := true
		var best lfEntry
		for k, v := range c.items {
			if first || v.freq < best.freq || (v.freq == best.freq && v.tick < best.tick) {
				victim, best, first = k, v, false
			}
		}
		delete(c.items, victim)
	}
	c.tick++
	c.items[k] = lfEntry{value, 1, c.tick}
}
func (c *lfu) keys() []string {
	keys := []string{}
	for k := range c.items {
		keys = append(keys, k)
	}
	slices.Sort(keys)
	return keys
}

type toyBloom uint8

func (b *toyBloom) add(x uint)       { *b |= 1 << (x % 8); *b |= 1 << ((3*x + 1) % 8) }
func (b toyBloom) maybe(x uint) bool { return b&(1<<(x%8)) != 0 && b&(1<<((3*x+1)%8)) != 0 }

type ringPoint struct {
	pos  int
	node string
}

func owner(r []ringPoint, key int) string {
	if len(r) == 0 {
		panic("empty ring")
	}
	i := sort.Search(len(r), func(i int) bool { return r[i].pos >= key })
	if i == len(r) {
		i = 0
	}
	return r[i].node
}

type record struct {
	key     string
	value   int
	deleted bool
}

// Newest layer first, already sorted within each layer; lookup is linear in this toy.
func lookup(layers [][]record, k string) (int, bool) {
	for _, layer := range layers {
		for _, r := range layer {
			if r.key == k {
				return r.value, !r.deleted
			}
		}
	}
	return 0, false
}

func run(w io.Writer) {
	copies, events := growDemo(8)
	fmt.Fprintf(w, "doubling: capacities=%v copied=%d appended=8\n", events, copies)
	l := list.New()
	l.PushBack("A")
	e := l.PushBack("B")
	l.PushBack("C")
	l.Remove(e)
	values := []any{}
	for e = l.Front(); e != nil; e = e.Next() {
		values = append(values, e.Value)
	}
	fmt.Fprintf(w, "list after removing known B=%v\n", values)
	stack := []int{1, 2, 3}
	top := stack[len(stack)-1]
	stack = stack[:len(stack)-1]
	fmt.Fprintf(w, "stack pop=%d remaining=%v\n", top, stack)
	queue := []int{1, 2, 3}
	head := 0
	first := queue[head]
	queue[head] = 0
	head++
	fmt.Fprintf(w, "queue pop=%d remaining=%v\n", first, queue[head:])
	buckets := make([][]int, 4)
	for _, x := range []int{1, 5, 9} {
		buckets[x%4] = append(buckets[x%4], x)
	}
	fmt.Fprintf(w, "toy hash bucket[1]=%v contains5=%t contains13=%t\n", buckets[1], slices.Contains(buckets[1], 5), slices.Contains(buckets[1], 13))
	h := &intHeap{4, 1, 3, 2}
	heap.Init(h)
	ordered := []int{}
	for h.Len() > 0 {
		ordered = append(ordered, heap.Pop(h).(int))
	}
	fmt.Fprintf(w, "heap pop=%v\n", ordered)
	fmt.Fprintf(w, "merge sort=%v\n", mergeSort([]int{4, 1, 3, 1, 2}))
	type person struct {
		name  string
		score int
	}
	ps := []person{{"A", 2}, {"B", 1}, {"C", 2}}
	slices.SortStableFunc(ps, func(a, b person) int { return cmp.Compare(a.score, b.score) })
	fmt.Fprintf(w, "stable sort=%v\n", ps)
	a := []int{1, 2, 2, 4}
	fmt.Fprintf(w, "lower_bound 2=%d 3=%d 5=%d\n", lowerBound(a, 2), lowerBound(a, 3), lowerBound(a, 5))
	x, y, ok := pairSum([]int{1, 2, 4, 7}, 9)
	fmt.Fprintf(w, "pair sum 9=%d+%d found=%t\n", x, y, ok)
	fmt.Fprintf(w, "min coins [1 3 4], amount=6: %d\n", minCoins([]int{1, 3, 4}, 6))
	fmt.Fprintf(w, "subsets [1 2]=%v\n", subsets([]int{1, 2}))
	fmt.Fprintf(w, "BFS distance=%v\n", bfs([][]int{{1, 2}, {3}, {3}, {}, {}}, 0))
	var b toyBloom
	b.add(1)
	fmt.Fprintf(w, "toy bloom: bits=%08b inserted1=%t absent9=%t absent2=%t\n", b, b.maybe(1), b.maybe(9), b.maybe(2))
	old := []ringPoint{{20, "A"}, {60, "B"}, {90, "C"}}
	added := []ringPoint{{20, "A"}, {40, "D"}, {60, "B"}, {90, "C"}}
	for _, key := range []int{10, 30, 70, 95} {
		fmt.Fprintf(w, "ring key=%d: %s -> %s\n", key, owner(old, key), owner(added, key))
	}
	lr, lf := newLRU(2), newLFU(2)
	for _, c := range []interface{ put(string, int) }{lr, lf} {
		c.put("A", 1)
		c.put("B", 2)
	}
	for range 3 {
		lr.get("A")
		lf.get("A")
	}
	lr.get("B")
	lf.get("B")
	lr.put("C", 3)
	lf.put("C", 3)
	fmt.Fprintf(w, "LRU newest-first=%v LFU sorted-keys=%v\n", lr.keys(), lf.keys())
	layers := [][]record{{{"A", 0, true}, {"B", 2, false}}, {{"A", 1, false}}}
	v, found := lookup(layers, "A")
	fmt.Fprintf(w, "LSM newest tombstone: A=%d found=%t\n", v, found)
}
func main() { run(os.Stdout) }