We put into practice the knowledge gained in the course MIT 6.00x (edx.org)

In the comments to my post about the course 6.002x MITx I was asked a question - was it useful in life. And I answered - yes, of course, here in the morning while I was brushing my teeth, I considered the RC constant ... But there was no proof. Since then I have completed two more courses - UC Berkeley CS188.1x Introduction to Artificial Intelligence (registration is open on February 18) and MITx: 6.00x Introduction to Computer Science and Programming . And if after CS188.1x I was just full of emotions and did not know where to stick my freshly acquired knowledge (except how to solve the knight's progress problem ), then after passing 6.00x I had a chance to show off.

The fact is that I downloaded a set of puzzles Mind Games in the appstore. And hopelessly stuck at the level of "Chinese checkers". It was possible to find the passage on the Internet , but this is no longer our method. Now we have a mustache. The world will never be the same again.

Chinese checkers

There is a field, there are chips on the field. One of the cells is empty. We can move only by eating a checker on a nearby cage, jumping over it. Diagonally eat checkers impossible. The initial state:

  oooooooooooooooo.  oooooooooooooooo 

The following move is possible, for example, like this:

  oooooooooooooo.  .  ooooooooooooooooo 

As a result, there should be only one (s). That is such a simple task. Hehe, I thought, about three minutes to decide. A few days later I was scratching hard in the back of my head and trying to give birth to some effective tactic. The task, ****, was not solved. Have to use a python.
')
From the courses I made out that in all search tasks you need to solve only three subtasks (God, to whom I am telling this - this is probably the basics):

1. Encode system status
2. Check if a particular state is a solution.
3. Generate the following states

I struggled with something, I struggled with state coding, and as a result I stopped on a simple line 49 characters long:

initState = ' ooo '+' ooo '+'ooooooo'+'o..oooo'+'ooooooo'+' ooo '+' ooo ' 

This greatly facilitates the decision of the first paragraph, but threatens the problems of the third. Well, okay. In general, as we were taught, we write the Problem class:

 class Problem(object): def __init__(self, initState): self.initState = initState def isGoal(self, state): if state.count('o') > 1: return False else: return True def generateSuccessors(self, state): res = [] idx = 0 for c in state: if c == '.': ##we can move here res += self.getValidMoves(state, idx) idx += 1 return res def getValidMoves(self, state, idx): res = [] ## get North: if idx in [16,17,18,23,24,25,28,29,30,31,32,33,34,37,38,39,44,45]: sN = state[:] if sN[idx-7] == 'o': if sN[idx-14] =='o': sN = sN[0:idx-14]+'.'+sN[idx-13:idx-7]+'.'+sN[idx-6:idx]+'o'+sN[idx+1:] res.append(sN) ## get South: if idx in [2,3,4,9,10,11,14,15,16,17,18,19,20,23,24,25,30,31,32]: sS = state[:] if sS[idx+7] == 'o': if sS[idx+14] =='o': sS = sS[0:idx]+'o'+sS[idx+1:idx+7]+'.'+sS[idx+8:idx+14]+'.'+sS[idx+15:] res.append(sS) ## get West: if idx in [4,11,16,17,18,19,20,23,24,25,26,27,30,31,32,33,34,39,46]: sW = state[:] if sW[idx-1] == 'o': if sW[idx-2] =='o': sW = sW[0:idx-2]+'..o'+sW[idx+1:] res.append(sW) ## get East: if idx in [2,9,14,15,16,17,18,21,22,23,24,25,28,29,30,31,32,37,44]: sE = state[:] if sE[idx+1] == 'o': if sE[idx+2] =='o': sE = sE[:idx]+'o..'+sE[idx+3:] res.append(sE) return res def printState(self, state): res = '' for x in range(7): for y in range(7): res += state[x*7+y]+' ' res+='\r\n' print res 

In fact, here we determine the initial value of the system during the initialization of the problem and determine the methods for solving paragraphs 2 and 3. Fortunately, check any condition on whether it is a solution, it’s very simple - we count how many chips are left on the board - if there is more than one, something else needs to be done.
But with the generation of valid next moves, I suffered a little bit because the string is one-dimensional and the board is two-dimensional. And it is necessary to somehow bring each other. Perhaps, even most likely, I have a double-barcode, but in my excuse I want to say that I, it seems, was able to apply the KISS principle, about which I read so much in Habré. And therefore we go on the board, on each empty cell we look in all directions - are there two chips in that direction. If yes, then replace those chips with empty places, and the empty space itself - with a chip. And give, as the next move.
A few observations:

• In this problem, the solution is always at the bottom of the graph. That means breadth-first search will always be as long as possible.
• In this task it is impossible to come to one of the previous states. Accordingly, it is possible not to bathe in checking for the earring of the graph (see further, everything is actually more interesting), but I was just taught that and I did it
• This task does not come up with heuristics. At least it does not come up easy. Any move leads to a decrease in the number of chips by 1. It means that it is possible to evaluate the “goodness” or “badness” of the state only by the mutual position of the chips. This is nontrivial

Therefore, the algorithm will be simple:

 def dfs(p): fringe = [[p.initState]] tried = set() while fringe: cur = fringe.pop() tried.add(cur[-1]) for lm in p.generateSuccessors(cur[-1]): if p.isGoal(lm): return cur+[lm] else: if lm not in tried: fringe.append(cur+[lm]) return None 

Here p is an object of class Problem

 p = Problem(initState) 

Everything is ready, we start and go to drink tea. Twelve years, as the computer will have to go through the worst case 2 ^ 32 combinations. Then I cheated and immediately reduced the number of combinations by half, making the first move for the computer and setting the initial state of the chips after the first move. Further, I noticed that the board is centrally symmetrical, which means there will always be four duplicate states, taking into account the rotation of the board by 90, 180 and 270 degrees. Slightly complicate the verification of the opened graph node:

 def rotateField(field): res = '' for i in range(7): for j in range(7): res += field[7*j+i] return res 

...

 if lm not in tried: lmr = rotateField(lm) if lmr not in tried: if rotateField(lmr) not in tried: if rotateField(lm) not in tried: fringe.append(cur+[lm]) 

Well, I still cut a few branches, including checking for the state when there are chips on the board, but they are guaranteed far away from each other and will not be able to devour each other:

  oooooo
 .  .  .  .  .  .  .  
 .  .  .  .  .  .  . 
 .  .  .  .  .  .  . 
     oooooo 

 def checkDeadCombinations(state): ''' False = dead True - combination is OK''' if '.'*21 in state: if '.' in state[:14] and '.' in state[-15:]: return False if '.'*21 in rotateField(state): if '.' in state[:14] and '.' in state[-15:]: return False 

Well, now there is a hope that I will live to see the computer solve this problem for me :-)

Dominoes

Previous problem solved, what led his wife to admiration, and immediately stumbled into the next. A box of dominoes is given (28 pieces, standard). You need to choose 8 knuckles and put them in a square 4x4, so that it turns out two vertically standing rows of four knuckles in each.

 Hhhh
 Hhhh 

The amounts in rows, columns and diagonals must be equal to six:
Here you can apply the search for a solution to a problem with constraints, but, having understood the principle, I have not learned how to implement it in code. Therefore, we stupidly brute force.
Generating knuckles:

 dices = [] for i in range(7): for j in range(i,7): dices.append((i,j)) 

As a result, we have a sheet of pairs of type (0,0), (1,0), etc. for each domino bone.
Since the sum of each line is six, four lines, we need all the combinations of chips giving a total of 24. I sat down, squeaked on the topic of how to make all these combinations, then I remembered that python comes with batteries included and just clicked On the power button:

 def iterWorkingSets(dices): for cmb in itertools.combinations(dices, 8): ds = 0 for dice in cmb: ds += dice[0] ds += dice[1] if ds == 24: yield cmb 

As a result, we have eliminated all the combinations of knuckles, which are guaranteed not to give a solution. Then I just went through all the combinations and for each combination I cross-knit, checking if there is a solution:

 def checkArr(arr): diag = 0 idx = 0 ##print arr for row in arr: diag += row[idx] idx += 1 if sum(row) != 6: #print 'row', idx, 'is not 6' return False if diag !=6: #print 'diag 1 is not 6' return False diag = 0 idx = 3 arr = arr.transpose() for row in arr: diag += row[idx] idx -= 1 if sum(row) != 6: #print 'column', idx, 'is not 6' return False if diag != 6: #print 'diag 2 is not 6' return False return True 

There was no solution. I launched again. There was no solution again. If I smoked, I would go for a smoke. Something is wrong here, I thought. Bruteforser is not so easy to take, the decision should be, which means an error in the bruteforcer. And he began to look for a mistake. No error was found. After drinking a certain amount of coffee, I went to play the game itself in order to understand what I was doing wrong. I started the game, left the knuckles on the field and began to move them and turn over ... TURN! Brute Forcer did not turn knuckles!
Oh, and how is it, damn, write? Again itertools, a generic superset for range (6), then for each combination we run it through the superset, turning the knuckles upside down. Oh, mom.

 ###        allsubsets = lambda n: list(itertools.chain(*[itertools.combinations(range(n), ni) for ni in range(n+1)])) 

 for wc in iterWorkingSets(dices): wc = list(wc) print 'I here loop through all set of dices that produce 24' print 'This is comb #', cmbNum, ':' print wc cmbNum += 1 for turn in allsubsets(6): tc = wc[:] for k in range(6): if k in turn: tc[k] = wc[k][::-1] else: tc[k] = wc[k] #print 'This is subcom of comb #', cmbNum, ':' #print tc for c in itertools.permutations(tc): ''' I here loop through all re-combinations of the same set''' allNum = [] for a in c: allNum+=list(a) arr = pylab.array(allNum).reshape(4,4) if checkArr(arr): print 'Solution:', arr break print 'Solution was not found' 

We start. At first there are no solutions, since “heavy bones” are present in the sets:

 This is comb # 3 : [(0, 0), (0, 1), (0, 2), (0, 3), (0, 4), (0, 5), (1, 1), (2, 5)] Solution was not found 

But then, starting with the nth combination, solutions begin to pour in:

  [[0 0 6 0]
  [1 4 0 1]
  [1 2 0 3]
  [4 0 0 2]] 

The bruteforser was meeed, but working.
Well that's all. Now, if you ask me if edx courses have been useful to me in life, I will proudly answer “Yes!” And give a link to this article.