Programming challenge: wildcard exclusion in cartesian products

[Geoffrey Summerhayes]

Re: Programming challenge: wildcard exclusion in cartesian products


"Dinko Tenev" <dinko.tenev@gm ail.com> wrote in message
news:1142612170 .404220.23410@e 56g2000cwe.goog legroups.com...[color=blue]
> wkehowski@cox.n et wrote:[color=green]
>> It would seem that your program is just filtering the full cartesian
>> product, right? The solution I'm looking for generates the elements
>> one-by-one so that it could be used in a loop.[/color]
>
> Oops...missed that part.
>
> It took me a while to study the exchange on this topic more thoroughly,
> and I now fully appreciate the fact that the problem calls for a much
> more sophisticated approach.
>
> Sorry for the hasty shot, I'll give it another shortly.[/color]

I wouldn't worry about it, Prolog generated the elements one-by-one.
The loop was the print,nl,fail line. Just beefing it up a bit, I
didn't take the time to clean it up though. :-)

gen(_,0,[]).
gen(S,N,[H|T]):- N > 0, N1 is N - 1, member(H,S), gen(S,N1,T).

filter([],[]).
filter([X|T],[X|T1]):- filter(T,T1).
filter([*|T],L):- filter(T,L).
filter([*|T],[_|T1]):- filter([*|T],T1).

filter_list(L,[[and|T]|_]):- filter_and(L,T) , !.
filter_list(L,[[or|T]|_]):- filter_list(L,T ), !.
filter_list(L,[H|_]):- H \= [and|_], H \= [or|_], filter(H,L),!.
filter_list(L,[H|T]):- H \= [and|_], H \= [or|_], filter_list(L,T ).

filter_and(_,[]) :- !.
filter_and(L,[H|T]):- filter_list(L,[H]), filter_and(L,T) .

generate_member (X,S,N,[]):-gen(S,N,X).
generate_member (X,S,N,[H|T]):-gen(S,N,X),\+ filter_list(X,[H|T]).

1 ?- generate_member (X,[a,b],3,[[a,*,b],[b,*,a]]).

X = [a, a, a] ;

X = [a, b, a] ;

X = [b, a, b] ;

X = [b, b, b] ;

No
2 ?- generate_member (X,[1,2],3,[[and, [*,2], [or, [2,1,*], [1,2,*]]]]).

X = [1, 1, 1] ;

X = [1, 1, 2] ;

X = [1, 2, 1] ;

X = [2, 1, 1] ;

X = [2, 2, 1] ;

X = [2, 2, 2] ;

No

---
Geoff

[Pascal Bourguignon]

Re: Programming challenge: wildcard exclusion in cartesian products

Mark Carter <me@privacy.net > writes:
[color=blue]
> I'd like to propose a coding challenge of my own. The challenge is to
> reproduce the TEA (Tiny Encryption Algorith):
> http://www.simonshepherd.supanet.com/tea.htm
> in your language of choice.
>
> Here's the code, just two simple functions:
>
> void encipher(unsign ed long *const v,unsigned long *const w,
> const unsigned long *const k)
> {
> register unsigned long y=v[0],z=v[1],sum=0,delta=0x 9E3779B9,
> a=k[0],b=k[1],c=k[2],d=k[3],n=32;
>
> while(n-->0)
> {
> sum += delta;
> y += (z << 4)+a ^ z+sum ^ (z >> 5)+b;
> z += (y << 4)+c ^ y+sum ^ (y >> 5)+d;
> }
>
> w[0]=y; w[1]=z;
> }
>
> void decipher(unsign ed long *const v,unsigned long *const w,
> const unsigned long *const k)
> {
> register unsigned long y=v[0],z=v[1],sum=0xC6EF3720 ,
> delta=0x9E3779B 9,a=k[0],b=k[1],
> c=k[2],d=k[3],n=32;
>
> /* sum = delta<<5, in general sum = delta * n */
>
> while(n-->0)
> {
> z -= (y << 4)+c ^ y+sum ^ (y >> 5)+d;
> y -= (z << 4)+a ^ z+sum ^ (z >> 5)+b;
> sum -= delta;
> }
>
> w[0]=y; w[1]=z;
> }[/color]

I get it shorter than in C:

(defun op (x a b sum) (logxor (+ (ash x 4) a) (+ x sum) (+ (ash x -5) b)))
(declaim (inline op))
(defmacro ciploop ((v w k y z a b c d (sum init-sum) delta) &body body)
`(let ((,y (aref ,v 0)) (,z (aref ,v 1)) (,sum ,init-sum) (,delta #x9E3779B9)
(,a (aref ,k 0)) (,b (aref ,k 1)) (,c (aref ,k 2)) (,d (aref ,k 3)))
(loop repeat 32 do ,@body finally (setf (aref ,w 0) ,y (aref ,w 1) ,z))))
(defmacro c-incf (var expr) `(setf ,var (mod (+ ,var ,expr) #x100000000)))
(defmacro c-decf (var expr) `(setf ,var (mod (- ,var ,expr) #x100000000)))
(defun encipher (v w k)
(ciploop (v w k y z a b c d (sum 0) delta)
(c-incf sum delta) (c-incf y (op z a b sum)) (c-incf z (op y c d sum))))
(defun decipher (v w k)
(ciploop (v w k y z a b c d (sum #xC6EF3720) delta)
(c-decf z (op y c d sum)) (c-decf y (op z a b sum)) (c-decf sum delta)))


You can also easily modify it to implement the improved version of TEA...
Note that this Lisp programs will work equally well on a 16-bit,
32-bit or 64-bit Common Lisp implementation. The same cannot be said
of the C program above.



;; Let's add a testbed:

(defun word (a b c d)
(dpb a (byte 8 24) (dpb b (byte 8 16) (dpb c (byte 8 8) d))))

(defun read-words (bits what)
(loop
for bytes = (progn (format *query-io* "Please enter ~D bits of ~A: "
bits what)
(ext:convert-string-to-bytes
(read-line *query-io* nil nil) ext:*TERMINAL-ENCODING*))
while (< (* 8 (length bytes)) bits)
finally (return
(loop for i from 0 by 4 below (truncate (+ 7 bits) 8)
collect (word (aref bytes (+ i 0))
(aref bytes (+ i 1))
(aref bytes (+ i 2))
(aref bytes (+ i 3))) into words
finally (return (coerce words 'vector))))))

(defun test ()
(loop
with code = (vector 0 0)
with decr = (vector 0 0)
for clear = (read-words 64 "clear text")
for key = (read-words 128 "key")
do (progn (encipher clear code key)
(format t "(encipher ~S ~S)~% --> ~S~%" clear key code)
(decipher code decr key)
(format t "(decipher ~S ~S)~% --> ~S~%" code key decr)
(unless (equalp clear decr) (format t "!!! ERROR !!!~%")))))


[11]> (test)
Please enter 64 bits of clear text: Hello World!
Please enter 128 bits of key: John McCarthy invented LISP.
(encipher #(1214606444 1864390511) #(1248815214 541942595 1634890856 2032167278))
--> #(913593965 183139965)
(decipher #(913593965 183139965) #(1248815214 541942595 1634890856 2032167278))
--> #(1214606444 1864390511)
Please enter 64 bits of clear text: Big Secret: LISP!
Please enter 128 bits of key: A very very secure key.
(encipher #(1114203936 1399153522) #(1092646501 1920540790 1702000928 1936024437))
--> #(3198111104 1851109064)
(decipher #(3198111104 1851109064) #(1092646501 1920540790 1702000928 1936024437))
--> #(1114203936 1399153522)
Please enter 64 bits of clear text: ^C





--
__Pascal Bourguignon__ http://www.informatimago.com/

ATTENTION: Despite any other listing of product contents found
herein, the consumer is advised that, in actuality, this product
consists of 99.9999999999% empty space.

[joswig@corporate-world.lisp.de]

Re: Programming challenge: wildcard exclusion in cartesian products

> I had a crack at it in Lisp. My version doesn't work - but of greater[color=blue]
> concern to me is that it doesn't appear nearly as compact as the C
> version. Anyway, here's my Lisp code (no prizes for guessing that I'm a
> noob to Lisp):[/color]

Lot's of things you can write more compact.
But compact is not always the best way to
write source. For me the most important
criteria is that I can return to some source
after, say, a year absence and everything
is clear and readable again.
[color=blue]
>
> (defconstant delta 2654435769 ) ; delta= 0x9E3779B9[/color]

(defconstant +delta+ #x9E3779B9)
[color=blue]
> (defun floorn (n) (nth-value 0 (floor n)))[/color]

is above used?
[color=blue]
> (defun >> (val num-bytes)
> "Right-shift positive integer val by num-bytes"
> (let* (t1 t2)
> (setf t1 (expt 2 num-bytes))
> (setf t2 (/ val t1))
> (floor t2)))[/color]

(defun >> (val num-bytes)
"Right-shift positive integer val by num-bytes"
(floor (/ val (expt 2 num-bytes))))
[color=blue]
> (defun transform (v1 v2 v3 v4)
> (let (t1 t2 t3)
> (setf t1 (<<4 v1))
> (setf t2 (expt v2 v1))
> (setf t3 (expt v3 (>> v2 5)))
> (+ t1 t2 t3 v4)))
>[/color]

(defun transform (v1 v2 v3 v4)
(+ (<<4 v1)
(expt v2 v1)
(expt v3 (>> v2 5))
v4))

and so on...

[Alexander Schmolck]

Re: Programming challenge: wildcard exclusion in cartesian products

joswig@corporat e-world.lisp.de writes:
[color=blue]
> (defun >> (val num-bytes)
> "Right-shift positive integer val by num-bytes"
> (floor (/ val (expt 2 num-bytes))))[/color]

or just (floor val (expt 2 num-bytes))

'as

[Christophe Rhodes]

Re: Programming challenge: wildcard exclusion in cartesian products

[ note followups ]

Mark Carter <me@privacy.net > writes:
[color=blue]
> I'd like to propose a coding challenge of my own. The challenge is to
> reproduce the TEA (Tiny Encryption Algorith):
> http://www.simonshepherd.supanet.com/tea.htm
> in your language of choice.[/color]

Here's mine, in Common Lisp.

(defmacro define-tea-pair ((encrypt decrypt) (delta n) (i1 j1 i2 j2))
`(macrolet ((32bitize (form) `(logand ,form #xffffffff))
(tea-kernel (x i j)
`(logxor (+ (ash ,x 4) (aref key ,i)) (+ ,x sum)
(+ (ash ,x -5) (aref key ,j))))
(tea-loop ((text n sum) &body body)
`(let ((result (make-array 2 :element-type '(unsigned-byte 32)))
(y (aref ,text 0))
(z (aref ,text 1)))
(do ((n ,n (- n 1)) (sum ,sum))
((<= n 0)
(prog1 result
(setf (aref result 0) y (aref result 1) z)))
,@body))))
(defun ,encrypt (plaintext key &aux (delta ,delta))
(declare (type (simple-array (unsigned-byte 32) (2)) plaintext)
(type (simple-array (unsigned-byte 32) (4)) key))
(tea-loop (plaintext ,n 0)
(setq sum (32bitize (+ sum delta))
y (32bitize (+ y (tea-kernel z ,i1 ,j1)))
z (32bitize (+ z (tea-kernel y ,i2 ,j2))))))
(defun ,decrypt (ciphertext key &aux (delta ,delta))
(declare (type (simple-array (unsigned-byte 32) (2)) ciphertext)
(type (simple-array (unsigned-byte 32) (4)) key))
(tea-loop (ciphertext ,n (32bitize (* ,n delta)))
(setq z (32bitize (- z (tea-kernel y ,i2 ,j2)))
y (32bitize (- y (tea-kernel z ,i1 ,j1)))
sum (32bitize (- sum delta)))))))

(define-tea-pair (encipher decipher) (#x9e3779b9 32) (0 1 2 3))

So far, so ordinary; only marginally shorter than the C version; I'm
certainly nowhere near Pascal's 14 lines, although my version has the
advantage over his that each constant is mentioned only once, and all
quantities derived from it are computed at compile-time; I can define
a different pair with

(define-tea-pair (eprime dprime) (#xabcdef01) (3 1 2 0))

and the new functions are inverses of each other as before.

The other thing that might be of interest is the inner loop. There
are no declarations other than the argument declarations, and all the
code that I have written is portable Common Lisp, and should work in
any conforming implemenation. In SBCL (on the PowerPC; other
platforms are similar), the inner loop for ENCIPHER is

addis $nl0,$nl3,-25033
addi $nl3,$nl0,31161
rlwinm $nl5,$nl2,4,0,2 7
lwz $nl6,1($fdefn)
add $nl6,$nl5,$nl6
add $nl0,$nl2,$nl3
xor $cfunc,$nl6,$nl 0
rlwinm $nl0,$nl2,27,5, 31
mr $nl5,$nl0
lwz $nl6,5($fdefn)
add $nl6,$nl5,$nl6
xor $nl6,$cfunc,$nl 6
add $nl1,$nl1,$nl6
rlwinm $nl5,$nl1,4,0,2 7
lwz $nl6,9($fdefn)
add $nl6,$nl5,$nl6
add $nl0,$nl1,$nl3
xor $cfunc,$nl6,$nl 0
rlwinm $nl0,$nl1,27,5, 31
mr $nl5,$nl0
lwz $nl6,13($fdefn)
add $nl6,$nl5,$nl6
xor $nl6,$cfunc,$nl 6
add $nl2,$nl2,$nl6
addi $nl4,$nl4,-4
cmpwi cr0,$nl4,0
bt gt,l0

and while this may be opaque to some readers, the point is that it is
pretty much comparable to the C code in performance (the differences
between this disassembly and gcc -O2 lie in the fact that SBCL's
instruction scheduler is pretty much nonexistent on the PowerPC
architecture).

Christophe

[wkehowski@cox.net]

Re: Programming challenge: wildcard exclusion in cartesian products

After the basic fact of generating the exclusion - a considerable
achievement - the program should be interactive. What if the target set
has thousands or millions of elements? There should be a loop-like way
('do' in Haskell, for example) to peel off the elements one-by-one and
then terminate.

[Dinko Tenev]

Re: Programming challenge: wildcard exclusion in cartesian products

wkehowski@cox.n et wrote:[color=blue]
> After the basic fact of generating the exclusion - a considerable
> achievement - the program should be interactive. What if the target set
> has thousands or millions of elements? There should be a loop-like way
> ('do' in Haskell, for example) to peel off the elements one-by-one and
> then terminate.[/color]

Um..."interacti vity" is a bit tricky in Prolog ;)

As Geoffrey pointed out in his posting, the solutions are generated
effectively one at a time. Following is a typical example of using the
generator:

generate_member ( X, ... ), do_something_wi th( X ), fail.

The underlying semantics is, roughly, 1) bind X, 2) do_something_wi th(
X ), 3) fail, meaning reject this binding of X and backtrack. In this
particular case, backtracking is tantamount to going back to 1).

You can regard ( generate_member ( X, ... ) ... fail ) as the equivalent
of a loop construct, and do_something_wi th( X ) as the loop body. At
any given time that the goal is being evaluated, there is only one
binding for X in effect.

On a side note, Haskell's "do" notation isn't really about loops. If
you're referring to Tomasz's code, it's rather mapM_ that can sort of
be thought of as looping through the list of values returned by
generateNotMatc hing :)

Cheers,

Dinko

[Dinko Tenev]

Re: Programming challenge: wildcard exclusion in cartesian products

Dinko Tenev wrote:[color=blue]
> Speculation: the time for
> building-up a smart structure to speed-up enumeration, together with
> the time for enumerating the set using that structure, should sum up to
> roughly Theta( n*|S^n| ), even with a really smart algorithm.[/color]

OK, maybe not.

This might be the worst case, looking at S^n - W only, but it's not
quite clear what "worst case" means in the context of concrete
implementations . Surely, one can clog the program with zillions of
wildcards to test, so we can produce an arbitrarily "bad" case :) --
but such a case is obviously of little or no practical importance. It
appears that, to make any sensible statements about performance in the
relevant cases, we have to take into account the size of the pattern
set used to specify W as well.
[color=blue]
> [...] here's another speculation:
> such structure would likely take up Theta( |S^n| ) space in memory, in
> the worst case.[/color]

....and similarly for "worst case" here.

Cheers,

Dinko

[Geoffrey Summerhayes]

Re: Programming challenge: wildcard exclusion in cartesian products


<wkehowski@cox. net> wrote in message
news:1142925259 .468795.104500@ t31g2000cwb.goo glegroups.com.. .[color=blue]
> After the basic fact of generating the exclusion - a considerable
> achievement - the program should be interactive. What if the target set
> has thousands or millions of elements? There should be a loop-like way
> ('do' in Haskell, for example) to peel off the elements one-by-one and
> then terminate.[/color]

There is...(Q&D)

1 ?- generate_member (X,[1,2],3,[[and, [*,2], [or, [2,1,*], [1,2,*]]]]),
write(X),nl,wri te('Is this the term you were looking for? (y/n):'),
get(Y), ((Y is 121) -> true; fail). % 121 = 'y'

[1, 1, 1]
Is this the term you were looking for? (y/n):n
[1, 1, 2]
Is this the term you were looking for? (y/n):|: n
[1, 2, 1]
Is this the term you were looking for? (y/n):|: y

Yes
2 ?-

---
Geoff

[funkyj]

Re: Programming challenge: wildcard exclusion in cartesian products

Dinko Tenev wrote:[color=blue]
> Doug Quale wrote:[/color]
[color=blue]
> Hmmm...storage is not an issue in the Prolog version. It generates a
> candidate solution, then checks membership in the wildcard set, then
> backtracks (backtracking is caused by "fail" in the test goal.) On
> backtracking, it effectively "forgets" the last solution, so the memory
> is freed up (or at least free to be reclaimed through GC.)[/color]

How about the other iterator characteristics ?

when there is a huge solution space can I ask the prolog version to
give me the first 1000 solutions? The next 1000 solutions (i.e. 1000 -
1999)?

If you can do that then it would appear that generators have no
advantage over your prolog solution.

[Dinko Tenev]

Re: Programming challenge: wildcard exclusion in cartesian products

funkyj wrote:[color=blue]
> How about the other iterator characteristics ?
>
> when there is a huge solution space can I ask the prolog version to
> give me the first 1000 solutions?[/color]

Geoffrey's post above offers one way to do this from within a REPL.

Within a program, as soon as you accept a solution, you're potentially
out of the "loop" (it is possible to use cut (!) to make this certain.)
[color=blue]
> The next 1000 solutions (i.e. 1000 - 1999)?[/color]

I am not quite sure how exactly you propose to do this in e.g. Python,
but if you mean to enumerate and skip over the first 1000 and then
continue with the rest, yes, this is also possible.
[color=blue]
> If you can do that then it would appear that generators have no
> advantage over your prolog solution.[/color]

To be fair, the Python implementation has one significant advantage --
it offers reduced runtime complexity for quite a number of practical
cases (of course, this improvement is achievable in Prolog too,) though
I'm still inclined to think that it can be made to run in exponential
time.

Also, my Prolog version is non-compliant in that it treats a wildcard
as matching a single position, rather than matching any sequence.
Geoffrey's implementation does the right thing though.

Cheers,

Dinko

[Dinko Tenev]

Re: Programming challenge: wildcard exclusion in cartesian products

OK, here's a case that will make your program run in exponential time:
S = { a, b }, W = { *a*b, *b*a } -- on my machine, it starts getting
ugly as soon as n is 15 or so. Note that S^n - W = { a^n, b^n }.

In general, whenever all the patterns in the set match against the last
position, your current implementation is guaranteed to have to sift
through all of S^n. I'd say the very idea of checking against a
blacklist is fundamentally flawed, as far as performance is concerned.

[Mark Carter]

Re: Programming challenge: wildcard exclusion in cartesian products

Mark Carter wrote:
[color=blue]
> At the risk of being labelled a troll[/color]

One thing I just discovered, and by which I mean *really* discovered ...
is that Lisp is an interactive environment. I am working on trying to
verify the contents of disks. I noticed that the input formats are
slightly wrong, and needed correction. In fact, there's a whole host of
jiggery pokery that I need to do in order to massage and build up
everything the way it needs to be.

A programmers mindset is usually geared towards "writing applications".
What I'm currently doing in Lisp is building up functions as I need
them. Using emacs, I can just C-x C-e to make my functions "live", and
when it's time to stop for the day, save my working image so that I can
use it the next day.

It seems to me that only Forth or Scheme really matches this capability.
Ruby and Python come kinda close - they do have a REPL, but it's kinda
clunky to try to create functions on the fly, plus of course they don't
support the idea of an image.

[Alexander Schmolck]

Re: Programming challenge: wildcard exclusion in cartesian products

Mark Carter <me@privacy.net > writes:[color=blue]
> A programmers mindset is usually geared towards "writing applications". What
> I'm currently doing in Lisp is building up functions as I need them. Using
> emacs, I can just C-x C-e to make my functions "live", and when it's time to
> stop for the day, save my working image so that I can use it the next day.
>
>
> It seems to me that only Forth or Scheme really matches this capability.[/color]

Not really. I'd say matlab's and squeak's (and presumably most smalltalks')
interactive environment is quite superior to cl+slime. Emacs lisp is also
better and I'd also suspect erlang to be better in some ways, but I haven't
used it yet. APL and descendants (J and K) also tend to have quite reasonable
interactive facilities and so do CAS systems.
[color=blue]
> Ruby and Python come kinda close - they do have a REPL, but it's kinda
> clunky to try to create functions on the fly, plus of course they don't
> support the idea of an image.[/color]

I don't think interactively creating functions is much harder in python but
changing module and class definitions is.

Actually although cl+slime is rather nice it is inferior to the much less
sophisticated and capable ipython+emacs combo in some regards (runtime error
reporting in CL tends to be pretty crap; (i)python docstrings, ease of
interactive testing and shell integration are superior). It's also much
easier to serialize stuff in python than it is in common lisp (never mind
pickle; you can't even readably print hashtables -- and unless I'm missing
something this is not user-fixable which really sucks).

Of course it's *much* easier to supply a nice interactive experience for a
quite limited language such as matlab than it is for CL (mostly because CL is
more powerful and geared towards efficient code generation).

So CL might well have the best interactiveness/(expressiveness *speed) ratio.

'as

[Dirk Thierbach]

Re: Programming challenge: wildcard exclusion in cartesian products

[Had to drop alt.comp.lang.h askell, otherwise my newsserver doesn't accept it]

Dinko Tenev <dinko.tenev@gm ail.com> wrote:[color=blue]
> OK, here's a case that will make your program run in exponential time:
> S = { a, b }, W = { *a*b, *b*a } -- on my machine, it starts getting
> ugly as soon as n is 15 or so. Note that S^n - W = { a^n, b^n }.[/color]
[color=blue]
> In general, whenever all the patterns in the set match against the last
> position, your current implementation is guaranteed to have to sift
> through all of S^n. I'd say the very idea of checking against a
> blacklist is fundamentally flawed, as far as performance is concerned.[/color]

If more time during preprocessing is allowed, another idea is to
treat the wildcard expressions as regular expressions, convert
each into a finite state machine, construct the "intersecti on" of
all these state machines, minimize it and then swap final and non-final
states. Then you can use the resulting automaton to efficiently
enumerate S^n - W. In the above case, the resulting FSM would have just
three states.

And it doesn't really matter what language you use to implement this
algorithm, it's the idea that counts. Notation aside, all
implementations will be quite similar.

- Dirk