Puzzle
Author Message
Puzzle

x is a list of length >1 of distinct integers;
y is a list of equal length of distinct integers;
find a permutation y1 of y such that x=y1 is all 0.

Tue, 10 Apr 2001 03:00:00 GMT
Puzzle

Quote:

>x is a list of length >1 of distinct integers;
>y is a list of equal length of distinct integers;
>find a permutation y1 of y such that x=y1 is all 0.

diffperm =: 4 : 0
NB. Get indexes of equal elements, plus one more (if it exists)
NB. which must be non-equal to all the equal ones

NB. Rotate those elements one position, to remove all matches

)
+./ (80 ? 100) ([ = diffperm) (80 ? 100)
0

Implicit form:

Henry Rich

Tue, 10 Apr 2001 03:00:00 GMT
Puzzle
Roger,

Is there an application problem behind this puzzle or is it just an
intellectual exercise?  I'd be interested in knowing a practical
application for this tidbit.

Thanks.

Tue, 10 Apr 2001 03:00:00 GMT
Puzzle
Roger Hui wrote on Oct 23:

Quote:
> x is a list of length >1 of distinct integers;
> y is a list of equal length of distinct integers;
> find a permutation y1 of y such that x=y1 is all 0.

S{<-}Y
Y1{<-}1{rotate}S

The trick is to arrange Y so elements that occur in X are in the same
locations as in X, and disjoint elements are in the remaining locations.
Then shift by one to ensure a mismatch.

I like the middle line: grade up and down, membership, iota, indexed
assignment and reference.  What a loaded seesaw of fundamental
operations!

If you'd rather avoid indexed assignment, you could write it as:

Jim

Tue, 10 Apr 2001 03:00:00 GMT
Puzzle

Quote:

>x is a list of length >1 of distinct integers;
>y is a list of equal length of distinct integers;
>find a permutation y1 of y such that x=y1 is all 0.

y1 <is> ((x=y)\1<rotatet>(x=y)/y)+(x <unequal> y)<times>y

Tue, 10 Apr 2001 03:00:00 GMT
Puzzle

Quote:

> x is a list of length >1 of distinct integers;
> y is a list of equal length of distinct integers;
> find a permutation y1 of y such that x=y1 is all 0.

y1=.  y A.~ 0 i.~ +./x=|:(i.!#y)A. y

One trusts the J interpreter has the sense not to try to build the
entire matrix
(i.!#y)A. y
...
-j

ps -- I could have used +./"1 instead of transposing, but then I'd have
a
"function argument to an operator" and God knows how many times
J would have applied it to each cell ...   :^)

Wed, 11 Apr 2001 03:00:00 GMT
Puzzle

Quote:

> >x is a list of length >1 of distinct integers;
> >y is a list of equal length of distinct integers;
> >find a permutation y1 of y such that x=y1 is all 0.

> y1 <is> ((x=y)\1<rotatet>(x=y)/y)+(x <unequal> y)<times>y

Unfortunately the above doesn't work when there is only a single match.
What has to be done is to select a minimum of two positions for the
rotate.

--

Wed, 11 Apr 2001 03:00:00 GMT
Puzzle

Quote:

>> x is a list of length >1 of distinct integers;
>> y is a list of equal length of distinct integers;
>> find a permutation y1 of y such that x=y1 is all 0.

> y1=.  y A.~ 0 i.~ +./x=|:(i.!#y)A. y

>One trusts the J interpreter has the sense not to try to build the
>entire matrix
>(i.!#y)A. y

Better check that before you put it into production...

x =. i. 8
y =. i. 8
7!:2 'y1=.  y A.~ 0 i.~ +./x=|:(i.!#y)A. y'
16640896

Henry Rich

Wed, 11 Apr 2001 03:00:00 GMT
Puzzle

Quote:
> x is a list of length >1 of distinct integers;
> y is a list of equal length of distinct integers;
> find a permutation y1 of y such that x=y1 is all 0.

==========================================================

NB. 3 Solutions to Roger's Puzzle
NB. 1.) UnMatchC using C.          (tacit)
NB. 2.) UnMatch using (v0`v1`v2)}  (tacit)
NB. 3.) P using { } and if.        (explicit)
NB. timings: on my machine is p twice as slow as 1.) and 2.)

NB. === 1.) UnMatchC using C.          (tacit) =================

UnMatchC=: UnMatchC f.

UnMatchC
5 6 7 UnMatchC 2 3 4
5 6 7 UnMatchC 5 3 4
5 6 7 UnMatchC 5 6 7

NB. === 2.) UnMatch using (v0`v1`v2)}  (tacit) =================
Rot=: 1&|.

Amed=: (Vals`[`])}
Inxs=: ] (Min2Inxs BX) =

UnMatch=: Inxs Amed ]
UnMatch=: UnMatch f.

NB. === 3.) P using { } and if.        (explicit) ===============
b=.x. = y1=.y.
if. 1 e. b do.
inx=. BX b
if. 1=#inx do.
inx=.inx,BX 1|.b
end.
y1 =. (1|.inx{y.) inx}y.
end.
y1
)

==========
JoHo

Thu, 12 Apr 2001 02:00:00 GMT
Puzzle

Quote:

> ...
> >One trusts the J interpreter has the sense not to try to build the
> >entire matrix
> >(i.!#y)A. y

> Better check that before you put it into production...

>    x =. i. 8
>    y =. i. 8
>    7!:2 'y1=.  y A.~ 0 i.~ +./x=|:(i.!#y)A. y'
> 16640896

> Henry Rich

I was being slightly facetious there (o,-)

In fact, though, this is a problem (like many real-world ones) where a
random
search is fairly efficient (the worst case, when x and y are identical,
solutions
are still something like 1 out of n (length of x or y) in the space).
So if there
were some function like dyadic i. that instead were defined to search
randomly,
and the interpreter was smart enough to jam the loops appropriately, it
would
actually be a usable algorithm.

Isn't that the whole point?  To have a language where one can state a
problem
formally but succinctly, and have the system do the dirty work?

-j

Thu, 12 Apr 2001 02:00:00 GMT

 Page 1 of 2 [ 27 post ] Go to page: [1] [2]

Relevant Pages