# LeetCode 332. Reconstruct Itinerary in F#

## URL

Reconstruct Itinerary - LeetCode

## Code

https://github.com/syohex/dotnet-study/tree/master/fsharp/leetcode/problems/0332/main.fsx

```
let toGraphAndTicketCount (tickets: (string * string) list) : Map<string, string list> * Map<(string * string), int> =
let rec toGraph' tickets graph ticketCount =
match tickets with
| [] -> graph, ticketCount
| (departure, arrival) :: t ->
let graph' =
match Map.tryFind departure graph with
| Some(v) -> Map.add departure (arrival :: v) graph
| None -> Map.add departure [ arrival ] graph
let ticketCount' =
match Map.tryFind (departure, arrival) ticketCount with
| Some(v) -> Map.add (departure, arrival) (v + 1) ticketCount
| None -> Map.add (departure, arrival) 1 ticketCount
toGraph' t graph' ticketCount'
toGraph' tickets Map.empty Map.empty
let findItinerary (tickets: (string * string) list) : string list =
let rec findItinerary' departure visited used limit graph ticketCount =
if used = limit then
Some(List.rev visited)
else
match Map.tryFind departure graph with
| None -> None
| Some(arrivals) ->
arrivals
|> List.fold
(fun acc arrival ->
match acc with
| Some(_) -> acc
| None ->
let key = departure, arrival
match Map.tryFind key ticketCount with
| None -> None
| Some(v) ->
if v > 0 then
let ticketCount' = Map.add key (v - 1) ticketCount
findItinerary' arrival (arrival :: visited) (used + 1) limit graph ticketCount'
else
None)
None
let graph, ticketCount = toGraphAndTicketCount tickets
let graph' = Map.map (fun _ v -> List.sort v) graph
let limit = List.length tickets
match findItinerary' "JFK" [ "JFK" ] 0 limit graph' ticketCount with
| Some(v) -> v
| None -> failwith "never reach here"
```