Brute Force behind the Observer

Photo by Deva Darshan on UnsplashBrute Force behind the ObserverHow to build micro-machines with the Observer pattern capable of solving the most complex problems.

Juan Manuel DatoBlockedUnblockFollowFollowingJun 7It is quite common to despise the power of brute force when searching.

It gives the impression that the best way to solve problems is through some suitable and careful method.

However, the more complex and less interactive the code, the more constrained the efficiency is.

If, on the other hand, we worry about implementing something more dynamic, then the applicability of the formulas to each case improves.

Therefore, for very complex problems and not very large entries, it may be advisable to have iterators that offer us the quickest solutions.

Brute force on timetablesImagine we want to implement a simple school timetable.

For this we would have to combine teachers, courses, classrooms… But a schedule recognizes, at least, a correspondence that designates for what class, what day and what time of the day, a teacher, a subject and a course.

So we can prepare this initialization:def test1(days, hours, clrooms, courses, teachs, subjs): D = ['d' + str(X) for X in range(days)] H = ['h' + str(X) for X in range(hours)] R = ['r' + str(X) for X in range(clrooms)] C = ['c' + str(X) for X in range(courses)] T = ['t' + str(X) for X in range(teachs)] S = ['s' + str(X) for X in range(subjs)] return ((R, H, D), (S, T, C))If we want to iterate a composition of lists (days, hours and classrooms; or courses, teachers and subjects), we must first combine the lists so that they can be well coded, so I can propose this class:class Combine: def __init__(self, domains): self.

D = domains self.

len = self.

_calculateLen()def _calculateLen(self): R = 1 for X in self.

D: R*= len(X) return Rdef __getitem__(self, item): R = [] for dom in self.

D: R.

append(dom[item % len(dom)]) item //= len(dom) return tuple(R)You can test the code above in this way:>>> c = Combine([('a', 'b'), ('1', '2', '3')])>>> for i in range(125, 136): print(''.

join(c[i]), end=' ')b3 a1 b1 a2 b2 a3 b3 a1 b1 a2 b2The aim of the Combine class is to offer a technique that allows us to traverse each of the possibilities without any margin of error (brute force).

And, on the other hand, that we were able to index any possibility with a large number.

Therefore an iterator that we can use would be the following one.

def corresp (dom, im, ini = 0): 'Returns the iterator' 'For every item in dom there is no more than one item in im' X = Combine(dom) Y = Combine(im) while True: C = {} index = ini for j in range(X.

len): C[X[ini + j]] = Y[index] index //= Y.

len yield C ini += 1This iterator is initially prepared exclusively to account for all matches.

So it is easy to build a timetable if it only has ONE correspondence as a constraint.

>>> for X in corresp(*test1(3, 4, 2, 2, 5, 5)): print(X) break{('r0', 'h0', 'd0'): ('s0', 't0', 'c0'), ('r1', 'h0', 'd0'): ('s0', 't0', 'c0'), ('r0', 'h1', 'd0'): ('s0', 't0', 'c0'), ('r1', 'h1', 'd0'): ('s0', 't0', 'c0'), ('r0', 'h2', 'd0'): ('s0', 't0', 'c0'), ('r1', 'h2', 'd0'): ('s0', 't0', 'c0'), ('r0', 'h3', 'd0'): ('s0', 't0', 'c0'), ('r1', 'h3', 'd0'): ('s0', 't0', 'c0'), ('r0', 'h0', 'd1'): ('s0', 't0', 'c0'), ('r1', 'h0', 'd1'): ('s0', 't0', 'c0'), ('r0', 'h1', 'd1'): ('s0', 't0', 'c0'), ('r1', 'h1', 'd1'): ('s0', 't0', 'c0'), ('r0', 'h2', 'd1'): ('s0', 't0', 'c0'), ('r1', 'h2', 'd1'): ('s0', 't0', 'c0'), ('r0', 'h3', 'd1'): ('s0', 't0', 'c0'), ('r1', 'h3', 'd1'): ('s0', 't0', 'c0'), ('r0', 'h0', 'd2'): ('s0', 't0', 'c0'), ('r1', 'h0', 'd2'): ('s0', 't0', 'c0'), ('r0', 'h1', 'd2'): ('s0', 't0', 'c0'), ('r1', 'h1', 'd2'): ('s0', 't0', 'c0'), ('r0', 'h2', 'd2'): ('s0', 't0', 'c0'), ('r1', 'h2', 'd2'): ('s0', 't0', 'c0'), ('r0', 'h3', 'd2'): ('s0', 't0', 'c0'), ('r1', 'h3', 'd2'): ('s0', 't0', 'c0')}But we must not forget that in a schedule it matters:the number of times a subject appears in the week,how many non-consecutive hours a subject has in each day, andhow many non-consecutive hours a teacher has in each day.

So this code could well be a first approximation.

Although the aim of this post is not to talk about how to generate schedules.

Brute force on logicWhen a small child has a problem with logic, he doesn’t seem to apply Kleene’s axioms to solve it; or any formal system product of some brilliant mind.

Reducing our axioms to the expression minimum sometimes does not help the resolution of our problems.

The mechanisms he uses seem to approach the Observer Pattern.

That is, try to apply simple operations on each of the apparitions within the expression.

Observer PatternTesting all combinations possible in a very well ordered structure could be a good technique to find fast solutions.

But, first of all, how the Observer Pattern works?Example of Observer PatternImagine that you are interested in a red dress, but you are not the only one interested.

As time goes by, it is possible that those kinds of dresses will appear in the store so, in order to go quickly to buy them, you give the store your phone number so they can call you.

Therefore, to apply the pattern, we must recognize a user subscription and a mechanism to notify everyone of any changes that occur.

How could this be applicable to logic?The Micro-machines reasonsWhen I offered an implementation capable of satisfying any Boolean formula in a loop I demanded a polynomial time, which would be neither less nor greater than n⁵, n being the number of clauses.

As explained below:The Boolean Satisfiability Problem, solved?Here I expose some ultimate techniques to make great tools for logic operations.

medium.

comHowever, O(n⁵) and o(n⁵) means that if for a size 10 (a Boolean formula of 10 clauses) entry we take 1 second for solving [10⁵ marks of time → 1 second], then for a size 20 entry we would take: 20⁵ = 2⁵ · 10⁵ → 2⁵ · 1 second = 32 seconds.

That’s why, even though the code will go much faster on future machines, we may be interested in faster results.

Preparing the structureTo solve any Boolean formula in record time taking advantage of the brute force on the observer pattern, we will need to put in an array all the variables, including the temporal ones.

Imagine an array that only stores Boolean values and the None value, and that when the value is not None all micro-machines that have subscribed to that cell will be notified (Observer Pattern).

In fact, it will be easier to work with this array if we could calculate its opposite through the index when accessing its elements.

That is, make some properties like : A[-X] = 1- A[X]class DiaconArray: def __init__(self, size): self.

body=[None]*size def __setitem__(self, position, value): if value == None: self.

body[position] = None elif position<0: self.

body[-position] = 1 – value else: self.

body[position] = value def __getitem__(self,position): if type(position) == slice: other = DiaconArray(1) other.

body = self.

body[position] return other elif self.

body[abs(position)] == None: return None elif position < 0: return 1 – self.

body[-position] else: return self.

body[position]You can find a link with the code at the end of this post.

Observers are constructed following a repeating logical operator pattern, i.

e.

all observers carry out the same logical operation.

In this case, we will use the so-called χ operator from Cryptanalysis.

Imagine we define χ as: chi = lambda x, y, z0: (x & (1^y)) ^ z0 Each observer will be composed by 4 temporal variables, where 3 must be the entry of χ, and the fourth one the output.

That means that if x, y and z0 were not None, the output could be solved by the formula above.

But, what could happen if the output were not None, and x and y…, then we had enough information to know the value of z0.

That’s why we have to define our micro-machine differently.

class Chi: opChi=[ lambda x,y,z0,z1:z0^z1 if y==0 else None, lambda x,y,z0,z1: z0^z1^1 if x==1 else None, lambda x,y,z0,z1:(x&(1^y))^z1, lambda x,y,z0,z1:(x&(1^y))^z0]In this case, we observe the four kind of operations we had to do if we wanted to guess the argument 0, 1, 2 or 3 in χ(x, y, z0, z1).

But what could we do if we only had some of the values instead of all the necessary ones?.The solution in the next code:X=["323121323020313010212010", #0000 "212010", #0001 "313010", #0010 "10", #0011 "323020", #0100 "20", #0101 "30", #0110 "0", #0111 "323121", #1000 "21", #1001 "31", #1010 "1", #1011 "32", #1100 "2", #1101 "3", #1110 "", #1111 ]If we knew all arguments but the fourth #1110 in χ(x, y, z0, z1), we only had to find the fourth "3" operator in opChi, and if we knew all but the third #1101, we only had to find the third "2" .

So logically, if we knew all arguments but the fourth AND the third #1100 we only had to find later or the third or the fourth operator "32" depending on which argument we deduce before.

class Chi: def __init__(self, n, op=[]): 'None means indeterminate' self.

observers=DiaconArray(n) self.

operators=op[:] self.

methods=[] #Invariant of the launchers # [(function, X, Y, Z0, Z1),.

] self.

launchers={} # observers no observed # {pos:[(posMet, posArg),.

],.

} # posArg respecting the string for K in range(n): self.

launchers[K]=[] for o in op: self.

_generateInvariant(o)In methods we put the string deduced in Chi.

X, and the positions in the array which are the arguments of the operation.

In launchers we put, for every None position claimed, what is the methods index, and the string function index of that None position.

We will notify the observer of all operators in _generateInvariant.

def _generateInvariant(self, operator): for op in operator: if abs(op)>=len(self.

observers): n=len(self.

observers) self.

observers+=DiaconArray(abs(op)-n+1) for K in range(n,len(self.

observers)): self.

launchers[K]=[] px,py,pz0,pz1=operator function=Chi.

X[Chi.

apply(self.

observers[px], self.

observers[py], self.

observers[pz0], self.

observers[pz1])] if len(function)==0: return False elif len(function)==1: value= Chi.

opChi[int(function)]( self.

observers[px], self.

observers[py], self.

observers[pz0], self.

observers[pz1]) self[(px,py,pz0,pz1)[int(function)]]=value return False elif function=="10": if not self.

observers[pz0]==self.

observers[pz1]: self[px]=1 self[py]=0 return False elif function=="20": if self.

observers[py]==1: self[pz0]=self.

observers[pz1] return False elif function=="30": if self.

observers[py]==1: self[pz1]=self.

observers[pz0] return False elif function=="21": if self.

observers[px]==0: self[pz0]=self.

observers[pz1] return False elif function=="31": if self.

observers[px]==0: self[pz1]=self.

observers[pz0] return False self.

methods.

append((function,px,py,pz0,pz1)) for k in range(4): Key=(px,py,pz0,pz1)[k] if self.

observers[Key]==None: self.

launchers[abs(Key)].

append( (len(self.

methods)-1,k)) return TrueTo understand the code you have to observe certain parts:apply method decodes the X index from the state None/not-None of each argument.

if len(function)==1means there is not needed a new Observer.

Because it is possible to solve the None argument directly.

There are some exceptions where it is not necessary a new Observer.

At last, the operator is added in methods and configured its every None argument launcher.

In my last version I implemented different ways to ensure a query: the higher the temperature parameter the more possibilities of giving a coherent response, but more operations will be carried out.

The Interface StructureAfter constructing the kernel of the Structure, you can notice that it is difficult to work with it: you need to imagine every logic formula as a combination of χ operators.

To solve that problem to test all the results, I have implemented in the same file the DiaconChi class.

class DiaconChi: def __init__(self,n): self.

C = Chi(2*n) self.

n = n self.

auxiliars = 1 self.

C[0] = 0 self.

C[1] = 1In this case we will use temporal variables in the odd positions of the array, and the user variables in the even positions.

Notice first temporal variable is 1 and first user variable is 0.

But the code we’re interested in is this one.

def _adjustN(self,*secuencia): for X in secuencia: if abs(X) >= self.

n: self.

n = abs(X) + 1def AND(self, result, *sec): self.

_adjustN(result) self.

_adjustN(*sec) R = 2 * sec[0] for op in sec[1:-1]: auxiliar = 2 * self.

auxiliars + 1 self.

auxiliars += 1 self.

C.

opera([R,-2*op,0,auxiliar]) R = auxiliar self.

C.

opera([R,-2*sec[-1],0,2*result])def _ANDaux(self, rAux, *sec): 'rAux is the output' self.

_adjustN(*sec) R = sec[0] for op in sec[1:-1]: auxiliar = 2 * self.

auxiliars + 1 self.

auxiliars += 1 self.

C.

opera([R, -op, 0, auxiliar]) R = auxiliar self.

C.

opera([R, -sec[-1], 0, rAux])def OR(self, result, *sec): self.

AND(-result, *tuple([-X for X in sec]))def SAT3(self, clauses): for c in clauses: self.

_ANDaux(0, -2*c[0], -2*c[1], -2*c[2])Considering,_adjustN is a method which makes the array longer if it is required by the variables.

opera is the native method that claims the χ operation.

SAT3 implements in the array a Boolean product of sum of three Boolean literals.

Let’s check it, (x + y + z)(¬x + ¬y + z)(x + ¬y + ¬z) = 1; if x=1 and z=0, what will happen with y?>>> C=DiaconChi(23)>>> C[0]0>>> C[1]>>> C.

SAT([(1,2,3),(-1,-2,3),(1,-2,-3)])>>> C[1]>>> C[2]>>> C[3]>>> C[1]=1>>> C[3]=0>>> C[2]0>>> C0100——————-About efficiency and precisionIn this section I will propose a code to test when the micro-machines works correctly and how fast they are in seconds.

from profile import timefrom random import randrangedef testGen(clauses, variables): cc = DiaconChi(variables) SAT3 = [[(randrange(variables)+1) * (2*randrange(2)-1) for Y in range(3)] for X in range(clauses)] cc.

SAT(SAT3) before = time.

time() try: for V in range(1, variables+1): if cc[V] is None: cc[V] = 0 except BadAssignment: return round(time.

time() – before), False elapsedTime = time.

time() – before for (A, B, C) in SAT3: if (cc[A] or cc[B] or cc[C]) == 0: raise "Fatal error"return round(elapsedTime, 4), TrueIn the previous code we can observe three possible returns:If there were a bad try, it would return time wasted and False.

If there were a solution, it would return time needed and True.

It there were a bug in the code (not expected), it will raise a “Fatal error”To get a good graph we will need something like this:def precision(clauses, variables, lots): T = 0 S = 0 for i in range(lots): time, sucess = testGen(clauses, variables) T += time S += int(sucess)return round(T/lots, 4), round(S/lots, 4)And this will return the pair (time, precision), averaging in lots.

You can consider time is dependent on the number of clauses (Observers), while precision of the ratio between variables and clauses (interconnectivity between Observers).

The Code and their conclusionsConsidering there are some other versions with other operators, this can be interesting to understand how easy it is to create an exclusive machine that gives unexpectedly good results.

One can think how easy it can be to distribute the Observers by different machines in a network.

So these applications are specially designed for situations that require a quick response and have an efficient distribution network.

You can test everything and find the code in two files of my book The two exact philosophies: DiaconArray.

py and diaconChi.

py.

. More details

Leave a Reply