Pascal Triangle 3/100

 Pascal Triangle 3/100

Running out of screen space!

Day 3 of 100 Days of Code

So, Leetcode has this problem of creating Pascal triangle. And I've seen the solutions that people put up. It's vector this, list that, and I think doing it that way is overkill. What's with push-pop and all that jazz.

Personally, I think a single dimensional array suffice. After all, you're not computing beyond the last line, and that you can compute in either direction. Every solution I saw was from 0-N, whereas I do N-0, and save myself an extra array!

Computing the values is one thing. Displaying it is another, and I found out real quick that I don't have a big enough monitor to display more that 20 lines of values without losing the shape of the triangle. By the way, I redid the algorithm for displaying the triangle, so no more recursion being used from Day 1 program.

#include <stdio.h>
#include <stdlib.h> 

int PascalTri(int N) {
  int rows[100]; int i,j; 

  if (N<0 || N>20) return 1; //Out of bounds!
  rows[0]=1; for (i=99;i;i--) rows[i]=0;
  for (i=0;i<N;i++) {
    for (j=N-i-1;j;j--) printf("   ");
    for (j=0;j<=i;j++) printf(" %5d",rows[j]);
    puts("");
    for (j=i+1;j;j--) rows[j]+=rows[j-1];
  }
  return 0;
} 

int main (int argc, char *argv[] ) {
  int e=0;
  if   (argc<2) puts("Usage: pascaltri N\n");
  else e=PascalTri(atoi(argv[1]));
  if (e==1) puts("Error: Range is 0-20 inclusive.");
  return e;
}

One final note: Turns out that there is a way to mathematically compute the values so that I don't even need the array. Alas, I'm no mathematician.

Travelling Salesman

Random Path Finding: Travelling Salesman

I was reading this bit of article about quantum computing where there is a commercial quality version being sold for $10 million dollars. Of course, quantum computing promises a lot of performance gain, but in this case, D-WAVE, is specific for optimisation algorithm.

In brief, optimisation algorithm can be described as "hill climbing" algorithm. Basically, you're looking for the highest point in the area. So, as long as there is higher ground, you keep going up until you reach the highest point. The problem is that you will encounter local hills, that is the highest in the area, but not the highest overall. So, you have to watch out for "false peak".

Another problem is when you want to find a path through the area, and you want to find the highest overall path, or maybe the lowest. When the hills and valleys represent productivity and cost, then the path you have represents the highest productivity and the lowest cost.

This is all very desirable in computing. The payoff is immense and immediate. So, efficient path finding algorithm is extremely desirable in computing industry. An example of this is the travelling salesman problem where he needs to find the least distance to travel in order to work his route. This is applicable not just to travel, but also in manufacturing where the least distance a tool traverse, be it cutter, welder, or packer, is desirable.

There are two main approaches in order to solve this problem. I will call this the "forest" and the "tree" approaches. This is just a simplification of the process. There is another approach that I will describe later, but for now, let's focus on these two methods.

The forest method looks at the overall picture of the area and try to find the absolute best path possible. The simple, traditional way to do it, is to just do permutation of all possible path, and decide which one is the best. It has the good point of finding optimal solution. The bad point is that it is extremely costly in terms of computing power. Permutation has factorial cost.

The tree method looks at immediate surrounding and simply choose the best solution that is immediately present. The good point is that it is extremely cheap to do. The bad point is that it is susceptible to false peaks, dead ends, and other traps.

So, most people who are serious in solving the travelling salesman problem would do a compromise. They take a section of the local area and solve that optimally using the forest method, and by connecting several sections, they solve the whole area using the tree method. It works, and works very well. It is not the optimum method, but it is a good enough solution.

Apparently, that's not what the quantum computing promises. Due to the extremely efficient computation power available to the quantum computer, they instead solve it by "random" method. That is, they simply lay a path haphazardly, then they jiggle the path to see if a better path presents itself. Repeat that many, many times and eventually, you'll come up with a pretty good solution.

What the quantum computer can do, however, is to just lay down thousands of path all at once, and therefore be able to find the optimum path extremely quickly. There is a problem in reading the quantum result, but we'll ignore that for now. So, what it boils down to, is simply trial and error method. Is that wise?

The proponent of the method points out that such trial and error method is desirable where the problem is so difficult that it is not solvable. I concede the point of the solution, but I am not convinced that the path finding problem is "difficult".

So, I will point out another high respected "random stab" method that has since fallen out of favor: Neural Network. The field of neural network was very interesting with the proponent promises fantastic dreams. Yet, all it boils down to is a few mathematical functions. So, you have one gigantic mathematical equation, and what you do is twiddle the parameters until the error rate is near zero. There is a very sophisticated algorithm that you use in order to determine the parameters, but it looks random to me.

There is another alternative parameter determination method. That is the "Bayesian" method: Fire together, wire together. This is the tree method, where as the former was the forest method. As you can surmise, the Bayesian method is very quick and effective. Will that effect run into false hill problem? So far that hasn't happened because the problem isn't about path, but of pattern recognition. So, the domain of the problem is limited, and it turns out that Bayesian algorithm is perfect for such thing. However, path finding is beyond Bayesian algorithm to solve.

So, this brings me to another idea: Bogo sort. For those who doesn't know Bogo sort, it's also called Clown sort. What you do, basically, is to throw out all the elements up in the air, and if they fall down sorted, you're done. Obviously, that will take an extremely long time to complete, and there is no guarantee that it will finish the job. This is the forest method.

So, if that's the forest method, what about  the tree method? Turns out, it's bubble sort, where you simply compare the elements that are next to each other. This is also slow, because you're comparing one to another repeatedly. It's still faster than Bogo sort, at O(N^2), but slow when compared to other method.

And here's the interesting thing: I found out that if you combine these two slowest sorting algorithm, you will speed up the execution speed appreciably. It's still not the greatest, but it's a good step up. Here's the algorithm:

Random Sort:
1. For each element on list
1.1. Randomly compare this with other elements, swap if out of order
2. Repeat until sorted.

Bubble Sort:
1. For each element on list
1.1. Compare this element with the next one, swap if out of order.
2. Repeat until sorted.


Random Bubble Sort:
1. For each element on list
1.1. Randomly compare this with other elements, swap if out of order
1.2. Compare this element with the next one, swap if out of order.
2. Repeat until sorted.

There you have synergy where the whole is greater than the sum of its part. By combining the two approaches, the problem of randomness is eliminated by fastidious bubble sort, and the problem of slowness is eliminated by large random jumps. Combined together, it represents a large cost reduction available. There is a better solution than this, and that is comb sort. But that's topic for another time. Let's focus on this random solution for now.

Going back to the original travelling salesman problem, what does this have to do with path finding? It turns out that at its heart, the travelling salesman problem can be looked at as a sorting problem. If you take the distance between two points, and you compare them, then you can see that a comparison sort can yield a rather quick solution. A bubble sort TSP will yield interesting result, indeed.

The problem with bubble sort TSP is easy to see: Being the tree solution, it falls foul to the false peak problem. A random sort TSP, however, will not fall so easily. A permutation (sort) TSP will yield optimum solution, but as we can see, extremely expensive solution.

So, a "random stab" method of TSP, in effect is inefficient because it lacks that self-organization factor that sorting does. However, that problem is alleviated by using Random Bubble sort on TSP:

1. Create a lookup table for distance travelled between two points.
2. Do Random Bubble Sort, using the lookup table for comparison.
3. Repeat until time runs out or no improvement to the solution.

The key point here is "random". You always want to jiggle the points repeatedly to see if reversing the order of visiting two towns will yield better result. Eventually, a path will present itself that will consists of points that are next to each other. It will automatically allow backtrack, too. Will it be optimum? Maybe not, but it will be good enough.

Obviously, there is room for improvement. The obvious one is to lay down all the points in order when comparing distant points containing various points enroute. Another improvement is to restrict points consideration to smaller and smaller distance. But that is for further research and not for this session.

Another question would be if another sorting algorithm will work just as well. The answer to that is no. The more efficient sorting algorithm will not work because it lacks the "random jiggle" method. We want a random algorithm that constantly scans for better solutions.

And yet, there will come a time where the solution is fixed, and it will not change. Will that be optimum? Chances are, it won't. However, it will be close enough and in quick enough time. Whenever you are curious, simply run the program multiple times and see if the solution changes.

And there you have it. A random bubble sort may not be desirable in sorting problem domain. However, as it turns out, it's extremely desirable in path finding domain. It's all about mating the tools to the problem. That is all.

Petit Computer Journal #30

Programming Turtle Graphic

It somewhat annoys me when people are teaching turtle graphic as the basis of learning computer programming. It's not that turtle graphic is bad, as I do believe that the thought process does indeed teach programming. It is that the turtle is presented as a module. A black box, if you will.

I think it's more appropriate, especially for computer programming students to learn how simple and easy it can be to write their own turtle module. Therefore, I propose that instead of turtle graphic module, it should be a turtle graphic routines. Instead of a mysterious black box, it should be a transparent wrapper.

Done as a function call, especially interested students can take a peek into the function and see exactly how easy it can be to write a useful program such as turtle graphic.

In fact, I believe that it can be done in one hour. Turtle Graphic algorithm as an "Hour of Code" challenge? Bring it on!

First, what is involved in a turtle graphic program? Well, there's turtle and there's graphic. What are the commands necessary? Forward, Left, Right, and Pen. Each of those commands are followed by a number. We'll call that Number variable. Well, well. There are only 4 commands, are they? Would you believe that they are doable in about one hour? Why not?

If you are familiar with Object Oriented methodology, those are called "methods". What about variables? There's the position of the turtle, X0 and Y0. There's the destination of the turtle, X1 and Y1. There's Angle and Distance. And there's Pen Color. Is that 8 variables total? Are you saying coding these 8 variables into 4 commands is a great challenge? I don't think so!

Of course, we're skipping a lot of things. Namely, the LOGO language. LOGO is a programming language and if you are learning LOGO, you are learning computer programming language. The first turtle graphic and LOGO make effective combination. Most people incorrectly assume that turtle graphic must involve LOGO somewhat. Yet, Turtle graphic is just the graphical component of it. As for the language, we'll use Petit Computer Smile Basic.

That's all there is to it. So, let's set the timer and begin. 1 hour is all that takes. For simplicity, I will assume that commands are given in Strings and consist of 3 characters: A letter command, followed by 2 digit number. If the string has more than 3 characters, then the program will extract the first three characters only. If the string is less than 3 characters, it will be ignored. Also, Color 0 means Pen Up, which means moving the turtle without drawing the line. And perhaps, we should expand the language so we can do GPAINT command for colorful final image. With that in mind, let's begin!

In 15 minutes, I got the initial framework already.

1. ACLS:CLEAR
2. 
   
3. @INIT
4. C$="":'COMMAND STRING
5. N=0:'COMMAND PARAMETER
6. X0=128:Y0=96:'TURTLE POSITION
7. X1=0:Y1=0:'TURTLE DESTINATION
8. A=0:'ANGLE
9. D=0:'DISTANCE
10. C=0:'PEN COLOR
11. SPSET 1,139,0,0,0,0:SPOFS 1,X0,Y0
12. 
    
13. @MAIN
14. 'CLASSIC RECTANGLE
15. C$="F35R90F35R90F35R90F35R90"
16. GOSUB @TURTLE
17. WAIT 300
18. 
    
19. @END
20. BEEP 6
21. END
22. 
    
23. @TURTLE
24. IF LEN(C$)<3 THEN RETURN
25. TC$=LEFT$(C$,3)
26. N=VAL(RIGHT$(TC$,2))
27. TC$=LEFT$(C$,1)
28. C$=RIGHT$(C$,LEN(C$)-3)
29. ?TC$;" ",N;"  ":WAIT 60
30. 
    
31. GOTO @TURTLE

If you look at the code, there is nothing much there. It's simply the structure to pass on the command for the turtle. We can use IF-THEN ladder structure, or we can use ON-GOTO command structure. Depending on TC$, which contains the actual command. We can actually skip TC$, and specify LEFT$(C$,1) instead, but using that extra variable clarifies things for now.

I decided to do the easy thing first and implement Paint and Color command. Change C$ to "C01P00C02P00C03P00C04P00" for now. Also, we'll use ON-GOTO. This requires a numeric variable, so we'll do this

1. TN=INSTR("FLRCP",TC$)
2. ?TC$,TN,N:WAIT 60
3. 
   
4. ON TN GOTO @TTF,@TTL,@TTR,@TTC,@TTP
5. GOTO @TURTLE
6. @TTF
7. GOTO @TURTLE
8. @TTL
9. GOTO @TURTLE
10. @TTR
11. GOTO @TURTLE
12. @TTC
13. C=N:GCOLOR C
14. GOTO @TURTLE
15. @TTP
16. IF N==0 THEN GPAINT X0,Y0,C ELSE GPAINT X0,Y0,N
17. GOTO @TURTLE

Wow, that was easy! Of course, the hard part is coming up. Specifically, we're going to talk a bit about polar coordinates. We need it to draw the turtle. But first, we're going to just set the angle. That's not too difficult. All we have to do is adjust the angle variable just like we did with color. About the only thing that we have to do is to convert the angle to radians.

A bit of caution here. Mostly, we can just to "L180" to do a turn-about movement. However, since we decided to limit the numeric portion to just 2 digits, the most we can do is quarter turn. If we want to have turn-about the turtle, then we have to do it twice, with "L90L90" command.

Another thing. We want to rotate the turtle to the appropriate angle. So far, all we did was display the sprite. Now we want to set the angle and have the turtle facing in the right direction. So, there are two steps. First, we want to convert degrees to radians, and second, we want to orient the sprite accordingly.

There is a complication here. That is, computers have 0,0 coordinate on the top-left corner of the screen, unlike math with their 0,0 coordinate on the bottom-left of the screen. We'll have to fudge the math a bit, and the best way to do it is to just experiment. So, we're going to set up a new subroutine @ROTATE which will rotate the sprites according to angles. That is, given the value of A in degree, set the direction accordingly. All we have to do then, is decide which values goes which direction. I think 0 degree should point up. With that in mind, do this real quick:

1. @TEST
2. FOR A=0 to 360 STEP 360/12
3. GOSUB @ROTATE:WAIT 60
4. NEXT
5. 
   
6. @ROTATE
7. A=A%360
8. SPANGLE 1,A,6
9. RETURN

We discovered a weakness in our program in that the rotation is not centered on the sprite. We fix it by adding this line on the @INIT subroutine.

SPHOME 1,8,8

Then we simply add these lines to the LEFT and RIGHT portion of the code:

1. @TTL
2. A=A-N:'TURN LEFT
3. GOSUB @ROTATE
4. 
   
5. @TTR
6. A=A+N:'TURN RIGHT
7. GOSUB @ROTATE

And there you go! Just one more function and that's all there is to it! Who says turtle graphic programming is hard? Haha, joking aside, we have been delaying the inevitable. Not only we have to convert degree to radians, but we also have to make sure that the turtle is facing the right way. Fortunately, there are functions RAD(),SIN() and COS() that makes it simple. There is something else that we have to worry about, but we'll defer that until later. For now, let's draw!

1. @TEST
2. FOR A=0 to 360 STEP 360/12
3. SPOFS 1,128,96:GOSUB @ROTATE
4. X1=50*SIN(RAD(A)):'RSINTHETA
5. Y1=50*COS(RAD(A)):'RCOSTHETA
6. SPOFS 1,128+X1,96+Y1,50:'50 IS THE DISTANCE
7. WAIT 60
8. NEXT

If you run this code, you will see that the whole thing breaks up. You see that the sprite and the movement do not match. We want to see the sprites to move in a clock-wise pattern. The problem now is how to fix it? Remember that the coordinate is centered at top-left? That's the problem! To the math savvy among you, it may interest you to come up with the solution yourself. Otherwise, here's the fix!

Y1=-50*COS(RAD(A)):'RCOSTHETA

Yes, it's that easy! Simply turn R into negative R, and that's all there is to it. Really. Now, all we have to do is do the @TTF subroutine and we'll be done!

1. @TTF
2. D=N
3. X1=D*SIN(RAD(A))
4. Y1=(-1*D)*COS(RAD(A))
5. SPOFS 1,X0+X1,Y0+Y1,D
6. @TTF1
7. SPREAD(1),TTFX,TTFY:'GOSUB @WRAP
8. IF C!=0 THEN GPSET TTFX,TTFY,C
9. IF SPCHK(1)!=0 GOTO @TTF1
10. X0=X0+X1:Y0=Y0+Y1

And that's it! You're probably wondering why we're doing interval D on SPOFS. The reason for it is so that we can retrieve sprite coordinates TTFX,TTFY along the way, and plot the points with color C. That's a pretty neat trick. Otherwise, we'd have to mess around with line drawing algorithm. Not that coming up with line drawing algorithm is bad, just that it's an unnecessary complexity if all that we want is a simple subroutine.

Oh, one more thing: Suppose we want to do a wrap around? What should we do? Well, I don't like to mess with the current code, but basically, what we want to do is adjust the sprite location and update the target accordingly. So, we need to check whether TTFX or TTFY is below zero and if so, shift everything by the screenful. Trivial, had we did our own line drawing algorithm. Not so much if we're dependent upon internal routines, just like we did.

What exactly do we need to implement coordinate wrapping, anyway? Well, we need the start and stop coordinates, which are X0,y0 and X1,Y1. We also need a coordinate that specifies the current location going there. And we want to be able to reset the coordinates from the sprites.

So, we can do a bunch of calculation, but basically, we want to handle these 2 lines:

SPOFS 1,NEWX,NEWY
SPOFS 1,ADJX,ADJY,TIMELEFT

So, we need 5 variables to be set. To the math savvy among you, I suggest that you work it out yourself.

Time left is easy. We have already have D. For the new D, all we have to do is calculate the distance of the current position with the target coordinate. TIMELEFT=SQR((X1-TTFX)^2+(Y1-TTFY)^2) The old distance formula standby. NEWX and NEWY is simply OLDX=OLDX+256 and OLDY=OLDy+192. Basically, screen width and height. Same thing with ADJX and ADJY.

There's nothing to it, is there? We need to add WRAP=1 and replace the commented 'GOSUB @WRAP with IF WRAP THEN GOSUB @WRAP.

Before we do a bunch of complicated math, though, I'll point out to you something very interesting. The fact that there is only one GPSET makes it easy. If we don't care about drawing the point where the turtle is, and just worry about wrap, we can easily modify the line to this:

1. IF C!=0 THEN GPSET ((TTFX+256)%256),((TTFY+192)%192),C
2. IF SPCHK(1)!=0 GOTO @TTF1
3. X0=((X0+X1+256)%256):Y0=((Y0+Y1+192)%192)
4. SPOFS 1,XO,YO

That's something to think about. Do we want to write some complicated routines or do we just want to get the job done? With that in mind, instead of doing a bunch of mathematics, we can simply create a secondary sprite and put it into the current point set whenever the original turtle is out of bound! Simple, yet effective!

1. @WRAP
2. SPOFS 2,((TTFX+256)%256),((TTFY+192)%192)
3. SPANGLE 2,A,0
4. RETURN

And that's all there is to it! We can easily implement this within one hour. With wrap function, we're pushing it into the hour, depending on how fast you can type with the stylus. Regardless, we're only typing less than 100 lines program, with testing subroutine. What's the test? Well, remember that we're limiting the data to only 2 digits? That helps when we're doing wrapping test cases. But how about when we want to do large drawings? The test subroutine is used throughout the development process in order to try out subroutines outside the main program.

I commented out the test subroutine in the final program, but it's a good example on how you can use it in your program, so I'm leaving it there. The total time that it takes to do this program is:

15 min Initial Framework
10 min C and P command
10 min Rotation
15 min TTF drawing
10 min Wrap option

Total Development time? 1 hour, including screen wrap function. Now that's what I call "Hour of Code"!

1. REM TURTLE GRAPHIC
2. REM BY HARRY HARDJONO
3. REM DEC 2013
4. 
   
5. ACLS:CLEAR
6. 
   
7. @INIT
8. WRAP=1
9. C$="":'COMMAND STRING
10. N=0:'COMMAND PARAMETER
11. X0=128:Y0=96:'TURTLE POSITION
12. X1=0:Y1=0:'TURTLE DESTINATION
13. A=0:'ANGLE
14. D=0:'DISTANCE
15. C=0:'PEN COLOR
16. SPSET 1,139,0,0,0,0:SPOFS 1,X0,Y0
17. SPHOME 1,8,8
18. SPSET 2,139,0,0,0,0:SPOFS 1,-255,-255
19. SPHOME 2,8,8
20. 
    
21. @MAIN
22. 'GOSUB @TEST
23. 'CLASSIC RECTANGLE
24. FOR I=1 TO 8
25. C$="F35R90F35R90F35R90F35R90"
26. GOSUB @TURTLE
27. NEXT
28. 
    
29. @END
30. BEEP 6:WAIT 600
31. END
32. 
    
33. @TURTLE
34. IF LEN(C$)<3 THEN RETURN
35. TC$=LEFT$(C$,3)
36. N=VAL(RIGHT$(TC$,2))
37. TC$=LEFT$(C$,1)
38. C$=RIGHT$(C$,LEN(C$)-3)
39. TN=INSTR("FLRCP",TC$)
40. ON TN GOTO @TTF,@TTL,@TTR,@TTC,@TTP
41. GOTO @TURTLE
42. @TTF
43. D=N
44. X1=D*SIN(RAD(A))
45. Y1=(-1*D)*COS(RAD(A))
46. SPOFS 1,X0+X1,Y0+Y1,D
47. @TTF1
48. SPREAD(1),TTFX,TTFY:IF WRAP THEN GOSUB @WRAP
49. IF C!=0 AND WRAP==1 THEN GPSET ((TTFX+256)%256),((TTFY+192)%102),C
50. IF C!=0 AND WRAP==0 THEN GPSET TTFX,TTFY,C
51. IF SPCHK(1)!=0 GOTO @TTF1
52. IF WRAP==1 THEN X0=((X0+X1+256)%256:Y0=((Y0+Y1+192)%192):SPOFS1,X0,Y0
53. IF WRAP==0 THEN X0=X0+X1:Y0=Y0+Y1
54. GOTO @TURTLE
55. 
    
56. @TTL
57. A=A-N:'TURN LEFT
58. GOSUB @ROTATE
59. GOTO @TURTLE
60. @TTR
61. A=A+N:'TURN RIGHT
62. GOSUB @ROTATE
63. GOTO @TURTLE
64. @TTC
65. C=N:GCOLOR C
66. GOTO @TURTLE
67. @TTP
68. IF N==0 THEN GPAINT X0,Y0,C ELSE GPAINT X0,Y0,N
69. GOTO @TURTLE
70. 
    
71. @TEST
72. WRAP=1:'0 OR 1
73. FOR SP=0 TO 150 STEP 3
74. V=SP:LOCATE 0,0:?SP
75. @LINER
76. IF V>99 THEN C$="F99":GOSUB @TURTLE:V=V-99:GOTO @LINER
77. L1$=RIGHT$(("000"+STR$(V)),2)
78. C$="F"+L1$+"R70C"+L1$:GOSUB @TURTLE
79. NEXT
80. RETURN
81. 
    
82. @ROTATE
83. IF A<0 THEN A=A+360:GOTO @ROTATE
84. A=A%360:SPANGLE 1,A,6
85. RETURN
86. 
    
87. @WRAP
88. SPOFS 2,((TTFX+256)%256),((TTFY+192)%192)
89. SPANGLE 2,A,0
90. RETURN
91. 
    

Petit Computer Journal #27

Boolean Operator Division

Have you ever wondered just how difficult it is to do division using nothing but NOT,AND,OR,XOR? Well, so do I. It turns out I also need ADD,SUB, and CMP. Also, Shift command. Still, these are easily within the domain of any assembly language programming.

1. CLS
2. A=RND(255):B=RND(15)
3. ?A,B
4. C=0:D=128:E=B*D
5. FOR I=1 TO 8
6. IF A-E>=0 THEN A=A-E:C=C+D
7. ?A,B,C,D,E
8. D=D/2:E=E/2
9. NEXT I
10. ?C,A
11. FOR I=0 TO 8
12. VSYNC 1:I=BTRIG():NEXT
13. GOTO @DIV2

A contains the number to be divided. B contains the number that divides. This computes C=A/B and A=A%B. A pretty nifty code that fits single screen challenge. Notice, that you can also do it this way (untested) on line 6:

1. A=A-E:IF A<0 THEN A=A+E ELSE C=C+D

This way, due to the calculation in Assembly language where the register holds the resulting value of the calculation.