1// run
2
3// Copyright 2024 The Go Authors. All rights reserved.
4// Use of this source code is governed by a BSD-style
5// license that can be found in the LICENSE file.
6
7package main
8
9func main() {
10	err := run()
11	if err != nil {
12		panic(err)
13	}
14}
15
16func run() error {
17	methods := "AB"
18
19	type node struct {
20		tag     string
21		choices []string
22	}
23	all := []node{
24		{"000", permutations(methods)},
25	}
26
27	next := 1
28	for len(all) > 0 {
29		cur := all[0]
30		k := copy(all, all[1:])
31		all = all[:k]
32
33		if len(cur.choices) == 1 {
34			continue
35		}
36
37		var bestM map[byte][]string
38		bMax := len(cur.choices) + 1
39		bMin := -1
40		for sel := range selections(methods) {
41			m := make(map[byte][]string)
42			for _, order := range cur.choices {
43				x := findFirstMatch(order, sel)
44				m[x] = append(m[x], order)
45			}
46
47			min := len(cur.choices) + 1
48			max := -1
49			for _, v := range m {
50				if len(v) < min {
51					min = len(v)
52				}
53				if len(v) > max {
54					max = len(v)
55				}
56			}
57			if max < bMax || (max == bMax && min > bMin) {
58				bestM = m
59				bMin = min
60				bMax = max
61			}
62		}
63
64		if bMax == len(cur.choices) {
65			continue
66		}
67
68		cc := Keys(bestM)
69		for c := range cc {
70			choices := bestM[c]
71			next++
72
73			switch c {
74			case 'A':
75			case 'B':
76			default:
77				panic("unexpected selector type " + string(c))
78			}
79			all = append(all, node{"", choices})
80		}
81	}
82	return nil
83}
84
85func permutations(s string) []string {
86	if len(s) <= 1 {
87		return []string{s}
88	}
89
90	var result []string
91	for i, char := range s {
92		rest := s[:i] + s[i+1:]
93		for _, perm := range permutations(rest) {
94			result = append(result, string(char)+perm)
95		}
96	}
97	return result
98}
99
100type Seq[V any] func(yield func(V) bool)
101
102func selections(s string) Seq[string] {
103	return func(yield func(string) bool) {
104		for bits := 1; bits < 1<<len(s); bits++ {
105			var choice string
106			for j, char := range s {
107				if bits&(1<<j) != 0 {
108					choice += string(char)
109				}
110			}
111			if !yield(choice) {
112				break
113			}
114		}
115	}
116}
117
118func findFirstMatch(order, sel string) byte {
119	for _, c := range order {
120		return byte(c)
121	}
122	return 0
123}
124
125func Keys[Map ~map[K]V, K comparable, V any](m Map) Seq[K] {
126	return func(yield func(K) bool) {
127		for k := range m {
128			if !yield(k) {
129				return
130			}
131		}
132	}
133}
134