NYCJUG/2006-04-11
Discussed shell, OpenGL, Traveling Salesman, learning J.
Agenda
1. Beginner's regatta: final update to "wait for external command": shell.
1. Show-and-tell: Using key.
Can Tom tell us about openGL?
1. Advanced topics: the Traveling Salesman Problem.
Suggestions for a new group project?
1. Learning and teaching J: quotesWin example or Mastermind?
Why the wacky suggestions? E.G. spaces to change precedence, writing code right-to-left.
Proceedings
This meeting meandered even more than usual so we only touched on a couple of agenda items. The first item on the agenda was the wrap up of invoking an external command (i.e. a DOS command) from within J but waiting for it to finish before proceeding. The shell function in the task.ijs script seemed to fill the bill better than any of the previous methods. It's easy to use and seemed to give the most stable timings. This discussion somehow mutated to one on the differences between American pari-mutual betting and the British system, involving "tic-tac" men and bookmakers. (See Waiting for Shell Command to Finish.doc)
On an advanced topic, we talked a little about the Traveling Salesman Problem and the start of a solution adapted from APL code originally written by Gerard Langlet. For those not familiar with this problem, in brief, given a set of points, say in 2-D, draw a line connecting the points, passing through each one only once, that is the shortest possible such path.
There are variants and ramifications but this is the simplest kernel of the problem. (See File:TSP.ijs.)
In his APL talk, Langlet claimed that at one time he may have had the most efficient algorithm. Another interesting claim that came out of his talk (I recall) at that long-ago conference was in response to a question from the audience. Langlet had been making statements to the effect that such and such a solution was some percentage of the optimal one when someone asked, since the search space for the complete solution of the problem grows so large so quickly, how Langlet knew "the optimal" solution.
Langlet responded that the optimal solutions were arrived at visually, that is, by looking at the points and manually plotting the solution. If true, this makes the problem even more intriguing since it seems trivially simple to solve small problems but the general solution for arbitrarily large problems may be practically impossible, at least to reach the single most optimal solution.
The example I'd brought was only the first part of Langlet's algorithm:
it constructs an initial, reasonably good path as a starting point for a better solution reached by improving the initial one. For the small sample of points I'd generated, the solution looked fairly good. However, at some point, I tried sketching a solution and it looks better than than the initial one; by a rough measure, my "eyeball" solution is about 25% shorter than the computer-generated initial solution. I'll have to complete converting Langlet's code to see how the complete algorithm fares.
(See 
.)
One member of our group, John, had brought a paper discussing a simulated annealing approach to the problem. We talked about how solutions to this problem often forgo complete optimality to concentrate on a "good enough in a sufficiently short time" solution.
We discussed HenryRich's File:JRefCardv601 20060413.pdf while on the topic of learning and teaching J. We agreed that, while some people seem to like this very dense presentation, it lacks a clear structure. In many ways, the original J vocabulary sheet is better organized though it serves more as a starting point that isn't nearly ambitious as Rich's J reference.
On this topic, where we touched on why modern textbooks are far too large and how the importance of teaching is in selecting and organizing the relevant pieces of a large body of material, we got into a discussion about how the J forum seems to attract more than its fair share of, shall we say, wildly innovative contributors. Even in our small group of NYC JUG, we see a divergence between people looking at simple, practical problems and those fascinated by the deeper, abstract structures of the language. However, the interplay between these perspectives is often fruitful.
Our final topic of the evening was an implementation of "Manhattan address arithmetic": often one is given a building address in terms of a "house number" and an avenue. However, what one needs to know is the cross street near the address. There is often a page in the phone book with a non-trivial, though not complex, formula for approximating this. I implemented this in J with a vector of different arrays ranging from scalar integers to matrixes including complex numbers. The actual code is fairly simple once the somewhat complex data structure has been defined. (See File:AddressArithmetic.ijs.)