How to solve pathfinding problem in Scheme?

Question

I been studing in Scheme for weeks and I ran into a problem that I couldn't solve. I can't find a way to solved it. Here is the problem:

Figure 1 shows an example path, which has a grid layout. In the grid, black cells are simply walls, which are basically obstacles for you. You can move among the white cells and you cannot pass the boundaries of the grid. In each path, the starting location will be the square of [0,0]. Additionally, there is also one white cell labeled with F. This label shows the finish square of the path. So, your aim is to find the movements from the starting location to the finish location. To this end, you can move in 4 directions; up, down, left, right. These 4 directions will be represented by characters U, D, L, and R, respectively.

The solution for the path shown in Figure 1 is "D D R R R R D D", which means move down 2 times, then move right 4 times and move down 2 times. The path is not a maze! It is a simple one way road and It has only one solution: there is always one possible next square for each move.

TASKS In Scheme, a path will be represented in the form of a linked-list. Figure 2 shows how the path in Figure 1 is represented in terms of a linked list in Scheme. Starting cell [0,0] has the letter S, the finishing cell has the letter F and empty cells have the letter E. The walls have the letter - (minus)

The following function "buildPath" on the left is given for you which takes a list of lists and creates a path (grid) using the lists. You can use this function to create different paths in order to test your code. On the right the code shows how the path in Figure 2 is created.

Task 1: Define two functions "getHeight" and "getWidth" which takes a path as an input and returns the height and the width of the path.

(getHeight sample-path) → should return 5

(getWidth sample-path) → should return 5

Task 2: Define a function "getLetter" which takes a path, a row number and a column number. Then it returns the letter from the path on the corresponding location [row, column]

(getLetter sample-path 0 0) → should return S

(getLetter sample-path 1 0) → should return E

(getLetter sample-path 1 1) → should return -

(getLetter sample-path 4 4) → should return F

Task 3: Define a function "solvePath" which takes a path and returns the solution for the path.

(solvePath sample-path) → should return (D D R R R R D D)

My codes are:

#lang scheme

(define (buildPath rows)
  (cond
    ((null? rows) null)
    (else (cons (buildPath (cdr rows))
                (car rows)))))

(define sample-path (buildPath
                     '(("S" "-" "-" "-" "-")
                       ("E" "-" "-" "-" "-")
                       ("E" "E" "E" "E" "E")
                       ("-" "-" "-" "-" "E")
                       ("-" "-" "-" "-" "F")))) 

(define (getHeight mylist)
  (define count 0)
  (define (height mylist)
    (cond
      ((null? mylist) null)
      (else 
       (if (null? (filter filter-out (cdr mylist))) null (set! count (+ 1 count)))
       (height (car mylist))
       )))
  (height mylist) count)

(define (getWidth mylist)
  (define count 0)
  (define (width mylist)
    (cond
      ((null? mylist) null)
      (else
       (define list-length (length(filter filter-out (cdr mylist))))
       (if (> list-length count) (set! count (+ 0 list-length)) null)
       (width (car mylist))
       )))
  (width mylist) count)

(define (getLetter mylist rownum columnum)
  (define count 0)
  (define (letter mylist)
    (cond
      ((eq? count rownum) (list-ref (cdr mylist) columnum))
      (else
       (set! count (+ 1 count))
       (letter (car mylist))
       )))
  (letter mylist))

(define (filter-out x)
  (if (eq? x "-") #f #t))

I solved Task 1 and Task 2 but stuck at Task 3. What logic can i use?

How to solve pathfinding problem in Scheme?

Answers (1)

Related Questions