ข้อถัดมา
Always Turn Left คือ สมมติว่าคุณมีหุ่นยนต์ตัวนึงเพื่อสำรวจเขาวงกต
หลักการของหุ่นยนต์ตัวนี้ง่ายมาก ถ้าเจอทางแยกจะเลี้ยวซ้ายเสมอ
โจทย์ต้องการให้คุณวาดแผนที่ออกมา
อ่านเพิ่มเติม
ที่นี่ โจทย์ข้อนี้หลักการคิดคือ
ระหว่างที่หุ่นยนต์ตัวนี้เดินไป เราก็แค่เก็บตำแหน่งและทิศทางของแต่ละจุด
แล้วก็เอามา plot เป็นแผนที่
ก่อนอื่นเรามารู้จัก type ชื่อ direction กันก่อน
[<Flags>]
type Direction =
| None = 0
| North = 1
| South = 2
| West = 4
| East = 8
ด้านบนเป็นวิธีการเขียน
enum ของ f#
แล้วก็ functions ต่างๆ ที่เกี่ยวกับทิศทาง
let turnLeft = function
| Direction.North -> Direction.West
| Direction.South -> Direction.East
| Direction.West -> Direction.South
| Direction.East -> Direction.North
let opposite = function
| Direction.North -> Direction.South
| Direction.South -> Direction.North
| Direction.West -> Direction.East
| Direction.East -> Direction.West
let turnRight = turnLeft >> opposite
หันซ้าย และ ย้อนกลับ ค่อนข้างตรงตัว
ส่วนหันขวาคือการเอาหันซ้ายและย้อนกลับมาผสมกัน
และ function เกี่ยวกับการเดินทาง
let move (r, c) dir =
match dir with
| Direction.North -> r - 1, c
| Direction.South -> r + 1, c
| Direction.West -> r, c - 1
| Direction.East -> r, c + 1
อันนี้เป็นคำสั่งเลื่อน 1 ตำแหน่ง r และ c คือ ตำแหน่ง (rows และ columns)
อีกคำสั่งยากหน่อยแต่ควรทำความเข้าใจ
let rec replay cmd states dir =
match cmd with
| [] -> states, dir
| 'L'::cmd -> replay cmd states (turnLeft dir)
| 'R'::cmd -> replay cmd states (turnRight dir)
| 'W'::cmd ->
let newList =
let (point, wall)::tail = states
let newPoint = move point dir
let newState = newPoint, opposite dir
if wall = Direction.None then
newState::tail
else
let head = (point, wall ||| dir)
newState::head::tail
replay cmd newList dir
คือ คำสั่ง replay บันทึกการเดินทาง
cmd เป็น list เก็บบันทึกการเดินทาง
states เป็น list เก็บตำแหน่ง และลักษณะของห้อง
dir เป็น direction เก็บทิศทางล่าสุด
ถ้าดูจาก function ถ้า replay หมดทุกคำสั่ง [] ก็จะ return state กับ dir ออกไป
ถ้าสั่ง L หรือ R ก็แค่หันซ้ายและขวา แล้วทำคำสั่งถัดไป
ทีนี้ที่เยอะคือสั่ง W หลักๆ เช่น เรากำลังหันไปทางทิศเหนือ
เราก็กำหนดให้ ตำแหน่งที่เราอยู่ มีทางเดินไปทางทิศเหนือได้
และตำแหน่งถัดไป มีทางเดินมาจากทางทิศใต้ได้
คราวนี้มาเริ่มกันเลย เริ่มจาก function หลัก
let solve forward backward =
forward คือ บันทึกการเดินทางขาไป
backward คือ บันทึกการเดินทางขากลับ
เริ่มจากสั่ง replay เดินไปกลับ
let startPoint = [(-1, 0), Direction.None]
let (point, _)::tail, dir = replay (List.ofSeq forward) startPoint Direction.South
let returnPoint = (point, Direction.None)::tail
let _::tail2, _ = replay (List.ofSeq backward) returnPoint (opposite dir)
จุดเริ่มต้น startPoint คือ แถว -1 และเดินเข้าเขาวงกตจากทิศใต้เสมอ (โจทย์กำหนด)
แล้วก็เอาผลลัพธ์ของการ replay ครั้งแรกไปใส่ returnPoint เพื่อจะได้ทำการ replay ขากลับ
ได้ผลลัพธ์ tail2 คือ บันทึกตำแหน่งและลักษณะห้องในเขาวงกตทั้งหมด
สุดท้ายคือการเอา บันทึกตำแหน่งมา plot เป็นแผนที่เขาวงกต
let mergeWalls (key, list) =
key, list |> Seq.map snd
|> Seq.fold (|||) Direction.None
let hex = sprintf "%x"
let createRows (key, list) = list |> Seq.sortBy fst
|> Seq.map (snd >> int >> hex)
|> String.Concat
|> (+) "\r\n"
tail2 |> Seq.groupBy fst
|> Seq.map mergeWalls
|> Seq.groupBy (fst >> fst)
|> Seq.sortBy fst
|> Seq.map createRows
|> String.Concat
tail2 เป็น list เก็บตำแหน่งและลักษณะของห้องทั้งหมด
Seq.groupBy fst คือ การ group ตามตำแหน่ง
Seq.map mergeWalls คือ การเอาลักษณะของห้องมารวมกัน
ห้องๆ นึงเราอาจเดินผ่านหลายรอบ เช่นครั้งแรกเดินเข้ามาทางทิศตะวันตก แล้วไปทิศเหนือ
ผ่านมาอีกครั้งอาจจะมาจากทางทิศเหนือ ไปทางทิศตะวันออก
เมื่อเราเอาข้อมูลมารวมกัน ก็จะรู้ว่าห้องนี้ มีทางเดินทางทิศตะวันตก ทิศเหนือ และทิศตะวันออก
Seq.groupBy (fst >> fst) คือ จัดกลุ่มตาม row
Seq.sortBy fst คือเรียงตาม row คือ row แรกให้อยู่ด้านบน
คราวนี้คือ Seq.map createRows คือ การพิมพ์ห้องต่างๆ ในแต่ละ row
createRows คือ คำสั่งแปลงลักษณะห้องต่างๆ เป็น hex (โจทย์กำหนด)
แล้วเอา hex ของทั้งแถวมาเชื่อมกัน
สุดท้าย String.Concat คือการเอา hex แต่ละแถวมาเชื่อมกัน
จะได้ออกมาเป็นแผนที่เขาวงกต
จบ