ripzery / tallman

Tallman Code challenge

โจทย์: การทดลองของทอลแมน

ทอลแมนจับหนูมาทำการทดลองวิ่งในเขาวงกตสังเกตดูพฤติกรรมในการเรียนรู้ของหนู โดยการเอาอาหารมาล่อไว้ในเขาวงกต แล้วปล่อยหนูวิ่ง ปรากฏว่า หนูสามารถไปหาอาหารได้ทุกครั้ง

มีวันหนึ่ง หนูตัวที่ทอลแมนใช้ในการทดลองเกิดตาย ทอลแมนไปได้หนูตัวใหม่มา ทอลแมนใช้หนูตัวใหม่กับการทดลองแบบเดิม แต่หนูตัวนี้ฉลาดมากกว่าที่ทอลแมนคิดไว้ หนูตัวนี้วางแผนไว้ล่วงหน้าว่าถ้าเส้นทางที่เอามาให้วิ่ง มีเส้นทางที่ไปถึงอาหารได้จริง ๆ ถึงจะวิ่งหา แต่ถ้าไปไม่ถึงก็จะไม่ออกวิ่ง

Input:

• แผนที่ที่เป็น array 2 มิติขนาด m*n ที่มีค่าเป็น 0 และ 1 โดยที่ 0 หมายถึงพื้นที่ว่าง และ 1 หมายถึงกำแพง
• ขนาดของแผนที่ m, n
• ตำแหน่งเริ่มต้นของหนู x, y
• ตำแหน่งของอาหารล่อ p, q

Output: True - ถ้ามีเส้นทางเดินจากจุด x, y บนแผนที่ ไปยังอาหารที่จุด p, q ได้ False - ถ้าไม่มีเส้นทางไหนจากจุด x, y ไปถึงจุด p, q

เช่น

[
  [0, 0, 0, 0, 0, 0, 0, 0],
  [1, 1, 0, 1, 1, 1, 1, 0],
  [0, 0, 0, 0, 0, 0, 0, 0],
  [0, 1, 1, 1, 1, 1, 1, 1],
  [0, 0, 0, 0, 1, 0, 0, 0],
  [1, 0, 1, 1, 0, 1, 1, 0],
  [0, 0, 0, 0, 0, 0, 0, 0],
  [0, 1, 1, 1, 0, 1, 1, 0]
],
8, 8,
0, 0,
4, 5
-> True

Usage

private val map1: Array<IntArray> = arrayOf(
    intArrayOf(0, 0, 0, 0, 0, 0, 0, 0),
    intArrayOf(1, 1, 0, 1, 1, 1, 1, 0),
    intArrayOf(0, 0, 0, 0, 0, 0, 0, 0),
    intArrayOf(0, 1, 1, 1, 1, 1, 1, 1),
    intArrayOf(0, 0, 0, 0, 1, 0, 0, 0),
    intArrayOf(1, 0, 1, 1, 0, 1, 1, 0),
    intArrayOf(0, 0, 0, 0, 0, 0, 0, 0),
    intArrayOf(0, 1, 1, 1, 0, 1, 1, 0)
)

val rat = TallManRat.throwInMaze(map = map1, food = 4 to 5, position = 0 to 0)
println(rat.think(SpeakOptions.ALL_ROUTE)) // Available options are: ALL_ROUTE, BEST_ROUTE

Output

All route

(0, 0) -> (0, 1) -> (0, 2) -> (1, 2) -> (2, 2) -> (2, 1) -> (2, 0) -> (3, 0) -> (4, 0) -> (4, 1) -> (5, 1) -> (6, 1) -> (6, 2) -> (6, 3) -> (6, 4) -> (6, 5) -> (6, 6) -> (6, 7) -> (5, 7) -> (4, 7) -> (4, 6) -> (4, 5)
Total steps: 21
(0, 0) -> (0, 1) -> (0, 2) -> (0, 3) -> (0, 4) -> (0, 5) -> (0, 6) -> (0, 7) -> (1, 7) -> (2, 7) -> (2, 6) -> (2, 5) -> (2, 4) -> (2, 3) -> (2, 2) -> (2, 1) -> (2, 0) -> (3, 0) -> (4, 0) -> (4, 1) -> (5, 1) -> (6, 1) -> (6, 2) -> (6, 3) -> (6, 4) -> (6, 5) -> (6, 6) -> (6, 7) -> (5, 7) -> (4, 7) -> (4, 6) -> (4, 5)
Total steps: 31
true

Best route

(0, 0) -> (0, 1) -> (0, 2) -> (1, 2) -> (2, 2) -> (2, 1) -> (2, 0) -> (3, 0) -> (4, 0) -> (4, 1) -> (5, 1) -> (6, 1) -> (6, 2) -> (6, 3) -> (6, 4) -> (6, 5) -> (6, 6) -> (6, 7) -> (5, 7) -> (4, 7) -> (4, 6) -> (4, 5)
Total steps: 21
true