In [9]:
import numpy as np
import svgwrite
from IPython.display import SVG
from IPython.display import HTML
In [10]:
blank = 0
vcar = 4
vtruck = 5
hcar = 6
htruck = 7
CAR_SYMBOLS = ['Q', 'A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'J', 'K', 'L']
TRUCK_SYMBOLS = ['T', 'R', 'W', 'Z']
CAR_COLORS = ['#7FFF00', '#7FFFD4', '#D2691E', '#8B008B', '#BDB76B'\
'#8B0000', '#FF1493', '#1E90FF', '#FFD700', '#ADFF2F',\
'#CD5C5C', '#F0E68C']
TRUCK_COLORS = ['#F08080', '#FFA07A', '#FF00FF', '#00FA9A']
RED_COLOR = '#FF0000'
RED_SYMBOL = 'X'
In [11]:
space_size = 30
board_size = 6*space_size
def svg_base():
dwg = svgwrite.Drawing('nosave.svg',(board_size,board_size),debug=True)
dwg.add(dwg.rect(insert=(0,0),size=(board_size,board_size),fill='#E6E6E6'))
#dwg.add(dwg.rect(insert=(0,0),size=(board_size,board_size),fill='rgb(211,211,211)'))
for x in range(7):
dwg.add(dwg.line((30*x,0),(30*x,180),stroke='black',stroke_width=2))
dwg.add(dwg.line((0,30*x),(180,30*x),stroke='black',stroke_width=2))
return dwg
# TEST
dwg = svg_base()
HTML(dwg.tostring())
Out[11]:
In [12]:
# orientation values: 'vcar',hcar',vtruck','htruck'
# color is hex value color (e.g. #7FFFD4)
space_size = 30
board_size = 6 * space_size
svg_border = 3
svg_round_radius = 5
svg_size = {}
svg_size['hcar'] = (2*space_size - 2*svg_border , space_size - 2*svg_border)
svg_size['vcar'] = (space_size - 2*svg_border, 2*space_size - 2*svg_border)
svg_size['vtruck'] = (space_size - 2*svg_border , 3*space_size - 2*svg_border)
svg_size['htruck'] = (3*space_size - 2*svg_border, space_size - 2*svg_border)
#dwg.add(dwg.rect(insert=(65, 35), size=(50, 20),rx=5,ry=5,fill='green', stroke_width=3))
def svg_add_piece(dwg,nd_x,nd_y,orientation,color,text):
car_x = nd_y* space_size + svg_border
car_y = nd_x*space_size + svg_border
size = svg_size[orientation]
dwg.add(dwg.rect(insert=(car_x,car_y),size=size,rx=svg_round_radius,ry=svg_round_radius,fill=color, stroke_width=3))
c_x = car_x + size[0]/2.0
c_y = car_y + size[1]/2.0
dwg.add(dwg.text(text,insert=(c_x,c_y),style='fill:black;text-anchor:middle;alignment-baseline:central'))
return dwg
# TEST
dwg = svg_base()
dwg = svg_add_piece(dwg, 0,0,'vcar','blue','P')
dwg = svg_add_piece(dwg, 1,1,'hcar','pink','Q')
dwg = svg_add_piece(dwg, 2,2,'vtruck','green','R')
dwg = svg_add_piece(dwg, 3,3,'htruck','yellow','T')
HTML(dwg.tostring())
Out[12]:
In [13]:
v = np.array([blank]*36).reshape(6,6)
v
Out[13]:
In [14]:
def svg_from_state(t,red_cols):
'''
input t: numpy array modeling a RH board configuration
input red_cols: 2-element array [c1,c2] that marks the columns of the red car
output: instance of svgwrite drawing
'''
v = np.copy(t)
c1,c2 = red_cols
car_colors = CAR_COLORS[:]
truck_colors = TRUCK_COLORS[:]
truck_symbols = TRUCK_SYMBOLS[:]
car_symbols = CAR_SYMBOLS[:]
dwg = svg_base()
# zero out red car. We know how to mark it visually
v[2,c1] = blank
v[2,c2] = blank
dwg = svg_add_piece(dwg,2,c1,'hcar',RED_COLOR,RED_SYMBOL)
vcars_y =np.unique(np.where(v==vcar)[1])
for y in vcars_y:
for x in np.where(v[:,y] == vcar)[0][0::2]:
dwg = svg_add_piece(dwg,int(x),int(y),'vcar',car_colors.pop(),car_symbols.pop())
hcars_x = np.unique(np.where(v==hcar)[0])
for x in hcars_x:
for y in np.where(v[x,:]==hcar)[0][0::2]:
dwg = svg_add_piece(dwg,int(x),int(y),'hcar',car_colors.pop(),car_symbols.pop())
vtrucks_y = np.unique(np.where(v==vtruck)[1])
for y in vtrucks_y:
for x in np.where(v[:,y] == vtruck)[0][0::3]:
dwg = svg_add_piece(dwg,int(x),int(y),'vtruck',truck_colors.pop(),truck_symbols.pop())
htrucks_x = np.unique(np.where(v==htruck)[0])
for x in htrucks_x:
for y in np.where(v[x,:]==htruck)[0][0::3]:
dwg = svg_add_piece(dwg,int(x),int(y),'htruck',truck_colors.pop(),truck_symbols.pop())
return dwg
In [15]:
# TEST
t = np.zeros((6,6),dtype=int)
t[2,0:2] = hcar
t[1,4:6] = hcar
t[2:4,4] = vcar
#t[0,2:5] = htruck
t[0,1:4] = htruck
t[3:6,2] = vtruck
t[4:,0] = vcar
t
Out[15]:
In [16]:
dwg = svg_from_state(t,[0,1])
HTML(dwg.tostring())
Out[16]:
In [17]:
def svg_from_state_generated_order(t,red_cols):
v = np.copy(t)
c1,c2 = red_cols
car_colors = CAR_COLORS[:]
truck_colors = TRUCK_COLORS[:]
truck_symbols = TRUCK_SYMBOLS[:]
car_symbols = CAR_SYMBOLS[:]
dwg = svg_base();
# zero out red car. We explicitly know how to mark it visually
v[2,c1] = blank
v[2,c2] = blank
dwg = svg_add_piece(dwg,2,c1,'hcar',RED_COLOR,RED_SYMBOL)
end_positions = []
vcars_y =np.unique(np.where(v==vcar)[1])
for y in vcars_y:
for x in np.where(v[:,y] == vcar)[0][0::2]:
#dwg = svg_add_piece(dwg,int(x),int(y),'vcar',car_colors.pop(),car_symbols.pop())
end_positions.append([int(x),int(y)])
hcars_x = np.unique(np.where(v==hcar)[0])
for x in hcars_x:
for y in np.where(v[x,:]==hcar)[0][0::2]:
#dwg = svg_add_piece(dwg,int(x),int(y),'hcar',car_colors.pop(),car_symbols.pop())
end_positions.append([int(x),int(y)])
vtrucks_y = np.unique(np.where(v==vtruck)[1])
for y in vtrucks_y:
for x in np.where(v[:,y] == vtruck)[0][0::3]:
#dwg = svg_add_piece(dwg,int(x),int(y),'vtruck',truck_colors.pop(),truck_symbols.pop())
end_positions.append([int(x),int(y)])
htrucks_x = np.unique(np.where(v==htruck)[0])
for x in htrucks_x:
for y in np.where(v[x,:]==htruck)[0][0::3]:
#dwg = svg_add_piece(dwg,int(x),int(y),'htruck',truck_colors.pop(),truck_symbols.pop())
end_positions.append([int(x),int(y)])
end_positions = sorted(end_positions)
for row,col in end_positions:
if v[row,col] == hcar:
dwg = svg_add_piece(dwg,int(row),int(col),'hcar',car_colors.pop(),car_symbols.pop() )
elif v[row,col] == vcar:
dwg = svg_add_piece(dwg,int(row),int(col),'vcar',car_colors.pop(),car_symbols.pop() )
elif v[row,col] == htruck:
dwg = svg_add_piece(dwg,int(row),int(col),'htruck',truck_colors.pop(),truck_symbols.pop() )
else:
dwg = svg_add_piece(dwg,int(row),int(col),'vtruck',truck_colors.pop(),truck_symbols.pop() )
return dwg
In [18]:
dwg = svg_from_state_generated_order(t,[0,1])
HTML(dwg.tostring())
Out[18]:
recursion algorithm needs to know three things:
In [19]:
def new_pivot(pivot_position):
#move left to right and then down.
row,col = pivot_position
if col < 5:
return [row,col+1]
elif col == 5 and row < 5:
return [row+1,0]
else:
# else return bad value to create error
#!!!! TODO - add proper error handling here
return[0.5,0.5]
# s is a State: numpy array representing board. And marker for position of red car
# num_cars is number of cars remaning to place on board
# num_trucks is number of trucks remaining to place on board
# pivot_position is the start position to loop through and place one car or one truck on the board.
def recurse(v,red_cols,num_cars,num_trucks,pivot_position):
'''
input
v: numpy array representing RH board
red_cols: 2-elt array [c0,c1] marking the columns of the red car
num_cars: number of cars to still be placed on the board
num_trucks: number of trucks still to be placed on the board
pivot_position: 2-elt array indicating the current place to attempt to place pieces on the board
'''
pivot_row,pivot_col = pivot_position
# test base case exit condition
if num_cars == 0 and num_trucks == 0:
record_state(v,red_cols)
return
# can't place piece hooked to last square
if pivot_position == [5,5]:
return
# in all cases of a recursive call, we move to next pivot position
new_pivot_position = new_pivot(pivot_position)
# test if current position is filled - move to next position on board
if v[pivot_row,pivot_col] != blank:
recurse(v,red_cols,num_cars,num_trucks,new_pivot_position)
return
# test for branch exit. If not posisible to lay down remaining pieces, then end recursion
#!!!! TODO - validate edge conditions here
if 2*num_cars + 3*num_trucks > 36 - 6*pivot_row + pivot_col:
return
for i in np.arange(pivot_row*6+pivot_col,36):
row = i//6
col = i%6
# place hcar if possible
if num_cars > 0 and col < 5 and np.all(v[row,col:col+2] == blank):
new_v = np.copy(v)
new_v[row,col:col+2] = hcar
recurse(new_v,red_cols,num_cars-1,num_trucks,new_pivot([row,col]))
# place vcar if possible
if num_cars > 0 and row < 5 and np.all(v[row:row+2,col] == blank):
new_v = np.copy(v)
new_v[row:row+2,col] = vcar
recurse(new_v,red_cols,num_cars-1,num_trucks,new_pivot([row,col]))
#place htruck if possible
if num_trucks > 0 and col < 4 and np.all(v[row,col:col+3]==blank):
new_v = np.copy(v)
new_v[row,col:col+3] = htruck
recurse(new_v,red_cols,num_cars,num_trucks-1,new_pivot([row,col]))
if num_trucks > 0 and row < 4 and np.all(v[row:row+3,col] == blank):
new_v = np.copy(v)
new_v[row:row+3,col] = vtruck
recurse(new_v,red_cols,num_cars,num_trucks-1,new_pivot([row,col]))
In [20]:
#globals
outfile = None
state_list = []
vf = np.vectorize(lambda x: bin(x)[2:].zfill(3))
vec_bitstring_3 = np.vectorize(lambda x: np.binary_repr(x,width=3) )
def board_to_int(v):
t = vec_bitstring_3(v)
return int(''.join(np.apply_along_axis(lambda x: ''.join(x), 1,t)),2)
def int_to_board(i):
#i = '154444257952488798331863040'
s = bin(int(i))[2:].zfill(108)
v = np.array([int(s[i:i+3],2) for i in range(0,len(s),3)])
return v.reshape((6,6))
def record_state(v,red_cols):
global state_counter
state_counter += 1
#record_state_outfile(v,red_cols)
record_state_list(v,red_cols)
def record_state_list(v,red_cols):
global state_list
state_list.append( (v,red_cols) )
def record_state_outfile(v,red_cols):
global outfile
v_hash = str(int(''.join(vf(v.reshape(1,36))[0]),2))
txt = ','.join([v_hash,str(red_cols[0]),str(red_cols[1])])
outfile.write(txt)
outfile.write('\n')
In [21]:
#TEST
t
Out[21]:
In [22]:
int_to_board(board_to_int(t))
Out[22]:
In [23]:
i = board_to_int(t)
i == board_to_int(int_to_board(i))
Out[23]:
In [29]:
def generate_states(num_cars, num_trucks):
global outfile
#outfile = open(r'\\kaufmanhall.net\vol02$\Axiom\Users\CHaithcock\%d-cars-%d-trucks.txt'%(num_cars,num_trucks),'w')
#global state_list
#state_list = []
for i in np.arange(5):
v = np.zeros((6,6),dtype=int)
v[2,i:i+2] = hcar
recurse(v,[int(i),int(i+1)],num_cars-1,num_trucks, [0,0])
#outfile.close()
In [30]:
# TEST
state_list = []
state_counter = 0
%time generate_states(2,0)
#len(state_list),state_list[4]
In [31]:
print(state_counter)
In [ ]:
# Prod with Timing
state_counter = 0
%time generate_states(8,0)
In [34]:
state_list[150]
Out[34]:
In [40]:
%time white_nodes = set([ (board_to_int(x[0]),x[1][0],x[1][1]) for x in state_list])
In [44]:
soln_states = set([x for x in white_nodes if 5 == x[2]])
In [45]:
type(soln_states)
Out[45]:
In [48]:
len(soln_states), len(white_nodes)
Out[48]:
In [49]:
white_states = white_nodes - soln_states
In [50]:
s1 = set([1,2,3,4,5])
s2 = set([1,3,5])
In [69]:
grey_states = soln_states.copy()
In [66]:
#while grey_states
s = grey_states.pop()
nbrs =
Out[66]:
In [67]:
len(black_states)
Out[67]:
In [ ]:
In [ ]:
In [ ]:
In [ ]:
In [ ]:
In [231]:
i = 206
j = 211
i = 90625
j = 90630
html = "<table><tr>"
for v,red_cols in state_list[i:i+5]:
html += "<td>"
html += svg_from_state_generated_order(v,red_cols).tostring()
html += "</td>"
html += "</tr><tr>"
for v,red_cols in state_list[j:j+5]:
html += "<td>"
html += svg_from_state_generated_order(v,red_cols).tostring()
html += "</td>"
html += "</table>"
HTML(html)
Out[231]:
In [ ]:
In [134]:
state_list[61]
Out[134]:
In [88]:
str(int(''.join(vf(v.reshape(1,36))[0]),2))
Out[88]:
In [89]:
','.join(['a','b','c'])
Out[89]:
In [90]:
[i for i in range(5)]
Out[90]:
In [6]:
i = '154444257952488798331863040'
s = bin(int(i))[2:].zfill(108)
v = np.array([int(s[i:i+3],2) for i in range(0,len(s),3)])
w = v.reshape((6,6))
#len(v)
w
Out[6]:
In [7]:
w
Out[7]:
In [8]:
board_to_int(w)
Out[8]:
In [9]:
int_to_board(board_to_int(w))
Out[9]:
In [ ]:
In [ ]: