Я пытаюсь придумать некоторые головоломки, посвященные многопоточности. Большинство проблем, которые я смог придумать, до сих пор были довольно специфичными для домена. Есть ли у кого-нибудь достойные программирующие головоломки для разработчиков, пытающихся изучить основные концепции многопоточных приложений?
Многопоточные головоломки
Ответ 1
В этой ссылке есть несколько тем.
Многопоточное программирование с помощью ThreadMentor: Учебное пособие
Edit:
Вот некоторые прямые ссылки на проблемы, перечисленные в этой ссылке, вместе с их начальными описаниями.
ThreadMentor: проблема столового философа
ThreadMentor: проблема столового философа: левая-правая версия
Проблема столовых философов изобретена Э. У. Дейкстре. Представьте себе, что пять философов, которые тратят свою жизнь, просто думают и на восток. В середине столовой находится круглый стол с пятью стульями. В таблице есть большая тарелка спагетти. Однако есть только пять палочек для еды, как показано на следующем рисунке. Каждый философ думает. Когда он проголодался, он садится и поднимает две палочки для еды, которые ближе всего к нему. Если философ может забрать обе палочки для еды, он ест какое-то время. После того, как философ закончит есть, он кладет палочки для еды и начинает думать.
ThreadMentor: проблема курения сигарет
Эта проблема связана с С. С. Патилом в 1971 году. Предположим, что для сигарет требуются три ингредиента: табак, бумага и спичка. Есть три курильщика цепи. У каждого из них есть только один ингредиент с бесконечным запасом. Существует агент, который имеет бесконечный запас всех трех ингредиентов. Чтобы сделать сигарету, курильщик имеет табак (например, бумагу и спичку), должен иметь две другие ингредиенты бумаги и спички (соответственно, табак и спичку, а также табак и бумагу). Агент и курильщики делят стол. Агент случайным образом генерирует два ингредиента и уведомляет курильщика, который нуждается в этих двух ингредиентах. Когда ингредиенты берутся из таблицы, агент поставляет еще два. С другой стороны, каждый курильщик ждет уведомления агента. Как только он будет уведомлен, курильщик подберет ингредиенты, запишет сигарету, курит какое-то время и возвращается к столу, ожидая его следующих ингредиентов.
ThreadMentor: проблема производителя/потребителя (или ограниченного буфера)
Предположим, что у нас есть круговой буфер с двумя указателями внутрь и снаружи, чтобы указать следующую доступную позицию для внесения данных и позицию, которая содержит следующие данные, которые должны быть получены. См. Диаграмму ниже. Есть две группы нитей, производителей и потребителей. Каждый производитель помещает элементы данных в позицию и продвигает указатель, и каждый потребитель извлекает элемент данных в положение и продвигает указатель.
ThreadMentor: проблема с роликовым конвейером
Предположим, что есть n пассажиров и один автомобиль американских горках. Пассажиры многократно ждут, чтобы поехать в машине, где могут находиться пассажиры максимум C, где C < п. Тем не менее, автомобиль может передвигаться по трассе только тогда, когда он заполнен. После завершения поездки каждый пассажир бродит вокруг парка развлечений, прежде чем вернуться на американские горки для еще одной поездки. Из-за соображений безопасности, автомобиль только ездит Т раз, а затем выстрелил.
У этого есть дополнительные ограничения:
- Автомобиль всегда ездит ровно с пассажирами C;
- Никакие пассажиры не спрыгнут с машины во время работы автомобиля;
- Никакие пассажиры не будут прыгать на автомобиле во время работы автомобиля;
- Никакие пассажиры не попросят проехать еще до того, как они смогут выйти из автомобиля.
ThreadMentor: проблема с мостом
Описание для этого зависит от изображений. Ниже приведена измененная цитата с удалением ссылок на изображения.
Рассмотрим узкий мост, который позволяет одновременно разрешать одновременное пересечение трех транспортных средств в одном направлении. Если на мосту есть три автомобиля, любой входящий автомобиль должен ждать, пока мост не станет чистым.
Когда транспортное средство выходит из моста, мы должны рассмотреть два случая. Случай 1, на мосту есть другие транспортные средства; и случай 2 - последний автомобиль на последнем мосту. В первом случае необходимо продолжить движение одного нового транспортного средства в том же направлении.
Случай 2 более сложный и имеет два подслучая. В этом случае выездное транспортное средство является последним транспортным средством на мосту. Если есть транспортные средства, ожидающие в противоположном направлении, один из них должен быть разрешен. Или, если нет транспортного средства, ожидающего в противоположном направлении, затем дайте ожидающему транспортному средству двигаться в том же направлении.
Ответ 2
"Обеденные проблемы философов" - это первый, о котором я думаю.
Ответ 3
У вас есть большая древовидная структура в памяти. Многие потоки должны искать структуру. Иногда поток должен вставлять или удалять что-то из структуры. Как вы контролируете доступ к структуре, чтобы программа работала корректно (ни один поток не будет топать друг на друга при изменении структуры) и эффективно (ни потоки не блокируются, когда они не должны быть)?
Ответ 4
проблема спящего парикмахера возникает, как и Проблема курения сигарет.
Ответ 5
Обеденные философы - это один из...
унисекс ванной - это еще один
Ответ 6
Возможно, вы можете использовать простую проблему тестирования и установки общего флага или доступа к некоторому ресурсу списка каким-то последовательным последовательным образом?
Ответ 7
Проблема Producer-Consumer.
Ответ 8
Здесь первая проблема Я когда-либо завершался многопоточным, еще во время моих студенческих исследований.
Ответ 9
В зависимости от того, что вы делаете при многопоточности, это имеет значение.
Вы находитесь в банке. Клиенты получают среднюю ставку 1 раз в 2 минуты. Каждый клиент обслуживается в среднем за 2 минуты.
Какое лучшее решение для обслуживания клиентов? Одна общая строка или одна строка для каждого счетчика?
Является ли ваш выбор достаточным, чтобы гарантировать определенную границу по длине линии?
Ответы: из-за марковского свойства прихода клиента и фактического времени обслуживания для каждого человека линия никогда не узнает об ограничении. Кроме того, это хорошая идея заставить их ждать в одной общей линии, хотя этого недостаточно для преодоления безграничной линии.
Ответ 10
Линейный симулятор довольно распространен.
Ответ 11
Здесь параллельный N-головоломка, реализованный в PARLANSE. Язык имеет синтаксис LISP, но по-настоящему ближе к C (скаляры, структуры, указатели, вызовы функций), но в отличие от C имеет локальные области. Секрет заключается в параллельном fork-зерновом операторе (||...), который выполняет все его операнды параллельно, а также способность PARLANSE использовать исключения для остановки родительских зерен.
Этот решатель обеспечивает линейные ускорения на всех 4-х и 8-позиционных машинах, на которых я его пробовал.
(define Version `N-puzzle Solver V1.1~l
Copyright (C) 1998-2009 Semantic Designs; All Rights Reserved~l')
(define SolveParticularPuzzle ~t)
(define ManhattanHeuristic ~t) ; Manhattan is really fast
(define PrintTrace ~f)
(include `parmodule.par')
(define ScrambleCount 10000)
(define PuzzleSize `Length of side of N-puzzle' +4) ; at least 3!
(define PuzzleSizeMinus1 +3)
(define PuzzleArea `Area of puzzle (= (-- N))' +16) ; (= (* PuzzleSize PuzzleSize))
(define PuzzleAreaMinus1 +15)
(define BlankTile `Code for a blank tile' 0)
(define puzzlepieceT `Codes for nonblank tiles'
(sort natural (range 1 PuzzleArea)))
(define BoardPositionT integer) ; normally positive, but sometime we reach off the edge
(define ConfigurationT (array puzzlepieceT 0 PuzzleAreaMinus1))
(define HardPuzzle1 `Solution found of length 29:
2 1 5 6 2 3 7 11 10 6 2 3 7 11 10 14 13 9 8
12 13 9 5 1 2 6 5 1 0'
(lambda (function ConfigurationT void)
(make ConfigurationT 01 11 02 00
04 06 09 05
13 12 07 03
08 14 10 15)
)lambda
)define
(define HardPuzzle2 `Solution found of length 31:
0 4 5 6 10 9 5 1 2 3 7 6 10 9 5 1
2 3 7 6 5 1 2 6 1 0 14 13 9 5 4 0'
(lambda (function ConfigurationT void)
(make ConfigurationT 13 00 02 09
04 05 06 01
08 07 03 11
12 14 10 15)
)lambda
)define
(define HardPuzzle3 `Solution found of length 56:
1 2 6 7 3 2 6 10 14 15 11 10 9 5
4 8 12 13 9 10 6 5 1 0 4 8 12 13
14 10 6 7 11 10 9 13 14 15 11 10
6 5 4 8 9 10 6 5 1 0 4 8 9 5 4 0
Total solution time in seconds: 18-24 (on 8 processor machine)'
(lambda (function ConfigurationT void)
(make ConfigurationT 00 09 10 08
15 12 03 02
01 11 13 14
06 04 07 05)
)lambda
)define
(define HardPuzzle4 `Solution found of length 50:
4 5 1 0 4 8 12 13 9 5 1 0 4 5 6
10 14 13 9 8 4 5 6 2 1 5 9 10 14
13 12 8 9 10 11 15 14 13 9 10 11
7 3 2 1 5 9 8 4 0
Total solution time in seconds: 125 (on 8 processor machine)'
(lambda (function ConfigurationT void)
(make ConfigurationT 00 15 06 07
12 03 08 11
04 13 02 05
01 14 09 10)
)lambda
)define
(define HardPuzzle5
`Solution found of length 68:
3 7 11 10 6 2 3 7 6 5 9 8 4 5 1 0 4 5 9 13 14 15 11
7 6 5 1 2 6 5 9 8 12 13 14 10 6 5 4 8 12 13 14 15 11
10 9 5 1 0 4 8 12 13 9 5 4 8 9 13 14 15 11 7 3 2 1 0
Total solution time in seconds: 2790 (on 8 processor machine)'
(lambda (function ConfigurationT void)
(make ConfigurationT 15 09 00 14
10 11 12 08
03 02 13 07
01 06 05 04)
)lambda
)define
(define ParticularPuzzleToSolve HardPuzzle5)
(define PrintConfiguration
(action (procedure [Puzzle (reference ConfigurationT)])
(do [position BoardPositionT] +0 PuzzleAreaMinus1 +1
(;; (ifthenelse (<= Puzzle:position 9)
(;; (PAR:PutConsoleCharacter "0")(PAR:PutConsoleNatural Puzzle:position) );;
(PAR:PutConsoleNatural Puzzle:position)
)ifthenelse
(PAR:PutConsoleSpace)
(ifthen (== (modulo (coerce natural position) (coerce natural PuzzleSize))
(coerce natural PuzzleSizeMinus1)coerce )==
(PAR:PutConsoleNewline)
)ifthen
);;
)do
)action
)define
(define Solved? `Determines if puzzle is solved.'
(lambda (function boolean
[board (reference ConfigurationT)]
)function
(value (;; `Fast check for completed':
(ifthen (~= board:0 BlankTile)
(return ~f)
)ifthen
(do [position BoardPositionT] PuzzleAreaMinus1 +1 -1
(ifthen (~= board:position (coerce natural position))
(return ~f)
)ifthen
)do
);;
~t ; all pieces are in proper places
)value
)lambda
)define
(define ScoreT `Estimate of configuration distance from solution.
Zero means configuration is a solution.'
(sort natural (range 0 1000))) ; s/b (range 0 (* PuzzleArea PuzzleArea))
(define SolvedScore `The score of a goal position.' 0)
(define UnsolvableScore `An impossibly big score.' 12345678)
(define LowerBoundOnScore
(lambda (function ScoreT [Puzzle (reference ConfigurationT)])
(let (= [OutOfPlaceTiles ScoreT] 0)
(value
(compileifthenelse ManhattanHeuristic ; ~t for Out-of-place, ~f for Manhattan
(do [Row BoardPositionT] PuzzleSizeMinus1 +0 -1
(do [Column BoardPositionT] PuzzleSizeMinus1 +0 -1
(local (;; (= [position integer] (+ (* Row PuzzleSize)
Column))=
(= [tile puzzlepieceT] Puzzle:position)
);;
(ifthen (~= tile BlankTile) ; ignore BlankTile
(+= OutOfPlaceTiles
(+ (magnitude (- Row (coerce integer (// tile (coerce natural PuzzleSize)))))
(magnitude (- Column (coerce integer (modulo tile (coerce natural PuzzleSize)))))
)+ ; add Manhattan distance of tile from tile goal
)+=
)ifthen
)local
)do ; Column
)do ; Row
(do [position BoardPositionT] PuzzleAreaMinus1
+1 ; skipping zero effectively ignores BlankTile
+1
(ifthen (~= Puzzle:position (coerce natural position))
(+= OutOfPlaceTiles)
)ifthen
)do
)compileifthenelse
OutOfPlaceTiles ; the answer
)value
)let
)lambda
)define
(recursive PathElementT
(define PathElementT `A series of moves of the blank tile.'
(structure [Move BoardPositionT]
[Next (reference PathElementT)]
)structure
)define
)recursive
(define EmptyPath (void (reference PathElementT))void )define
(define ValuedPathT `A path and the score it acheives.'
(structure [Solved boolean]
[Score ScoreT]
[Path (reference PathElementT)])
)define
(define MakeMove `Applies a move to a configuration'
(lambda (function ConfigurationT
(structure [BlankTilePosition BoardPositionT]
[NewBlankPosition BoardPositionT]
[ConfigurationBeforeMove
(reference ConfigurationT)]
)structure )function
(let (= [ResultConfiguration ConfigurationT]
(@ ConfigurationBeforeMove) )=
(value
(;;
(compileifthen PrintTrace
(;; (PAR:PutConsoleNatural BlankTilePosition)
(PAR:PutConsoleNatural NewBlankPosition)
);;
)compileifthen
(trust (== ConfigurationBeforeMove:BlankTilePosition
BlankTile))
(= ResultConfiguration:BlankTilePosition
ConfigurationBeforeMove:NewBlankPosition)
(= ResultConfiguration:NewBlankPosition BlankTile)
);;
ResultConfiguration
)value
)let
)lambda
)define
(define TopEdge? `Determines if a position is along top edge of puzzle.'
(lambda (function boolean BoardPositionT)
(< ? PuzzleSize)
)lambda
)define
(define BottomEdge? `Determines if a position is along bottom edge of puzzle.'
(lambda (function boolean BoardPositionT)
(>= ? (- PuzzleArea PuzzleSize))
)lambda
)define
(define LeftEdge? `Determines if a position is along left edge of puzzle.'
(lambda (function boolean BoardPositionT)
(== (modulo (coerce natural ?) (coerce natural PuzzleSize)) 0)==
)lambda
)define
(define RightEdge? `Determines if a position is along right edge of puzzle.'
(lambda (function boolean BoardPositionT)
(== (modulo (coerce natural ?) (coerce natural PuzzleSize))modulo
(coerce natural PuzzleSizeMinus1)coerce )==
)lambda
)define
(define Solved! (exception (lambda (function string (reference ValuedPathT))
`N-puzzle solution is:~l'
)lambda
)exception
)define
[SerialPrint semaphore]
[MaxMoves natural]
(define Npuzzle
(lambda (function ValuedPathT
[BlankTilePosition BoardPositionT]
[PreviousBlankTilePosition BoardPositionT]
[Puzzle ConfigurationT]
[MovesToHere natural]
)function
)lambda
)define
(define Npuzzle `Solves a puzzle and generates a sequence which is a solution.'
(lambda (function ValuedPathT
[BlankTilePosition BoardPositionT]
[PreviousBlankTilePosition BoardPositionT]
[Puzzle ConfigurationT]
[MovesToHere natural]
)function
(ifthenelse (value (compileifthen PrintTrace
(;; (PAR:PutConsole (. `In Npuzzle at depth '))
(PAR:PutConsoleNatural MovesToHere) (PAR:PutConsoleNewline)
(PrintConfiguration (. Puzzle))
);;
)compileifthen
(Solved? (. Puzzle)))
(make ValuedPathT ~t 0 EmptyPath)make ; the answer
(let (|| [valuedpath1 ValuedPathT]
[valuedpath2 ValuedPathT]
[valuedpath3 ValuedPathT]
[valuedpath4 ValuedPathT]
[Best ValuedPathT]
(= [EstimatedDistance natural]
(+ MovesToHere (LowerBoundOnScore (. Puzzle)))+ )=
)||
(ifthenelse (value (compileifthen PrintTrace
(;; (PAR:PutConsole (. `Inside LET EstimatedDistance= '))
(PAR:PutConsoleNatural EstimatedDistance) (PAR:PutConsoleNewline)
);;
)compileifthen
(> EstimatedDistance MaxMoves) )
(make ValuedPathT ~f EstimatedDistance EmptyPath) ; don't explore any further
(value
(;; (assert (& (<= +0 BlankTilePosition)
(< BlankTilePosition PuzzleArea) )& )assert
; (PAR:PutConsole (. `Solve subpuzzles: blank @ '))(PAR:PutConsoleNatural BlankTilePosition)(PAR:PutConsoleNewline)
(try `Solve subpuzzles':
(|| ; replace this by (;; to see pure serial execution times
`Fork Right':
(local (|| (= [NewBlankTilePosition BoardPositionT]
(++ BlankTilePosition) )=
[ExtendedPath (reference PathElementT)]
)||
(ifthenelse (value (;; ; (PAR:PutConsole (. `Fork Right~l'))
);;
(&& (~= NewBlankTilePosition
PreviousBlankTilePosition )~=
(~ (RightEdge? BlankTilePosition))~
)&& )value
(;; (= valuedpath1
(Npuzzle NewBlankTilePosition
BlankTilePosition
(MakeMove BlankTilePosition
NewBlankTilePosition
(. Puzzle) )MakeMove
(++ MovesToHere)
)Npuzzle )=
(ifthen valuedpath1:Solved
(;; (+= valuedpath1:Score) ; since we added a move
(= ExtendedPath (new PathElementT))
(= (@ ExtendedPath) (make PathElementT NewBlankTilePosition valuedpath1:Path) )=
(= valuedpath1:Path ExtendedPath)
(raise Solved! (. valuedpath1))
);;
)ifthen
);;
(= valuedpath1 (make ValuedPathT ~f UnsolvableScore EmptyPath))=
)ifthenelse
)local
`Fork Left':
(local (|| (= [NewBlankTilePosition BoardPositionT]
(-- BlankTilePosition) )=
[ExtendedPath (reference PathElementT)]
)||
(ifthenelse (value (;; ; (PAR:PutConsole (. `Fork Left~l'))
);;
(&& (~= NewBlankTilePosition
PreviousBlankTilePosition )~=
(~ (LeftEdge? BlankTilePosition))~
)&& )value
(;; (= valuedpath2
(Npuzzle NewBlankTilePosition
BlankTilePosition
(MakeMove BlankTilePosition
NewBlankTilePosition
(. Puzzle) )MakeMove
(++ MovesToHere)
)Npuzzle )=
(ifthen valuedpath2:Solved
(;; (+= valuedpath2:Score) ; since we added a move
(= ExtendedPath (new PathElementT))
(= (@ ExtendedPath) (make PathElementT NewBlankTilePosition valuedpath2:Path) )=
(= valuedpath2:Path ExtendedPath)
(raise Solved! (. valuedpath2))
);;
)ifthen
);;
(= valuedpath2 (make ValuedPathT ~f UnsolvableScore EmptyPath))=
)ifthenelse
)local
`Fork Down':
(local (|| (= [NewBlankTilePosition BoardPositionT]
(- BlankTilePosition PuzzleSize) )=
[ExtendedPath (reference PathElementT)]
)||
(ifthenelse (value (;; ; (PAR:PutConsole (. `Fork Down~l'))
);;
(&& (~= NewBlankTilePosition
PreviousBlankTilePosition )~=
(~ (TopEdge? BlankTilePosition))~
)&& )value
(;; (= valuedpath3
(Npuzzle NewBlankTilePosition
BlankTilePosition
(MakeMove BlankTilePosition
NewBlankTilePosition
(. Puzzle) )MakeMove
(++ MovesToHere)
)Npuzzle )=
(ifthen valuedpath3:Solved
(;; (+= valuedpath3:Score) ; since we added a move
(= ExtendedPath (new PathElementT))
(= (@ ExtendedPath) (make PathElementT NewBlankTilePosition valuedpath3:Path) )=
(= valuedpath3:Path ExtendedPath)
(raise Solved! (. valuedpath3))
);;
)ifthen
);;
(= valuedpath3 (make ValuedPathT ~f UnsolvableScore EmptyPath))=
)ifthenelse
)local
`Fork Up':
(local (|| (= [NewBlankTilePosition BoardPositionT]
(+ BlankTilePosition PuzzleSize) )=
[ExtendedPath (reference PathElementT)]
)||
(ifthenelse (value (;; ; (PAR:PutConsole (. `Fork Up~l'))
);;
(&& (~= NewBlankTilePosition
PreviousBlankTilePosition )~=
(~ (BottomEdge? BlankTilePosition))~
)&& )value
(;; (= valuedpath4
(Npuzzle NewBlankTilePosition
BlankTilePosition
(MakeMove BlankTilePosition
NewBlankTilePosition
(. Puzzle) )MakeMove
(++ MovesToHere)
)Npuzzle )=
(ifthen valuedpath4:Solved
(;; (+= valuedpath4:Score) ; since we added a move
(= ExtendedPath (new PathElementT))
(= (@ ExtendedPath) (make PathElementT NewBlankTilePosition valuedpath4:Path) )=
(= valuedpath4:Path ExtendedPath)
(raise Solved! (. valuedpath4))
);;
)ifthen
);;
(= valuedpath4 (make ValuedPathT ~f UnsolvableScore EmptyPath))=
)ifthenelse
)local
) ; || or ;;
`Exception handler':
(;; ; (PAR:PutConsole (. `Exception handler~l'))
(ifthenelse (== (exception) Solved!)==
(;; (= Best (@ (exceptionargument (reference ValuedPathT))))=
(acknowledge (;; );; )acknowledge
);;
(propagate) ; oops, something unexpected!
)ifthenelse
);;
`Success handler':
(;; ; (PAR:PutConsole (. `Success (no exception raised)!~l'))
`If we get here, no result is a solution,
and all results have leaf-estimated scores.'
(ifthenelse (< valuedpath1:Score valuedpath2:Score)
(= Best valuedpath1)
(= Best valuedpath2)
)ifthenelse
(ifthen (< valuedpath3:Score Best:Score)
(= Best valuedpath3) )ifthen
(ifthen (< valuedpath4:Score Best:Score)
(= Best valuedpath4) )ifthen
);;
)try
);;
Best ; the answer to return
)value
)ifthenelse
)let
)ifthenelse
)lambda
)define
[StartTimeMicroseconds natural]
(define ElapsedTimeSeconds
`Returns time in seconds rounded to nearest integer'
(lambda (function natural void)
(/ (- (+ (MicrosecondClock) 500000) StartTimeMicroseconds) 1000000)
)lambda
)define
(define main
(action (procedure void)
(local (|| [PuzzleToSolve ConfigurationT]
[BlankTilePosition BoardPositionT]
[Solution ValuedPathT]
[BlankLocation BoardPositionT]
[Neighbor BoardPositionT]
[PathScanP (reference PathElementT)]
[ElapsedTime natural]
)||
(;; (PAR:PutConsoleString Version)
(consume (addresource SerialPrint 1))
`Set PuzzleToSolve to Solved position':
(do [position BoardPositionT] +0 PuzzleAreaMinus1 +1
(= PuzzleToSolve:position (coerce puzzlepieceT position) )=
)do
(ifthenelse SolveParticularPuzzle
(;; (PAR:PutConsole (. `Hard puzzle...~l'))
(= PuzzleToSolve (ParticularPuzzleToSolve) )= );;
(;; `Scramble puzzle position'
(PAR:PutConsole (. `Random puzzle...~l'))
(= BlankLocation +0)
(do [i natural] 1 (modulo (MicrosecondClock)
ScrambleCount)modulo 1
(;; (= Neighbor BlankLocation)
(ifthenelse (== (PAR:GetRandomNat 2) 0)
(;; `Move Blank up or down'
(ifthenelse (== (PAR:GetRandomNat 2) 0)
(ifthen (~ (TopEdge? BlankLocation)) (-= Neighbor PuzzleSize))
(ifthen (~ (BottomEdge? BlankLocation)) (+= Neighbor PuzzleSize))
)ifthenelse
);;
(;; `Move Blank left or right'
(ifthenelse (== (PAR:GetRandomNat 2) 0)
(ifthen (~ (LeftEdge? BlankLocation)) (-= Neighbor))
(ifthen (~ (RightEdge? BlankLocation)) (+= Neighbor))
)ifthenelse
);;
)ifthenelse
; (PAR:PutConsoleNatural BlankLocation)(PAR:PutConsoleNatural Neighbor)(PAR:PutConsoleSpace)
(ifthen (~= BlankLocation Neighbor)
(= PuzzleToSolve
(MakeMove BlankLocation Neighbor (. PuzzleToSolve). )MakeMove )=
)ifthen
(= BlankLocation Neighbor)=
);;
)do
);;
)ifthenelse
(;; `Initialize solver'
(= Solution:Solved ~f)
(= Solution:Score 0)
(do FindBlankTile
[position BoardPositionT] +0 PuzzleAreaMinus1 +1
(ifthen (== PuzzleToSolve:position BlankTile)
(;; (= BlankTilePosition position)
(exitblock FindBlankTile)
);; )ifthen )do
);;
(PAR:PutConsole (. `~lInitial Configuration:~l'))
(PrintConfiguration (. PuzzleToSolve))
(PAR:PutConsole (. `Estimate of solution length: '))
(PAR:PutConsoleNatural (LowerBoundOnScore (. PuzzleToSolve)))
(PAR:PutConsoleNewline)
(= StartTimeMicroseconds (MicrosecondClock))
(while (~ Solution:Solved)
(;; (critical SerialPrint 1
(;; (PAR:PutConsole (. `*** Iteration to depth '))
(PAR:PutConsoleNatural Solution:Score)
(PAR:PutConsole (. ` ')) (PAR:PutConsoleNatural (ElapsedTimeSeconds)) (PAR:PutConsole (. ` Seconds'))
(PAR:PutConsoleNewline)
);;
)critical
(= MaxMoves Solution:Score)
(= Solution (Npuzzle BlankTilePosition BlankTilePosition PuzzleToSolve 0) )=
);;
)while
(= ElapsedTime (ElapsedTimeSeconds))
(critical SerialPrint 1
(;; (PAR:PutConsole (. `Solution found of length '))
(PAR:PutConsoleNatural Solution:Score) (PAR:PutConsole (. `: '))
(iterate (= PathScanP Solution:Path)
(~= PathScanP EmptyPath)
(= PathScanP PathScanP:Next)
(;; (PAR:PutConsoleNatural (coerce natural PathScanP:Move)) (PAR:PutConsoleSpace)
);;
)iterate
(PAR:PutConsoleNewline)
(PAR:PutConsole (. `Total solution time in seconds: ')) (PAR:PutConsoleNatural ElapsedTime) (PAR:PutConsoleNewline)
);;
)critical
);;
)local
)action
)define
Ответ 12
Маленькая книга семафоров, в которой свободно доступна книга, содержит множество головоломок синхронизации. Он включает в себя почти все головоломки, приведенные в других ответах. Решения предоставляются для всех головоломок.