issue69507.go

     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  
     7  package main
     8  
     9  func main() {
    10  	err := run()
    11  	if err != nil {
    12  		panic(err)
    13  	}
    14  }
    15  
    16  func 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  
    85  func 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  
   100  type Seq[V any] func(yield func(V) bool)
   101  
   102  func 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  
   118  func findFirstMatch(order, sel string) byte {
   119  	for _, c := range order {
   120  		return byte(c)
   121  	}
   122  	return 0
   123  }
   124  
   125  func 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
View as plain text