Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
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()
@zenspider

This comment has been minimized.

Copy link

commented Dec 20, 2016

It appears that the second iteration does not actually terminate. The first iteration does.

@agnanachandran

This comment has been minimized.

Copy link
Owner Author

commented Dec 27, 2016

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.

@andrewczgithub

This comment has been minimized.

Copy link

commented Jul 16, 2019

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

@agnanachandran

This comment has been minimized.

Copy link
Owner Author

commented Jul 20, 2019

@andrewczgithub

This comment has been minimized.

Copy link

commented Jul 21, 2019

Hi @agnanachandran !
You are an absolute champion!! thankyou!!
Will give it a go!
Cheers,
Andrew

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.