algorithms/Simple Recursive/Word Search/code.js at cd81d659a97c54efed92e3d10d39000eb3a645e8 · algorithm-visualizer/algorithms · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
// import visualization libraries {
    const { Array2DTracer,Array1DTracer, Layout, LogTracer, Tracer, VerticalLayout } = require('algorithm-visualizer');
    // }

    const N = 4; // just change the value of N and the visuals will reflect the configuration!
    const board = [
        ['A','L','U','C'],
        ['E','F','L','U'],
        ['X','I','N','C'],
        ['Q','Y','E','K']
    ];

    const word = ['L','U','C','K'];

    // define tracer variables {
    const boardTracer = new Array2DTracer('Board');
    const logger = new LogTracer('Progress');
    const wordTracer = new Array1DTracer('Word');
    Layout.setRoot(new VerticalLayout([boardTracer,wordTracer,logger]));
    boardTracer.set(board);
    wordTracer.set(word);
    logger.println(`board of size ${N} X ${N} consisting of letters`);
    Tracer.delay()
    // }

    function wordSearch(board,word,r,c,indx){
        let rowBounds = r >= 0 && r < board.length;
        let colBounds = c >= 0 && c < board.length;
        if(!rowBounds){
            // logger {
                logger.println("The current position is out of bounds");
           // }
            return false;
        }
        if(!colBounds){
             // logger {
                logger.println("The current position is out of bounds");
           // }
            return false;
        }
        if(board[r][c] == '#'){
             // logger {
                logger.println(`The current position ${r} and ${c} is already visited`);
           // }
            return false;
        }
        if(indx == word.length){
              // logger {
                logger.println("The given word is found");
           // }
            return true;
        }
        // visualize {
        boardTracer.select(r, c);
        wordTracer.select(indx);
        Tracer.delay();
        logger.println(`Trying matching word ${word[indx]} at row ${r} & col ${c}`);
        // }
        if(board[r][c] == word[indx]){
            let temp = board[r][c];
            board[r][c] = '#';
            // visualize {
                boardTracer.patch(r,c,temp);
                Tracer.delay();
           // }
            let isFound = false;
            isFound = isFound || wordSearch(board,word,r + 1,c,indx + 1);
            isFound = isFound || wordSearch(board,word,r - 1,c,indx + 1);
            isFound = isFound || wordSearch(board,word,r,c + 1,indx + 1);
            isFound = isFound || wordSearch(board,word,r,c - 1,indx + 1);
            if(isFound){
                return true;
            }
        // visualize {
          boardTracer.deselect(r, c);
          Tracer.delay();
          logger.println(`row ${r} & col ${c} didn't work out`);
          // }
            board[r][c] = temp;
        // visualize {
                boardTracer.deselect(r,c);
                wordTracer.deselect(indx);
                boardTracer.depatch(r,c);
                Tracer.delay();
         // }
        }
        // visualize {
              boardTracer.deselect(r,c);
              wordTracer.deselect(indx);
              Tracer.delay();
        // }
        return false;
    }
    function main(){
        for(let i = 0; i < N; i++){
            for(let j = 0; j < N; j++){
                // visualize {
                 wordTracer.select(0);
                  boardTracer.select(i,j);
                  Tracer.delay();
                // }
                if(board[i][j] == word[0]){
                    // logger {
                        logger.println(`The letter ${word[0]} is matched and the function is going to run to traverse and find the remaining letters to form target word`);
                    // }
                    if(wordSearch(board,word,i,j,0)){
                        return true;
                    }
                }
                 // visualize {
                  wordTracer.deselect(0);
                  boardTracer.deselect(i,j);
                  Tracer.delay();
                // }
            }
        }
        return false;
    }
    main();