So, if one stays in the imperative world, why not just the generic problem instead of the specific one ?
This clojure solution can solve the problem for any N (total weight) and any M (any number of parts the stone can be spit into): https://gist.github.com/1332020 The implementation is a bit longer than I expected, but I wanted to not cheat by hard-wiring mathematical assumptions inside it (thus the intermediate definition for a diff function working on unordered lists of elements to be considered as "bags" - where the same element could appear twice-) 2011/11/13 Jules <julesjac...@gmail.com> > 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 > -- 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
