1/*
2Redistribution and use in source and binary forms, with or without
3modification, are permitted provided that the following conditions are met:
4
5    * Redistributions of source code must retain the above copyright
6    notice, this list of conditions and the following disclaimer.
7
8    * Redistributions in binary form must reproduce the above copyright
9    notice, this list of conditions and the following disclaimer in the
10    documentation and/or other materials provided with the distribution.
11
12    * Neither the name of "The Computer Language Benchmarks Game" nor the
13    name of "The Computer Language Shootout Benchmarks" nor the names of
14    its contributors may be used to endorse or promote products derived
15    from this software without specific prior written permission.
16
17THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
18AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
19IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
20ARE DISCLAIMED.  IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE
21LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
22CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
23SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
24INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
25CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
26ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
27POSSIBILITY OF SUCH DAMAGE.
28*/
29
30/* The Computer Language Benchmarks Game
31 * http://shootout.alioth.debian.org/
32 *
33 * contributed by The Go Authors.
34 */
35
36package main
37
38import (
39	"flag"
40	"fmt"
41	"strconv"
42)
43
44const (
45	blue = iota
46	red
47	yellow
48	ncol
49)
50
51var complement = [...]int{
52	red | red<<2:       red,
53	red | yellow<<2:    blue,
54	red | blue<<2:      yellow,
55	yellow | red<<2:    blue,
56	yellow | yellow<<2: yellow,
57	yellow | blue<<2:   red,
58	blue | red<<2:      yellow,
59	blue | yellow<<2:   red,
60	blue | blue<<2:     blue,
61}
62
63var colname = [...]string{
64	blue:   "blue",
65	red:    "red",
66	yellow: "yellow",
67}
68
69// information about the current state of a creature.
70type info struct {
71	colour int // creature's current colour.
72	name   int // creature's name.
73}
74
75// exclusive access data-structure kept inside meetingplace.
76// if mate is nil, it indicates there's no creature currently waiting;
77// otherwise the creature's info is stored in info, and
78// it is waiting to receive its mate's information on the mate channel.
79type rendez struct {
80	n    int         // current number of encounters.
81	mate chan<- info // creature waiting when non-nil.
82	info info        // info about creature waiting.
83}
84
85// result sent by each creature at the end of processing.
86type result struct {
87	met  int
88	same int
89}
90
91var n = 600
92
93func main() {
94	flag.Parse()
95	if flag.NArg() > 0 {
96		n, _ = strconv.Atoi(flag.Arg(0))
97	}
98
99	for c0 := 0; c0 < ncol; c0++ {
100		for c1 := 0; c1 < ncol; c1++ {
101			fmt.Printf("%s + %s -> %s\n", colname[c0], colname[c1], colname[complement[c0|c1<<2]])
102		}
103	}
104	fmt.Print("\n")
105
106	pallmall([]int{blue, red, yellow})
107	pallmall([]int{blue, red, yellow, red, yellow, blue, red, yellow, red, blue})
108}
109
110func pallmall(cols []int) {
111
112	// invariant: meetingplace always contains a value unless a creature
113	// is currently dealing with it (whereupon it must put it back).
114	meetingplace := make(chan rendez, 1)
115	meetingplace <- rendez{n: 0}
116
117	ended := make(chan result)
118	msg := ""
119	for i, col := range cols {
120		go creature(info{col, i}, meetingplace, ended)
121		msg += " " + colname[col]
122	}
123	fmt.Println(msg)
124	tot := 0
125	// wait for all results
126	for _ = range cols {
127		result := <-ended
128		tot += result.met
129		fmt.Printf("%v%v\n", result.met, spell(result.same, true))
130	}
131	fmt.Printf("%v\n\n", spell(tot, true))
132}
133
134// in this function, variables ending in 0 refer to the local creature,
135// variables ending in 1 to the creature we've met.
136func creature(info0 info, meetingplace chan rendez, ended chan result) {
137	c0 := make(chan info)
138	met := 0
139	same := 0
140	for {
141		var othername int
142		// get access to rendez data and decide what to do.
143		switch r := <-meetingplace; {
144		case r.n >= n:
145			// if no more meetings left, then send our result data and exit.
146			meetingplace <- rendez{n: r.n}
147			ended <- result{met, same}
148			return
149		case r.mate == nil:
150			// no creature waiting; wait for someone to meet us,
151			// get their info and send our info in reply.
152			meetingplace <- rendez{n: r.n, info: info0, mate: c0}
153			info1 := <-c0
154			othername = info1.name
155			info0.colour = complement[info0.colour|info1.colour<<2]
156		default:
157			// another creature is waiting for us with its info;
158			// increment meeting count,
159			// send them our info in reply.
160			r.n++
161			meetingplace <- rendez{n: r.n, mate: nil}
162			r.mate <- info0
163			othername = r.info.name
164			info0.colour = complement[info0.colour|r.info.colour<<2]
165		}
166		if othername == info0.name {
167			same++
168		}
169		met++
170	}
171}
172
173var digits = [...]string{"zero", "one", "two", "three", "four", "five", "six", "seven", "eight", "nine"}
174
175func spell(n int, required bool) string {
176	if n == 0 && !required {
177		return ""
178	}
179	return spell(n/10, false) + " " + digits[n%10]
180}
181