Sokoban: Difference between revisions
Content added Content deleted
m (→{{header|Java}}: small changes) |
(Added Elixir) |
||
| Line 1,322: | Line 1,322: | ||
return 0; |
return 0; |
||
}</lang> |
}</lang> |
||
=={{header|Elixir}}== |
|||
{{works with|Elixir|1.3}} |
|||
{{trans|Ruby}} |
|||
<lang elixir>defmodule Sokoban do |
|||
defp setup(level) do |
|||
{leng, board} = normalize(level) |
|||
{player, goal} = check_position(board) |
|||
board = replace(board, [{".", " "}, {"+", " "}, {"*", "$"}]) |
|||
lurd = [{-1, "l", "L"}, {-leng, "u", "U"}, {1, "r", "R"}, {leng, "d", "D"}] |
|||
dirs = [-1, -leng, 1, leng] |
|||
dead_zone = set_dead_zone(board, goal, dirs) |
|||
{board, player, goal, lurd, dead_zone} |
|||
end |
|||
defp normalize(level) do |
|||
board = String.split(level, "\n", trim: true) |
|||
|> Enum.map(&String.trim_trailing &1) |
|||
leng = Enum.map(board, &String.length &1) |> Enum.max |
|||
board = Enum.map(board, &String.pad_trailing(&1, leng)) |> Enum.join |
|||
{leng, board} |
|||
end |
|||
defp check_position(board) do |
|||
board = String.codepoints(board) |
|||
player = Enum.find_index(board, fn c -> c in ["@", "+"] end) |
|||
goal = Enum.with_index(board) |
|||
|> Enum.filter_map(fn {c,_} -> c in [".", "+", "*"] end, fn {_,i} -> i end) |
|||
{player, goal} |
|||
end |
|||
defp set_dead_zone(board, goal, dirs) do |
|||
wall = String.replace(board, ~r/[^#]/, " ") |
|||
|> String.codepoints |
|||
|> Enum.with_index |
|||
|> Enum.into(Map.new, fn {c,i} -> {i,c} end) |
|||
corner = search_corner(wall, goal, dirs) |
|||
set_dead_zone(wall, dirs, goal, corner, corner) |
|||
end |
|||
defp set_dead_zone(wall, dirs, goal, corner, dead) do |
|||
dead2 = Enum.reduce(corner, dead, fn pos,acc -> |
|||
Enum.reduce(dirs, acc, fn dir,acc2 -> |
|||
if wall[pos+dir] == "#", do: acc2, |
|||
else: acc2 ++ check_side(wall, dirs, pos+dir, dir, goal, dead, []) |
|||
end) |
|||
end) |
|||
if dead == dead2, do: :lists.usort(dead), |
|||
else: set_dead_zone(wall, dirs, goal, corner, dead2) |
|||
end |
|||
defp replace(string, replacement) do |
|||
Enum.reduce(replacement, string, fn {a,b},str -> |
|||
String.replace(str, a, b) |
|||
end) |
|||
end |
|||
defp search_corner(wall, goal, dirs) do |
|||
Enum.reduce(wall, [], fn {i,c},corner -> |
|||
if c == "#" or i in goal do |
|||
corner |
|||
else |
|||
case count_wall(wall, i, dirs) do |
|||
2 -> if wall[i-1] != wall[i+1], do: [i | corner], else: corner |
|||
3 -> [i | corner] |
|||
_ -> corner |
|||
end |
|||
end |
|||
end) |
|||
end |
|||
defp check_side(wall, dirs, pos, dir, goal, dead, acc) do |
|||
if wall[pos] == "#" or |
|||
count_wall(wall, pos, dirs) == 0 or |
|||
pos in goal do |
|||
[] |
|||
else |
|||
if pos in dead, do: acc, else: check_side(wall, dirs, pos+dir, dir, goal, dead, [pos|acc]) |
|||
end |
|||
end |
|||
defp count_wall(wall, pos, dirs) do |
|||
Enum.count(dirs, fn dir -> wall[pos + dir] == "#" end) |
|||
end |
|||
defp push_box(board, pos, dir, route, goal, dead_zone) do |
|||
pos2dir = pos + 2 * dir |
|||
if String.at(board, pos2dir) == " " and not pos2dir in dead_zone do |
|||
board2 = board |> replace_at(pos, " ") |
|||
|> replace_at(pos+dir, "@") |
|||
|> replace_at(pos2dir, "$") |
|||
unless visited?(board2) do |
|||
if solved?(board2, goal) do |
|||
IO.puts route |
|||
exit(:normal) |
|||
else |
|||
queue_in({board2, pos+dir, route}) |
|||
end |
|||
end |
|||
end |
|||
end |
|||
defp move_player(board, pos, dir) do |
|||
board |> replace_at(pos, " ") |> replace_at(pos+dir, "@") |
|||
end |
|||
defp replace_at(str, pos, c) do |
|||
{left, right} = String.split_at(str, pos) |
|||
{_, right} = String.split_at(right, 1) |
|||
left <> c <> right |
|||
# String.slice(str, 0, pos) <> c <> String.slice(str, pos+1..-1) |
|||
end |
|||
defp solved?(board, goal) do |
|||
Enum.all?(goal, fn g -> String.at(board, g) == "$" end) |
|||
end |
|||
@pattern :sokoban_pattern_set |
|||
@queue :sokoban_queue |
|||
defp start_link do |
|||
Agent.start_link(fn -> MapSet.new end, name: @pattern) |
|||
Agent.start_link(fn -> :queue.new end, name: @queue) |
|||
end |
|||
defp visited?(board) do |
|||
Agent.get_and_update(@pattern, fn set -> |
|||
{board in set, MapSet.put(set, board)} |
|||
end) |
|||
end |
|||
defp queue_in(data) do |
|||
Agent.update(@queue, fn queue -> :queue.in(data, queue) end) |
|||
end |
|||
defp queue_out do |
|||
Agent.get_and_update(@queue, fn q -> |
|||
case :queue.out(q) do |
|||
{{:value, data}, queue} -> {data, queue} |
|||
x -> x |
|||
end |
|||
end) |
|||
end |
|||
def solve(level) do |
|||
{board, player, goal, lurd, dead_zone} = setup(level) |
|||
start_link |
|||
visited?(board) |
|||
queue_in({board, player, ""}) |
|||
solve(goal, lurd, dead_zone) |
|||
end |
|||
defp solve(goal, lurd, dead_zone) do |
|||
case queue_out do |
|||
{board, pos, route} -> |
|||
Enum.each(lurd, fn {dir,move,push} -> |
|||
case String.at(board, pos+dir) do |
|||
"$" -> push_box(board, pos, dir, route<>push, goal, dead_zone) |
|||
" " -> board2 = move_player(board, pos, dir) |
|||
unless visited?(board2) do |
|||
queue_in({board2, pos+dir, route<>move}) |
|||
end |
|||
_ -> :not_move # wall |
|||
end |
|||
end) |
|||
_ -> |
|||
IO.puts "No solution" |
|||
exit(:normal) |
|||
end |
|||
solve(goal, lurd, dead_zone) |
|||
end |
|||
end |
|||
level = """ |
|||
####### |
|||
# # |
|||
# # |
|||
#. # # |
|||
#. $$ # |
|||
#.$$ # |
|||
#.# @# |
|||
####### |
|||
""" |
|||
IO.puts level |
|||
Sokoban.solve(level)</lang> |
|||
{{out}} |
|||
<pre> |
|||
####### |
|||
# # |
|||
# # |
|||
#. # # |
|||
#. $$ # |
|||
#.$$ # |
|||
#.# @# |
|||
####### |
|||
luULLulDDurrrddlULrruLLrrUruLLLulD |
|||
</pre> |
|||
=={{header|Go}}== |
=={{header|Go}}== |
||