Puzzler: Converting numbers
Author Message
Puzzler: Converting numbers

Hello,
who can solve the following problem without using
each or loop or outer-product?

We want to convert a natural number into its "Excel"-representation.
That is: a natural number is converted into a string which consists of
the alphabet 'ABCDEFGHIJKLMNOPQRSTUVWXYZ ' only.
For example      1 -> A
...
26 -> Z
27 -> AA
28 -> AB
...
52 -> AZ
53 -> BA
...

and so on. The function/expression should be able to handle
arbitrary alphabets and numeric vectors as its arguments.
I found a looping solution only ;-( IMHO this is not easy, right?

Best,
Bernhard Strohmeier

Sat, 10 Oct 1998 03:00:00 GMT
Puzzler: Converting numbers
Bernhard Strohmeier:
We want to convert a natural number into its
"Excel"-representation.  That is: a natural number is converted
into a string which consists of the alphabet
'ABCDEFGHIJKLMNOPQRSTUVWXYZ ' only.  For example 1 -> A ...  26 ->
Z 27 -> AA 28 -> AB ...  52 -> AZ 53 -> BA ...

Well...

One thing to note is that if
alpha=. ' ABCDEFGHIJKLMNOPQRSTUVWXYZ'
then
26 #. alpha i. x
does the right thing to convert from excel representation back to
numbers.  But note that alpha has 27 elements, and indices into alpha
are being treated base 26.  So, this is some kind of "off-by-one"
problem.

Now, if we try the "obvious,"
(26 26 #: n) { alpha
the problem is that anything over 26 isn't quite handled right.  The
problem (again) is this "off-by-one" problem.

This problem is a bit messy to generalize without addressing the issue
of the number of digits of precision for the result.  I could get
fancy and allow arbitrary precision, but I'm going to arbitrarily say
that "excel representation" only goes to three character symbols.
This yields an expression like:

(0 0 1 + 26 26 26 #: n-1) { alpha

The equivalent vs-apl expression would be:

alpha[0 0 1 + 26 26 26 {represent} n-1]

Of course, you can generalize this in a variety of directions.

--
Raul

Sat, 10 Oct 1998 03:00:00 GMT
Puzzler: Converting numbers

Quote:

> Bernhard Strohmeier:
>    We want to convert a natural number into its
>    "Excel"-representation.  That is: a natural number is converted
>    into a string which consists of the alphabet
>    'ABCDEFGHIJKLMNOPQRSTUVWXYZ ' only.  For example 1 -> A ...  26 ->
>    Z 27 -> AA 28 -> AB ...  52 -> AZ 53 -> BA ...

> Well...

> One thing to note is that if
>  alpha=. ' ABCDEFGHIJKLMNOPQRSTUVWXYZ'
> then
>  26 #. alpha i. x
> does the right thing to convert from excel representation back to
> numbers.  But note that alpha has 27 elements, and indices into alpha
> are being treated base 26.  So, this is some kind of "off-by-one"
> problem.

> Now, if we try the "obvious,"
>  (26 26 #: n) { alpha
> the problem is that anything over 26 isn't quite handled right.  The
> problem (again) is this "off-by-one" problem.

> This problem is a bit messy to generalize without addressing the issue
> of the number of digits of precision for the result.  I could get
> fancy and allow arbitrary precision, but I'm going to arbitrarily say
> that "excel representation" only goes to three character symbols.
> This yields an expression like:

>    (0 0 1 + 26 26 26 #: n-1) { alpha

> The equivalent vs-apl expression would be:

>    alpha[0 0 1 + 26 26 26 {represent} n-1]

> Of course, you can generalize this in a variety of directions.

> --
> Raul

I tried
(0 0 1 + 26 26 26 #: 676) { alpha
a a

Not correct, sorry.
Bernhard

Sun, 11 Oct 1998 03:00:00 GMT
Puzzler: Converting numbers

Bernhard Strohmeier writes on Tuesday, April 23:

Quote:
> We want to convert a natural number into its "Excel"-representation.
> That is: a natural number is converted into a string which consists of
> the alphabet 'ABCDEFGHIJKLMNOPQRSTUVWXYZ ' only.
> For example      1 -> A
>                  ...
>                 26 -> Z
>                 27 -> AA
>                 28 -> AB
>                  ...
>                 52 -> AZ
>                 53 -> BA
>                  ...

> and so on. The function/expression should be able to handle
> arbitrary alphabets and numeric vectors as its arguments.
> I found a looping solution only ;-( IMHO this is not easy, right?

I believe both the solution by Raul Miller and the one by
R.G. Selfridge are incorrect, as the problem is different from
the ordinary base value and representation.  Consider the case
where the alphabet is 'ab':

Excel-2     base-2
1-origin    0-origin
1 a        0  0
2 b        1  1
3 aa       2  10
4 ab       3  11
5 ba       4  100
6 bb       5  101
7 aaa      6  110
8 aab      7  111
9 aba      8  1000
10 abb      9  1001
11 baa     10  1010
12 bab     11  1011
13 bba     12  1100
14 bbb     13  1101

That is, there is a difference more fundamental than the
difference between 0-origin and 1-origin:  in base-n notation,
k or fewer digits represent n^k values; in Excel-n notation,
k or fewer digits represent +/n^1+i.k values.

alp   =: 'abcdefghijklmnopqrstuvwxyz'
n     =: # alp

rep   =: (nd \$ n"_) #: ] - nd { breaks

(":,.i) ,. ' ',. conv i=: }. ,(+/\ 26^/0 1 2 3 4)+/_1 0 1
1 a
2 b
26 z
27 aa
28 ab
702 zz
703 aaa
704 aab
18278 zzz
18279 aaaa
18280 aaab
475254 zzzz
475255 aaaaa
475256 aaaab

Sun, 11 Oct 1998 03:00:00 GMT
Puzzler: Converting numbers
Roger Hui writes on Wednesday, April 24:

Quote:
> alp   =: 'abcdefghijklmnopqrstuvwxyz'
> n     =: # alp

> rep   =: (nd \$ n"_) #: ] - nd { breaks

The number of elements required for "breaks" is rather limited,
so one might precompute it for a given alphabet.  Thus:

alp   =: 'abcdefghijklmnopqrstuvwxyz'
n     =: # alp

rep   =: (nd \$ n"_) #: ] - nd { breaks"_

Sun, 11 Oct 1998 03:00:00 GMT
Puzzler: Converting numbers
Bernhard Strohmeier:
I tried
(0 0 1 + 26 26 26 #: 676) { alpha
a a

think of it before.

The problem, essentially, is that most of the time you want base 26,
however the first time you run into a digit, you want base 27.

A-Z constitutes one (base 26) range
AA-ZZ constitutes another (base 26) range
AAA-ZZZ constitutes third (base 26) range,
etc.

These correspond to the decimal numeric ranges:
1-26, 27-702, 703-18278, etc.

However, technically, 0 can be considered part of that first range, so
it's 0-26.  [In all the other ranges, the number which would
correspond to zero falls in the previous range.]

An expression bounding each of these ranges at the low end would be:
lowbound =. (}: |. +/\  26 ^ i. 8), 0
or
lowbound=. 8353082582 321272406 12356630 475254 18278 702 26 0

[Note, the 8 is an explicit encoding of the idea that 8 digits is
adequate for expressing any 32 bit integer.  You can change it to suit

Given this definition of these ranges, the result you're looking for is:
alpha=. 'ABCDEFGHIJKLMNOPQRSTUVWXYZ '
alpha {~ 27 | (26 * n </ lowbound) + ((#lowbound)#26) #: n

You can simplify slightly to:
alpha {~ (- n </ lowbound) + ((#lowbound)#26) #: n

--
Raul

Sun, 11 Oct 1998 03:00:00 GMT
Puzzler: Converting numbers

Quote:

> lowbound=. 8353082582 321272406 12356630 475254 18278 702 26 0
> alpha=. 'ABCDEFGHIJKLMNOPQRSTUVWXYZ '
> alpha {~ 27 | (26 * n </ lowbound) + ((#lowbound)#26) #: n
> alpha {~ (- n </ lowbound) + ((#lowbound)#26) #: n

Let's try this one:

alpha {~ (- n </ lowbound) + ((#lowbound)#26) #: n =: 26 27
AA
BB

Looks wrong because if 26 is AA then 27 should be AB. The only
solution which seems to be correct up to now is (of course) from Roger
Hui. Unfortunately, I don't know enough J -- although from time to
time I make attempts to learn it -- to tell wether his code is without
loops or inner products.

Bernhard

Tue, 13 Oct 1998 03:00:00 GMT
Puzzler: Converting numbers

Ok, Rocky, this time for sure...

It's easy to prove that this doesn't require looping.  I'm in the
middle of some more important projects, so I'm not going to try for
elegance on this.  Here's a brute force solution:

breaks=. +/\ 0, }. 26 ^ i. 8
ABC=.'ABCDEFGHIJKLMNOPQRSTUVWXYZ'

breaks
0 26 702 18278 475254 1.23566e7 3.21272e8 8.35308e9
excel 1 2 3 24 25 26 27 28 700 701 702 703 704 18277 18278 18279

I'll let someone else worry about simplifying 'excel'

--
Raul

Tue, 13 Oct 1998 03:00:00 GMT

 Page 1 of 1 [ 8 post ]

Relevant Pages