Putting into practice the knowledge gained on the MIT 6.00x course (edx.org)
In the comments to my post about the 6.002x MITx course, I was asked a question - was it useful in life. And I answered - yes, of course, here in the morning while brushing my teeth, I calculated the RC constant ... But there were no proofs. Since then I have completed two more courses - UC Berkeley CS188.1x Introduction to Artificial Intelligence (registration 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 freshly obtained knowledge (except how to solve the problem of the horse’s progress ), then after passing 6.00x I got the chance to show off.
The fact is that in the appstore I downloaded a set of puzzles Mind Games. And hopelessly stuck at the level of "Chinese Drafts." You could find a walkthrough on the Internet , but this is no longer our method. Now we ourselves with a mustache. The world will never be the same again.
There is a field, there are chips on the field. One of the cells is empty. We can only move by eating a checker on a neighboring cell, jumping over it. It is impossible to eat checkers diagonally. The initial state:
The following move is possible, for example, this:
As a result, there should be only one (s) left. Here is such a simple task. Hehe, I thought, about three minutes to a decision. A few days later, I scratched my head tightly in the back of my head and tried to give birth to some active tactics. The problem, ****, was not solved. Have to use python.
I learned from the courses that in all the search tasks, only three sub-tasks need to be solved (God, to whom I tell you this is probably the basics):
Something I fought, struggled with state encoding, and eventually settled on a simple line of 49 characters long:
This greatly facilitates the solution of the first paragraph, but threatens with problems of the third. Well, okay. In general, as we were taught, we write the Problem class:
In fact, here we determine the initial value of the system during the initialization of the problem and determine the methods for solving items 2 and 3. Fortunately, checking any condition for whether it is a solution is extremely simple - consider how many chips are left on the board - if there are more than one, then we still have to work.
But with the generation of valid next moves, I suffered a little, as the line is one-dimensional, and the board is two-dimensional. And we must somehow bring it to each other. Perhaps, even most likely, I ran into the code, but in my defense I want to say that I, it seems, was able to apply the KISS principle, about which I read so much on the hub And so we go along the board, on each empty cell we look in all directions - are there two chips in that direction. If so, then we replace those chips with empty places, and the empty space itself with a chip. And give, as the next move.
A few observations:
Therefore, the algorithm will be simple:
Here p is an object of class Problem
Everything is ready, we start and we leave to drink tea. Twelve years, since the computer will have to sort out in the worst case 2 ^ 32 combinations. Then I cheated and immediately halved the number of combinations, making the first move for the computer and setting the initial state of the position 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. Let's slightly complicate the check for the expanded nodes of the graph:
...
Well, after all, I cut off several branches, including checking for the state when there are chips on the board, but they are guaranteed to be far from each other and will not be able to gobble up each other:
Well, now there is a hope that I will live up to the moment when the computer solves this problem for me :-)
I solved the previous problem, which brought my wife in admiration, and immediately buried myself in the next. Given a box of dominoes (28 pieces, standard). You need to select 8 knuckles and fold them into a 4x4 square, so that you get two vertically standing rows of four knuckles in each.
The sums of the rows, columns and diagonals should be equal to six:
Here you can apply the search for a solution to the problem with restrictions, but, having understood the principle, I still have not learned how to implement it in the code. Therefore, we will stupidly brute force.
Generate knuckles:
As a result, we have a sheet of pairs of the type (0,0), (1,0), etc. for every domino bone.
Since the sum in each row is six, the rows are four, then we need all combinations of chips giving a total of 24. I sat there, gritted my brains on how to make all these combinations, then I remembered that python comes with batteries included and just clicked on the power button:
As a result, we eliminated all the knuckle combinations that are guaranteed not to give a solution. Then I simply went through all the combinations and for each combination I rearranged the knuckles, checking if there was a solution:
There was no decision. I ran it again. There was no decision again. If I smoked, I would go for a smoke. Something's wrong here, I thought. You can’t easily pick up the brute force forwarder, there must be a solution, which means a mistake in the brute force. And he began to look for a mistake. The error was not found. After drinking a certain amount of coffee, I went to play the game itself to understand - what am I doing wrong. He started the game, left the knuckles on the field and began to move them and turn them over ... TURN OVER! Brutforser did not turn knuckles!
Oh, and how is it, damn it, to write? Again itertools, we generate the superset for range (6), then for each combination we run it through the superset, turning over the knuckles. Oh mom.
We start. At first, there are no solutions, since there are “heavy bones” in the sets:
But then, starting with the nth combination, decisions begin to pour in:
Brutforser turned meeeled, but working.
That's it. Now, if you ask me if edx courses have come in handy in my life, I will proudly answer “Yes!” and give a link to this article.
The fact is that in the appstore I downloaded a set of puzzles Mind Games. And hopelessly stuck at the level of "Chinese Drafts." You could find a walkthrough on the Internet , but this is no longer our method. Now we ourselves with 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 only move by eating a checker on a neighboring cell, jumping over it. It is impossible to eat checkers diagonally. The initial state:
ooo
ooo
ooooooo
ooo. ooo
ooooooo
ooo
ooo The following move is possible, for example, this:
ooo
ooo
ooooooo
o. . oooo
ooooooo
ooo
ooo As a result, there should be only one (s) left. Here is such a simple task. Hehe, I thought, about three minutes to a decision. A few days later, I scratched my head tightly in the back of my head and tried to give birth to some active tactics. The problem, ****, was not solved. Have to use python.
I learned from the courses that in all the search tasks, only three sub-tasks need to be solved (God, to whom I tell you this is probably the basics):
- Encode system status
- Check if a certain state is a solution
- Generate the following states
Something I fought, struggled with state encoding, and eventually settled on a simple line of 49 characters long:
initState = ' ooo '+' ooo '+'ooooooo'+'o..oooo'+'ooooooo'+' ooo '+' ooo '
This greatly facilitates the solution of the first paragraph, but threatens with 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 items 2 and 3. Fortunately, checking any condition for whether it is a solution is extremely simple - consider how many chips are left on the board - if there are more than one, then we still have to work.
But with the generation of valid next moves, I suffered a little, as the line is one-dimensional, and the board is two-dimensional. And we must somehow bring it to each other. Perhaps, even most likely, I ran into the code, but in my defense I want to say that I, it seems, was able to apply the KISS principle, about which I read so much on the hub And so we go along the board, on each empty cell we look in all directions - are there two chips in that direction. If so, then we 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. So 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, you can not take a steam bath by checking for a graph loop (see further, everything is actually more interesting), but they just taught me that and I did it
- Heuristic is not thought up for this task. At least she does not come up simply. Any move leads to a decrease in the number of chips by 1. Therefore, it is possible only by the relative position of the chips to evaluate the “good” or “bad” state. And 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 we leave to drink tea. Twelve years, since the computer will have to sort out in the worst case 2 ^ 32 combinations. Then I cheated and immediately halved the number of combinations, making the first move for the computer and setting the initial state of the position 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. Let's slightly complicate the check for the expanded nodes of the graph:
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, after all, I cut off several branches, including checking for the state when there are chips on the board, but they are guaranteed to be far from each other and will not be able to gobble up each other:
ooo
ooo
. . . . . . .
. . . . . . .
. . . . . . .
ooo
ooo 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 up to the moment when the computer solves this problem for me :-)
Dominoes
I solved the previous problem, which brought my wife in admiration, and immediately buried myself in the next. Given a box of dominoes (28 pieces, standard). You need to select 8 knuckles and fold them into a 4x4 square, so that you get two vertically standing rows of four knuckles in each.
Hhhh Hhhh
The sums of the rows, columns and diagonals should be equal to six:
Here you can apply the search for a solution to the problem with restrictions, but, having understood the principle, I still have not learned how to implement it in the code. Therefore, we will stupidly brute force.
Generate 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 the type (0,0), (1,0), etc. for every domino bone.
Since the sum in each row is six, the rows are four, then we need all combinations of chips giving a total of 24. I sat there, gritted my brains on 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 eliminated all the knuckle combinations that are guaranteed not to give a solution. Then I simply went through all the combinations and for each combination I rearranged the knuckles, checking if there was 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 decision. I ran it again. There was no decision again. If I smoked, I would go for a smoke. Something's wrong here, I thought. You can’t easily pick up the brute force forwarder, there must be a solution, which means a mistake in the brute force. And he began to look for a mistake. The error was not found. After drinking a certain amount of coffee, I went to play the game itself to understand - what am I doing wrong. He started the game, left the knuckles on the field and began to move them and turn them over ... TURN OVER! Brutforser did not turn knuckles!
Oh, and how is it, damn it, to write? Again itertools, we generate the superset for range (6), then for each combination we run it through the superset, turning over the knuckles. 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 there are “heavy bones” 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, decisions begin to pour in:
[[0 0 6 0] [1 4 0 1] [1 2 0 3] [4 0 0 2]]
Brutforser turned meeeled, but working.
That's it. Now, if you ask me if edx courses have come in handy in my life, I will proudly answer “Yes!” and give a link to this article.