name keywords etiquetas etiqueta ejemplos description content algorithm f# tree traversal

algorithm - keywords - meta tags ejemplos



¿Qué pasa con mi código de cruce de árbol? (1)

Como comentó Robert, tal vez su función makeCorridor necesita algo de atención. He adaptado tu código, haciendo mi propia función makeCorridor y reemplazando Rect por int.

He usado un patrón activo para determinar cuándo un BspTree es una habitación. ¡También utilicé el yield! sequence yield! sequence lugar de for x in sequence -> x . Estas modificaciones resultan en el mismo comportamiento. Solo quería mostrar lo que un patrón activo puede hacer:

type BspTree = | Node of int * BspTree * BspTree | Null let (|IsRoom|_|) dungeon = match dungeon with | Node(_,Null,Null) -> Some dungeon | _ -> None let rec getRooms = function | IsRoom dungeon -> Seq.singleton dungeon | Null -> Seq.empty | Node (_, left, right) -> seq { yield! getRooms left yield! getRooms right } let makeCorridor leftNode rightNode = match leftNode, rightNode with | Node(left,Null,Null), Node(right,Null,Null) -> sprintf "(%d) -> (%d)" left right | _ -> failwith "Illegal corridor!" let rec getCorridors = function | Null -> failwith "Unexpected null room" | Node(_, Null, Null) -> Seq.empty | Node(_, IsRoom left, IsRoom right) -> seq { yield makeCorridor left right } | Node(_, left, right) -> seq { yield! getCorridors left yield! getCorridors right }

Ejemplo:

let dungeon = Node(1, Node(2, Node(4,Null,Null), Node(5,Node(8,Null,Null), Node(9,Null,Null))), Node(3, Node(6,Null,Null), Node(7,Null,Null)))

Resultado en FSI:

> getCorridors dungeon;; val it : seq<string> = seq ["(8) -> (9)"; "(6) -> (7)"]

Tengo un árbol simple, definido así:

type BspTree = | Node of Rect * BspTree * BspTree | Null

Puedo obtener una colección de nodos de hojas (salas en mi árbol "mazmorra") como esta, y parece funcionar:

let isRoom = function | Node(_, Null, Null) -> true | _ -> false let rec getRooms dungeon = if isRoom dungeon then seq { yield dungeon } else match dungeon with | Node(_, left, right) -> seq { for r in getRooms left -> r for r in getRooms right -> r } | Null -> Seq.empty

Pero ahora estoy tratando de obtener salas de nodo hermana para poder conectarlas con corredores, y estoy fallando miserablemente (como suelo hacer a menudo). Aquí está mi intento:

let rec getCorridors dungeon = match dungeon with | Null -> failwith "Unexpected null room" | Node(_, left, right) -> match left, right with | Null, Null -> Seq.empty | Node(leftRect, _, _), Node(rightRect, _, _) -> if isRoom left && isRoom right then seq { yield makeCorridor leftRect rightRect } else seq { for l in getCorridors left -> l for r in getCorridors right -> r } | _ -> failwith "Unexpected!"

Acabo de terminar con un seq vacío. De todos modos, todo esto me duele el cerebro, y sé que es poco probable que alguien lo atraviese, pero pensé que no estaría de más preguntarlo.