Puzzler: Accumulations Syntax
Author Message
Puzzler: Accumulations Syntax

Jim Weigang writes on Sunday, March 31:

Quote:
> Here's the latest puzzle from Gary Bergquist's Zark APL Tutor
> Newsletter.  After the tough challenge last quarter, this one is much
> easier--he's only asking for you to design syntax.  Mail your ideas to
> Gary at the address below and please post them here as well.
> A classic:  Suppose you have two numeric vectors whose elements are in
> one-to-one correspondence.  The first (ACCT) is a vector of account
> numbers; the second (AMT) is a vector of dollar amounts.  The account
> numbers in ACCT are not distinct; they repeat.  What are the distinct
> account numbers?  How many times does each account number occur?  What
> is the sum of the numbers in AMT for each distinct account number?  What
> is the percent of each number in AMT relative to the total for its
> account?
> The efficient APL algorithms for these problems are well known and will
> be discussed in the next issue.  Your task is to DESIGN the syntax of
> one or more utility functions that make the solutions to such problems
> convenient and intuitive.  ...

The key adverb /. is well suited for these tasks.  In x v/. y,
items of x specify keys for corresponding items of y and the verb
v is applied to each collection of y having identical keys.
Key works for any verb v and for any pair of arrays x and y
having a like number of items, whether numeric or literal,
open or boxed, arrays of any rank, independently for x and y.
(Key was discussed recently in this forum in prime factors
cancellation in calculating binomial coefficients, and in
Bernhard Strohmeier's string containment problem.)  Thus:

[ acct=. ?12\$5             NB. random account numbers
0 3 2 2 1 0 3 3 4 1 2 4
[ amt =. 0.1*?12\$2e3       NB. corresponding amounts
6.9 10.6 105.9 134.2 1.5 76.6 13.3 83.4 137.3 117.7 186 169.2

acct {./. acct             NB. distinct account numbers; {. is first
0 3 2 1 4
{./.~ acct                 NB. f~x is x f x
0 3 2 1 4
~. acct                    NB. {./~ is ~.
0 3 2 1 4

#/.~ acct                  NB. # of occurrences of each account number
2 3 3 2 2
({. , #) /.~ acct          NB. account number and # of occurrences
0 2
3 3
2 3
1 2
4 2
({./.~ ,. #/.~) acct
0 2
3 3
2 3
1 2
4 2

acct +//. amt              NB. total amount for each account
83.5 107.3 426.1 119.2 306.5

NB. fraction of an amount in its account

amt % (({./.~acct) i. acct) { acct +//. amt
0.0826347 0.0987884 0.248533 0.31495 0.0125839 0.917365 ...
amt % ((~.acct) i. acct) { acct +//. amt
0.0826347 0.0987884 0.248533 0.31495 0.0125839 0.917365 ...

+-----------+-----------+-----------+-----------+-----------+
|0 0.0826347|1 0.0987884| 2 0.248533|4 0.0125839| 8 0.447961|
|5  0.917365|6  0.123952| 3  0.31495|9  0.987416|11 0.552039|
|           |7   0.77726|10 0.436517|           |           |
+-----------+-----------+-----------+-----------+-----------+

0.0826347 0.0987884 0.248533 0.31495 0.0125839 0.917365 ...

Key is similar to the dyad of the beta adverb in the Connection
Machine (references below), a highly parallel computer, and is
presumbably well supported by the hardware.  Basically, x v beta y is
x v//. y .  Beta is therefore less flexible than key, because the
verb to be applied must be a reduction.

Daniel Hillis, The Connection Machine, MIT Press, 1985;
Section 2.6, Generalized Beta.
Guy Steele & Daniel Hillis, Connection Machine Lisp:
Fine-Grained Parallel Symbolic Processing, Technical Report 86.16,
Thinking Machine Corporation, May 1986; Section 4.3, Reduction
and Combining.

Fri, 18 Sep 1998 03:00:00 GMT
Puzzler: Accumulations Syntax
At one of the APLnn conferences, Sykes presented an entire APL
programming tutorial based upon efficiently coding the accumulation
problem.  Does anyone know if that was ever published in any form?

--

Mathematics & Statistics Dept.            Voice:  413-545-2859 (W)
University of Massachusetts                       413-549-1020 (H)
Amherst, MA 01003                           Fax:  413-545-180

Sun, 20 Sep 1998 03:00:00 GMT
Puzzler: Accumulations Syntax
I saw a puzzle today that I have not seen for a long time.
It is actually quite entertaining. It is relatively easy to
solve but it might give someone a bit of fun over the holidays.

You get 12 balls.
You get a balance scale and are allowed to use it three times.
All 12 balls are the same size and color.
11 of the balls are the same weight.
1 is either heavier or lighter than the rest.
You are supposed to find the oddball and say if it is lighter or
heavier than the rest.

Extra points for a solution using J

--

http://www2.simi.is/~gosi
http://www.jsoftware.com

Sun, 20 Sep 1998 03:00:00 GMT
Puzzler: Accumulations Syntax

Quote:

> I saw a puzzle today that I have not seen for a long time.
> It is actually quite entertaining. It is relatively easy to
> solve but it might give someone a bit of fun over the holidays.

> You get 12 balls.
> You get a balance scale and are allowed to use it three times.
> All 12 balls are the same size and color.
> 11 of the balls are the same weight.
> 1 is either heavier or lighter than the rest.
> You are supposed to find the oddball and say if it is lighter or
> heavier than the rest.

There is a nice solution to this problem. I don't know where I read
it, probably in Scientific American (by Martin Gardner?). It goes like
this:

You label the balls with the characters SILENT COWARD. Then you
weight SCAN against WORD, SCAR against LINE, and SLOT against RAID.
You mark all the heavier words. If two words are in balance you cancel
all the characters of these words from all six words. Then consider
the marked words. If there exists a character which is not canceled and
appears in all the marked words, this character points towards the ball
which is heavier than the others. If there is no such character, then there
exists one character which is canceled in all words which are not marked.
This character corresponds to the ball which is lighter than the others.

There is a way to solve the problem for 1.5 * (3^(n-1)-1) balls in
n trials using the ternary system.

Quote:
> Extra points for a solution using J

Sorry, I don't see the need for code, here.

Bernhard

Sat, 26 Sep 1998 03:00:00 GMT

 Page 1 of 1 [ 4 post ]

Relevant Pages