Last active
April 16, 2021 05:47
-
-
Save agnanachandran/1cdb49e8360d4c1ac8bea877c252aed3 to your computer and use it in GitHub Desktop.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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() |
Hi,
Not sure if you still need help, but I noticed two issues. After resolving
them I was able to run the code and produce the correct result:
1) `h[NAT]=='newcastle' and h[TIM]=='5am'` should be `h[DEST]=='newcastle'
and h[TIM]=='5am'`
2) The order of the attributes in the state needs to match the values of "NAT",
"COL", etc., otherwise the state representations will be wrong. In this
case, you just need to have CT = 2, and DEST = 4 (they were swapped before).
Hope this helps!
…On Mon, Jul 15, 2019 at 9:49 PM andrewczgithub ***@***.***> wrote:
Hi @agnanachandran <https://github.com/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 mad an attempt and this is the code i have written-
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
—
You are receiving this because you were mentioned.
Reply to this email directly, view it on GitHub
<https://gist.github.com/1cdb49e8360d4c1ac8bea877c252aed3?email_source=notifications&email_token=AAMKXD2JBJPNLUMRKD54GZLP7VHO3A5CNFSM4ID5AWG2YY3PNVWWK3TUL52HS4DFVNDWS43UINXW23LFNZ2KUY3PNVWWK3TUL5UWJTQAFVLTQ#gistcomment-2971448>,
or mute the thread
<https://github.com/notifications/unsubscribe-auth/AAMKXD7KARH6WHKE2FEJWALP7VHO3ANCNFSM4ID5AWGQ>
.
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
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
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([
def sa(initial):
current = initial
current_cost = cost_of_state(current)
temp = 1.0
num_iterations = 0
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' ]
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