성냥 게임

본고에서 나는 면접식의 문제 해결과 인코딩 연습을 하고 싶다.실제로 나는 면접에서 이 문제를 만난 적이 없다. 나는 어렸을 때 낡은 컴퓨터에서 우연히 이 문제를 만난 적이 있다. 그러나 나는 이것이 정말 좋은 면접 후보라고 생각한다.복잡한 수학이나 알고리즘에 의존하지 않기 때문에 기본적인 문제 해결과 프로그래밍 기능을 평가하는 좋은 방법이다.실현은 elm에서 진행될 것이다. 이것은 순함수식 언어/전단 웹 프레임워크이다.내가elm를 사용하기로 결정한 것은 주로 내가 이전에 시도해 본 적이 없기 때문에 본고는 새로운 것을 배우는 좋은 핑계이다.

규칙


이 게임의 규칙은 매우 간단하다. 게임이 시작될 때, 두 명의 유저 앞에 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 + 1m은 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라운드에서 인간 유저에게 승리할 기회가 있기를 희망하기 때문에, 우리는 currentPlayerComputerPlayer으로 초기화할 것이다.우리는 21개의 성냥봉을 설치했는데, lastSelectionNoneSelected이다. 왜냐하면 이전에 모퉁이를 돌지 않았기 때문이다.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을 생성합니다.CmdProcess.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가 실행될 때 이 새 모델을 사용하여 내부 상태를 업데이트하고 보기를 새로 고칩니다.updateCmd을 반환하여elm의 부작용을 문의하는 데 사용할 수 있습니다.elm는 순수한 언어이기 때문에elm에는 I/O를 직접 실행하는 함수가 없습니다. 명령이 있는 Cmd개의 대상만 되돌려줍니다.elm이 실행될 때 이 명령을 사용하여 실제 입력/출력을 실행하지만, 이것은 하나의 단독 절차로 완성된 것이다.
명령 외에도elm는 subscriptions을 지원하여 정기 업데이트를 처리하는 데 사용할 수 있지만, 이 예에서는 구독을 사용하지 않습니다.

프레젠테이션


이 예제의 demo을 codepen에서 볼 수 있습니다.

소스 코드


github에서는 모든 소스 코드를 제공합니다.

Nested 소프트웨어 / 성냥개비 놀이


elm에서 이루어진 21개의 성냥방망이 게임


이 코드는 elminstalled으로 요구합니다.
  • 에서 코드를 컴파일하고 Main을 생성합니다.js, 운행 elm make src/Main.elm --output=Main.js
  • 단원 테스트를 실행하려면 elm-test을 실행하십시오.
  • Demo
  • 이 두 명령은 모두 프로젝트의 루트 디렉터리에서 실행할 수 있습니다.
    게임 규칙: 성냥 21개가 있습니다.두 명의 유저가 번갈아 매번 1, 2, 3개의 성냥방망이를 꺼낸다.마지막 성냥봉을 제거해야 했던 유저가 졌습니다.
    View on GitHub

    좋은 웹페이지 즐겨찾기