First some bad news:
s=: ,`(}.@])@.(= -@{:)/
s 1 _1 0
1 _1 0
s=: ,`(}.@])@.(= -@{.)/
s 1 _1 0
0
s 0 1 _1
So our solutions don't work if the accumulator array goes empty before the end.
Fortunately this can be fixed (see below).
Now some good news:
s=: ,`(}.@])@.(0:`(= -@{.)@.(*@#@]))/
s=: , `(}.@])@.(0:`(= -@{.)@.(*@#@]))/
d=: ,~`(}:@])@.(0:`(= -@{:)@.(*@#@]))/@|.
k=: 1 _1 2 _2 {~ 100 ?.@# 4
s 1 _1 0
0
s 0 1 _1
0
s k
2 1 2 1 _2 _1 2 1 1 2 2 2 _1 2 _1 2 1 2 2 2 1 1 _2 _1 2 1 _2 _1 _2 _2 _2 _2 _1
_2 _1 _1 _2 _2 1 1 1 2 1 _2 1 _2 _1 _1 _1 2
d k
2 1 2 1 _2 _1 2 1 1 2 2 2 _1 2 _1 2 1 2 2 2 1 1 _2 _1 2 1 _2 _1 _2 _2 _2 _2 _1
_2 _1 _1 _2 _2 1 1 1 2 1 _2 1 _2 _1 _1 _1 2
K1=: 1 _1 2 _2 {~ 10000 ?.@# 4
K2=: 1 _1 2 _2 {~ 100000 ?.@# 4
timespacex 'd K1'
0.006343 233024
timespacex 'd K2'
0.055919 1.83866e6
Linear as it should be.
Moral: Always append to the end of arrays.
Or: We aren't using linked lists!
Cheers,
Louis
----Original Message----
From : [email protected]
Date : 07/12/2019 - 12:33 (CEST)
To : [email protected]
Subject : Re: [Jprogramming] Removing annihilating pairs
Forcrand's solution is more or less the version I came up with, unfortunately,
it's far from linear (what is not compensated by its elegance).
foo=: ,`(}.@])@.(0=(+{.))/
ts'foo 1 _1 2 _2{~10000?.@#4'
0.0166915 854720
ts'foo 1 _1 2 _2{~100000?.@#4'
1.9109807 6818496
Miller's solution is better in that respect (and much faster)
ts'an2 1 _1 2 _2{~10000?.@#4'
0.0024111 722816
ts'an2 1 _1 2 _2{~100000?.@#4'
0.0281419 6293376
ddup from Rich also seems to be linear but is a factor 10 slower than an2
ts'ddup 1 _1 2 _2{~10000?.@#4'
0.0219618 395264
ts'ddup 1 _1 2 _2{~100000?.@#4'
0.2124874 3147776
Jasmin's solution is far too slow
ts'(delitemG~ 2, 0 i.~ 2&(+/\))(^:_) 1 _1 2 _2{~10000?.@#4'
1.2363434 1585408
Thanks for all the contributions
R.E. Boss
> -----Oorspronkelijk bericht-----
> Van: Programming <[email protected]>
> Namens Louis de Forcrand
> Verzonden: zaterdag 7 december 2019 00:26
> Aan: [email protected]
> Onderwerp: Re: [Jprogramming] Removing annihilating pairs
>
> Not particularly J-ish, but (array-shuffling aside) linear solution:
>
> s=: ,`(1}.])@.(= -@{.)/
> s 1 _1 2 _2{~100?.@#4
> 2 1 2 1 _2 _1 2 1 1 2 2 2 _1 2 _1 2 1 2 2 2 1 1 _2 _1 2 1 _2 _1 _2 _2 _2 _2
> _1 _2 _1
> _1 _2 _2 1 1 1 2 1 _2 1 _2 _1 _1 _1 2
>
> Since the reduced form of the input list is unique, we are free to perform
> reductions in any order we please; in particular, we can start simplifying
> from
> the back, which is what s does.
> Might do strange stuff on an empty input list.
>
> Cheers,
> Louis
>
> ----Original Message----
> From : [email protected]
> Date : 06/12/2019 - 23:51 (CEST)
> To : [email protected]
> Subject : Re: [Jprogramming] Removing annihilating pairs
>
> If the answer to Jimmy's question is no, then the uniqueness of the resulting
> array has to do (surprisingly) with free groups
> (https://en.wikipedia.org/wiki/Free_group).
> Indeed we can view a vector of numbers as a word over the alphabet [0,∞)
> of positive real numbers (where negative numbers / zero are inverses of
> letters in our alphabet). The fact that all maximal reductions (reductions
> which contain no adjacent inverses) of a given word are equal means exactly
> that our reduced list is unique.
> For a proof see:
> https://math.stackexchange.com/a/2425147
>
> I'll look into this problem, it's interesting!
> Cheers,
> Louis
>
> ----Original Message----
> From : [email protected]
> Date : 06/12/2019 - 23:36 (CEST)
> To : [email protected]
> Subject : Re: [Jprogramming] Removing annihilating pairs
>
> Hi,
>
> is the expected output of transforming 1 3 _3 3 5 to be 1 3 5 or 1 5 ?
>
> On Fri, Dec 6, 2019 at 7:15 AM R.E. Boss <[email protected]> wrote:
>
> > Given an array with zero or more annihilating pairs, i.e., two
> > subsequent numbers which add up to zero, the question is to clean up
> > the array by deleting all annihilating pairs such that no such pairs are
> > left.
> > I do have a solution that is both elegant and efficient (I believe),
> > but I am curious about other thoughts.
> >
> > foo 2 1 1 _1 2 _2 _1
> > 2
> >
> > foo 1 _1 2 _2{~100?.@#4 NB. Notice (?.)
> > 2 1 2 1 _2 _1 2 1 1 2 2 2 _1 2 _1 2 1 2 2 2 1 1 _2 _1 2 1 _2 _1 _2 _2
> > _2
> > _2 _1 _2 _1 _1 _2 _2 1 1 1 2 1 _2 1 _2 _1 _1 _1 2
> >
> >
> > R.E. Boss
> > ----------------------------------------------------------------------
> > For information about J forums see
> http://www.jsoftware.com/forums.htm
> >
> ----------------------------------------------------------------------
> For information about J forums see http://www.jsoftware.com/forums.htm
>
> ----------------------------------------------------------------------
> For information about J forums see http://www.jsoftware.com/forums.htm
>
> ----------------------------------------------------------------------
> For information about J forums see http://www.jsoftware.com/forums.htm
----------------------------------------------------------------------
For information about J forums see http://www.jsoftware.com/forums.htm
----------------------------------------------------------------------
For information about J forums see http://www.jsoftware.com/forums.htm
