Here is a slight modification of the previous program that can be
executed in two directions:
N = [40]
A = range(1,40)
B = range(1,40)
C = range(1,40)
D = range(1,40)
def valid(a,b,c,d,n):
weights = set(w*a+x*b+y*c+z*d for w in [-1,0,1]
for x in [-1,0,1]
for y in [-1,0,1]
for z in [-1,0,1])
return weights >= set(range(1,n+1))
ws = [(a,b,c,d,n) for n in N
for a in A
for b in B if a <= b
for c in C if b <= c
for d in D if c <= d
if a+b+c+d == n and valid(a,b,c,d,n)]
Change the variable domains to execute it in the other direction:
N = range(1,100)
A = [1]
B = [3]
C = [9]
D = [27]
This produces the single answer (1,3,9,27,40), i.e. the only solution
is with n = 40.
What I mean by cheating is that you hard-code part of the solution.
Would you consider the program `print "1,3,9,27"` a good solution? To
me at least, it's non obvious that the solution would have to have a=1
and would have to have a,b,c,d all different. Sure, for the way you
interpreted the problem originally, a=1 is obvious. But since now you
can subtract weights as well as adding them it is not obvious (to me).
Why couldn't a=3 and b=4 work? Then you can still weigh 1lbs. If you
consider it obvious, can you explain?
> I'm curious if it can be written more concisely. Not sure. I note that most
good solutions in Python and Haskell while fast and neat can only work
in
one direction.
I think that you can use the same technique as the Python program.
What are the weights we can measure with stones that weigh a,b,c,d?
Well, for each stone we can either put it on the left scale (-a) or on
the right scale (+a) or not on the scale at all (0). So the weights we
can measure is the set {w*a + x*b + y*c + z*d | w,x,y,z are -1, 0 or
1}. So for example if w=-1, x=0, y=1, z=1 then stone A is on the left,
stone B is not on the scale and stones C and D are on the right. The
condition we need to satisfy is that this set contains all the weights
{1..40}. With list/set comprehensions you can use this method
directly, but with logic programming you need to do it slightly
differently.
You can define a relation (canmake a b c d x) which checks if a,b,c,d
can make the weight x by creating four new finite domain variables
w,x,y,z each with domain {-1,0,1}. Then you assert w*a+x*b+y*c+z*d ==
x. So now you have a relation that succeeds iff weights a b c d can
make x. Then you just have to assert every (canmake a b c d 1) ...
(canmake a b c d 40). I don't know if cKanren has a library predicate
for that, but something like (forall xs p) that asserts p on all
elements of xs isn't hard to define.
Whether the resulting program is more concise I don't know, but I
think it would at least be easier to understand.
Jules
On Nov 13, 5:17 am, David Nolen <dnolen.li...@gmail.com> wrote:
> checko and subchecko work together to determine whether an ordered set of
> weights can produce integers 1 to 40 in reverse. It's more verbose since we
> are preserving the ability to run our program backwards - which is simply a
> byproduct of writing a purely relational program.
>
> I'm curious if it can be written more concisely. Not sure. I note that most
> good solutions in Python and Haskell while fast and neat can only work in
> one direction.
>
> I would love to see purely relational versions in Haskell, Python etc. even
> if they involve bringing in a constraint solver (which alone isn't enough
> as far as I know)
>
> On Saturday, November 12, 2011, Ambrose Bonnaire-Sergeant
> <abonnaireserge...@gmail.com> wrote:
> > I'll just clarify, the "matches" function body jumps out at me. "checko"
>
> doesn't, but it's role in the problem is still clear, even if its
> implementation is not. I think that's still an important trait.> Can checko
> be improved? I'm not sure. What does subchecko do, David?
> > Ambrose
>
> > On Sun, Nov 13, 2011 at 11:37 AM, Ambrose Bonnaire-Sergeant <
> abonnaireserge...@gmail.com> wrote:
>
> > "Understandability" is subjective. The meaning of the cKanren really
>
> jumps out at me, the python program takes a lot more for me to think
> through.> There is nothing wrong with pruning the search space in this
> program. As
>
> you said, doing so reduced the Python program execution time to 2ms!
>
>
>
>
>
>
>
> > Ambrose
>
> > On Sat, Nov 12, 2011 at 11:30 PM, Jules <julesjac...@gmail.com> wrote:
>
> > The time difference is largely due to using the product library
> > function instead of for comprehensions and the fact that the cKanren
> > version cheats by hardcoding part of the solution, and hardcoding an
> > extra constraint alldiff(a,b,c,d). The following code takes ~12ms with
> > PyPy on my computer:
>
> > def valid(a,b,c,d):
> > weights = set(w*a+x*b+y*c+z*d for w in [-1,0,1]
> > for x in [-1,0,1]
> > for y in [-1,0,1]
> > for z in [-1,0,1])
> > return weights >= set(range(1,41))
>
> > ws = [(a,b,c,d) for a in range(1,40)
> > for b in range(1,40) if a <= b
> > for c in range(1,40) if b <= c
> > for d in range(1,40) if c <= d
> > if a+b+c+d == 40 and valid(a,b,c,d)]
>
> > If you cheat with `for a in [1]` instead of `for a in range(1,40)` and
> > changing the <= to < (the same cheat as the alldiff), then the
> > execution time drops to 2ms.
>
> > Since we don't seem to be going to agree on the definition of
> > declarative, lets use another word: nice. Lets define niceness as
> > understandability and closeness to mathematical specification. I agree
> > that the matches definition is already nice: it handles the
> > constraints and symmetry breaking nicely (better than the Python
> > version if you ignore syntactic issues e.g. a+b+c+d=40 is more
> > convoluted). But the checko and subchecko leave a lot to be desired.
> > So my question is: can the cKanren version be improved so that it also
> > becomes nice?
>
> > Jules
>
> > On 12 nov, 07:16, David Nolen <dnolen.li...@gmail.com> wrote:
> >> Also note that even given all this generality over the Python code - the
> >> earlier Python implementation takes ~300ms and this implementation takes
>
> >> >900ms on my machine.
>
> >> Quite a bit slower than ~12ms. Inferring 40 takes even less time of
> course
> >> - ~8ms.
>
> >> But really the execution time is just icing on the declarative cake ;)
>
> >> David
>
> >> On Fri, Nov 11, 2011 at 8:09 PM, Jules <julesjac...@gmail.com> wrote:
> >> > Here is a new program. Perhaps you would consider this declarative:
>
> >> > def valid(a,b,c,d):
> >> > weights = set(w*a+x*b+y*c+z*d for (w,x,y,z) in
> >> > product([-1,0,1],repeat=4))
> >> > return weights >= set(range(1,41))
>
> >> > ws = [(a,b,c,d) for (a,b,c,d) in product(range(1,41),repeat=4)
> >> > if a <= b <= c <= d and a+b+c+d == 40 and
> >> > valid(a,b,c,d)]
>
> >> > On 12 nov, 01:48, Jules <julesjac...@gmail.com> wrote:
> >> > > Are we reading the same cKanren code? I'll give you that the matches
> >> > > definition is declarative, but then read checko and subchecko. They
> >> > > are all about (recursive) control flow. Where does the specification
> >> > > say anything remotely close to the checko and subchecko relations? In
> >> > > contrast to this, the Python set comprehensions have minimal control
> >> > > flow. Yeah, the standard Python implementation has a certain order of
> >> > > executing the comprehensions, but so does the cKanren implementation
> >> > > when executing the predicates. My Python program doesn't depend on
>
> > --
> > You received this message because you are subscribed to the Google
> > Groups "Clojure" group.
> > To post to this group, send email to clojure@googlegroups.com
> > Note that posts from new members are moderated - please be patient with
> your first post.
> > To unsubscribe from this group, send email to
> > clojure+unsubscr...@googlegroups.com
> > For more options, visit this group at
> >http://groups.google.com/group/clojure?hl=en
--
You received this message because you are subscribed to the Google
Groups "Clojure" group.
To post to this group, send email to clojure@googlegroups.com
Note that posts from new members are moderated - please be patient with your
first post.
To unsubscribe from this group, send email to
clojure+unsubscr...@googlegroups.com
For more options, visit this group at
http://groups.google.com/group/clojure?hl=en
