Duplicate argument

Програмиране с Go

Курс във Факултета по Математика и Информатика към СУ

Решение на Ескалатори в мола от Дойчин Атанасов

Обратно към всички решения

Към профила на Дойчин Атанасов

Резултати

  • 10 точки от тестове
  • 0 бонус точки
  • 10 точки общо
  • 10 успешни тест(а)
  • 0 неуспешни тест(а)

Код

package main
import "fmt"
import "sync"
var (
OCCUPIED = 'X'
EMPTY = '-'
)
var (
END_OF_TURNS = [2]int{-1, -1}
STUCK = [2]int{-2, -2}
)
func possibleMoves(position [2]int) [][2]int {
var out [][2]int
for _, diff := range [][2]int{{-1, -1}, {1, 1}, {1, -1}, {-1, 1}} {
x := (position[0] + diff[0]) % 4
y := (position[1] + diff[1]) % 4
if x < 0 {
x = 4 + x
}
if y < 0 {
y = 4 + y
}
out = append(out, [2]int{x, y})
}
return out
}
type Mall struct {
// The current state of the mall
world [4][4]rune
// Lock representing each shop
locks [4][4]sync.Mutex
// To make sure there is only one goroutine which is trying to lock something
// in the world.
gettinLocks sync.Mutex
}
/*
This Lock method locks sequentially. This makes it possible for one goroutine
to acquire lock A and start waiting for lock B while an other routine acquire B and
wait for A - deadlock. To fight this problem we have the gettingLocks lock which
makes sure only one of our goroutines is locking at the moment.
*/
func (mall *Mall) Lock(positions [][2]int) {
mall.gettinLocks.Lock()
for _, pos := range positions {
mall.locks[pos[0]][pos[1]].Lock()
}
mall.gettinLocks.Unlock()
}
func (mall *Mall) Unlock(positions [][2]int) {
for _, pos := range positions {
mall.locks[pos[0]][pos[1]].Unlock()
}
}
// To be only used with locked from and to
func (mall *Mall) Move(from [2]int, to [2]int) error {
if mall.Occupied(to) || !mall.Occupied(from) {
return fmt.Errorf("Invalid move from %#v to %#v", from, to)
}
mall.world[from[0]][from[1]] = EMPTY
mall.world[to[0]][to[1]] = OCCUPIED
return nil
}
// To be only used with locked pos
func (mall *Mall) Occupied(pos [2]int) bool {
return mall.world[pos[0]][pos[1]] == OCCUPIED
}
// Our main function
func playMall(mallStart [4][4]rune) [][2][2]int {
var allMoves [][2][2]int
wg := new(sync.WaitGroup)
movesChan := make(chan [2][2]int)
defer func() { close(movesChan) }()
mall := new(Mall)
mall.world = mallStart
maller := func(position [2]int) {
defer wg.Done()
myMoves := 0
for {
if myMoves >= 100 {
movesChan <- [2][2]int{position, END_OF_TURNS}
return
}
moved := false
allPossibleMoves := possibleMoves(position)
for _, nextPosition := range allPossibleMoves {
if moved {
break
}
locking := [][2]int{position, nextPosition}
mall.Lock(locking)
err := mall.Move(position, nextPosition)
if err == nil {
moved = true
movesChan <- [2][2]int{position, nextPosition}
myMoves += 1
position = nextPosition
}
mall.Unlock(locking)
}
if moved {
continue
}
wasStuck := false
locking := append(allPossibleMoves, position)
mall.Lock(locking)
allOccupied := true
for _, possibleMove := range allPossibleMoves {
if !mall.Occupied(possibleMove) {
allOccupied = false
break
}
}
if allOccupied {
movesChan <- [2][2]int{position, STUCK}
wasStuck = true
}
mall.Unlock(locking)
if wasStuck {
return
}
}
}
mallers := 0
for mallX, coll := range mall.world {
for mallY, cell := range coll {
if cell == EMPTY {
continue
}
wg.Add(1)
mallers += 1
go maller([2]int{mallX, mallY})
}
}
for {
if mallers == 0 {
break
}
move := <-movesChan
allMoves = append(allMoves, move)
if move[1] == STUCK || move[1] == END_OF_TURNS {
mallers -= 1
}
}
wg.Wait()
return allMoves
}

Лог от изпълнението

PASS
ok  	_/tmp/d20140123-11403-6rnzjb	0.012s
PASS
ok  	_/tmp/d20140123-11403-6rnzjb	0.017s
PASS
ok  	_/tmp/d20140123-11403-6rnzjb	0.014s
PASS
ok  	_/tmp/d20140123-11403-6rnzjb	0.012s
PASS
ok  	_/tmp/d20140123-11403-6rnzjb	0.012s
PASS
ok  	_/tmp/d20140123-11403-6rnzjb	0.013s
PASS
ok  	_/tmp/d20140123-11403-6rnzjb	0.013s
PASS
ok  	_/tmp/d20140123-11403-6rnzjb	0.016s
PASS
ok  	_/tmp/d20140123-11403-6rnzjb	0.012s
PASS
ok  	_/tmp/d20140123-11403-6rnzjb	0.011s

История (3 версии и 5 коментара)

Дойчин обнови решението на 21.01.2014 17:19 (преди над 4 години)

+package main
+
+import "sync"
+
+var END_OF_TURNS = [2]int{-1, -1}
+var STUCK = [2]int{-2, -2}
+
+func possibleMoves(position [2]int) [][2]int {
+ var out [][2]int
+
+ for _, diff := range [][2]int{{-1, -1}, {1, 1}, {-1, 1}, {1, -1}} {
+ x := (position[0] + diff[0]) % 4
+ y := (position[1] + diff[1]) % 4
+ if x < 0 {
+ x = 4 + x
+ }
+ if y < 0 {
+ y = 4 + y
+ }
+ out = append(out, [2]int{x, y})
+ }
+
+ return out
+}
+
+func playMall(mall [4][4]rune) [][2][2]int {
+ var allMoves [][2][2]int
+
+ wg := new(sync.WaitGroup)
+
+ freedomToMoveChan := make(chan int)
+ defer func() { close(freedomToMoveChan) }()
+ movesChan := make(chan [2][2]int)
+ defer func() { close(movesChan) }()
+
+ maller := func(position [2]int) {
+ defer wg.Done()
+ myMoves := 0
+
+ for {
+ _ = <-freedomToMoveChan
+ if myMoves >= 100 {
+ movesChan <- [2][2]int{position, END_OF_TURNS}
+ return
+ }
+ moved := false
+ for _, movePosition := range possibleMoves(position) {
+ if mall[movePosition[0]][movePosition[1]] == '-' {
+ mall[position[0]][position[1]] = '-'
+ mall[movePosition[0]][movePosition[1]] = 'X'
+ moved = true
+ movesChan <- [2][2]int{position, movePosition}
+ position = movePosition
+ myMoves += 1
+ break
+ }
+ }
+ if !moved {
+ movesChan <- [2][2]int{position, STUCK}
+ return
+ }
+ }
+ }
+
+ mallers := 0
+ for mallX, coll := range mall {
+ for mallY, cell := range coll {
+ if cell == '-' {
+ continue
+ }
+ wg.Add(1)
+ mallers += 1
+ go maller([2]int{mallX, mallY})
+ }
+ }
+
+ for {
+ if mallers == 0 {
+ break
+ }
+ freedomToMoveChan <- 42
+ move := <-movesChan
+ allMoves = append(allMoves, move)
+ if move[1] == STUCK || move[1] == END_OF_TURNS {
+ mallers -= 1
+ }
+ }
+
+ wg.Wait()
+
+ return allMoves
+}

На това му казвам последователно решение. Вие го наричайте "атомарно" ако искате. Вместо обикновен for имаме нещо много по - сложно, което е излишно. Само защото условието го изисква.

Обитателите се движат "паралелно" и "независимо" един от друг - в отделни рутини са и scheduler-a избира кой да се движи паралелно и независимо. Другите съвсем паралелно и независимо си го чакат.

Супер полезен пример за паралелизъм! Какво научихме? Това е глупост, която прави кода много по - сложен за същия краен резултат.

Дойчин обнови решението на 23.01.2014 01:41 (преди над 4 години)

package main
+import "fmt"
import "sync"
-var END_OF_TURNS = [2]int{-1, -1}
-var STUCK = [2]int{-2, -2}
+var (
+ OCCUPIED = 'X'
+ EMPTY = '-'
+)
+var (
+ END_OF_TURNS = [2]int{-1, -1}
+ STUCK = [2]int{-2, -2}
+)
+
func possibleMoves(position [2]int) [][2]int {
var out [][2]int
for _, diff := range [][2]int{{-1, -1}, {1, 1}, {-1, 1}, {1, -1}} {
x := (position[0] + diff[0]) % 4
y := (position[1] + diff[1]) % 4
if x < 0 {
x = 4 + x
}
if y < 0 {
y = 4 + y
}
out = append(out, [2]int{x, y})
}
return out
}
-func playMall(mall [4][4]rune) [][2][2]int {
+type Mall struct {
+ // The current state of the mall
+ world [4][4]rune
+
+ // Lock representing each shop
+ locks [4][4]sync.Mutex
+
+ // To make sure there is only one goroutine which is trying to lock something
+ // in the world.
+ gettinLocks sync.Mutex
+}
+
+/*
+This Lock method locks sequentially. This makes it possible for one goroutine
+to acquire lock A and start waiting for lock B while an other routine acquire B and
+wait for A - deadlock. To fight this problem we have the gettingLocks lock which
+makes sure only one of our goroutines is locking at given moment.
+*/
+func (mall *Mall) Lock(positions [][2]int) {
+ mall.gettinLocks.Lock()
+ for _, pos := range positions {
+ mall.locks[pos[0]][pos[1]].Lock()
+ }
+ mall.gettinLocks.Unlock()
+}
+
+func (mall *Mall) Unlock(positions [][2]int) {
+ for _, pos := range positions {
+ mall.locks[pos[0]][pos[1]].Unlock()
+ }
+}
+
+// To be only used with locked from and to
+func (mall *Mall) Move(from [2]int, to [2]int) error {
+ if mall.Occupied(to) || !mall.Occupied(from) {
+ return fmt.Errorf("Invalid move from %#v to %#v", from, to)
+ }
+ mall.world[from[0]][from[1]] = EMPTY
+ mall.world[to[0]][to[1]] = OCCUPIED
+ return nil
+}
+
+// To be only used with locked pos
+func (mall *Mall) Occupied(pos [2]int) bool {
+ return mall.world[pos[0]][pos[1]] == OCCUPIED
+}
+
+// Our main function
+func playMall(mallStart [4][4]rune) [][2][2]int {
var allMoves [][2][2]int
wg := new(sync.WaitGroup)
- freedomToMoveChan := make(chan int)
- defer func() { close(freedomToMoveChan) }()
movesChan := make(chan [2][2]int)
defer func() { close(movesChan) }()
+ mall := new(Mall)
+ mall.world = mallStart
+
maller := func(position [2]int) {
defer wg.Done()
myMoves := 0
for {
- _ = <-freedomToMoveChan
if myMoves >= 100 {
movesChan <- [2][2]int{position, END_OF_TURNS}
return
}
moved := false
- for _, movePosition := range possibleMoves(position) {
- if mall[movePosition[0]][movePosition[1]] == '-' {
- mall[position[0]][position[1]] = '-'
- mall[movePosition[0]][movePosition[1]] = 'X'
+ allPossibleMoves := possibleMoves(position)
+
+ for _, nextPosition := range allPossibleMoves {
+ if moved {
+ break
+ }
+ locking := [][2]int{position, nextPosition}
+ mall.Lock(locking)
+ err := mall.Move(position, nextPosition)
+ if err == nil {
moved = true
- movesChan <- [2][2]int{position, movePosition}
- position = movePosition
+ movesChan <- [2][2]int{position, nextPosition}
myMoves += 1
+ position = nextPosition
+ }
+ mall.Unlock(locking)
+ }
+
+ if moved {
+ continue
+ }
+
+ wasStuck := false
+ locking := append(allPossibleMoves, position)
+ mall.Lock(locking)
+
+ allOccupied := true
+ for _, possibleMove := range allPossibleMoves {
+ if !mall.Occupied(possibleMove) {
+ allOccupied = false
break
}
}
- if !moved {
+
+ if allOccupied {
movesChan <- [2][2]int{position, STUCK}
+ wasStuck = true
+ }
+
+ mall.Unlock(locking)
+
+ if wasStuck {
return
}
}
}
mallers := 0
- for mallX, coll := range mall {
+ for mallX, coll := range mall.world {
for mallY, cell := range coll {
- if cell == '-' {
+ if cell == EMPTY {
continue
}
wg.Add(1)
mallers += 1
go maller([2]int{mallX, mallY})
}
}
for {
if mallers == 0 {
break
}
- freedomToMoveChan <- 42
move := <-movesChan
allMoves = append(allMoves, move)
if move[1] == STUCK || move[1] == END_OF_TURNS {
mallers -= 1
}
}
wg.Wait()
return allMoves
}

Решение с мютекси. Тук вече наистина всички са паралелни. Но мютекса gettingLocks на типа Mall е тясна точка. Ако един обитател (Гертруда) чака да му отключат някой магазин, то всички несвързани няма да могат да си заключат нови магазини за проверка докато Гертруда не успее и не пусне gettingLocks.

Следователно ще мисля по - добро решение.

Дойчин обнови решението на 23.01.2014 11:30 (преди над 4 години)

package main
import "fmt"
import "sync"
var (
OCCUPIED = 'X'
EMPTY = '-'
)
var (
END_OF_TURNS = [2]int{-1, -1}
STUCK = [2]int{-2, -2}
)
func possibleMoves(position [2]int) [][2]int {
var out [][2]int
- for _, diff := range [][2]int{{-1, -1}, {1, 1}, {-1, 1}, {1, -1}} {
+ for _, diff := range [][2]int{{-1, -1}, {1, 1}, {1, -1}, {-1, 1}} {
x := (position[0] + diff[0]) % 4
y := (position[1] + diff[1]) % 4
if x < 0 {
x = 4 + x
}
if y < 0 {
y = 4 + y
}
out = append(out, [2]int{x, y})
}
return out
}
type Mall struct {
// The current state of the mall
world [4][4]rune
// Lock representing each shop
locks [4][4]sync.Mutex
// To make sure there is only one goroutine which is trying to lock something
// in the world.
gettinLocks sync.Mutex
}
/*
This Lock method locks sequentially. This makes it possible for one goroutine
to acquire lock A and start waiting for lock B while an other routine acquire B and
wait for A - deadlock. To fight this problem we have the gettingLocks lock which
-makes sure only one of our goroutines is locking at given moment.
+makes sure only one of our goroutines is locking at the moment.
*/
func (mall *Mall) Lock(positions [][2]int) {
mall.gettinLocks.Lock()
for _, pos := range positions {
mall.locks[pos[0]][pos[1]].Lock()
}
mall.gettinLocks.Unlock()
}
func (mall *Mall) Unlock(positions [][2]int) {
for _, pos := range positions {
mall.locks[pos[0]][pos[1]].Unlock()
}
}
// To be only used with locked from and to
func (mall *Mall) Move(from [2]int, to [2]int) error {
if mall.Occupied(to) || !mall.Occupied(from) {
return fmt.Errorf("Invalid move from %#v to %#v", from, to)
}
mall.world[from[0]][from[1]] = EMPTY
mall.world[to[0]][to[1]] = OCCUPIED
return nil
}
// To be only used with locked pos
func (mall *Mall) Occupied(pos [2]int) bool {
return mall.world[pos[0]][pos[1]] == OCCUPIED
}
// Our main function
func playMall(mallStart [4][4]rune) [][2][2]int {
var allMoves [][2][2]int
wg := new(sync.WaitGroup)
movesChan := make(chan [2][2]int)
defer func() { close(movesChan) }()
mall := new(Mall)
mall.world = mallStart
maller := func(position [2]int) {
defer wg.Done()
myMoves := 0
for {
if myMoves >= 100 {
movesChan <- [2][2]int{position, END_OF_TURNS}
return
}
moved := false
allPossibleMoves := possibleMoves(position)
for _, nextPosition := range allPossibleMoves {
if moved {
break
}
locking := [][2]int{position, nextPosition}
mall.Lock(locking)
err := mall.Move(position, nextPosition)
if err == nil {
moved = true
movesChan <- [2][2]int{position, nextPosition}
myMoves += 1
position = nextPosition
}
mall.Unlock(locking)
}
if moved {
continue
}
wasStuck := false
locking := append(allPossibleMoves, position)
mall.Lock(locking)
allOccupied := true
for _, possibleMove := range allPossibleMoves {
if !mall.Occupied(possibleMove) {
allOccupied = false
break
}
}
if allOccupied {
movesChan <- [2][2]int{position, STUCK}
wasStuck = true
}
mall.Unlock(locking)
if wasStuck {
return
}
}
}
mallers := 0
for mallX, coll := range mall.world {
for mallY, cell := range coll {
if cell == EMPTY {
continue
}
wg.Add(1)
mallers += 1
go maller([2]int{mallX, mallY})
}
}
for {
if mallers == 0 {
break
}
move := <-movesChan
allMoves = append(allMoves, move)
if move[1] == STUCK || move[1] == END_OF_TURNS {
mallers -= 1
}
}
wg.Wait()
return allMoves
}