1 files changed, 227 insertions, 0 deletions
diff --git a/dependencies/pkg/mod/golang.org/x/exp@v0.0.0-20220613132600-b0d781184e0d/shootout/fannkuch-parallel.go b/dependencies/pkg/mod/golang.org/x/exp@v0.0.0-20220613132600-b0d781184e0d/shootout/fannkuch-parallel.go
new file mode 100644
index 0000000..a69b09c
--- /dev/null
+++ b/dependencies/pkg/mod/golang.org/x/exp@v0.0.0-20220613132600-b0d781184e0d/shootout/fannkuch-parallel.go
@@ -0,0 +1,227 @@
+//go:build ignore
+// +build ignore
+
+/*
+Redistribution and use in source and binary forms, with or without
+modification, are permitted provided that the following conditions are met:
+
+    * Redistributions of source code must retain the above copyright
+    notice, this list of conditions and the following disclaimer.
+
+    * Redistributions in binary form must reproduce the above copyright
+    notice, this list of conditions and the following disclaimer in the
+    documentation and/or other materials provided with the distribution.
+
+    * Neither the name of "The Computer Language Benchmarks Game" nor the
+    name of "The Computer Language Shootout Benchmarks" nor the names of
+    its contributors may be used to endorse or promote products derived
+    from this software without specific prior written permission.
+
+THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
+AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
+ARE DISCLAIMED.  IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE
+LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
+CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
+SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
+INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
+CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
+ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
+POSSIBILITY OF SUCH DAMAGE.
+*/
+
+/*
+ * The Computer Language Benchmarks Game
+ * http://shootout.alioth.debian.org/
+ *
+ * contributed by The Go Authors.
+ * Based on fannkuch.scala by Rex Kerr
+ */
+
+package main
+
+import (
+	"flag"
+	"fmt"
+	"runtime"
+)
+
+var n = flag.Int("n", 7, "count")
+var nCPU = flag.Int("ncpu", 4, "number of cpus")
+
+type Job struct {
+	start []int
+	n     int
+}
+
+type Found struct {
+	who *Kucher
+	k   int
+}
+
+type Kucher struct {
+	perm []int
+	temp []int
+	flip []int
+	in   chan Job
+}
+
+func NewKucher(length int) *Kucher {
+	return &Kucher{
+		perm: make([]int, length),
+		temp: make([]int, length),
+		flip: make([]int, length),
+		in:   make(chan Job),
+	}
+}
+
+func (k *Kucher) permute(n int) bool {
+	i := 0
+	for ; i < n-1 && k.flip[i] == 0; i++ {
+		t := k.perm[0]
+		j := 0
+		for ; j <= i; j++ {
+			k.perm[j] = k.perm[j+1]
+		}
+		k.perm[j] = t
+	}
+	k.flip[i]--
+	for i > 0 {
+		i--
+		k.flip[i] = i
+	}
+	return k.flip[n-1] >= 0
+}
+
+func (k *Kucher) count() int {
+	K := 0
+	copy(k.temp, k.perm)
+	for k.temp[0] != 0 {
+		m := k.temp[0]
+		for i := 0; i < m; i++ {
+			k.temp[i], k.temp[m] = k.temp[m], k.temp[i]
+			m--
+		}
+		K++
+	}
+	return K
+}
+
+func (k *Kucher) Run(foreman chan<- Found) {
+	for job := range k.in {
+		verbose := 30
+		copy(k.perm, job.start)
+		for i, v := range k.perm {
+			if v != i {
+				verbose = 0
+			}
+			k.flip[i] = i
+		}
+		K := 0
+		for {
+			if verbose > 0 {
+				for _, p := range k.perm {
+					fmt.Print(p + 1)
+				}
+				fmt.Println()
+				verbose--
+			}
+			count := k.count()
+			if count > K {
+				K = count
+			}
+			if !k.permute(job.n) {
+				break
+			}
+		}
+		foreman <- Found{k, K}
+	}
+}
+
+type Fanner struct {
+	jobind   int
+	jobsdone int
+	k        int
+	jobs     []Job
+	workers  []*Kucher
+	in       chan Found
+	result   chan int
+}
+
+func NewFanner(jobs []Job, workers []*Kucher) *Fanner {
+	return &Fanner{
+		jobs: jobs, workers: workers,
+		in:     make(chan Found),
+		result: make(chan int),
+	}
+}
+
+func (f *Fanner) Run(N int) {
+	for msg := range f.in {
+		if msg.k > f.k {
+			f.k = msg.k
+		}
+		if msg.k >= 0 {
+			f.jobsdone++
+		}
+		if f.jobind < len(f.jobs) {
+			msg.who.in <- f.jobs[f.jobind]
+			f.jobind++
+		} else if f.jobsdone == len(f.jobs) {
+			f.result <- f.k
+			return
+		}
+	}
+}
+
+func swapped(a []int, i, j int) []int {
+	b := make([]int, len(a))
+	copy(b, a)
+	b[i], b[j] = a[j], a[i]
+	return b
+}
+
+func main() {
+	flag.Parse()
+	runtime.GOMAXPROCS(*nCPU)
+	N := *n
+	base := make([]int, N)
+	for i := range base {
+		base[i] = i
+	}
+
+	njobs := 1
+	if N > 8 {
+		njobs += (N*(N-1))/2 - 28 // njobs = 1 + sum(8..N-1) = 1 + sum(1..N-1) - sum(1..7)
+	}
+	jobs := make([]Job, njobs)
+	jobsind := 0
+
+	firstN := N
+	if firstN > 8 {
+		firstN = 8
+	}
+	jobs[jobsind] = Job{base, firstN}
+	jobsind++
+	for i := N - 1; i >= 8; i-- {
+		for j := 0; j < i; j++ {
+			jobs[jobsind] = Job{swapped(base, i, j), i}
+			jobsind++
+		}
+	}
+
+	nworkers := *nCPU
+	if njobs < nworkers {
+		nworkers = njobs
+	}
+	workers := make([]*Kucher, nworkers)
+	foreman := NewFanner(jobs, workers)
+	go foreman.Run(N)
+	for i := range workers {
+		k := NewKucher(N)
+		workers[i] = k
+		go k.Run(foreman.in)
+		foreman.in <- Found{k, -1}
+	}
+	fmt.Printf("Pfannkuchen(%d) = %d\n", N, <-foreman.result)
+}