138 lines
3.9 KiB
Julia
138 lines
3.9 KiB
Julia
function winp(hall, rooms)
|
|
all(map(==('A'), rooms[1])) && all(map(==('B'), rooms[2])) && all(map(==('C'), rooms[3])) && all(map(==('D'), rooms[4]))
|
|
end
|
|
|
|
function moveroomp(hall, rooms, room, pos, letter)
|
|
# check empty path
|
|
if pos > room * 2 + 1
|
|
if !all(map(==(' '), hall[(room * 2 + 1):(pos-1)]))
|
|
return false
|
|
end
|
|
else
|
|
if !all(map(==(' '), hall[(pos+1):(room * 2 + 1)]))
|
|
return false
|
|
end
|
|
end
|
|
# check place in room
|
|
if rooms[room][1] != ' '
|
|
return false
|
|
end
|
|
# check other is same
|
|
if any(map(i->rooms[room][i] != ' ' && rooms[room][i] != letter, 2:length(rooms[room])))
|
|
return false
|
|
end
|
|
true
|
|
end
|
|
|
|
function makemove(hall, rooms, i, letter, cost, stepcost, room)
|
|
h = copy(hall)
|
|
r = deepcopy(rooms)
|
|
h[i] = ' '
|
|
lastempty = reduce(max, filter(i->r[room][i] == ' ', 1:length(r[room])))
|
|
c = cost + (abs(i - (room*2+1)) + lastempty) * stepcost;
|
|
r[room][lastempty] = letter
|
|
h, r, c
|
|
end
|
|
|
|
function makemoves(rooms, hall, room, cost)
|
|
if all(map(==(' '), rooms[room]))
|
|
return []
|
|
end
|
|
if all(map(letter->((codepoint(letter)-0x40)==room || letter == ' '), rooms[room]))
|
|
return []
|
|
end
|
|
up = (room*2+1):length(hall)
|
|
down = reverse(1:(room*2+1))
|
|
targets = filter(i->!(i in [3,5,7,9]),
|
|
union(Iterators.takewhile(i->hall[i]==' ', up),
|
|
Iterators.takewhile(i->hall[i]==' ', down)))
|
|
firstnonempty = reduce(min, filter(i->rooms[room][i] != ' ', 1:length(rooms[room])))
|
|
map(targets) do target
|
|
h = copy(hall)
|
|
r = deepcopy(rooms)
|
|
h[target] = rooms[room][firstnonempty]
|
|
c = cost + (abs(target - (room*2+1)) + firstnonempty) * 10^(codepoint(h[target])-0x41);
|
|
r[room][firstnonempty] = ' '
|
|
h, r, c
|
|
end
|
|
end
|
|
|
|
function legalmoves(hall, rooms, cost)
|
|
moves = []
|
|
for i in 1:length(hall)
|
|
if hall[i] == ' '
|
|
continue
|
|
end
|
|
if hall[i] == 'A' && moveroomp(hall, rooms, 1, i, 'A')
|
|
push!(moves, makemove(hall, rooms, i, 'A', cost, 1, 1))
|
|
continue
|
|
end
|
|
if hall[i] == 'B' && moveroomp(hall, rooms, 2, i, 'B')
|
|
push!(moves, makemove(hall, rooms, i, 'B', cost, 10, 2))
|
|
continue
|
|
end
|
|
if hall[i] == 'C' && moveroomp(hall, rooms, 3, i, 'C')
|
|
push!(moves, makemove(hall, rooms, i, 'C', cost, 100, 3))
|
|
continue
|
|
end
|
|
if hall[i] == 'D' && moveroomp(hall, rooms, 4, i, 'D')
|
|
push!(moves, makemove(hall, rooms, i, 'D', cost, 1000, 4))
|
|
end
|
|
end
|
|
for i in 1:4
|
|
append!(moves, makemoves(rooms, hall, i, cost))
|
|
end
|
|
moves
|
|
end
|
|
|
|
function cheapsort(hall, rooms)
|
|
costmin = typemax(Int64)
|
|
visited = Dict()
|
|
moves = legalmoves(hall, rooms, 0)
|
|
|
|
while length(moves) > 0
|
|
|
|
sort!(moves, by=m->m[3])
|
|
|
|
while length(moves) > 0 && last(moves)[3] >= costmin
|
|
pop!(moves)
|
|
end
|
|
if length(moves) == 0
|
|
break
|
|
end
|
|
|
|
move = pop!(moves)
|
|
if haskey(visited, move)
|
|
continue
|
|
end
|
|
|
|
if move[3] >= costmin
|
|
break
|
|
end
|
|
if winp(move[1], move[2])
|
|
println(length(moves), ' ', move[3], ' ', loops)
|
|
costmin = move[3]
|
|
continue
|
|
end
|
|
append!(moves, legalmoves(move[1], move[2], move[3]))
|
|
visited[move] = true
|
|
end
|
|
costmin
|
|
end
|
|
|
|
function solution23_1()
|
|
hall = fill(' ', 11)
|
|
rooms = [['B', 'A'], ['C', 'D'], ['B', 'C'], ['D', 'A']]
|
|
# rooms = [['A', 'C'], ['D', 'D'], ['A', 'B'], ['C', 'B']]
|
|
cheapsort(hall, rooms)
|
|
end
|
|
|
|
function solution23_2()
|
|
hall = fill(' ', 11)
|
|
rooms = [['B', 'D', 'D', 'A'], ['C', 'C', 'B', 'D'], ['B', 'B', 'A', 'C'], ['D', 'A', 'C', 'A']]
|
|
# rooms = [['A', 'D', 'D', 'C'], ['D', 'C', 'B', 'D'], ['A', 'B', 'A', 'B'], ['C', 'A', 'C', 'B']]
|
|
cheapsort(hall, rooms)
|
|
end
|
|
|
|
solution23_2()
|