houses.py

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()

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

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, 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