Date: Thu, 14 Oct 93 09:10:14 EDT From: swensotc@ss1.ss1.sews.wpafb.af.mil (TIMOTHY C. SWENSON) To: ts@chyde.uwasa.fi (Timo Salmi) Subject: Q L H A C K E R ' S J O U R N A L =========================================== Supporting All QL Programmers =========================================== #15 October 1993 The QL Hacker's Journal (QHJ) is published by Tim Swenson as a service to the QL Community. The QHJ is freely distributable. Past issues are available on disk, via e-mail, or via the Anon-FTP server, garbo.uwasa.fi. The QHJ is always on the look out for article submissions. QL Hacker's Journal c/o Tim Swenson 5615 Botkins Rd Huber Heights, OH 45424 USA (513) 233-2178 swensotc@ss1.sews.wpafb.af.mil swensotc@p2.ams.wpafb.af.mil tswenson@dgis.dtic.dla.mil Editor's Forumn It has taken a while to get this issue out. I would like to thank Al Boehm for submitting an article and making this issue that much bigger. I'm always ready to recieve an article for submission. I'd like to see what programming other are doing out there. The last weekend of August is the Dayton ComputerFest. For most Sinclair people in roughly the Mid-West area, it has been a meeting place, in lue of a Sinclair Fest. The event is anchored by Mechanical Affinity (Frank Davis and Paul Holmgren of Indiana). Some of the local user groups attend as well. User groups like, SMUG (Wisconson), ITSUG (Indiana), Chicago Area User Group, and the Dayton group (as small as we are). In previous years, most of the Sinclair people would get togther and go to a restraunt for dinner. This year I decided to put on a Bar-B-Q at my place and invite every one over. I wanted a place where everyone could mingle and chat with everyone. You normally don't get to do this at a regular restaurant. With a total turn out of about 23 people, things went pretty well. While at the ComputerFest, I finally broke down and picked up a 3.5" 720K disk drive. When I was in Virginia a local QL user was able to transfer between formats for me. Now, in Dayton I'm sort of on my own. After some fiddling with the ribbon cable (the 3.5" wanted it differently than the 5.25") I was able to get it fully working. So, now I am able to handle both types of disk sizes. Hex Movement Library Recently I've been distracted by one of my other hobby, wargaming. There has been a discussion on USENET about freeware space combat games. Having designed one a few years back, I quickly did an ASCII version and posted it. This then lead to further distractions in that hobby. Feeling guilty about "abandoning" the QL, I wanted to come up with some program that would tie the two hobbies together. Most wargames are based on hex maps. One of the difficulties in putting wargames on a computer is the hex map system. A square map system is nothing more than a 2D array. But a hex map system, with each cell having 6 neighbors is takes some work. It's workable with a square map, by extending the rules for what squares are "next" to the current square. After pondering over this, and pursuing how I would represent a hex map in an array, I discovered that I really don't need to store the hex map, just a way of determining what hex was next to the current hex. Anything relating to what is in a hex can be stored in an array, looked up by the hex number. These routines will determine two things, what hex is next to the current hex (given any direction), and the distance (in hexes) between two hexes. Determining what hex is next to another hex was fairly easy. Finding the proper distance was a more challenging task. I first tried the distance formula used in square coordinate system. This had some flaws. I then tried a different appoached based on simple common sense about hexes. This worked until I got back to the program the next day and THEN saw that it did not work. Back to the distance formula. After much pluging and chugging, plus some tinking with the distance formula, I found an algorithm that worked (at least in the cases that I tested). I found the general case that failed in the plain distance formula and found a fix for these cases. I'm pretty sure that it all works fine, but I have not tested all cases. The hex number system that I used came from my favorite wargame, OGRE. I have not played with other numbering systems. Each hex number is two numbers combined, a column number and a row number. 0102 is column 01 and row 02. Below is a quick drawing of the numbering system __ / \ __/ Y \__ / \ / \ /|\ Hex X = 0102 / X \__/ Z \ | Hex Y = 0201 \ / \ / Hex Z = 0302 \__/ A \__/ N Hex A = 0202 \ / \__/ 100 DEFine FuNction even(num) 110 true = 1 : false = 0 120 IF (num MOD 2) = 0 THEN 130 RETurn true 140 ELSE 150 RETurn false 160 END IF 170 END DEFine 190 DEFine FuNction odd(num) 200 true = 1 : false = 0 210 IF (num MOD 2) > 0 THEN 220 RETurn true 230 ELSE 240 RETurn false 250 END IF 260 END DEFine 270 DEFine FuNction hex_north$(hex_num$) 280 LOCal column$, row, temp$ 290 column$ = hex_num$(1 TO 2) 300 row = hex_num$(3 TO 4) 310 row = row - 1 320 temp$ = row 330 IF LEN(temp$) = 1 THEN temp$="0"&temp$ 340 RETurn column$&temp$ 350 END DEFine 360 DEFine FuNction hex_south$(hex_num$) 370 LOCal column$, row, temp$ 380 column$ = hex_num$(1 TO 2) 390 row = hex_num$(3 TO 4) 400 row = row + 1 410 temp$ = row 420 IF LEN(temp$) = 1 THEN temp$="0"&temp$ 430 RETurn column$&temp$ 440 END DEFine 450 DEFine FuNction hex_ne$(hex_num$) 460 LOCal temp1$,temp2$,column,row 470 column = hex_num$(1 TO 2) 480 row = hex_num$(3 TO 4) 490 IF odd(column) THEN row=row-1 500 column=column+1 510 temp1$ = row 520 IF LEN(temp1$) = 1 THEN temp1$ = "0"&temp1$ 530 temp2$ = column 540 IF LEN(temp2$) = 1 THEN temp2$ = "0"&temp2$ 550 RETurn temp2$&temp1$ 560 END DEFine 570 DEFine FuNction hex_se$(hex_num$) 580 LOCal temp1$,temp2$,column,row 590 column = hex_num$(1 TO 2) 600 row = hex_num$(3 TO 4) 610 IF even(column) THEN row=row+1 620 column=column+1 630 temp1$ = row 640 IF LEN(temp1$) = 1 THEN temp1$ = "0"&temp1$ 650 temp2$ = column 660 IF LEN(temp2$) = 1 THEN temp2$ = "0"&temp2$ 670 RETurn temp2$&temp1$ 680 END DEFine 690 DEFine FuNction hex_nw$(hex_num$) 700 LOCal temp1$,temp2$,column,row 710 column = hex_num$(1 TO 2) 720 row = hex_num$(3 TO 4) 730 IF odd(column) THEN row=row-1 740 column=column-1 750 temp1$ = row 760 IF LEN(temp1$) = 1 THEN temp1$ = "0"&temp1$ 770 temp2$ = column 780 IF LEN(temp2$) = 1 THEN temp2$ = "0"&temp2$ 790 RETurn temp2$&temp1$ 800 END DEFine 810 DEFine FuNction hex_sw$(hex_num$) 820 LOCal temp1$,temp2$,column,row 830 column = hex_num$(1 TO 2) 840 row = hex_num$(3 TO 4) 850 IF even(column) THEN row=row+1 860 column=column-1 870 temp1$ = row 880 IF LEN(temp1$) = 1 THEN temp1$ = "0"&temp1$ 890 temp2$ = column 900 IF LEN(temp2$) = 1 THEN temp2$ = "0"&temp2$ 910 RETurn temp2$&temp1$ 920 END DEFine 930 DEFine FuNction hex_dist(hex1$,hex2$) 940 LOCal temp1, temp2, col1, col2, row1, row2, dist 950 col1 = hex1$(1 TO 2) 960 row1 = hex1$(3 TO 4) 970 col2 = hex2$(1 TO 2) 980 row2 = hex2$(3 TO 4) 990 temp1 = col2 - col1 1000 temp2 = row2 - row1 1010 dist = temp1^2 + temp2^2 1020 dist = SQRT(dist) 1030 IF INT(dist) < dist THEN 1040 IF row2 = row1-1 THEN 1050 dist = INT(dist) 1060 ELSE 1070 dist = INT(dist)+1 1080 END IF 1090 END IF 1100 RETurn dist 1110 END DEFine As a side note, if there are any QLer's out there that are interested in Wargaming, I've got a few Freeware wargames that I have designed and a few that I have picked up off the Internet. I've designed one tactical space combat and one tank combat game. I have all of these as Quill documents. If any are interested, please contact me. Base Conversion In some postings in on Usenet, there have been some conversations about converting from different bases. I found this task interesting and thought I'd give it a try. I did fairly well in writing a routine that would convert from Base X to Base 10. Converting from base 10 to base X was more difficult. It got the the point that I decided to give up (my programming time is limited these days, so I hate to bang my head againt a programming wall). As a textbook would say "I'll leave it as an exercise for the reader." 100 DEFine FuNction base_ten(num$,origin_base) 110 LOCal x,y,z,total 120 total = 0 130 FOR x = LEN(num$) TO 1 STEP -1 140 y = CODE(num$(x)) 150 IF y<65 THEN z = num$(x) 160 IF y>=65 AND y<=90 THEN z = y-54 170 IF y >97 AND y<=122 THEN z = y-86 180 total = total+(z*(origin_base^(LEN(num$)-x))) 190 NEXT x 200 RETurn total 210 END DEFine Computer Language Humor Here are a couple of related postings that I found on USENET. Each one gives a slighly different view of a number of computer languages. Programming Languages As A Car Assembler - A formula I race car. Very fast but difficult to drive and maintain. FORTRAN II - A Model T Ford. Once it was the king of the road. FORTRAN IV - A Model A Ford. FORTRAN 77 - a six-cylinder Ford Fairlane with standard transmission and no seat belts. COBOL - A deliver van It's bulky and ugly but it does the work. BASIC - A second-hand Rambler with a rebuilt engine and patched upholstery. Your dad bought it for you to learn to drive. You'll ditch it as soon as you can afford a new one. C - A black Firebird, the all macho car. Comes with optional seatbelt (lint) and optional fuzz buster (escape to assembler). Pascal - A Volkswagon Beetle. It's small but sturdy. Was once popular with intellectual types. Modula II - A Volkswagon Rabbit with a trailer hitch. LISP - An electric car. It's simple but slow. Seat belts are not available. FORTH - A go-cart. LOGO - A kiddie's replica of a Rolls Royce. Comes with a real engine and a working horn. APL - A double-decker bus. It takes rows and columns of passengers to the same place all at the same time but it drives only in reverse and is instrumented in Greek. Ada - An army-green Mercedes-Benz staff car. Power steering, power brakes, and automatic transmission are standard. No other colors or options are available. If it's good enough for generals, it's good enough for you. THE PROGRAMMER'S QUICK GUIDE TO THE LANGUAGES The proliferation of modern programming languages (all of which seem to have stolen countless features from one another) sometimes makes it difficult to remember what language you're currently using. This handy reference is offered as a public service to help programmers who find themselves in such a dilemma. TASK: Shoot yourself in the foot. C: You shoot yourself in the foot. C++: You accidentally create a dozen instances of yourself and shoot them all in the foot. Providing emergency medical assistance is impossible since you can't tell which are bitwise copies and which are just pointing at others and saying, "That's me, over there." FORTRAN: You shoot yourself in each toe, iteratively, until you run out of toes, then you read in the next foot and repeat. If you run out of bullets, you continue with the attempts to shoot yourself anyways because you have no exception-handling capability. Pascal: The compiler won't let you shoot yourself in the foot. Ada: After correctly packing your foot, you attempt to concurrently load the gun, pull the trigger, scream, and shoot yourself in the foot. When you try, however, you discover you can't because your foot is of the wrong type. COBOL: Using a COLT 45 HANDGUN, AIM gun at LEG.FOOT, THEN place ARM.HAND.FINGER on HANDGUN.TRIGGER and SQUEEZE. THEN return HANDGUN to HOLSTER. CHECK whether shoelace needs to be re-tied. LISP: You shoot yourself in the appendage which holds the gun with which you shoot yourself in the appendage which holds the gun with which you shoot yourself in the appendage which holds the gun with which you shoot yourself in the appendage which holds the gun with which you shoot yourself in the appendage which holds the gun with which you shoot yourself in the appendage which holds... FORTH: Foot in yourself shoot. BASIC: Shoot yourself in the foot with a water pistol. On large systems, continue until entire lower body is waterlogged. Visual Basic: You'll really only _appear_ to have shot yourself in the foot, but you'll have had so much fun doing it that you won't care. APL: You shoot yourself in the foot, then spend all day figuring out how to do it in fewer characters. Assembler: You try to shoot yourself in the foot, only to discover you must first invent the gun, the bullet, the trigger, and your foot. INTERNET CONSICENESS PRORAMMING CONSTEST Round 5 [ In past issues of the QHJ I've covered this contest. I've included Round 5 for completeness - ED ] PAPER FOLDING You are given a sheet of paper that contains all asterisks ('*') on top, and all pound signs ('#') on the bottom. A three by five sheet of this paper would look like this ***** ***** ***** on top, and this ##### ##### ##### on the bottom. If you were to make a vertical fold in the paper one unit from the right edge of the paper, the resulting paper would look like this ***# ***# ***# on top. For this round, you will be writing a program which, given the dimensions of a piece of paper with asterisks on top and pound signs on the bottom, will show how that piece of paper looks after a number of folds have been made in it. The Input There will be multiple data sets in the input file. Each data set will start with two numbers on a single line separated by a space ( 1 <= x <= 10, 1 <= y <= 10 ). These are the dimensions of the piece of paper -- x rows and y columns. The next line of the data set contains a single number which indicates the number of folds you are to make in the piece of paper. The next lines will each contain a description of a fold in the form ED N where E is either 'T', 'B', 'L', or 'R' (meaning 'top', 'bottom', 'left', and 'right' respectively); D is either 'O' or 'U' (meaning 'over' or 'under' respectively; and N is an integer indicating how many units from the edge you are to make the fold. E will always be in column 1, D will always be in column 2, a space will always be in column 3, and N will always start in column 4. The specifiers E, D, and N mean that you are to fold the E edge of the paper in the direction D at a point N units from the E edge. Thus, a line which reads RO 1 means you are to fold the right side of the paper over, one unit from the _current_ rightmost edge of the paper. A line reading BU 3 means you are to fold the _current_ bottom edge of the paper under, three units from the current bottom edge. The Output Produce as output what the paper looks like after all folds have been made. Left justify your output, and print a blank line between data sets. Sample Input 3 5 1 RO 1 4 6 2 BU 1 RO 1 6 6 1 LU 5 Sample Output ***# ***# ***# ****# ****# ***** *#### *#### *#### *#### *#### *#### HOW DO THEY DO THAT - EDITORS [ Here is an interesting response to a posting on editing files larger than memory. The algorithm listed below has a few good points, but also a few bad ones. I guess the key problem is finding the last line of a file quickly without scanning through the entire file each time. - ED ] arisz@csri.toronto.edu (Aris Zakinthinos) writes: > I was working on a document in a wordprocessor a couple >of days ago and one thing struck me as cool. Even though >the document is around 500k I could insert text at the >begining of the document with ease. The characters were >appearing as fast as I could type. So I started thinking >how do they do it. I don't believe they move ~500k of >memory around for every new keystroke. Anybody have any >ideas on how this is done? A relatively simple scheme that allows editing of files as large as disk space permits goes as follows: Keep the current line in memory. Keep all lines above current line in one temporary file (file 1) and all lines beyond current line in another temporary file (file 2). The trick is to keep the lines in file 2 in reverse order. Suppose that I'm editing the following file: 1 2 3 4 5 6 7 8 9 And that the curser is placed at line 4: The edit files will show: File 1: File 2: 1 10 2 9 3 8 7 6 5 To insert a line above current line: Append to file 1: To insert a line beyond current line: Append to file 2: To delete a line: Read last line from file 2 into buffer. To move one line up: Append buffer to file 2 and read last line from file 1 into buffer. To move one line down: Append buffer to file 1 and read last line from file 2 into buffer. Initially file 1 will be empty and file 2 will contain the original file in reverse line order. To create file 2 in the first place at least two different approaches may be used: 1) If no processing is to be done on the original file (no CR LF expansion etc), that is if file 2 will be exactly the same size as the original file the following scheme may be used: Obtain the size of the original file. Call it SIZE Create file 2 and seek to position SIZE. Read original file one line at a time each time seeking backwards in file 2 the size of the line read and write the line to file 2. After writing seek backwards again. 2) If there is some need for processing on the original file: Open original file, seek to the end, and read backwards one line at a time and append the lines read to file 2. The advantage of 1) above is that the original file is read from the beginning and that file 2 is created from the end.. This makes it possible in a multitasking system (Unix) to do the creation of temporary files as a separate task (process). Using proper syncronization between editing and copying it is possible to allow the user to start edit the file even before file 2 is finished. Quite impressing to start editing a 5 MB file and see the first page show up immediately. Actually we are using exactly this scheme on a Unix based wordprocessor system. Of course this scheme is not as fast as a strictly memory based one, but using proper buffer sizes and disk caching the performance may be quite good. The main disadvantage is, that moving around requires moving data between the two temporary files. Per H. Nielsen Stochastic Indexing by Al Boehm This demo program, SID (Stochastic Indexing Demo), see listing 1 below, simulates clouds as seen by a satellite looking straight down. As a pictorial rendering of clouds, it is rather poor since it only uses circles to indicate where clouds are. But with a little imagination, one can see structures that resemble some types of clouds. By varying the random number seed, the number of clouds, puffs, rows, etc., a wide variety of patterns can be generated. However, cloud depiction is not its purpose. Its purpose is to demonstrate a new method of "storing" and retrieving randomly generated features. One hundred cloud clusters each with up to 30 puffs (an average of 17) are generated for a total of about 1700 puffs. The location and size of each of these puffs can be retrieved very fast. The computer memory storage required to "store" this information is ZERO!! Furthermore, the number of puffs could have just as easily been 10 million with additional information on liquid water content, vertical velocity, etc. etc., and the required storage still would be zero. The method is not limited to clouds. The same method could be used for simulated trees in a forest, simulated fish in the sea, or simulated accounts in a bank. The trick is to reseed the random number generator using the feature's index - in this case the cloud's identification number, 1 to 100. Some background on random number generators may help understanding. Random Number Generators Computer random number generators start with some initial number, operate on this number, then return the result as a "random number". Often used is the simple congruential generator: New_random_number = (Old_random_number * V1 + V2) mod V3 where the constants V1, V2, and V3 are carefully chosen to emulate randomness and keep the series of numbers as large as possible before the same number repeats. Thus, these numbers are not random at all but have a definite sequence to them. [Extra Credit Brain Teaser: Given three consecutive random numbers from a simple congruential generator, how can V1, V2, and V3 be calculated?] Some computers use the video refresh frame number as a Old_random_number to obtain varied sequences. I once worked on a program that used this method only to keep getting the same random sequence. It turned out that at the command RUN, the video refresh frame number was reset to zero and the same Old_random_number was always obtained. Another case I read about used an analog to digital converter hooked up to a Geiger counter reading background random radiation to obtain a "true" random number. The only trouble was that the random numbers had a distinct period in them that coincided with a nearby revolving radar. In any case, stochastic indexing makes use of these reproducible sequences to rapidly regenerate specific information about each indexed feature such as location, size, etc. The Demo Program With regard to the demo program itself, programmers will understand most lines. But a few sections need some additional explanation. The most important part is the procedure Ith_Cloud. It is used to initially define each clouds parameters when called from line 230 and is also used to retrieve the ith cloud's parameters when called from line 320. Ith_Cloud Spacer In Ith_Cloud, line 470 sets the random number seed for the ith cloud. The 99 times the index is a spacer so that the starting number for each cloud is 99 items further along in the random number sequence. Without the 99, the y location of the first cloud would be the x location of the second cloud (sometimes!). A spacer larger than the largest possible number of parameters for each feature keeps the same sequences from being reused. Sometimes too small a spacer causes no noticeable effect; other times, some weird things happen. Acceptance/Rejection The algorithm as stated so far will give a uniformly random distribution of clouds. That is, any point is just as likely to have a cloud as any other. There are many simulation algorithms to convert uniform distributions to some desired pattern. The one used here is an acceptance/ rejection method that allows stochastic indexing to produce varied patterns. Lines 480 to 510 contain an acceptance/rejection algorithm which is pretty standard in simulation. It works like this: A function is defined over the area that is close to 1 where you want most clouds, close to zero where you want few clouds, and negative where you want no clouds. The function chosen (feel free to chose your own) here is COS(2*PI*Nrows*(x-y)) where Nrows determines the number of cloud rows and (x-y) locates them in lower-left to upper- right orientation. The Cosine function varies from 1 to -1 as x-y varies. Next a potential site, x and y, is selected. The function at x and y (-1 to 1 in this case) is compared to a random number (0 to 1). If the function is larger then the random number, the site is selected; but if the random number is larger, then the site is rejected and a new pair of x and y is selected. This continues (REPeat accept_reject) until a site is selected. Do you see why sites with a function near one will have more clouds? Any function can be used, but make sure it is positive at least in some areas or the REPeat loop will never be exited. Also functions with small areas of positive values and areas with most values near zero will run very long since most sites will be rejected most of the time. Speed, Networking, and Portability Random number generators are generally coded to be very fast. In many cases, a random number can be generated as fast or faster than a number can be fetched from an array in ram, particularly a multi-dimensional array. If the array must be sent over a LAN (Local Area Network) or WAN (Wide Area Network) for distributed simulation, then stochastic indexing is much faster. On the other hand, random number generators are often specific to a particular computer. If all computers on the net are the same, then there is no problem. But if they are different, the random number sequences can be different. The QL random numbers are different from the Thor XVI random numbers. There are such things as portable random number generators, But as they say, that is another story. ORIGIN Stochastic Indexing was developed by me on the QL computer in May 1991. At the time I thought it was a very neat trick but that simulators probably used it all the time. In the last two years, I have not found any mention of it in the simulation literature so it's possible that it is original. On the other hand, I wouldn't be very surprised to find it used in a 1948 simulation program. LISTING 1 This is written in SuperBasic. Math sections are similar enough for any Basic or FORTRAN programmer to understand. 100 REMark SID Stochastic Indexing Demo 30 Aug 1993 110 REMark Set limits. Try varying these. 120 Seed=898 :REMark defines a new random set. 130 Total_clouds=100 :REMark Number of clouds. 140 max_puffs=30 :REMark Max Number of puffs for each cloud 150 max_i_size=10 :REMark max size of cluster, closeness of puffs 160 max_puff_size=2 :REMark max size of puff in cluster 170 Nrows=4 :REMark Number of rows per unit(height of window)distance 180 : 190 WINDOW 512,246,0,0:WINDOW#2,512,10,0,246:PAPER#2,0 :INK#2,5 200 REMark ************ make cloud scape ************ 210 MODE 8:PAPER 1:INK 7:CLS 220 FOR i=1 TO Total_clouds 230 Ith_Cloud i:REMark sets x,y,isize,npuffs_at_i 240 FOR j=1 TO npuffs_at_i 250 CIRCLE x+RND*isize,y+RND*isize,RND*max_puff_size 260 END FOR j 270 END FOR i 280 REMark ******* find cloud i, puff j ******** 290 REPeat find 300 CLS#2:PRINT#2, 'Find which cloud? Enter 1 to '; Total_clouds,:INPUT#2, i 310 IF i<1 OR i>Total_clouds THEN BEEP 2000,100:GO TO 300 320 Ith_Cloud i:REMark Call to Ith_Cloud sets x,y,isize, npuffs_at_i 330 PRINT#2, 'Cloud ';i,'Which puff? Enter 1 to '; npuffs_at_i;:INPUT#2, j 340 IF j<1 OR j>npuffs_at_i THEN BEEP 2000,100:GO TO 320 350 FOR k=1 TO j-1:a=RND:b=RND:c=RND 360 x= x+RND*isize:y=y+RND*isize:r=RND*max_puff_size 370 PRINT #2,'Push s to stop or another key to go on.'; 380 REPeat blink 390 INK 0:CIRCLE x,y,r 400 INK 7:CIRCLE x,y,r 410 a$=INKEY$:IF a$<>'' THEN EXIT blink 420 END REPeat blink 430 IF a$=='S' THEN STOP 440 END REPeat find 450 STOP 460 DEFine PROCedure Ith_Cloud (i) 470 RANDOMISE i*99+Seed:REMark sets new seed as a function of i 480 REPeat accept_reject 490 x=RND:y=RND 500 d=COS(2*PI*Nrows*(x-y)):IF d>RND THEN EXIT accept_reject 510 END REPeat accept_reject 520 x=x*162:y=y*100:REMark scale to fill screen 530 isize=RND*max_i_size 540 npuffs_at_i=RND(5 TO max_puffs) 550 END DEFine Ith_Cloud Stochastic Indexing is from NESQLIG August 1993 Newsletter with correction: line 340 changed to 320