okay let's finish our derivation of the condom problem we started Oct
leads a very simple brewed for solution
then and the second step we took
an the generation process and we made sure that we
never generates expressions that were invalid
and what we're going to do in this third step is we're going to
shrink the search space by and leveraging
a algebraic properties of expression in particular
the fact that multiplication is committed F
and the fact that Wong is the new char element
for multiplication game saw
these are the property we're going to use multiplication
is commuted F and and
Wong is the new char element for
multiplication alright
sure here's the I am previous definition of whether an
expression was valid and every member
an expression was valid when the
numbers %uh which it was composure your boss in Excel
when we added to an
values well thats now let's because adding to positive numbers is
get a positive number when we subtract two numbers
the result is positive when the first number is larger than the second
multiplication of two numbers positive numbers is always positive
and here we had to make sure that
we I'm remains within the integer domain
well in this case instead of just returning true
well we do now is we say we want actually be less than why so we're going
to make this thing biased so
adding X to Y is valid
if axes less than why and we were doing we're going to do the same
for multiplication K and now
am we also want to say that
if the axe is Wong
and we don't considered distinct sell it
case you were drawing up on the way so what we're what we did
is really biased the representation we say we always want the wall on the left
to be larger than the right and by that we have lemon and
eliminated ads y ax as a valid expression
shit is funny clever trick so if action wired the same it's still that let
but they've X is less than why that's very cool then why
we have eliminated an the
an committed if expression at YX
good and then we also
onto an used to gauge where
X or why is wrong K so this takes into account
the community devotee of multiplication and addition
and the fact that an Wong is the neutral element
of multiplication I'm and finally
also when we and divide by Wong
that's the same as X lemme
applied is very simple an extension dude ass
it as quite dramatic result so when we look at the solutions
for this there's now only two hundred fifty dollars and valid expressions
K so that's about twenty times less than before
and and when we look at the solutions
there are about sixteen time less because all the solutions that we had
were duplicates of each other all the solution there were many duplicates
and ocean oceans so when we run this now
runs it finds the first solution
and to understand the second but even more important
it's fine all the solutions and under
hot of a second so is she
really all that
and problems from this TV program
are solved by then of a second
and we started out with all solutions being about
44 seconds over this is quite a dramatic improvement
you see there was not that difficult we made to small steps
starting with obviously correction ocean that was slow
and MBB factor it to remain correct
but become fast and this is the way
and Haskell programmers like to work so
start with something that's right and then you make it better
great thank you so much happy hacking
make sure you do your homework and then see you next week