성냥 게임
25477 단어 elmproblemsolvinginterview
규칙
이 게임의 규칙은 매우 간단하다. 게임이 시작될 때, 두 명의 유저 앞에 21개의 성냥을 놓는다.선수들은 번갈아 1개, 2개 또는 3개의 성냥방망이를 제거한다.어쩔 수 없이 마지막 성냥방망이를 든 선수가 졌다.
문제 단순화
이 게임을 하기에 가장 좋은 방법이 있습니까?이 문제를 해결하기 위해서 우리는 가능한 한 문제를 간소화하자. 성냥 한 개비만 남았다고 가정하면 이제 우리 차례다.우리는 그것을 받아들여야 하기 때문에 우리는 졌다.
하지만 성냥 2개가 있으면 1개를 가져갈 수 있고, 나머지 1개는 다른 유저에게 남겨둘 수 있다.성냥 세 개가 있으면 우리는 두 개비를 가져올 수 있고, 아직 한 개비가 남았다.성냥 4개가 있다면, 우리는 3개를 가져갈 수 있고, 다른 유저는 다시 마지막 1개를 가져갈 수밖에 없다.
모드
우리는 귀납 모델의 출현을 볼 수 있다. 성냥 하나만 있으면 우리는 진다.2, 3, 4가 있어서 우리가 이겼다.현재 5경기가 생겼는데, 우리는 다시 한 번 번거로움에 빠졌다. 우리가 무엇을 하든, 우리의 상대는 2경기, 3경기 또는 4경기를 남게 될 것이다. 우리는 이것이 그들이 이길 수 있다는 것을 이미 알고 있다.6경기, 7경기 또는 8경기에서 우리는 다시 승리할 위치에 있다.9시에 우리는 또 졌다. 이런 식으로 미루자.
우리는 이 모델을 간단한 대수로 바꿀 수 있다. 만약에 m×4+1개의 성냥봉이 있다면 그 중에서 m가 0에서 5 사이의 정수라면 현재 유저는 실패한 위치에 있다.따라서 게임의 목표는 상대방을 패배의 위치에 들어가게 하는 것이다. 거기서부터 그것은 일방통행으로 바뀌었다.우리는 경기를 시작하는 선수가 반드시 져야 한다는 것을 볼 수 있다.즉, 다른 유저가 틀리지 않으면!
코드에 주력하다
우리는
count
의 아래 값이 손실 금액을 나타낸다는 것을 안다.count = m × 4 + 1
m
은 0과 5 사이의 정수로 4
은 한 유저가 들 수 있는 성냥봉의 최대 수량보다 하나 더 많다.정수 나눗셈 m:
m = (count - 1) ÷ 4
정수 나눗셈의 나머지는:r = (count - 1) mod 4
만약 나머지가 0이라면, 우리는 실패한 위치에 있기 때문에, 우리는 성냥 한 개비만 가져올 수 있다. 마지막 한 개비, 게임이 끝나든지, 아니면 우리는 게임을 연장할 수 있고, 우리의 상대가 실수를 범하기를 바란다.다른 한편, 만약 나머지가 0이 아니라면 우리는 이길 수 있다.그렇다면 성냥 몇 개를 가져가야 합니까?좋아, 우리는 우리의 상대가 그들이 이 계산을 실행할 차례가 되었을 때 0의 나머지를 얻기를 바란다.따라서 우리가 해야 할 일은
r
에 대응하는 성냥봉의 수량을 없애는 것이다. 이것은 현재 성냥봉의 수량과 다음 실패 위치 사이의 차이이다.위조 코드에서 우리는 그것을
if r is 0 take 1 else take r
으로 묘사할 수 있다.단원 테스트
계산 결과가 정확한지 확인하기 위해 단원 테스트를 작성합니다.
test "matchsticksToTake gives correct values for 1 to 21" <|
\_ ->
let
expectedMatchsticksToTake =
[ ( 1, 1 ) -- lose
, ( 2, 1 ) -- win
, ( 3, 2 ) -- win
, ( 4, 3 ) -- win
, ( 5, 1 ) -- lose
, ( 6, 1 ) -- win
, ( 7, 2 ) -- win
, ( 8, 3 ) -- win
, ( 9, 1 ) -- lose
, ( 10, 1 ) -- win
, ( 11, 2 ) -- win
, ( 12, 3 ) -- win
, ( 13, 1 ) -- lose
, ( 14, 1 ) -- win
, ( 15, 2 ) -- win
, ( 16, 3 ) -- win
, ( 17, 1 ) -- lose
, ( 18, 1 ) -- win
, ( 19, 2 ) -- win
, ( 20, 3 ) -- win
, ( 21, 1 ) -- lose
]
matchsticks =
List.range 1 21
actualMatchsticksToTake =
List.map
(\count -> matchsticksToTake count)
matchsticks
in
Expect.equal
expectedMatchsticksToTake
actualMatchsticksToTake
matchsticksToTake
also returns the matchstick count to make testing a bit easier.
비즈니스 논리
우리는 이미 기본적인 논리를 해결했으니 실제적인 실현을 보여 주자.
matchsticksToTake : Int -> ( Int, Int )
matchsticksToTake count =
let
remainder =
remainderBy 4 (count - 1)
take =
if remainder == 0 then
1
else
remainder
in
( count, take )
그렇습니다!우리의 테스트가 통과되었고, 게임의 핵심 논리가 완성되었다!사용자 인터페이스 및 게임성
프로그래밍의 흥미로운 점은 업무 논리가 전체 코드 라이브러리에서 상대적으로 작은 일부분일 수 있다는 것이다.인터뷰를 진행할 때, 나는 내가 이 게임에 대해 간단한 명령행을 요구할 수 있을 것이라고 생각한다.설령 내가elm로 작성한 소량의 코드로 게임을 일하게 한다 하더라도 인터뷰 인코딩 세션에 있어서는 너무 많을 것이다.하지만 흥미가 있으시다면 계속해 주십시오. 저도 이 부분을 간략하게 요약하겠습니다.
우리는 가능한 한 가장 간단한 사용자 인터페이스를 사용하여 기능을 보여 주기를 바란다.물론, 우리는 성냥봉의 현재 수량을 표시해야 한다.우리는 누구의 차례인지 더 알아야 한다.나는 지난 라운드에서 성냥 몇 개를 가져갔는지 보여주기로 했다.마지막으로, 우리는 게이머들이 원하는 성냥방망이 수량을 선택할 수 있도록 단추가 필요하다.다음은 해당하는 elm 코드입니다.
view : Model -> Html Msg
view model =
div []
[ h1
[]
[ playerTurnLabel model ]
, h1 [] [ text (String.fromInt model.matchsticks) ]
, button [ onClick (Take 1), disabled (disable model) ]
[ text "take 1" ]
, button [ onClick (Take 2), disabled (disable model) ]
[ text "take 2" ]
, button [ onClick (Take 3), disabled (disable model) ]
[ text "take 3" ]
, p [] [ text <| lastMoveString model.lastSelection ]
]
우리는 이 사용자 인터페이스의 게임 상태를 추적하기 위해 매우 간단한 모형을 필요로 하는 것을 볼 수 있다.type alias Model =
{ currentPlayer : Player
, matchsticks : Int
, lastSelection : Selection
}
type Player
= ComputerPlayer
| HumanPlayer
type Selection
= Selected Player Int
| NoneSelected
우리는 현재 유저, 현재 성냥방망이 수량과 이전 유저의 선택을 추적하고 있습니다.게임의 매 라운드마다elm는 우리에게
update
회 메시지를 보냅니다.메시지는 현재 유저가 사용하고자 하는 성냥개비 수량을 포함합니다:type Msg
= ComputerTake Int
| Take Int
| DoNothing
컴퓨터(ComputerTake
)나 인간 유저(Take
)가 라운드를 원합니다.만약 메시지가 DoNothing
이라면, 이것은 우리가 현재 모델로 돌아가 아무런 변경도 하지 않는다는 것을 의미할 뿐이다.프로그램이 시작될 때,elm가 실행될 때
init
함수를 호출합니다.init : () -> ( Model, Cmd Msg )
init _ =
-- let the computer start the game
wrapNextMsgWithCmd
( Model ComputerPlayer 21 NoneSelected, computerTakesNextTurn 21 )
우리는 컴퓨터가 1라운드에서 인간 유저에게 승리할 기회가 있기를 희망하기 때문에, 우리는 currentPlayer
을 ComputerPlayer
으로 초기화할 것이다.우리는 21
개의 성냥봉을 설치했는데, lastSelection
은 NoneSelected
이다. 왜냐하면 이전에 모퉁이를 돌지 않았기 때문이다.computerTakesNextTurn 21
은 이 컴퓨터가 돌아왔다는 메시지를 업데이트에 보내기를 희망합니다.이 소식을 조금만 늦추면 모든 인간 유저가 차례가 된 후에 바로 화면을 업데이트하지 않을 수 있다는 것이 비결이다.이를 위해 우리는 Cmd
을 사용했다.일반적으로 명령은 http 요청을 보내는 등 부작용을 실행하는 데 사용됩니다.여기서 우리는 명령을 사용하여 컴퓨터의 운행을 지연시킨다.우리는 기본적으로 "이 명령을 내린 후에 다음 메시지를 update
으로 보내십시오."라고 말한다.테스트 목적으로
computerTakesNextTurn
을 간단한 Msg
으로 만드는 것이 더 쉬울 것 같습니다.wrapNextMsgWithCmd
의 목적은 이 메시지 포장에 필요한 명령을 둘러싼 것이다.wrapNextMsgWithCmd : ( Model, Msg ) -> ( Model, Cmd Msg )
wrapNextMsgWithCmd ( nextModel, nextMsg ) =
( nextModel, wrapWithCmd nextMsg )
wrapWithCmd : Msg -> Cmd Msg
wrapWithCmd nextMsg =
case nextMsg of
DoNothing ->
Cmd.none
Take _ ->
Cmd.none
ComputerTake _ ->
Cmd.batch
[ Task.perform
(\_ -> nextMsg)
(Process.sleep 3000)
]
여기에서 우리가 update
에 보내는 다음 메시지가 컴퓨터 라운드(ComputerTake
)라면 이 메시지를 포함하는 Cmd
을 생성합니다.Cmd
은 Process.sleep
작업을 3초 동안 실행하고 nextMsg
으로 업데이트를 호출합니다.updateWithoutCmd
기본 게임 처리:updateWithoutCmd : Msg -> Model -> ( Model, Msg )
updateWithoutCmd msg model =
case msg of
Take selectedMatchsticks ->
humanPlayerTakesTurn model selectedMatchsticks
ComputerTake selectedMatchsticks ->
computerPlayerTakesTurn model selectedMatchsticks
DoNothing ->
( model, DoNothing )
humanPlayerTakesTurn : Model -> Int -> ( Model, Msg )
humanPlayerTakesTurn model selectedMatchsticks =
case model.currentPlayer of
HumanPlayer ->
tryToPlayTurn
model
selectedMatchsticks
(computerPlaysNextOrEndOfGame
model.matchsticks
selectedMatchsticks
)
ComputerPlayer ->
rejectPlayerTurn model
computerPlayerTakesTurn : Model -> Int -> ( Model, Msg )
computerPlayerTakesTurn model selectedMatchsticks =
case model.currentPlayer of
ComputerPlayer ->
tryToPlayTurn model selectedMatchsticks DoNothing
HumanPlayer ->
rejectPlayerTurn model
이 코드는 만약 게이머들이 성냥봉을 가지려고 한다면 사실상 그들의 차례가 될 것이라고 보장한다.그것은 성냥봉의 수량이 효과가 있는지도 검사한다.rejectPlayerTurn
은 정말 필요하지 않을 수도 있습니다. 왜냐하면 우리는 입력 단추를 회색으로 했지만 대량의 서버 사이드 코드를 작성한 사람으로서 낡은 습관을 고치기 어렵습니다!우리는 한 인간 유저가 모퉁이를 돌자 컴퓨터 유저가 다음 게임
computerPlaysNextOrEndOfGame
을 할 수 있도록 메시지를 생성한 것을 볼 수 있다.computerPlaysNextOrEndOfGame : Int -> Int -> Msg
computerPlaysNextOrEndOfGame matchsticks selectedMatchsticks =
if gameOver (matchsticks - selectedMatchsticks) then
DoNothing
else
computerTakesNextTurn <|
takeMatchsticks matchsticks selectedMatchsticks
computerTakesNextTurn : Int -> Msg
computerTakesNextTurn matchsticks =
ComputerTake <| Tuple.second <| matchsticksToTake matchsticks
만약 인류 유저가 현재 라운드 후 게임이 아직 끝나지 않았다면 우리는 해당하는 ComputerTake
메시지를 생성할 수 있습니다.현재 유저가 선택한 후 남은 성냥방망이 수량에 따라 이 메시지는 컴퓨터 유저의 matchsticksToTake
을 포함합니다.Elm 건물
기본적인 elm architecture은 상당히 간단한 순환이다. 사용자가 UI와 상호작용할 때 이것은 적당한 메시지를
update
함수로 보내는 것을 촉발한다.update
은 받은 메시지에 따라 변경된 새 모델로 되돌아옵니다.elm가 실행될 때 이 새 모델을 사용하여 내부 상태를 업데이트하고 보기를 새로 고칩니다.update
은 Cmd
을 반환하여elm의 부작용을 문의하는 데 사용할 수 있습니다.elm는 순수한 언어이기 때문에elm에는 I/O를 직접 실행하는 함수가 없습니다. 명령이 있는 Cmd
개의 대상만 되돌려줍니다.elm
이 실행될 때 이 명령을 사용하여 실제 입력/출력을 실행하지만, 이것은 하나의 단독 절차로 완성된 것이다.명령 외에도elm는 subscriptions을 지원하여 정기 업데이트를 처리하는 데 사용할 수 있지만, 이 예에서는 구독을 사용하지 않습니다.
프레젠테이션
이 예제의 demo을 codepen에서 볼 수 있습니다.
소스 코드
github에서는 모든 소스 코드를 제공합니다.
Nested 소프트웨어 / 성냥개비 놀이
elm에서 이루어진 21개의 성냥방망이 게임
이 코드는 elm을 installed으로 요구합니다.
elm make src/Main.elm --output=Main.js
elm-test
을 실행하십시오.게임 규칙: 성냥 21개가 있습니다.두 명의 유저가 번갈아 매번 1, 2, 3개의 성냥방망이를 꺼낸다.마지막 성냥봉을 제거해야 했던 유저가 졌습니다.
View on GitHub
Reference
이 문제에 관하여(성냥 게임), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://dev.to/nestedsoftware/coding-interview-the-matchstick-game-43a8텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)