Date: Wed, 14 Jul 93 11:27:43 EDT
From: swensotc@ss1.sews.wpafb.af.mil (TIMOTHY C. SWENSON)
To: ts@chyde.uwasa.fi
Subject: <No subject>

    Q L   H A C K E R ' S    J O U R N A L
=======================================================
   #14                         July 1993

   The QL Hacker's Journal is newsletter decicated to
supporting all QL programmers and is published as a
service to the QL community by Tim Swenson.

   The QHJ is freely distributable in whole or part as
long a mention is made of where the material came from.

	QL Hacker's Journal
	  c/o Tim Swenson
	  5615 Botkins Rd.
	  Huber Heights, OH 45424
	  (513) 233-2178
	  swensotc@p2.ams.wpafb.af.mil
	  swensotc@ss1.sews.wpafb.af.mil
	  tswenson@dgis.dtic.dla.mil



EDITOR'S FORUMN
   By Tim Swenson

   It's been a few months since the last QHJ, but I've been
busy working on a few projects and doing some traveling.

   In early June I traveled to Newport, Rhode Island to
attend the "Miracle in Newport 93" QL show.  There I was
able to meet some QL'ers that I have not met before, plus
renew accquantances with those that I have met but not seen
in a while.  Attendence was fairly good.  I was pleased to
see that three vendors from the UK were able to make it.
Stuart Honeyball of Miracle, Tony Firshman of T.F. Services,
and Bill Richardson (can't remember what company he owned)
provided a few new Sinclair stories for all to enjoy.

   The hit of the show was the new QXL card.  I must admit
that I did not take a close look at it, knowing that my
pocket book was not ready for it (plus I don't have a PC to
run it on).  Some people were hesitant to buy, knowing that
it is so new and not quite ready ( I believe the Basic is
still being worked on).  But, there was one buyer who braved
the waters and bought a full QXL (I can handle 8 Meg of
memory, but comes with various amounts of memory, so you can
buy memory on the local market).

   The most entertaining story was the one Bill Richardson
told about Sir Clive.  About a year and a half ago, Bill ran
across Sir Clive, whom he had known for some time.  Sir
Clive asked Bill what he was doing, and Bill mentioned that
he was selling hardware and software for Sir Clive's
computers.  "You mean the Z88", said Sir Clive.  "No, the
QL", replied Bill.  Sir Clive's answer was "The what?"  It
seems Sir Clive had forgotten all about the QL.

   While on the subject of Sir Clive, I happened to see a
.sig file from a Sinclair fan (can't remember who it was)
that said "If only Clive Sinclair was Bill Gates, and vice
versa".  Kind of makes you think.

   Now to another subject, I am working on a QL Freeware
list.  I know that there is an Freeware Exchange (IFE), but
I am trying to compile a list of the more major QL freeware
packages, like MicroEmacs, C68, GNU Awk, Yacc, QeM, and so
on.  Full packages, not just a short utility.  Believe me,
nothing I write will probably show up on the list.  I plan
to upload a draft version to Garbo.  I hope others will
download it and provide me with comments, additions, and
changes.

   In the April 1993 edition of "The C Users Journal",
there is an article covering natural language processing.
The accompanying source code was plain C so I thought I
would get it to run on the QL.  I got a hold of the code
and compiled it with C68.  It compiled just fine (no errors
or warnings).  Then the test, to see if it will run.  It
seemed to work fine, execpt that it always returned "I
don't know" to all the questions I asked it.  I used the
examples from the book and still no luck.

   As a control test, I compiled the code under MS-DOS with
Mix Power C and everything worked fine.  The examples in
the book gave the proper answer.

   Now for some debugging.  I put some print statements in
the QL version to see where things might be going awry.
After a while I noticed that the program was not looking at
a file on disk as it should.  I did not know if this was
because of a buffer or an error with C68.

   Not having the expertise in C (or the time), I would
like to throw the gauntlet to anyone out there.  I can
e-mail someone the source code or put it on disk.  To
further peak someone's interest, there was a follow on
article in the June issue expanding the language processor
(adding tense).  I hope some C expert out there will take
the time to port this program over to the QL.


MORE ON TEXT EDITORS
   By Franz Herrmann

   Reading through Tim's article on text editors in QHJ
#13, I found that his list of editors available on the QL
was far from being complete. That is why I would like to
add the following to his overview.

SEDIT by Ralf Redoendt of Dilwyn Jones Computing

   A small and fast editor written in compiled SuperBASIC
and assembly language.  SEDIT is commercial but there is a
free demo version.  Under the Pointer Environment, SEDIT
can be cloned, ie. several copies run from the same
version.  SEDIT does not require any system extensions.

DME

   Thanks to C68, this powerfull editor has been ported
from the Amiga. Similar to MicroEmacs, DME is a very large,
fully programmable, can edit multiple files and is free.
DME is much faster than MicroEmacs and has even been
further improved over the Amiga version.

QD by Jochen Merz Software

   QD, now at version 5.x, is a commercial editor for the
QL and much different from all the others because it is
using all the latest improvements to QDOS to the full:
Pointer Environment, Things, Menu Extensions, Button Frame
and more.

   The advantage is not simply a graphical user interface,
optionally mouse driven, at the cost of increased memory
requirements and reduced editing speed.  QD is able to
exploit higher screen resolutions due to the use of the
Pointer Environment.  This is important for those poeple
who are using one of those Atari emulators with Extended
MODE 4, it's successor, the QVME caard which gives up to
1024x1024 pixels resolution at four colors (provided you
can pay for the monitor) for the Atari range of computers,
the QXL card (Miracles 68040 QL to be pllugged into PCs)
that will be able to support higher resolutions with future
driver releases or the forthcoming so-called Graphics Card,
another QL machine from Miracle.  The QD window can be
resized and repositioned at runtime.

   From version 5 onwards, QD has a much improved Thing
interface, allowing other programs to control the actions
of QD, you could even write your own commands for QD - if
you are very good at machine code programming.

   QD does not support editing multiple files but it is not
necessary because you can run several QD jobs from the same
piece of code in memory.  All the usual editor commands are
implemented in menus and the more important ones can be
called by short key presses.

Other Editors

   There are even more editors but I have only heard of
them resp. saw them from a distance at QL meetings: ArcEd
from Cowo Electronics (Switzerland), the editors supplied
with GenQL assembler and Computer One programming
languages.

   Myself, I am using QD except for large files which QED
loads and edits much faster.


TEN COMMANDMENTS OF C PROGRAMMERS
   by Henry Spencer

   [ This was a document that I found on the Internet that
I thought would be an interest to the C programmers out
there - ED ]

   1. Thou shalt run lint frequently and study its
pronouncements with care, for verily its perception and
judgement oft exceed thine.

   2. Thou shalt not follow the null pointer, for chaos and
madness await thee at its end.

   3. Thou shalt cast all function arguements to the
expected type if they are not of that type already, even
when thou art convinced that this is unnecessary, lest they
take cruel vengence upon thee when thou least expect it.

   4. If thy header files fail to declare the return types
of thy library functions, thou shalt declare them thyself
with the most meticulous care, lest grievous harm befall
thy program.

   5. Thou shalt check the array bounds of all strings
(indeed, all arrays), for surely where thou typest 'foo'
someone someday shall type
'supercalifragilisticexpialidocious'.

   6. If a function be advertised to return an error code
in the event of difficulties, shou shalt check for that
code, yea, even though the checks triple the size of thy
code and produce aches in thy typing fingers, for if thou
thinkest 'it cannot happen to me', the gods shall surely
punish thee for thy arrogance.

   7. Thou shalt study thy libraries and strive not to
re-invent them without cause, that thy code may be short
and readable and thy days pleasant and productive.

   8. Thou shalt make thy program's purpose and structure
clear to thy fellow man by using the One True Brace Style,
even if thou likest it not, for thy creativity is better
used in solving problems than in creating beautiful new
impediments to understanding.

   9. Thy external identifiers shall be unique in the first
six characters, though his harsh discipline be irksome and
the years of its necessity stretch before thee seemingly
without end, lest thou tear thy hair out and go mad on that
fateful day when thou desirest to make thy program run on
an old system.

   10. Thou shalt foreswear, renounce, and abjure the vile
heresy which claimeth that 'All the world's a VAX', and
have no commerce with the benighted heathens who cling to
this barbarous belief, that the days of thy program may be
long even though the days of thy current machine be short.


INTERNET CONCISENESS CONSTEST

   Mark Schnitzius (schnitzi@eustis.cs.ucf.edu) has started
and runs the Internet Conciseness Contest.  The contest is
designed to provide an outlet for recreational programming.
The contest accepts programs only in Ansi C.  Scores are
based on the number of tokens in a program.  The lower the
score the better.

Mark is up to Round number 4.  Below is the problems from
each round.

    The Internet Conciseness Programming Contest Series
              Problem #1 -- Range Arithmetic

   Scientists modelling physical systems often need to
perform arithmetic involving numbers which are not
precisely specified.  For instance, if the pressure in a
tank is known to be greater than or equal to twenty and
less than twenty-five, and this pressure increases by an
amount greater than one but less than or equal to three,
the resulting pressure will be greater than twenty-one but
less than twenty-eight.  This equation could be represented
as

   [20,25)+(1,3]=(21,28)

   Notice here that the square brackets "[]" mean that the
endpoint is included, while the round brackets "()" mean
that it is not.  Your job is to write a program which reads
in simple range arithmetic expressions and produces the
correct results.

INPUT FORMAT:

   There will be one simple expression per line in the
following format:

    <range1><operator><range2>

   where operator is one of "+" (addition), "-"
(subtraction), and "*" (multiplication).  You will not need
to worry about division in this problem, as it presents
some trickiness (especially when dividing by a range which
includes zero).

The ranges will be in this format:

    <left-delimeter><int1><comma><int2><right-delimeter>

where

   <left-delimeter> is "[" or "("
   <int1> is the integer denoting the low end of the range
   <int2> is the integer denoting the high end of the range
   <right-delimeter> is "]" or ")"

<int1> is guaranteed to be LESS THAN <int2>.  There will be
no spaces or extra characters in the input.

OUTPUT FORMAT:

   For each line of input, echo the expression that you
read in, followed an equals sign, followed by the range
that represents the result of the expression, in the same
range format specified above.


SAMPLE INPUT:

[20,25)+(1,3]
(4,5)*(1,2]
[9,10]-[3,4)
(-4,2)*[2,3)
[-2,2]*(-2,2)
[-2,2]*[-2,2)

SAMPLE OUTPUT:

[20,25)+(1,3]=(21,28)
(4,5)*(1,2]=(4,10)
[9,10]-[3,4)=(5,7]
(-4,2)*[2,3)=(-12,6)
[-2,2]*(-2,2)=(-4,4)
[-2,2]*[-2,2)=[-4,4]

             Problem #2 -- TARGET NUMBERS

   Consider the numbers 1, 2, and 3.  If you combine them
using ordinary operators (+,-,*,/), possibly adding
parentheses, they can be made to equal a number of
different values:

         1+2-3 = 0
         3*2+1 = 7
       (2+1)*3 = 9

The Problem:

   You are to write a program that, given a set of integers
and a target integer, produces an arithmatic expression
equaling the target value which uses ALL of the integers in
the input set.  You may use all of the above-mentioned
operators.  The precedence of the operators is defined as
follows:

    '*'  equals  '/'  greater than  '+'  equals  '-'

   Hence, all multiplications and divisions are done first
(left to right) before the additions and subtractions
(which are also left to right).  You may need to include
parentheses in your expression, but ADD NO MORE THAN ARE
NECESSARY.

Input Format:

   YOUR PROGRAM MUST BE ABLE TO ACCEPT MULTIPLE DATA SETS.
I will redirect a file containing judge data into your
program, so your program must accept input from stdin.
Each data set consists of three lines.  The first line will
contain a single integer <n> where 2 <= n <= 5.  The second
line will contain <n> POSITIVE integers seperated by
spaces, which represent the set of integers you have to
work with. The third line will contain an integer (POSITIVE
or NEGATIVE) which is the value you are targeting.

Output Format:

   For each data set, output (to stdout) an expression
which equals the target number and uses EVERY integer in
the input set, followed by an equal sign, followed by the
target number.  If it is not possible to generate the
target number from the set of integers, output the line
'TARGET NUMBER UNREACHABLE'.

Sample Input:

3
1 2 3
0
3
1 2 3
9
5
1 1 0 5 23
-13
3
1 1 1
8
3
10 5 13
26
5
2 2 2 2 2
20

Sample Output:

2+1-3=0
(1+2)*3=9
5*(1+1)-23+0=-13
TARGET NUMBER UNREACHABLE
10/5*13=26
((2+2)*2+2)*2=20

   Before you ask, here are some other points:

   o There may be more than one way to generate a target
value. Print out only one -- it does not matter which, as
long as the expression is well-formed and generates the
correct target value without using more parentheses than
are needed for that expression (there may be other
expressions equaling the target number which use fewer
parentheses, but as long as there are no extraneous
parentheses in the expression you output, that is okay).

   o Only use the '/' in a situation where it will divide
evenly.  For example, if you are given the numbers 3, 2 and
2 with a target of 3, the equation '3/2*2=3' is incorrect,
while '2/2*3=3' is okay.

   o You may not add a unary '-' to a number or expression
to negate it.  Combine the numbers using the four operators
in a binary fashion only.

   o Do not combine numbers by catenating their digit
strings. That is, do not combine a 5 and a 7 into 57.

          Problem #3  --  "Maximum Products"

   Here's a problem that sounds deceptively simple, but a
lot of subtlety is involved in making it concise.

The Problem:

   Given a long string of digits, insert a '*' into it so
that the product formed is maximal.

   The input file consists of multiple lines of input.
Each input line contains an n-digit number in columns 1
through n (1 < n <= 35).  There will be no leading zeros in
the input. Your output should be the original digit string
with the '*' inserted, followed by an equal sign, followed
by the resulting product.  Leading zeros on any of the
numbers that you output are not allowed.  If more than one
answer is possible for a given input, print any one.

Sample input:

12343
10000000
333
10001
1122334455667788998877665544332211

Sample output:

123*43=5289
1000000*0=0
33*3=99
1000*1=1000
1122334455667788*998877665544332211=
   1121074821037408888890148523519268

              The Problem #4 -- Minesweeper

   This problem was adapted from the Windows game called
'Minesweeper'.  Those of you familiar with the game need to
pay close attention, as there are some differences.

   Consider the following 5x5 square grid:

    ----*
    -----
    *----
    *----
    -*---

   The asterisks on this grid represent 'mines'.  The
matrix that would result as a sweep of this grid would look
like this:

   00011
   11011
   22000
   33100
   22100

   Here, a number <n> in row <i> column <j> means that
there are <n> mines adjacent to (or directly at) row <i>
column <j>.  Your program is to read in matrices
representing sweeps of a mine field and produce a map
showing the likely locations of mines.

Input Format:

   There will be multiple data sets.  Each data set will
start with a single integer n (1 <= n <= 10) on a line by
itself. The next n lines will each contain n columns of
single-digit integers representing the n by n matrix that
is the minesweep of the field.

Output Format:

   For each data set, output an n by n grid with asterisks
showing the probable location of mines and minus signs as
'safe' locations as implied by the minesweep matrix that
you read in.  Print a blank line after each grid.  If more
than one answer is possible for a given input set, output
any one answer.  There is guaranteed to be at least one
correct solution for any input set.

   PLEASE NOTE: A straight
'generate-all-possible-combinations- and-test' approach
will not likely finish within the 5 minute time limit.

Sample Input:

5
00011
11011
22000
33100
22100
10
0011100111
0011100111
0000111000
0000111000
0000111000
0012210000
0013320011
0013320022
1101110022
1100000011

Sample Output:

----*
-----
*----
*----
-*---

---*----*-
----------
----------
-----*----
----------
----------
---**-----
----*----*
---------*
*---------

   In round 1, Mark was not using a program to count tokens
but used something like the number of characters, so
programs were submitted that were very unreadable.  I tried
to running the winnner of round 1 using C68.  It compiled
fine, but did not run right.  I've included it below for
those that might want take a shot at decyphering this
program.

     Round 1 winner

#define Z(Y,X) if (X & h[2]) \
  do {i=a[f^=g^=1] Y a[g+2]; W(<,c,b) W(>,d,e)} while (
f|g);

#define W(V,U,T) if (f & g | i V U | i==U & !T)
U=1,T=h[f]&h[g+3]&16;

a[4],b,c,d,e,f,g;

char h[5];

main(i,j)
{
   while(gets(j))
   {
      Z(*,sscanf(j,"%c%d,%d%3c%d,%d%c",h,a,a+1,h+1,a+2,
        a+3,h+4))
      Z(+,1)
      Z(-,4)
      printf("%s=%c%d,%d%c\n",j,b ? 91:40,c,d,e ?
         93:41);
   }
}

   I found the round 3 problem to the be most interesting.
My first thought was to try to find a way to solve it
without using the brute force method.  I thought a binary
search might work when I noticed that the answer would tend
to gavitate to the center, but there were cases where the
answer would be at one end (like 1000*1).

   Here is my first attempt the program.

100 INPUT "Enter Number: ";in$
110 LET position = 0
120 LET greatest = 0
130 IF LEN(in$)=0 OR LEN(in$)=1 THEN
140    PRINT "Bad Value"
150    STOP
160 END IF
170 IF LEN(in$) = 2 THEN
180    PRINT in$(1);"*";in$(2)
190   STOP
200 END IF
210 FOR x = 1 TO LEN(in$)-1
220   y = in$(1 TO x)
230   z = in$(x+1 TO )
240   total = y * z
250   IF total > greatest THEN
260      position = x
270      greatest = total
280   END IF
290 END FOR x
300 PRINT in$(1 TO position);"*";in$(position+1 TO )

   By looking at the program, I was able to whittle it down
at bit, but at the sacrifice of neatness and it's
readability.  Here is the second version.

100 INPUT "Enter Number: ";in$
110 position = 0
120 greatest = 0
130 IF LEN(in$)=0 OR LEN(in$)=1 THEN PRINT "Bad Value" : STOP
140 IF LEN(in$) = 2 THEN PRINT in$(1);"*";in$(2): STOP
150 FOR x = 1 TO LEN(in$)-1
160   IF (in$(1 TO x) * in$(x+1 TO )) > greatest THEN
    position = x : greatest = in$(1 TO x) * in$(x+1 TO)
170 END FOR x
180 PRINT in$(1 TO position);"*";in$(position+1 TO )


ANOTHER LOOK AT MAZES

   [In QHJ #12 there was an article on Cellular Automata
that discussed how CA could be used to quickly and easily
solve mazes.  On Usenet I've seen some postings that deal
with other ways to solve mazes (the more "classical"
appoaches).  I thought they would be of interest. - ED]

   >Can anyone gave me suggestions as to algorithms for
   >searching and finding the shortest path through a maze?

   A maze can be thought of as a graph, where the starting
point is the "start vertex" and the destination is the "end
vertex."  Then by modeling the maze as a graph such that a
vertex represents a "decision point" in the maze where more
than one path can be followed, and where the edge represents
the path between two such "decision points," then the
"shortest path" algorithm for a graph will find the shortest
path in the maze.

   _______________
   |S     X      |              S----------X-------X
   |------ |----X|  S = Start             /       /
   |--X ---| __| |  E = End              /       /
   | | |    X    |                      X       /
   | | | --------|                      |      X
   | |  ---- --- |                      |       \
   |__X_____X__|E|                      |        \
                                        X---------X-----E

   We can create a "vertex" at all decision pints ("forks in
the road").  There are marked "X" ni the graph above.  The
edges will exist if there's a direct path between two X's
without crossing another X.  We then have a graph, and when
a "shortest path" algorithm returns the set of vertices (in
order) which have been visited, we can "transform" the
problem back to a maze and find the path selected.  In the
above example, there are clearly two paths that work; the
"shortest" would depend on the length of the edges ( as
represented by a "weight" for each edge.  There are several
"weighted graph shortest edge" algorithms, such as
Dijkstra's algorithm.  Any decent book on algorithms will
give you this algorithm ( and might even discuss a
"maze-to-graph transformation" in more detail.

Tim Irvin J056600@LMSC5.IS.LMSC.LOCKHEED.COM

---------------------------------------------------------

   Breadth First Search.  This requires marking maze cells
as "distance K from entrance", and appending the indices to
these cells to a queue.

   You can, for example, thread the queue through an array
representation of the maze itself: if a cell holds (i,j,k),
then it is distance k, and the next cell on the queue is
cell (i,j).

   BFS is basically this:
      1. mark and put in the queue neighbors of the entrance
cel (distance k = 1).
      2. repeat this step until the queue is empty, or (*):
mark the neighbors of the head of the queue (distance k+1)
and append them to the queue, if they are not already
marked; move the head-of-queue to successor.

(*) the first time the exit cell is marked, it's distance to
the entrance becomes known; a trace-back (k->..->0) can be
done to produce an optimal path.

William Chang (wchang@csh1.org)