Programming challenge: wildcard exclusion in cartesian products

[funkyj]

Re: Programming challenge: wildcard exclusion in cartesian products

wkehowski@cox.n et wrote:[color=blue]
> 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]

One advantage of a generator over filtering the full product is that I,
as the user of the generator, am not obligated to iterate over the
entire solution space.

Are there other _practical_ advantages of generators over mapping &
filtering complete sets?

[Doug Quale]

Re: Programming challenge: wildcard exclusion in cartesian products

"funkyj" <funkyj@gmail.c om> writes:
[color=blue]
> One advantage of a generator over filtering the full product is that I,
> as the user of the generator, am not obligated to iterate over the
> entire solution space.
>
> Are there other _practical_ advantages of generators over mapping &
> filtering complete sets?[/color]

Storage. You can iterate over problem spaces much too large to fit in
memory. Also generate + iterate can be faster because of reduced
memory pressure.

[wkehowski@cox.net]

Re: Programming challenge: wildcard exclusion in cartesian products

Yes, the program is quite a jumble: but it works. And I didn't post to
python newsgroup since I was limited to just 5 newsgroups and didn't
feel like doing multiple postings to multiple newsgroups.

[wkehowski@cox.net]

Re: Programming challenge: wildcard exclusion in cartesian products

Here is an nice intro to K:

http://www.kuro5hin.org/?op=displaystory;sid=2002/11/14/22741/791

"This is where K starts to set itself from apart from most of the
common programming languages in use today. You rarely write loops in K
(KDB is 100% loop-free), instead you use adverbs. An adverb modifies a
function, returning another function, changing the ways it operates
over its arguments and what it does with it's return values."

How about an interactive loop-like version? Generating the target set
is good for baby test cases but not if the cardinality of the target is
large. Does that make the problem more intersesting?

[wkehowski@cox.net]

Re: Programming challenge: wildcard exclusion in cartesian products

When I run this I get through ghc I get

C:\Documents and Settings\User\M y Documents\wildc ard>ghc
"./wc-zielonka.hs"
compilation IS NOT required
C:/Languages/ghc/ghc-6.4.1/libHSrts.a(Main .o)(.text+0x1d) :Main.c:
undefined refe
rence to `__stginit_ZCMa in'
C:/Languages/ghc/ghc-6.4.1/libHSrts.a(Main .o)(.text+0x43) :Main.c:
undefined refe
rence to `ZCMain_main_cl osure'
collect2: ld returned 1 exit status

Unless there's a command line option I'm missing?

[wkehowski@cox.net]

Re: Programming challenge: wildcard exclusion in cartesian products

The cardinality of excluding '*a*b*' from S^n should be
(m-1)^(n-1)*(m+n-1), where m=|S|. For m=5 this becomes 4^(n-1)*(n+4),
and your table fits this formula. As far as generating and testing, an
'ideal' solution would be to 'start from the ground up', as in
excluding length 2 wc, and then length 3, etc, until all wc's have been
excluded. The 'ideal' solution would intrinsically exclude wc's and not
test against a background generation of all of S^n. Does that make
sense?

[wkehowski@cox.net]

Re: Programming challenge: wildcard exclusion in cartesian products

Nice! How to put it in a loop? I'm totally a newbie to Lisp myself,
just gettng into Graham and Touretzky. Let's create a problem. Suppose
after excluding I want to know if the digits sum to 12, say, like maybe
they're part of a partition. S={0,..6}, S^5, excluding "*1*5*" and
"1*2*3*", say. How would I do that?

[Joachim Durchholz]

Re: Programming challenge: wildcard exclusion in cartesian products

wkehowski@cox.n et schrieb:[color=blue]
> "This is where K starts to set itself from apart from most of the
> common programming languages in use today. You rarely write loops in K
> (KDB is 100% loop-free), instead you use adverbs. An adverb modifies a
> function, returning another function, changing the ways it operates
> over its arguments and what it does with it's return values."[/color]

Doesn't sound too different from what closures do. Or lazy parameter
passing.
<rant> I'm not sure whether the K designer actually fits that
description, but there are too many language designers around
reinventing the wheel, arguing whether it should have seven, eight or
thirteen sides... </rant>

Regards,
Jo

[wkehowski@cox.net]

Re: Programming challenge: wildcard exclusion in cartesian products

OK, a bad case of RTFM. I saved your file as WildCartesian.h s and then

1) command line: ghci WildCartesian.h s
2) Get some loading messages
3) command line: test

and it works! But how do I compile it to get a program with command
line arguments? I'm looking through Daume's tutorial right now.

[Dinko Tenev]

Re: Programming challenge: wildcard exclusion in cartesian products

Doug Quale wrote:[color=blue]
> "funkyj" <funkyj@gmail.c om> writes:
>[color=green]
> > One advantage of a generator over filtering the full product is that I,
> > as the user of the generator, am not obligated to iterate over the
> > entire solution space.
> >
> > Are there other _practical_ advantages of generators over mapping &
> > filtering complete sets?[/color]
>
> Storage. You can iterate over problem spaces much too large to fit in
> memory. Also generate + iterate can be faster because of reduced
> memory pressure.[/color]

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.)

Cheers,

Dinko

[Dinko Tenev]

Re: Programming challenge: wildcard exclusion in cartesian products

wkehowski@cox.n et wrote:[color=blue]
> 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]

OK, having read some of the comments so far, I have the feeling that I
may be missing the point in more than one way, so let's set this
straight:

If I understand correctly, for an alphabet S, and a subset W of S*
specified by the wildcards, you expect the enumeration of sequences of
length n to run in Theta( n*|S^n - W| ) instead of Theta( n*|S^n| ).

First, this doesn't seem to hold for your Python program. Try, for
example, S = { a, b, c }, W = { *a*b*, *b*c*, *c*a*, *b*a*, *c*b*,
*a*c* }, with some large values of n. Theta( n*|S^n - W| ) predicts
that the enumeration time should grow linearly with n, as |S^n - W| =
3, but if you take some measurements, you'd notice that it grows faster
than that.

Second, my current bet is that such an improvement in asymptotic
complexity is not possible, if we consider *both* pre-processing of the
wildcard set and subsequent enumeration. 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.

Even if you're willing to pay up-front for tighter loop execution
later, and you build a suitable structure for this purpose, you would
have to consider the structure's size, so here's another speculation:
such structure would likely take up Theta( |S^n| ) space in memory, in
the worst case.

I would really appreciate it if you could pour some light into what
you're trying to do exactly, and possibly point out anything that I
might have missed so far.

Cheers,

Dinko

[Mark Tarver]

Re: Programming challenge: wildcard exclusion in cartesian products

Hi,

You wrote into the Qilang News group with your problem.
This is a solution in 17 lines of Qi for any n-product >= 2.
It falls short of your complete requirement since it uses
generate and then test, rather than interleaving the
two.

(define challenge
Patterns N X -> (filter (/. Y (member Y Patterns)) (n-product N X)))

(define n-product
2 X -> (cartesian-product l X X)
N X -> (cartesian-product c X (n-product (- N 1) X)))

(define cartesian-product
_ [ ] _ -> [ ]
c [X | Y] Z -> (append (map (/. W [X | W]) Z) (cartesian-product c Y
Z))
l [X | Y] Z -> (append (map (/. W [X W]) Z) (cartesian-product l Y
Z)))

(define filter
_ [] -> []
F [X | Y] -> (filter F Y) where (F X)
F [X | Y] -> [X | (filter F Y)])

(define member
_ [] -> false
X [Pattern | _] -> true where (query-prolog [[= Pattern X]])
X [_ | Patterns] -> (member X Patterns))

Notes:

Pattern filtering is done by a unification test within the member
function. You
can do this most easily by calling Qi Prolog using query-prolog.
Here's a test.

(42 -) (n-product 3 [a b c])
[[a a a] [a a b] [a a c] [a b a] [a b b] [a b c] [a c a] [a c b] [a c
c]
[b a a] [b a b] [b a c] [b b a] [b b b] [b b c] [b c a] [b c b] [b c
c]
[c a a] [c a b] [c a c] [c b a] [c b b] [c b c] [c c a] [c c b] [c c
c]]

OK, remove all lists beginning [a a ....].

(43-) (challenge [[a a | X]] 3 [a b c])
[[a b a] [a b b] [a b c] [a c a] [a c b] [a c c] [b a a] [b a b] [b a
c]
[b b a] [b b b] [b b c] [b c a] [b c b] [b c c] [c a a] [c a b] [c a
c]
[c b a] [c b b] [c b c] [c c a] [c c b] [c c c]]

Remove all lists beginning with a or b.

(51-) (challenge [[a | X] [b | X]] 3 [a b c])
[[c a a] [c a b] [c a c] [c b a] [c b b] [c b c] [c c a] [c c b] [c c
c]]

Mark

[Mark Carter]

Re: Programming challenge: wildcard exclusion in cartesian products

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;
}

I had a crack at it in Lisp. My version doesn't work - but of greater
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):

(defconstant delta 2654435769 ) ; delta= 0x9E3779B9

(defun floorn (n) (nth-value 0 (floor n)))

(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)))

(defun << (val num-bytes)
"Left-shift positive integer v by num-bytes"
(* val (expt 2 num-bytes)))

(defun <<4 (i) (<< i 4))

(defun byte-n (v n)
"Return the nth byte of a value v"
(let* ((bits-to-shift (* 8 (1- n)))
(shifted-value (>> v bits-to-shift)))
(logand shifted-value 256)))


(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)))

(defun pack64 (b1 b2) (+ (<< b1 32) b2))

(defun encipher (v k)
(let ((sum 0)
(a (byte-n k 3)) ; a=k[0]
(b (byte-n k 2)) ; b=k[1]
(c (byte-n k 1)) ; c=k[2]
(d (byte-n k 0)) ; d=k[3]
(y (byte-n v 1)) ; y=v[4]
(z (byte-n v 0))) ; z=v[1]


(loop for n from 0 to 31 do ;n=32, while(n-->0)
(incf sum delta) ;sum += delta;
(incf y (transform z a sum b)) ; y += (z << 4)+a ^ z+sum ^ (z >> 5)+b
(incf z (transform y c sum d)) ;z += (y << 4)+c ^ y+sum ^ (y >> 5)+d;
)

(pack64 y z) ; w[0]=y; w[1]=z;
))


(defun decipher (v k)
(let ((sum 3337565984) ; 0xC6EF3720
(a (byte-n k 3)) ; a=k[0]
(b (byte-n k 2)) ; b=k[1]
(c (byte-n k 1)) ; c=k[2]
(d (byte-n k 0)) ; d=k[3]
(y (byte-n v 1)) ; y=v[4]
(z (byte-n v 0))) ; z=v[1]

(loop for n from 0 to 31 do ;n=32, while(n-->0)
(decf z (transform y c sum d)) ;z -= (y << 4)+c ^ y+sum ^ (y >> 5)+d;
(decf y (transform z a sum b)) ;y -= (z << 4)+a ^ z+sum ^ (z >> 5)+b;
(decf sum delta) ;sum -= delta;
)

(pack64 y z) ; w[0]=y; w[1]=z;
))

[Mark Tarver]

Re: Programming challenge: wildcard exclusion in cartesian products

Interesting. But you probably need to post this as a new
message, since it is a distinctly different
problem from the one driving this thread.

Mark

[Mark Carter]

Re: Programming challenge: wildcard exclusion in cartesian products

Mark Tarver wrote:[color=blue]
> Interesting.[/color]

At the risk of being labelled a troll, one thought that is occuring to
me is that in Lisp it seems that sometimes it is difficult to achieve a
simple thing in a simple way. To clarify ... recently, I had been
trying to obtain md5 hashes of the files we had on our server (a
different exercise than the one I mentioned in my OP, just in case you
thought that I didn't understand the difference between encryption and
hashing). There is an md5 package for Lisp available on the web, which I
used with CLISP. I had a file that contained a non-standard character,
causing CLISP to throw an error when it tried to print it.

Well, I suppose I could have tried to figure out a way to cajole CLISP
into printing something it didn't want to print, but I was keen to give
Corman Lisp 2.5 a try-out anyway, so I tried the package on it. EXCEPT,
for some reason when you try to read a file with an :element-type of
(unsigned-byte 8) (or something similar), Corman didn't like it.

In the end, I hacked together an md5 DLL from some sources I found on
the internet. You can get the package here, together with Corman Lisp
bindings:

http://www.markcarter.me.uk/computing/freeware/md5mc/md5mc.htm

In the past, I had also employed a similar technique in order to get
access to some console functions that I was interested in.

My worry is that it seems to be a recurring theme with me ... get
stumped in Lisp, realise that it is probably just plain easier in C, and
then link the whole thing together in Lisp. Which is kinda less than
expected.