-
-
Save agnanachandran/1cdb49e8360d4c1ac8bea877c252aed3 to your computer and use it in GitHub Desktop.
import math | |
import random | |
def get_random_neighbour(state): | |
neighbour = [house[:] for house in state] # Deep copy | |
i, j = random.sample(xrange(5), 2) | |
attr_idx = random.randint(0, 4) | |
neighbour[i][attr_idx], neighbour[j][attr_idx] = neighbour[j][attr_idx], neighbour[i][attr_idx] | |
return neighbour | |
NAT = 0 | |
COL = 1 | |
ANI = 2 | |
BEV = 3 | |
CIG = 4 | |
def cost_of_state(state): | |
cost = 15 | |
for i, h in enumerate(state): | |
cost -= sum([ | |
h[NAT] == 'brit' and h[COL] == 'red', | |
h[NAT] == 'swede' and h[ANI] == 'dog', | |
h[NAT] == 'dane' and h[BEV] == 'tea', | |
i < 4 and h[COL] == 'green' and state[i+1][COL] == 'white', | |
h[COL] == 'green' and h[BEV] == 'coffee', | |
h[CIG] == 'pall mall' and h[ANI] == 'bird', | |
h[COL] == 'yellow' and h[CIG] == 'dunhill', | |
i == 2 and h[BEV] == 'milk', | |
i == 0 and h[NAT] == 'norwegian', | |
h[CIG] == 'blends' and ((i > 0 and state[i-1][ANI] == 'cat') or (i < 4 and state[i+1][ANI] == 'cat')), | |
h[ANI] == 'horse' and ((i > 0 and state[i-1][CIG] == 'dunhill') or (i < 4 and state[i+1][CIG] == 'dunhill')), | |
h[CIG] == 'blue master' and h[BEV] == 'root beer', | |
h[NAT] == 'german' and h[CIG] == 'prince', | |
h[NAT] == 'norwegian' and ((i > 0 and state[i-1][COL] == 'blue') or (i < 4 and state[i+1][COL] == 'blue')), | |
h[CIG] == 'blends' and ((i > 0 and state[i-1][BEV] == 'water') or (i < 4 and state[i+1][BEV] == 'water')), | |
]) | |
return cost | |
def sa(initial): | |
current = initial | |
current_cost = cost_of_state(current) | |
temp = 1.0 | |
num_iterations = 0 | |
while current_cost > 0: | |
neighbour = get_random_neighbour(current) | |
neighbour_cost = cost_of_state(neighbour) | |
cost_delta = neighbour_cost - current_cost | |
if cost_delta <= 0 or random.random() < math.exp(-cost_delta/temp): | |
current, current_cost = neighbour, neighbour_cost | |
num_iterations += 1 | |
if num_iterations % 500 == 0 and temp > 0.20: | |
temp -= 0.05 | |
return current, num_iterations | |
def main(): | |
nationalities = [ 'dane', 'brit', 'swede', 'norwegian', 'german' ] | |
colours = [ 'yellow', 'red', 'white', 'green', 'blue' ] | |
animals = [ 'horse', 'cat', 'bird', 'fish', 'dog' ] | |
beverages = [ 'water', 'tea', 'milk', 'coffee', 'root beer' ] | |
cigars = [ 'pall mall', 'prince', 'blue master', 'dunhill', 'blends' ] | |
attributes = [nationalities, colours, animals, beverages, cigars] | |
NUM_HOUSES = 5 | |
initial = [] | |
for i in xrange(NUM_HOUSES): | |
initial.append([attr[i] for attr in attributes]) | |
random.seed(100) | |
solution, iterations = sa(initial) | |
for house in solution: | |
print house | |
print 'Number of iterations:', iterations | |
if __name__ == "__main__": | |
main() |
Should be fixed now! My second revision also had the same issue of not including the end of the range, as you mentioned on my blog post.
Hi @agnanachandran!
I am trying to use your method to solve a similar problem.
The clues we have been given are as follows-
5 cars were parked in a row from left to right, that is first, second, ... , and last at the Hertz depot outside the Armidale Airport.
The Toyota Camry was hired at 6:00am by a British couple.
The car in the middle had a black colour.
The Hyundai Accent left the depot at 9:00am.
The Holden Barina with a blue colour was to the left of the car that carries the British couple.
To the right of the car hired by a French lady was the car going to Gold Coast.
The Nissan X-Trail was heading for Sydney.
To the right of the car carrying a Chinese businessman was the car with a green colour.
The car going to Newcastle left at 5:00am.
The Honda Civic left at 7:00am and was on the right of the car heading for Gold Coast.
The car with a red colour was going to Tamworth.
To the left of the car that left at 7:00am was the car with a white colour.
The last car was hired by an Indian man.
The car with a black colour left at 8:00am.
The car carrying an Indian man was to the right of the car hired by a Chinese businessman.
The car heading for Tamworth left at 6:00am.
Which car was going to Port Macquarie? Which car was hired by a Canadian couple?
So I have made an attempt and the code is below-
mport math
import random
def get_random_neighbour(state):
neighbour = [cars[:] for cars in state] # Deep copy
i, j = random.sample(xrange(5), 2)
attr_idx = random.randint(0, 4)
neighbour[i][attr_idx], neighbour[j][attr_idx] = neighbour[j][attr_idx], neighbour[i][attr_idx]
return neighbour
NAT = 0
COL = 1
DEST = 2
TIM = 3
CT = 4
def cost_of_state(state):
cost = 15
for i, h in enumerate(state):
cost -= sum([
h[NAT]=='british' and h[TIM]=='6am' and h[CT]=='toyota',
i==2 and h[COL]=='black',
h[CT]=='hyundai' and h[TIM]=='9am',
i<4 and h[CT]=='holden' and h[COL]=='blue' and state[i+1][NAT]=='british',
i>0 and h[DEST]=='gold_coast' and state[i-1][NAT]=='french',
h[CT]=='nissan' and h[DEST]=='sydney',
i>0 and h[COL]=='green' and state[i-1][NAT]=='chinese',
h[NAT]=='newcastle' and h[TIM]=='5am',
i>0 and h[CT]=='honda' and h[TIM]=='7am' and state[i-1][DEST]=='gold_coast',
h[COL]=='red' and h[DEST]=='tamworth',
i<4 and h[COL]=='white' and state[i+1][TIM]=='7am',
i==4 and h[NAT]=='indian',
h[COL]=='black' and h[TIM]=='8am',
i>0 and h[NAT]=='indian' and state[i-1][NAT]=='chinese',
h[DEST]=='tamworth' and h[TIM]=='6am',
])
return cost
def sa(initial):
current = initial
current_cost = cost_of_state(current)
temp = 1.0
num_iterations = 0
while current_cost > 0:
neighbour = get_random_neighbour(current)
neighbour_cost = cost_of_state(neighbour)
cost_delta = neighbour_cost - current_cost
if cost_delta <= 0 or random.random() < math.exp(-cost_delta/temp):
current, current_cost = neighbour, neighbour_cost
print(current_cost)
num_iterations += 1
print(num_iterations)
if num_iterations % 500 == 0 and temp > 0.20:
temp -= 0.05
return current, num_iterations
def main():
nationalities = [ 'british', 'french', 'chinese', 'indian', 'canadian' ]
colours = [ 'red', 'black', 'blue', 'green', 'white' ]
car_type = [ 'toyota', 'hyundai', 'nissan', 'honda', 'holden' ]
time = [ '6am', '7am', '8am', '9am', '5am' ]
destination = [ 'newcastle', 'gold_coast', 'tamworth', 'sydney', 'port_macquarie' ]
attributes = [nationalities, colours, car_type, time, destination]
NUM_CARS = 5
initial = []
for i in xrange(NUM_CARS):
initial.append([attr[i] for attr in attributes])
random.seed(100)
solution, iterations = sa(initial)
for cars in solution:
print cars
print 'Number of iterations:', iterations
if name == "main":
main()
I think my issue is located in the cost function but i cant find where I went wrong?
Could please have a look provide an opinion.
Sincere thanks in advance.
Best regards,
Andrew
Hi @agnanachandran !
You are an absolute champion!! thankyou!!
Will give it a go!
Cheers,
Andrew
It appears that the second iteration does not actually terminate. The first iteration does.