welcome back I hope that you
yeah were able to get the RSL bed after this
a.m. long sequence an
and what we did in the first part of this lecture
is take the description
the informal description of the expression a
problem astoria the expression problem up to come down problem
expression problem is something completely different again Google that
and
again you can spend years trying to solve the expression problem
but we are trying to solve the Condon problem here
and what we did is re constructed
a brute-force solution where
regis gender aidid's all possible expressions
and then checked weathered a satisfied
the rules of the game what we're going to do
now is your gun going to try to check
if we can avoid to generate
and invalid expressions up front
okay and our hope is that this rule
definitely gives a perfect performance improvement big us
you know there's only I'm you now quite a small fraction
of all the possible expressions are valid and
and so the way we're going to do that is we're going to look at
bears of expressions and their
values K so is the expression
and this is the value so we carry around both this symbolic representation of the
expression
and the numeric representation of the expression
and what we want is we want to have a
function that fuses together
degeneration and the evaluation
of the expressions so this is the
result evaluating the expression and that is the
result of generating the expression but we needed
the result of evaluating the expression to check
whether it satisfied and the constraints of the game
K so that's what we're going to do we're going to try
to define a function that will combine
the generation and evaluation and
the way we can do that ish as follows:
if three want to find the results
for the empty nest well that's the empty nest when we want to
generate the combination of expressions and their values
for single-a meshed well what do we do
we did what we did before be and
generate expression we know its value
but this is only valid remember when
the and number was greater than 0
so now we can put this test right here
and the rest of the gods is now
fairly obvious where we just do exactly the same
except that we recursively call results
okay and and then
we still have to define the combine function here
that will do the same thing that will kinda check
weather D result are fell it so here is
combine its exactly the same
as our previous combine function accepts
that now we also check weathered the results are valid
you see that we can do that because we are now
carrying around a pair of the expression and its value
and that allows us to check HERE whether
the result is valid as we are generating
these new expressions some it's got a small
an change am but its
to quite dramatic so here's the new function that solves the condom problem
am and it's just a.m. using
this new results a function here so we take all the choices
we calculate the results given the east and then
we check rather the result is the wrong
that we want and this case every run this now
its about ten times faster so it's now an
you know for hundreds of a second
and also this guy here which used to be a mother wasn't 43 seconds
is now down to three and a half seconds and
this is fabulous this is really fabulous
can we do even better
can we do even better and we can
biggest we have now eliminated
generating invalid expressions
because me we're generating the expressions with their results it said
we could always check
whether they were okay but they're still
cemeteries that we're not using okay
biggest really every have X times why
thats basically the same ardent basically dead is the same
as white I'm check so we don't have to generate
both of these to results
and if we happened to multiply number by WAM
we might as well just use X okay
so if we use these properties we will eliminate
you now we won't be using the expressions here on the left
because they are considered to be the same
as the expressions on the right so hopefully
we can reduce the search space
fordice and that's what we'll do
and the next part so take a small break
and all season