I'm battling with a programming problem that suggests a more
stripped-down version:
Given the atoms +,*,1,2 and a number n, the function returns n expressed
in terms of the atoms, e.g.
n = 15
=> (- (* 2 2 2 2) 1)
This has a whiff to me of macro-building, automata, maybe AI....Has
anyone tackled an analogous problem? What would be some approaches that
might be fruitful for me to pursue?
Always grateful,
Drew
Drew Krause wrote:
> Pascal's solution is very elegant. What if the problem depended less on
> domain-knowledge, so (abstractly):
>
> given n, express n as s-expression using (func1, func2, atom1, atom2)?
Oh, man, thank god, I was hoping Pascal's response was unresponsive.
I was also going to ask:
>>> I'm battling with a programming problem that suggests a more
>>> stripped-down version:
>>>
>>> Given the atoms +,*,1,2 and a number n, the function returns n
>>> expressed in terms of the atoms, e.g.
>>>
>>> n = 15
>>> => (- (* 2 2 2 2) 1)
- is one of +,*,1,2? Typo, or are we allowed to invert operations? I
guess the former now that we have to handle arbitrary funcs for which we
could not guess the inverse.
Constraints? All numeric all the time? Looking for shorter paths? Is
func1 always to be applied to the output of func2 applied to all atoms?
no. sorry. but howseabout func1 always applied to ((output of func2
applied to any number of atoms) and any number of atoms)? No iteration
in the final form? etc etc.
kenny
Ken Tilton wrote:
> Constraints? All numeric all the time? Looking for shorter paths? Is
> func1 always to be applied to the output of func2 applied to all atoms?
> no. sorry. but howseabout func1 always applied to ((output of func2
> applied to any number of atoms) and any number of atoms)? No iteration
> in the final form? etc etc.
OK. To lay bare the problem I'm working on, I have:
a starting node,
and ending node,
several unary operations that can act on the first or any intermediate
steps,
and no other restrictions that I'm aware of (*except* that failure is a
possibility)
so for example, tg = target, s = start, op1...opn = operations
solution might look like tg = (op2 (op1 (op7084 (op10 (op2 (op5 s))))))
.. and yes, shortest path would be nice, but ITWICG (I'll take what I
can get)..
DK
Drew Krause wrote:
> Ken Tilton wrote:
>
>> Constraints? All numeric all the time? Looking for shorter paths? Is
>> func1 always to be applied to the output of func2 applied to all
>> atoms? no. sorry. but howseabout func1 always applied to ((output of
>> func2 applied to any number of atoms) and any number of atoms)? No
>> iteration in the final form? etc etc.
>
>
> OK. To lay bare the problem I'm working on, I have:
>
> a starting node,
> and ending node,
> several unary operations that can act on the first or any intermediate
> steps,
> and no other restrictions that I'm aware of (*except* that failure is a
> possibility)
Ah, new concepts, nodes and steps. Hmmm. Before we had op1 and op2 as
given data atoms. Now I see just one, with other operands being
generated by the operators. After which any number of operands can be
used, and each can be used any number of times. Makes 3D chess sound
like a small solution space.
So you want to try each operator on the original input (1 or more times)
to see if it produces the target, if not saving the result if it has not
been seen before. Rinse, repeat, and each time you have to experiment
with 1 - infinity uses of each operand in the pool.
if you get a sweep with no new results, hasta la vista baby. Not sure
how else you might determine nonconvergence, unless for each operator
you pair optionally a "no mas" function that is allowed to see all
results and all results generated by the paired generator and can
indicate that the paired generator is no longer to be tried. If it can
tell. Otherwise you have to impose an arbitrary depth.
Not sure if it helps to have an inverse operation for each operation.
You could then search backwards populating a space of "solved
intermediates". When this intersects with the "accomplished results" you
can go home.
I wonder if something like Screamer or Prolog would make this easier to
express. Have you done any Prolog? Now there is a mindf*ck. ACL trial
might include its prolog. That might be harder though than writing it in
Lisp (from painful experience trying to get Prolog to DWIM).
hth, kenny
--
Cells: http://common-lisp.net/project/cells/
"I'll say I'm losing my grip, and it feels terrific."
-- Smiling husband to scowling wife, New Yorker cartoon
Yes, I thought of screamer...but it looks like this may be one for GA...
I'll report back --
Ken Tilton wrote:
>
>
> Drew Krause wrote:
>
>> Ken Tilton wrote:
>>
>>> Constraints? All numeric all the time? Looking for shorter paths? Is
>>> func1 always to be applied to the output of func2 applied to all
>>> atoms? no. sorry. but howseabout func1 always applied to ((output of
>>> func2 applied to any number of atoms) and any number of atoms)? No
>>> iteration in the final form? etc etc.
>>
>>
>>
>> OK. To lay bare the problem I'm working on, I have:
>>
>> a starting node,
>> and ending node,
>> several unary operations that can act on the first or any intermediate
>> steps,
>> and no other restrictions that I'm aware of (*except* that failure is
>> a possibility)
>
>
> Ah, new concepts, nodes and steps. Hmmm. Before we had op1 and op2 as
> given data atoms. Now I see just one, with other operands being
> generated by the operators. After which any number of operands can be
> used, and each can be used any number of times. Makes 3D chess sound
> like a small solution space.
>
> So you want to try each operator on the original input (1 or more times)
> to see if it produces the target, if not saving the result if it has not
> been seen before. Rinse, repeat, and each time you have to experiment
> with 1 - infinity uses of each operand in the pool.
>
> if you get a sweep with no new results, hasta la vista baby. Not sure
> how else you might determine nonconvergence, unless for each operator
> you pair optionally a "no mas" function that is allowed to see all
> results and all results generated by the paired generator and can
> indicate that the paired generator is no longer to be tried. If it can
> tell. Otherwise you have to impose an arbitrary depth.
>
> Not sure if it helps to have an inverse operation for each operation.
> You could then search backwards populating a space of "solved
> intermediates". When this intersects with the "accomplished results" you
> can go home.
>
> I wonder if something like Screamer or Prolog would make this easier to
> express. Have you done any Prolog? Now there is a mindf*ck. ACL trial
> might include its prolog. That might be harder though than writing it in
> Lisp (from painful experience trying to get Prolog to DWIM).
>
> hth, kenny
>
On 4691 September 1993, Drew Krause wrote:
> OK. To lay bare the problem I'm working on, I have:
> a starting node, and ending node, several unary operations that can
> act on the first or any intermediate steps, and no other
> restrictions that I'm aware of (*except* that failure is a
> possibility)
> so for example, tg = target, s = start, op1...opn = operations
> solution might look like tg = (op2 (op1 (op7084 (op10 (op2 (op5 s))))))
> .. and yes, shortest path would be nice, but ITWICG (I'll take what I
> can get)..
Isn't this just a classic planning game you're playing? Perhaps you
could view each result of an operation as some intermediate node in
the graph you've to traverse, perhaps, like in the original posting,
this is natural. In this case, you might be able to come up with a
heuristic, how far from the target you are at any current node. If so,
that just sounds pretty much like a case for A* search. I'm not sure
but I think you might find a sample implementation in PAIP, and if
not, I would bet there's one in the classic CMU archives.
Holger
Drew Krause wrote:
> Ken Tilton wrote:
>
>> Constraints? All numeric all the time? Looking for shorter paths? Is
>> func1 always to be applied to the output of func2 applied to all
>> atoms? no. sorry. but howseabout func1 always applied to ((output of
>> func2 applied to any number of atoms) and any number of atoms)? No
>> iteration in the final form? etc etc.
>
>
> OK. To lay bare the problem I'm working on, I have:
>
> a starting node,
> and ending node,
> several unary operations that can act on the first or any intermediate
> steps,
> and no other restrictions that I'm aware of (*except* that failure is a
> possibility)
>
> so for example, tg = target, s = start, op1...opn = operations
>
> solution might look like tg = (op2 (op1 (op7084 (op10 (op2 (op5 s))))))
>
> .. and yes, shortest path would be nice, but ITWICG (I'll take what I
> can get)..
>
sounds like an A* problem. A* (A-star) is a search algorithm
that finds optimal paths in maze or near-maze conditions. It's
basically an optimization of breadth-first search.
What it consists of is keeping a set of reachable points (numbers
in this problem domain, I guess) ordered by an estimate as to the
minimum possible number of steps from each point to the solution
space. You use some kind of heuristic to come up with the estimate.
You repeatedly take the point with the smallest estimate, apply your
possible moves to that point to give you new points, apply your
heuristic to the new points to give estimates of remaining-steps
for each, and then repeat.
The heuristic is key. As long as it's conservative (smaller than
the actual number of steps required to get there from that point)
the algorithm is guaranteed to find the shortest path.
Bear
Yes. This is the solution that I'll try. Thanks, Drew
Ray Dillinger wrote:
> sounds like an A* problem. A* (A-star) is a search algorithm
> that finds optimal paths in maze or near-maze conditions. It's
> basically an optimization of breadth-first search.
>
> What it consists of is keeping a set of reachable points (numbers
> in this problem domain, I guess) ordered by an estimate as to the
> minimum possible number of steps from each point to the solution
> space. You use some kind of heuristic to come up with the estimate.
> You repeatedly take the point with the smallest estimate, apply your
> possible moves to that point to give you new points, apply your
> heuristic to the new points to give estimates of remaining-steps
> for each, and then repeat.
>
> The heuristic is key. As long as it's conservative (smaller than
> the actual number of steps required to get there from that point)
> the algorithm is guaranteed to find the shortest path.
>
> Bear
>
>
>
>
>
>
>
>
>
Drew Krause <········@mindspring.com> writes:
> Ken Tilton wrote:
>
> > Constraints? All numeric all the time? Looking for shorter paths? Is
> > func1 always to be applied to the output of func2 applied to all
> > atoms? no. sorry. but howseabout func1 always applied to ((output of
> > func2 applied to any number of atoms) and any number of atoms)? No
> > iteration in the final form? etc etc.
>
>
> OK. To lay bare the problem I'm working on, I have:
>
> a starting node,
> and ending node,
> several unary operations that can act on the first or any intermediate
> steps,
>
> and no other restrictions that I'm aware of (*except* that failure is a
> possibility)
>
>
> so for example, tg = target, s = start, op1...opn = operations
>
> solution might look like tg = (op2 (op1 (op7084 (op10 (op2 (op5 s))))))
>
> .. and yes, shortest path would be nice, but ITWICG (I'll take what I
> can get)..
Wouldn't a STRIPs style planner work for this?
Or to be more sophisticated, one of the newer planning algorithms?
--
Thomas A. Russ, USC/Information Sciences Institute
The A* search enabled me to solve this problem. There are several
implementations out there, but the one below worked for me right 'out of
the box':
http://www.apl.jhu.edu/~hall/lisp/Search/A-Star.lisp
Many thanks to everyone for your help!
Drew
Drew Krause wrote:
> Pascal's solution is very elegant. What if the problem depended less on
> domain-knowledge, so (abstractly):
>
> given n, express n as s-expression using (func1, func2, atom1, atom2)?
>
Drew Krause wrote:
> I'm battling with a programming problem that suggests a more
> stripped-down version:
>
> Given the atoms +,*,1,2 and a number n, the function returns n expressed
> in terms of the atoms, e.g.
>
> n = 15
> => (- (* 2 2 2 2) 1)
>
> This has a whiff to me of macro-building, automata, maybe AI....Has
> anyone tackled an analogous problem? What would be some approaches that
> might be fruitful for me to pursue?
>
> Always grateful,
> Drew
Two words: Genetic Programming (or alternatively Grammatical Evolution).
Although the current implementations are really hard to use and
almost everyone using GP (including myself) has created his own little
mad mix of a GP and a GE system, they are really a joy to work with.
Give it a try!
http://bc.tech.coop/blog/040619.html
(Warning: not for the easily discouraged :-)
I'm sure alternative solutions that use more conventional AI algorithms
exist, I'm just too lazy to think up something. I'm sure someone comes up
with an interesting solution.
On Thu, 06 Jul 2006 18:33:17 +0200, Drew Krause <········@mindspring.com>
wrote:
> I'm battling with a programming problem that suggests a more
> stripped-down version:
>
> Given the atoms +,*,1,2 and a number n, the function returns n expressed
> in terms of the atoms, e.g.
>
> n = 15
> => (- (* 2 2 2 2) 1)
>
> This has a whiff to me of macro-building, automata, maybe AI....Has
> anyone tackled an analogous problem? What would be some approaches that
> might be fruitful for me to pursue?
>
> Always grateful,
> Drew
That example uses '-' which is not one of the atoms.
With those atoms the only way to represent 15 is
(+ (* 2 2 2) (* 2 2) 2 1)
Which is just a alaborate form for a binary number.
Thus use the 2 logarith to reduce the expression.
This is a trivial reductive decomposition.
I also assume n >= 1 since there is no way to render 0.
Is this in fact what you mean?
--
Using Opera's revolutionary e-mail client: http://www.opera.com/mail/
"John Thingstad" <··············@chello.no> writes:
> On Thu, 06 Jul 2006 18:33:17 +0200, Drew Krause
> <········@mindspring.com> wrote:
>
>> I'm battling with a programming problem that suggests a more
>> stripped-down version:
>>
>> Given the atoms +,*,1,2 and a number n, the function returns n
>> expressed in terms of the atoms, e.g.
>>
>> n = 15
>> => (- (* 2 2 2 2) 1)
>>
>> This has a whiff to me of macro-building, automata, maybe AI....Has
>> anyone tackled an analogous problem? What would be some approaches
>> that might be fruitful for me to pursue?
>>
>> Always grateful,
>> Drew
>
> That example uses '-' which is not one of the atoms.
> With those atoms the only way to represent 15 is
> (+ (* 2 2 2) (* 2 2) 2 1)
Not the only way:
(+ (* (+ 1 1) 2 2) (* 2 2) 2 1)
> Which is just a alaborate form for a binary number.
> Thus use the 2 logarith to reduce the expression.
> This is a trivial reductive decomposition.
> I also assume n >= 1 since there is no way to render 0.
(+) --> 0
--
__Pascal Bourguignon__ http://www.informatimago.com/
The world will now reboot. don't bother saving your artefacts.
On Fri, 07 Jul 2006 22:22:51 +0200, Pascal Bourguignon
<···@informatimago.com> wrote:
> "John Thingstad" <··············@chello.no> writes:
>
> Not the only way:
>
> (+ (* (+ 1 1) 2 2) (* 2 2) 2 1)
>
I stand corrected. Uniquely the shortest way.
>> Which is just a alaborate form for a binary number.
>> Thus use the 2 logarith to reduce the expression.
>> This is a trivial reductive decomposition.
>> I also assume n >= 1 since there is no way to render 0.
>
> (+) --> 0
>
>
If you consider that 0.
I don't since all other expressions use numbers.
(+) isn't well formed.
--
Using Opera's revolutionary e-mail client: http://www.opera.com/mail/
On Fri, 07 Jul 2006 23:17:21 +0200, Marcus Breiing
<······@2006w27.mail.breiing.com> wrote:
> "John Thingstad" <··············@chello.no> writes:
>
>> > Not the only way:
>> >
>> > (+ (* (+ 1 1) 2 2) (* 2 2) 2 1)
>> >
>>
>> I stand corrected. Uniquely the shortest way.
>
> (+ (* 2 2 2) 2 2 2 1)
>
Opps missed that one.
Of course it only works for the case (* 2 2) = (+ 2 2)
Still it seems to complicate the algorithm more than it's
worth to include this spesial case.
(To my mind)
--
Using Opera's revolutionary e-mail client: http://www.opera.com/mail/
"John Thingstad" <··············@chello.no> writes:
> On Fri, 07 Jul 2006 22:22:51 +0200, Pascal Bourguignon
> <···@informatimago.com> wrote:
>
>> "John Thingstad" <··············@chello.no> writes:
>>
>> Not the only way:
>>
>> (+ (* (+ 1 1) 2 2) (* 2 2) 2 1)
>>
>
> I stand corrected. Uniquely the shortest way.
>
>>> Which is just a alaborate form for a binary number.
>>> Thus use the 2 logarith to reduce the expression.
>>> This is a trivial reductive decomposition.
>>> I also assume n >= 1 since there is no way to render 0.
>>
>> (+) --> 0
>>
>>
>
> If you consider that 0.
> I don't since all other expressions use numbers.
> (+) isn't well formed.
In Common Lisp, (+) is well formed and precisely defined to return the
neutral element of the additive field, and (*) is defined to return
the neutral element of the multiplicative field.
[201]> (+)
0
[202]> (*)
1
[203]>
--
__Pascal Bourguignon__ http://www.informatimago.com/
This is a signature virus. Add me to your signature and help me to live.
"John Thingstad" <··············@chello.no> writes:
> With those atoms the only way to represent 15 is
> (+ (* 2 2 2) (* 2 2) 2 1)
(+ 1 (* 2 (+ 1 (* 2 (+ 1 2)))))
> I also assume n >= 1 since there is no way to render 0.
(+)
--
Marcus Breiing
Drew Krause <········@mindspring.com> writes:
> I'm battling with a programming problem that suggests a more
> stripped-down version:
>
>
> Given the atoms +,*,1,2 and a number n, the function returns n expressed
> in terms of the atoms, e.g.
>
> n = 15
> => (- (* 2 2 2 2) 1)
It seems to me that the simplest solution given the minimal constraints
above would be to not use * at all:
(defun can-of-worms (n)
(if (oddp n)
`(+ ,@(make-list (truncate n 2) :initial-element 2) 1)
`(+ ,@(make-list (truncate n 2) :initial-element 2))))
or alternately:
(defun can-of-worms2 (n)
(let ((twos (make-list (truncate n 2) :initial-element 2)))
(if (oddp n)
(cons '+ (cons 1 twos))
(cons '+ twos))))
Test:
(loop for n from 0 to 21
unless (= n (eval (can-of-worms n)))
do (error "Failed for ~D" n)
finally (return 'success))
--
Thomas A. Russ, USC/Information Sciences Institute