ข้อถัดมา 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 แต่ละแถวมาเชื่อมกัน

จะได้ออกมาเป็นแผนที่เขาวงกต



จบ