Movatterモバイル変換

[0]ホーム
URL:

Skip to content

Navigation Menu

Sign in
Appearance settings

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly

 Sign up
Appearance settings

Commita6f8cd5

Browse files
Yee17264json
authored andcommitted
Improve Knuth-Morris-Pratt's String Search (#14)
* Improve Knuth-Morris-Pratt's String SearchThe original code.js has both display and correctness errors.* Reconstruct Knuth-Morris-Pratt's String Search/code.js1. Add code foldings2. Delete log tracer to simplify the content3. Delete redundant display steps4. Indent using 4 spaces5. Rename variables6. Use fixed pattern and string to illustrate* Try to add code folding
1 parentf2af23a commita6f8cd5

File tree

26 files changed

+545
-182
lines changed

26 files changed

+545
-182
lines changed

‎Backtracking/Knight's Tour Problem/code.js

Lines changed: 19 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -1,4 +1,6 @@
1+
// import visualization libraries {
12
const{ Tracer, Array1DTracer, Array2DTracer, LogTracer, Layout, VerticalLayout}=require('algorithm-visualizer');
3+
// }
24

35
/*
46
For N>3 the time taken by this algorithm is sufficiently high
@@ -26,13 +28,15 @@ const Y = [1, 2, 2, 1, -1, -2, -2, -1];
2628
constpos=newArray(2);
2729
pos[0]=pos[1]=-1;
2830

31+
// define tracer variables {
2932
constboardTracer=newArray2DTracer('Board');
3033
constposTracer=newArray1DTracer('Knight Position');
3134
constlogTracer=newLogTracer('Console');
3235
boardTracer.set(board);
3336
posTracer.set(pos);
3437
Layout.setRoot(newVerticalLayout([boardTracer,posTracer,logTracer]));
3538
Tracer.delay();
39+
// }
3640

3741
functionknightTour(x,y,moveNum){
3842
if(moveNum===N*N){
@@ -43,37 +47,48 @@ function knightTour(x, y, moveNum) {
4347
constnextX=x+X[i];
4448
constnextY=y+Y[i];
4549

50+
// visualize {
4651
posTracer.patch(0,nextX);
4752
Tracer.delay();
4853
posTracer.patch(1,nextY);
4954
Tracer.delay();
5055
posTracer.depatch(0);
5156
posTracer.depatch(1);
57+
// }
5258
/*
5359
Check if knight is still in the board
5460
Check that knight does not visit an already visited square
5561
*/
5662
if(nextX>=0&&nextX<N&&nextY>=0&&nextY<N&&board[nextX][nextY]===-1){
5763
board[nextX][nextY]=moveNum;
5864

65+
// visualize {
5966
logTracer.println(`Move to${nextX},${nextY}`);
6067
boardTracer.patch(nextX,nextY,moveNum);
6168
Tracer.delay();
6269
boardTracer.depatch(nextX,nextY);
6370
boardTracer.select(nextX,nextY);
71+
// }
6472

6573
constnextMoveNum=moveNum+1;
6674
if(knightTour(nextX,nextY,nextMoveNum)===true){
6775
returntrue;
6876
}
77+
78+
// logger {
6979
logTracer.println(`No place to move from${nextX},${nextY}: Backtrack`);
80+
// }
7081
board[nextX][nextY]=-1;// backtrack
82+
// visualize {
7183
boardTracer.patch(nextX,nextY,-1);
7284
Tracer.delay();
7385
boardTracer.depatch(nextX,nextY);
7486
boardTracer.deselect(nextX,nextY);
87+
// }
7588
}else{
89+
// logger {
7690
logTracer.println(`${nextX},${nextY} is not a valid move`);
91+
// }
7792
}
7893
}
7994
returnfalse;
@@ -83,6 +98,7 @@ board[0][0] = 0; // start from this position
8398
pos[0]=0;
8499
pos[0]=0;
85100

101+
// visualize {
86102
boardTracer.patch(0,0,0);
87103
Tracer.delay();
88104
posTracer.patch(0,0);
@@ -93,9 +109,12 @@ boardTracer.depatch(0, 0);
93109
boardTracer.depatch(0,0);
94110
posTracer.depatch(0);
95111
posTracer.depatch(1);
112+
// }
96113

114+
// logger {
97115
if(knightTour(0,0,1)===false){
98116
logTracer.println('Solution does not exist');
99117
}else{
100118
logTracer.println('Solution found');
101119
}
120+
// }

‎Backtracking/N-Queens Problem/code.js

Lines changed: 20 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -1,4 +1,6 @@
1+
// import visualization libraries {
12
const{ Tracer, Array2DTracer, LogTracer, Layout, VerticalLayout}=require('algorithm-visualizer');
3+
// }
24

35
constN=4;// just change the value of N and the visuals will reflect the configuration!
46
constboard=(functioncreateArray(N){
@@ -16,6 +18,7 @@ const queens = (function qSetup(N) {
1618
returnresult;
1719
}(N));
1820

21+
// define tracer variables {
1922
constboardTracer=newArray2DTracer('Board');
2023
constqueenTracer=newArray2DTracer('Queen Positions');
2124
constlogger=newLogTracer('Progress');
@@ -25,6 +28,7 @@ boardTracer.set(board);
2528
queenTracer.set(queens);
2629
logger.println(`N Queens:${N}X${N}matrix,${N} queens`);
2730
Tracer.delay();
31+
// }
2832

2933
functionvalidState(row,col,currentQueen){
3034
for(letq=0;q<currentQueen;q++){
@@ -37,24 +41,31 @@ function validState(row, col, currentQueen) {
3741
}
3842

3943
functionnQ(currentQueen,currentCol){
44+
// logger {
4045
logger.println(`Starting new iteration of nQueens () with currentQueen =${currentQueen} & currentCol =${currentCol}`);
4146
logger.println('------------------------------------------------------------------');
47+
// }
4248
if(currentQueen>=N){
49+
// logger {
4350
logger.println('The recursion has BOTTOMED OUT. All queens have been placed successfully');
51+
// }
4452
returntrue;
4553
}
4654

4755
letfound=false;
4856
letrow=0;
4957
while((row<N)&&(!found)){
58+
// visualize {
5059
boardTracer.select(row,currentCol);
5160
Tracer.delay();
5261
logger.println(`Trying queen${currentQueen} at row${row} & col${currentCol}`);
53-
62+
// }
63+
5464
if(validState(row,currentCol,currentQueen)){
5565
queens[currentQueen][0]=row;
5666
queens[currentQueen][1]=currentCol;
5767

68+
// visualize {
5869
queenTracer.patch(currentQueen,0,row);
5970
Tracer.delay();
6071
queenTracer.patch(currentQueen,1,currentCol);
@@ -63,21 +74,28 @@ function nQ(currentQueen, currentCol) {
6374
Tracer.delay();
6475
queenTracer.depatch(currentQueen,1);
6576
Tracer.delay();
66-
77+
// }
78+
6779
found=nQ(currentQueen+1,currentCol+1);
6880
}
6981

7082
if(!found){
83+
// visualize {
7184
boardTracer.deselect(row,currentCol);
7285
Tracer.delay();
7386
logger.println(`row${row} & col${currentCol} didn't work out. Going down`);
87+
// }
7488
}
7589
row++;
7690
}
7791

7892
returnfound;
7993
}
8094

95+
// logger {
8196
logger.println('Starting execution');
97+
// }
8298
nQ(0,0);
99+
// logger {
83100
logger.println('DONE');
101+
// }

‎Branch and Bound/Binary Search Tree/insertion.js

Lines changed: 17 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -1,19 +1,26 @@
1+
// import visualization libraries {
12
const{ Tracer, Array1DTracer, GraphTracer, LogTracer, Layout, VerticalLayout}=require('algorithm-visualizer');
3+
// }
24

35
constT={};
46

57
constelements=[5,8,10,3,1,6,9,7,2,0,4];// item to be inserted
8+
9+
// define tracer variables {
610
constgraphTracer=newGraphTracer(' BST - Elements marked red indicates the current status of tree ');
711
constelemTracer=newArray1DTracer(' Elements ');
812
constlogger=newLogTracer(' Log ');
913
Layout.setRoot(newVerticalLayout([graphTracer,elemTracer,logger]));
1014
elemTracer.set(elements);
1115
graphTracer.log(logger);
1216
Tracer.delay();
17+
// }
1318

1419
functionbstInsert(root,element,parent){// root = current node , parent = previous node
20+
// visualize {
1521
graphTracer.visit(root,parent);
1622
Tracer.delay();
23+
// }
1724
consttreeNode=T[root];
1825
letpropName='';
1926
if(element<root){
@@ -25,30 +32,40 @@ function bstInsert(root, element, parent) { // root = current node , parent = pr
2532
if(!(propNameintreeNode)){// insert as left child of root
2633
treeNode[propName]=element;
2734
T[element]={};
35+
// visualize {
2836
graphTracer.addNode(element);
2937
graphTracer.addEdge(root,element);
3038
graphTracer.select(element,root);
3139
Tracer.delay();
3240
graphTracer.deselect(element,root);
3341
logger.println(`${element} Inserted`);
42+
// }
3443
}else{
3544
bstInsert(treeNode[propName],element,root);
3645
}
3746
}
47+
// visualize {
3848
graphTracer.leave(root,parent);
3949
Tracer.delay();
50+
// }
4051
}
4152

4253
constRoot=elements[0];// take first element as root
4354
T[Root]={};
55+
// visualize {
4456
graphTracer.addNode(Root);
4557
graphTracer.layoutTree(Root,true);
4658
logger.println(`${Root} Inserted as root of tree `);
59+
// }
4760

4861
for(leti=1;i<elements.length;i++){
62+
// visualize {
4963
elemTracer.select(i);
5064
Tracer.delay();
65+
// }
5166
bstInsert(Root,elements[i]);// insert ith element
67+
// visualize {
5268
elemTracer.deselect(i);
5369
Tracer.delay();
70+
// }
5471
}

‎Branch and Bound/Binary Search Tree/search.js

Lines changed: 14 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -1,4 +1,6 @@
1+
// import visualization libraries {
12
const{ Tracer, GraphTracer, LogTracer, Randomize, Layout, VerticalLayout}=require('algorithm-visualizer');
3+
// }
24

35
constG=[// G[i][j] indicates whether the path from the i-th node to the j-th node exists or not
46
[0,0,0,0,0,0,0,0,0,0,0],
@@ -29,33 +31,45 @@ const T = [ // mapping to G as a binary tree , [i][0] indicates left child, [i][
2931
];
3032

3133
constkey=Randomize.Integer({min:0,max:G.length-1});// item to be searched
34+
// define tracer variables {
3235
consttracer=newGraphTracer(' Binary Search Tree ');
3336
constlogger=newLogTracer(' Log ');
3437
Layout.setRoot(newVerticalLayout([tracer,logger]));
3538
tracer.set(G);
3639
tracer.layoutTree(5);
3740
tracer.log(logger);
3841
Tracer.delay();
42+
// }
3943

4044
functionbst(item,node,parent){// node = current node , parent = previous node
45+
// visualize {
4146
tracer.visit(node,parent);
4247
Tracer.delay();
48+
// }
4349
if(item===node){// key found
50+
// logger {
4451
logger.println(' Match Found ');
52+
// }
4553
}elseif(item<node){// key less than value of current node
4654
if(T[node][0]===-1){
55+
// logger {
4756
logger.println(' Not Found ');
57+
// }
4858
}else{
4959
bst(item,T[node][0],node);
5060
}
5161
}else{// key greater than value of current node
5262
if(T[node][1]===-1){
63+
// logger {
5364
logger.println(' Not Found ');
65+
// }
5466
}else{
5567
bst(item,T[node][1],node);
5668
}
5769
}
5870
}
5971

72+
// logger {
6073
logger.println(`Finding number${key}`);
74+
// }
6175
bst(key,5);// node with key 5 is the root

‎Branch and Bound/Binary Search/iterative.js

Lines changed: 16 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -1,5 +1,8 @@
1+
// import visualization libraries {
12
const{ Tracer, Array1DTracer, ChartTracer, LogTracer, Randomize, Layout, VerticalLayout}=require('algorithm-visualizer');
3+
// }
24

5+
// define tracer variables {
36
constchart=newChartTracer();
47
consttracer=newArray1DTracer();
58
constlogger=newLogTracer();
@@ -8,6 +11,7 @@ const D = Randomize.Array1D({ N: 15, value: () => Randomize.Integer({ min: 0, ma
811
tracer.set(D);
912
tracer.chart(chart);
1013
Tracer.delay();
14+
// }
1115

1216
functionBinarySearch(array,element){// array = sorted array, element = element to be found
1317
letminIndex=0;
@@ -18,33 +22,45 @@ function BinarySearch(array, element) { // array = sorted array, element = eleme
1822
constmiddleIndex=Math.floor((minIndex+maxIndex)/2);
1923
testElement=array[middleIndex];
2024

25+
// visualize {
2126
tracer.select(minIndex,maxIndex);
2227
Tracer.delay();
2328
tracer.patch(middleIndex);
2429
logger.println(`Searching at index:${middleIndex}`);
2530
Tracer.delay();
2631
tracer.depatch(middleIndex);
2732
tracer.deselect(minIndex,maxIndex);
33+
// }
2834

2935
if(testElement<element){
36+
// logger {
3037
logger.println('Going right.');
38+
// }
3139
minIndex=middleIndex+1;
3240
}elseif(testElement>element){
41+
// logger {
3342
logger.println('Going left.');
43+
// }
3444
maxIndex=middleIndex-1;
3545
}else{
46+
// visualize {
3647
logger.println(`${element} is found at position${middleIndex}!`);
3748
tracer.select(middleIndex);
49+
// }
3850

3951
returnmiddleIndex;
4052
}
4153
}
4254

55+
// logger {
4356
logger.println(`${element} is not found!`);
57+
// }
4458
return-1;
4559
}
4660

4761
constelement=D[Randomize.Integer({min:0,max:D.length-1})];
4862

63+
// logger {
4964
logger.println(`Using iterative binary search to find${element}`);
65+
// }
5066
BinarySearch(D,element);

0 commit comments

Comments
 (0)
[8]ページ先頭
©2009-2025 Movatter.jp