Михаил обнови решението на 22.01.2014 14:24 (преди над 4 години)
+package main
+
+import (
+ "fmt"
+ "runtime"
+ "sync/atomic"
+)
+
+// a lock with the ability to not block but to fail if it can't lock the lock immediately
+type nonblockingLock struct {
+ want chan interface{}
+ done chan interface{}
+}
+
+func newNonblockingLock() (u *nonblockingLock) {
+ u = new(nonblockingLock)
+ u.want = make(chan interface{}, 0)
+ u.done = make(chan interface{}, 1)
+
+ go func() {
+ for _ = range u.want { // so we can close it ... maybe
+ <-u.done
+ }
+ }()
+ return u
+}
+
+func (u *nonblockingLock) UnLock() {
+ u.done <- struct{}{}
+}
+
+// blocks until the lock is acquired
+func (u *nonblockingLock) BlockLock() {
+ u.want <- struct{}{}
+}
+
+// returns true if it gets the lock false otherwise. Doesn't block
+func (u *nonblockingLock) Lock() bool {
+ select {
+ case u.want <- struct{}{}:
+ return true
+ default:
+ return false
+ }
+}
+
+// locks all of the locks.
+// If a given lock can not be locked immediately all others are
+// being unlocked and then it blocks waiting for the lock it
+// couldn't lock. And it goes like that until all locks are acquired.
+type lockGroup struct {
+ locks map[*nonblockingLock]bool
+}
+
+func newLockGroup(locks []*nonblockingLock) *lockGroup {
+ l := new(lockGroup)
+ l.locks = make(map[*nonblockingLock]bool)
+ for _, lock := range locks {
+ l.locks[lock] = false
+ }
+
+ return l
+}
+
+func (l *lockGroup) unLockOthers(stay *nonblockingLock) {
+ for lock, locked := range l.locks {
+ if locked && lock != stay {
+ lock.UnLock()
+ l.locks[lock] = false
+ }
+ }
+}
+func (l *lockGroup) Lock() {
+start:
+ for lock, locked := range l.locks {
+ if locked == true {
+ continue
+ }
+
+ l.locks[lock] = true
+
+ if !lock.Lock() {
+ l.unLockOthers(lock)
+ lock.BlockLock()
+ goto start // cause gotos are cool
+ }
+ }
+}
+
+func (l *lockGroup) UnLock() {
+ for lock, _ := range l.locks {
+ lock.UnLock()
+ l.locks[lock] = false
+ }
+}
+
+type Mall struct {
+ m [4][4]rune
+ l [4][4]*nonblockingLock
+}
+
+func newMall(m *[4][4]rune) *Mall {
+ mall := new(Mall)
+
+ mall.m = *m
+
+ for i := 0; i < 4; i++ {
+ for j := 0; j < 4; j++ {
+ mall.l[i][j] = newNonblockingLock()
+ }
+ }
+
+ return mall
+}
+
+func (m *Mall) cellAt(row int, column int) cell {
+ return &(m.m[row][column])
+}
+
+func (m *Mall) String() string {
+ return fmt.Sprintf("[%q\n %q\n %q\n %q]\n", m.m[0], m.m[1], m.m[2], m.m[3])
+}
+
+const (
+ resSymb = 'X'
+ empty = '-'
+)
+
+type cell *rune
+
+func module(x, y int) int {
+ return (y + x) % y
+}
+
+type resident struct {
+ m *Mall
+ moves int
+ row int
+ column int
+}
+
+func (r *resident) move() [2][2]int {
+ r.moves--
+ if r.moves == 0 {
+ return [2][2]int{{r.row, r.column}, {-1, -1}}
+ }
+ turns := possibleTurns(r.row, r.column)
+ for _, cell := range turns {
+ //fmt.Printf(" trying [%d, %d]\n", cell[0], cell[1])
+
+ result := [2][2]int{{r.row, r.column}, {cell[0], cell[1]}}
+
+ if r.moveTo(cell[0], cell[1]) {
+ r.row = cell[0]
+ r.column = cell[1]
+ return result
+ }
+
+ }
+
+ r.moves = 0
+ return [2][2]int{{r.row, r.column}, {-2, -2}}
+}
+
+func (r *resident) Life(result chan<- [2][2]int) {
+ for {
+ lg := r.Lock()
+ move := r.move()
+ result <- move
+ lg.UnLock()
+ if move[1][0] < 0 {
+ return
+ }
+ }
+}
+
+func (r *resident) moveTo(row, column int) bool {
+ var (
+ current = r.m.cellAt(r.row, r.column)
+ target = r.m.cellAt(row, column)
+ )
+ if atomic.CompareAndSwapInt32(target, empty, resSymb) {
+ atomic.CompareAndSwapInt32(current, resSymb, empty)
+ r.row = row
+ r.column = column
+
+ return true
+ }
+
+ return false
+}
+
+func possibleTurns(row, column int) [4][2]int {
+ return [4][2]int{
+ {module(row-1, 4), module(column-1, 4)},
+ {module(row+1, 4), module(column+1, 4)},
+ {module(row+1, 4), module(column-1, 4)},
+ {module(row-1, 4), module(column+1, 4)},
+ }
+}
+
+// locks all the possible turns and the current space the resident resides on
+func (r *resident) Lock() *lockGroup {
+ locks := make([]*nonblockingLock, 5)
+ locks[0] = r.m.l[r.row][r.column]
+ for i, turn := range possibleTurns(r.row, r.column) {
+ locks[i+1] = r.m.l[turn[0]][turn[1]]
+ }
+ lg := newLockGroup(locks)
+ lg.Lock()
+ return lg
+}
+
+func newResident(mall *Mall, row, column int) (res *resident) {
+ res = new(resident)
+ res.m = mall
+ res.row = row
+ res.column = column
+ res.moves = 101
+
+ return res
+}
+
+func playMall(m [4][4]rune) (result [][2][2]int) {
+ runtime.GOMAXPROCS(4) // otherwise I get into infinitive lock, unlock cycle :)
+ mall := newMall(&m)
+ var ch = make(chan [2][2]int)
+ var residents []*resident
+ for r, row := range m {
+ for c, cell := range row {
+ if cell == resSymb {
+ res := newResident(mall, r, c)
+ residents = append(residents, res)
+ }
+ }
+ }
+
+ count := len(residents)
+ for _, resident := range residents {
+ go resident.Life(ch)
+ }
+
+ for move := range ch {
+ result = append(result, move)
+ if move[1][0] < 0 {
+ count--
+ }
+ if count == 0 {
+ break
+ }
+ }
+
+ return result
+}
runtime.GOMAXPROCS(4)
ми е нужно защото при 1 и 2 начина по който sheduler-а предава коя горутина води до постоянно локване и унлокване на части от мола и съответно AllStuck върви безкрайно - с 3 и повече минава като че ли без изобщо да се получава горния цикъл.
Аз иначе продължавам да го мисля как да стане по ... лесно