Anagram Assist and TopDown vs. BottomUp 
Author Message
 Anagram Assist and TopDown vs. BottomUp

To hopefully restate this problem:

Given:
     X is a list of items; Y is the items one wants to remove from X,
treating multiple occurences of the same item in X as different items.
(That is, if you have three e's in X, and you remove one e, you will be
left with two e's)

Two approaches seem equally workable:
1) Generalize the idea of "less" (-. in J, or ~ in APL). This problem can
almost be solved by less, except that it removes all occurences of the same
item at once. If we could make each duplicate item look unique for a
moment, THEN apply the less verb, and then return to normal, then
ProblemSolved.
      NB.  let "augment" be the verb that makes each item unique.
      NB.  let "deaugment" be the verb that returns everything to normal.
           answer =. deaugment (augment X) -. (augment Y)
      NB. or to use J stuff:

      NB. I'd have liked to use:
      NB.  answerverb =. -.&.(augment:.deaugment),
      NB.  but :. gives spelling error in JWin 6.2...

The top-down idea came in two steps: First, see what "almost" solves the
problem; and second, see what we could do before, and what we could do
after "almost" solving the problem.

How to make the items unique? Make the list some sort of ordinal (the first
A, the 5th  e...)
i.e.    'cool' ->  'c 1' 'o 1' 'o 2' 'l 1'

How to get them back? Take the head of each item.

In short;


----
The second approach is the "finite state" idea, which was also discussed. I
had this thought: if you had a finite state machine, and the verb "FSM"
worked as follows:
      nextstate =. state FSM transition
you could take the initial state, all the transitions, line them up, and do
some sort of reduction (or in the j'ese, Insert) and get the final state.

Well, it turns out that
      finalstate =. FSM~/ |. state0,transitionlist
works. There are some games to be played in this case: box X to get state0,
and box each letter in Y to get transitionlist. but the finite state idea
works.

When I read the comment about "J being a bottom-up language" I thought,
yes, and no, depending on what part you look at. There does seem to be a
division in the language in that when you are looking a whole problems you
think in terms of the adverbs and conjunctions, and when you look at pieces
of problems, you think in terms of verbs.

So (Top Down J = Adverbs/conjunctions; Bottom up J = verbs)

---------------------------------------------------------------------
|\/|                         |
|\\| Randy A MacDonald ..... | "You just ASK them?"  R.P. Feynmann
---------------------------------------------------------------------



Mon, 25 Mar 1996 12:29:08 GMT  
 Anagram Assist and TopDown vs. BottomUp
         NB.  answerverb =. -.&.(augment:.deaugment),
         NB.  but :. gives spelling error in JWin 6.2...
try           answerverb =. -.&.(augment :.deaugment)

By the way, good ideas.

Raul D. Miller



Tue, 26 Mar 1996 05:07:10 GMT  
 
 [ 2 post ] 

 Relevant Pages 

1. Assist me with ASSIST info

2. ANNOUNCE: VisualAge Usability Assist Tool - VA Assist - Free Trial

3. Topdown design

4. Fwd: re: Puzzler: Permutations and Anagrams

5. Puzzler: Permutations and Anagrams

6. Puzzler: Permutations and Anagrams

7. Puzzler: Permutations and Anagrams

8. anagram

9. speedup of anagram finder

10. speedup of anagram finder

11. Anagrams in Prolog

12. Anagram

 

 
Powered by phpBB® Forum Software