Knight's tour: Difference between revisions

Content added Content deleted
(→‎{{header|Elm}}: Updated to Elm 0.19.1)
(→‎{{header|Elm}}: More archetypal Elm)
Line 2,525: Line 2,525:


import Browser exposing (element)
import Browser exposing (element)
import List exposing (concatMap, foldl, head,member,filter,length,minimum,concat,map,map2,tail)
import List.Extra exposing (minimumBy, andThen)
import String exposing (join)
import Html as H
import Html as H
import Html.Attributes as HA
import Html.Attributes as HA
import Time exposing (Posix, every)
import List exposing (filter, head, length, map, map2, member, tail)
import Svg exposing (rect, line, svg, g)
import List.Extra exposing (andThen, minimumBy)
import String exposing (join)
import Svg exposing (g, line, rect, svg)
import Svg.Attributes exposing (fill, height, style, version, viewBox, width, x, x1, x2, y, y1, y2)
import Svg.Events exposing (onClick)
import Svg.Events exposing (onClick)
import Time exposing (every)
import Svg.Attributes exposing (version, viewBox, x, y, x1, y1, x2, y2, fill, style, width, height)
import Tuple


w = 450
h = 450
rowCount=20
colCount=20


type alias Cell = (Int, Int)
type alias Cell =
( Int, Int )

type alias BoardSize =
( Int, Int )


type alias Model =
type alias Model =
{ path : List Cell
{ path : List Cell
, board : List Cell
, board : List Cell
, pause_ms : Float
, size : BoardSize
}
}


type Msg
type Msg
= Tick Time.Posix
= NoOp
| SetStart Cell
| Tick Time.Posix
| SetStart Cell
| SetSize BoardSize
| SetPause Float


boardsize_width: BoardSize -> Int
init : () -> (Model,Cmd Msg)
boardsize_width bs =
Tuple.second bs

boardsize_height: BoardSize -> Int
boardsize_height bs =
Tuple.first bs

boardsize_dec: Int -> Int
boardsize_dec n =
let
minimum_size = 3
in
if n <= minimum_size then
minimum_size
else
n - 1
boardsize_inc: Int -> Int
boardsize_inc n =
let
maximum_size = 40
in
if n >= maximum_size then
maximum_size
else
n + 1

pause_inc: Float -> Float
pause_inc n =
n + 10

-- decreasing pause time (ms) increases speed
pause_dec: Float -> Float
pause_dec n =
let
minimum_pause = 0
in
if n <= minimum_pause then
minimum_pause
else
n - 10

board_init : BoardSize -> List Cell
board_init board_size =
List.range 0 (boardsize_height board_size - 1)
|> andThen
(\r ->
List.range 0 (boardsize_width board_size - 1)
|> andThen
(\c ->
[ ( r, c ) ]
)
)

nextMoves : Model -> Cell -> List Cell
nextMoves model ( stRow, stCol ) =
let
c =
[ 1, 2, -1, -2 ]

km =
c
|> andThen
(\cRow ->
c
|> andThen
(\cCol ->
if abs cRow == abs cCol then
[]

else
[ ( cRow, cCol ) ]
)
)

jumps =
List.map (\( kmRow, kmCol ) -> ( kmRow + stRow, kmCol + stCol )) km
in
List.filter (\j -> List.member j model.board && not (List.member j model.path)) jumps


bestMove : Model -> Maybe Cell
bestMove model =
case List.head model.path of
Just mph ->
minimumBy (List.length << nextMoves model) (nextMoves model mph)
_ ->
Nothing


-- Initialize the application - https://guide.elm-lang.org/effects/
init : () -> ( Model, Cmd Msg )
init _ =
init _ =
let
let board = (List.range 0 (rowCount-1))
|> andThen
-- Initial board height and width
(\r ->
initial_size =
(List.range 0 (colCount-1))
8

|> andThen
-- Initial chess board
(\c ->
initial_board =
[(r, c)]
)
board_init (initial_size, initial_size)

)
path = []
initial_path =
in (Model path board, Cmd.none)
[]
initial_pause =
10
in
( Model initial_path initial_board initial_pause (initial_size, initial_size), Cmd.none )



-- View the model - https://guide.elm-lang.org/effects/
view : Model -> H.Html Msg
view : Model -> H.Html Msg
view model =
view model =
let
let
showChecker row col =
showChecker row col =
rect [ x <| String.fromInt col
rect
, y <| String.fromInt row
[ x <| String.fromInt col
, width "1"
, y <| String.fromInt row
, height "1"
, width "1"
, fill <| if modBy 2 (row + col) == 0 then "blue" else "grey"
, height "1"
, onClick <| SetStart (row, col)
, fill <|
]
if modBy 2 (row + col) == 0 then
[]
"blue"


showMove (row0,col0) (row1,col1) =
else
line [ x1 <| String.fromFloat ((toFloat col0) + 0.5)
"grey"
, y1 <| String.fromFloat ((toFloat row0) + 0.5)
, onClick <| SetStart ( row, col )
, x2 <| String.fromFloat ((toFloat col1) + 0.5)
]
, y2 <| String.fromFloat ((toFloat row1) + 0.5)
[]

, style "stroke:yellow;stroke-width:0.05"
]
showMove ( row0, col0 ) ( row1, col1 ) =
[]
line
[ x1 <| String.fromFloat (toFloat col0 + 0.5)
, y1 <| String.fromFloat (toFloat row0 + 0.5)
, x2 <| String.fromFloat (toFloat col1 + 0.5)
, y2 <| String.fromFloat (toFloat row1 + 0.5)
, style "stroke:yellow;stroke-width:0.05"
]
[]


render mdl =
render mdl =
let checkers = mdl.board
let
|> andThen
checkers =
(\(r,c) ->
mdl.board
[showChecker r c]
|> andThen
)
(\( r, c ) ->
moves = case List.tail mdl.path of
[ showChecker r c ]
Nothing -> []
)
Just tl -> List.map2 showMove mdl.path tl
in checkers ++ moves


unvisited = length model.board - length model.path
moves =
case List.tail mdl.path of
Nothing ->
[]


Just tl ->
center = [ HA.style "text-align" "center" ]
List.map2 showMove mdl.path tl
in
checkers ++ moves


unvisited =
length model.board - length model.path

center =
[ HA.style "text-align" "center" ]

table =
[ HA.style "text-align" "center", HA.style "display" "table", HA.style "width" "auto", HA.style "margin" "auto" ]
table_row =
[ HA.style "display" "table-row", HA.style "width" "auto" ]

table_cell =
[ HA.style "display" "table-cell", HA.style "width" "auto", HA.style "padding" "1px 3px" ]
rows =
boardsize_height model.size

cols =
boardsize_width model.size
in
in
H.div
H.div
[]
[]
[ H.h2 center [H.text "Knight's Tour"]
[ H.h1 center [ H.text "Knight's Tour" ]
-- controls
, H.h2 center [H.text <| "Unvisited count : " ++ String.fromInt unvisited ]
, H.h2 center [H.text "(pick a square)"]
, H.div
, H.div
table
center
[ H.div -- labels
[ svg
table_row
[ version "1.1"
[ H.div
, width (String.fromInt w)
table_cell
, height (String.fromInt h)
[ H.text "Rows"]
, viewBox (join " "
, H.div
[ String.fromInt 0
table_cell
, String.fromInt 0
[ H.text "Columns"]
, String.fromInt colCount
, H.div
, String.fromInt rowCount ])
table_cell
]
[ H.text ""]
[ g [] <| render model]
, H.div
]
table_cell
]
[ H.text "Pause (ms)"]
]
, H.div
table_row
[ H.div -- Increase
table_cell
[ H.button [onClick <| SetSize ( boardsize_inc rows, cols )] [ H.text "▲"] ]
, H.div
table_cell
[ H.button [onClick <| SetSize ( rows, boardsize_inc cols )] [ H.text "▲"] ]
, H.div
table_cell
[ H.text ""]
, H.div
table_cell
[ H.button [onClick <| SetPause ( pause_inc model.pause_ms )] [ H.text "▲"] ]
]
, H.div
table_row
[ H.div -- Value
table_cell
[ H.text <| String.fromInt rows ]
, H.div
table_cell
[ H.text <| String.fromInt cols]
, H.div
table_cell
[ H.text ""]
, H.div
table_cell
[ H.text <| String.fromFloat model.pause_ms]
]
, H.div
table_row
[ H.div -- Decrease
table_cell
[ H.button [onClick <| SetSize ( boardsize_dec rows, cols )] [ H.text "▼"] ]
, H.div
table_cell
[ H.button [onClick <| SetSize ( rows, boardsize_dec cols )] [ H.text "▼"] ]
, H.div
table_cell
[ H.text ""]
, H.div
table_cell
[ H.button [onClick <| SetPause ( pause_dec model.pause_ms )] [ H.text "▼"] ]
]
]
, H.h2 center [ H.text "(pick a square)" ]
, H.div -- chess board
center
[ svg
[ version "1.1"
, width (String.fromInt (25 * cols))
, height (String.fromInt (25 * rows))
, viewBox
(join " "
[ String.fromInt 0
, String.fromInt 0
, String.fromInt cols
, String.fromInt rows
]
)
]
[ g [] <| render model ]
]
, H.h3 center [ H.text <| "Unvisited count : " ++ String.fromInt unvisited ]
]


-- Update the model - https://guide.elm-lang.org/effects/
nextMoves : Model -> Cell -> List Cell
update : Msg -> Model -> ( Model, Cmd Msg )
nextMoves model (stRow,stCol) =
update msg model =
let c = [ 1, 2, -1, -2]
let
mo =
case msg of
SetPause pause ->
{ model | pause_ms = pause }


SetSize board_size ->
km = c
{ model | board = board_init board_size, path = [], size = board_size }
|> andThen
(\cRow ->
c
|> andThen
(\cCol ->
if abs(cRow) == abs(cCol) then [] else [(cRow,cCol)]
)
)


jumps = List.map (\(kmRow,kmCol) -> (kmRow + stRow, kmCol + stCol)) km
SetStart start ->
{ model | path = [ start ] }


Tick _ ->
in List.filter (\j -> List.member j model.board && not (List.member j model.path) ) jumps
case model.path of
[] ->
model


_ ->
bestMove : Model -> Maybe Cell
bestMove model =
case bestMove model of
Nothing ->
case List.head (model.path) of
model
Nothing -> Nothing

Just mph -> minimumBy (List.length << nextMoves model) (nextMoves model mph)
Just best ->
{ model | path = best :: model.path }
in
( mo, Cmd.none )


update : Msg -> Model -> (Model, Cmd Msg)
update msg model =
let mo = case msg of
SetStart start ->
{model | path = [start]}
Tick posix ->
case model.path of
[] -> model
_ -> case bestMove model of
Nothing -> model
Just best -> {model | path = best::model.path }
NoOp -> model
in (mo, Cmd.none)


-- Subscribe to https://guide.elm-lang.org/effects/
subscriptions : Model -> Sub Msg
subscriptions : Model -> Sub Msg
subscriptions _ =
subscriptions model =
Time.every 10 Tick
Time.every model.pause_ms Tick


-- Application entry point
main: Program () Model Msg
main =
main =
element -- https://package.elm-lang.org/packages/elm/browser/latest/Browser#element
element
{ init = init
{ init = init
, view = view
, view = view
, update = update
, update = update
, subscriptions = subscriptions
, subscriptions = subscriptions
}
}
</lang>
</lang>


Link to live demo: http://dc25.github.io/knightsTourElm/
Link to live demo: https://dmcbane.github.io/knights-tour/


=={{header|Erlang}}==
=={{header|Erlang}}==
Retrieved from "https://rosettacode.org/wiki/Knight%27s_tour"