Sokoban: Difference between revisions
Rename Perl 6 -> Raku, alphabetize, minor clean-up
Thundergnat (talk | contribs) (Rename Perl 6 -> Raku, alphabetize, minor clean-up) |
|||
Line 421:
return 0;
}</lang>
=={{header|C sharp|C#}}==
<lang csharp>using System.Collections.Generic;
using System.Linq;
using System.Text;
namespace SokobanSolver
{
public class SokobanSolver
{
private class Board
{
public string Cur { get; internal set; }
public string Sol { get; internal set; }
public int X { get; internal set; }
public int Y { get; internal set; }
public Board(string cur, string sol, int x, int y)
{
Cur = cur;
Sol = sol;
X = x;
Y = y;
}
}
private string destBoard, currBoard;
private int playerX, playerY, nCols;
SokobanSolver(string[] board)
{
nCols = board[0].Length;
StringBuilder destBuf = new StringBuilder();
StringBuilder currBuf = new StringBuilder();
for (int r = 0; r < board.Length; r++)
{
for (int c = 0; c < nCols; c++)
{
char ch = board[r][c];
destBuf.Append(ch != '$' && ch != '@' ? ch : ' ');
currBuf.Append(ch != '.' ? ch : ' ');
if (ch == '@')
{
this.playerX = c;
this.playerY = r;
}
}
}
destBoard = destBuf.ToString();
currBoard = currBuf.ToString();
}
private string Move(int x, int y, int dx, int dy, string trialBoard)
{
int newPlayerPos = (y + dy) * nCols + x + dx;
if (trialBoard[newPlayerPos] != ' ')
return null;
char[] trial = trialBoard.ToCharArray();
trial[y * nCols + x] = ' ';
trial[newPlayerPos] = '@';
return new string(trial);
}
private string Push(int x, int y, int dx, int dy, string trialBoard)
{
int newBoxPos = (y + 2 * dy) * nCols + x + 2 * dx;
if (trialBoard[newBoxPos] != ' ')
return null;
char[] trial = trialBoard.ToCharArray();
trial[y * nCols + x] = ' ';
trial[(y + dy) * nCols + x + dx] = '@';
trial[newBoxPos] = '$';
return new string(trial);
}
private bool IsSolved(string trialBoard)
{
for (int i = 0; i < trialBoard.Length; i++)
if ((destBoard[i] == '.')
!= (trialBoard[i] == '$'))
return false;
return true;
}
private string Solve()
{
char[,] dirLabels = { { 'u', 'U' }, { 'r', 'R' }, { 'd', 'D' }, { 'l', 'L' } };
int[,] dirs = { { 0, -1 }, { 1, 0 }, { 0, 1 }, { -1, 0 } };
ISet<string> history = new HashSet<string>();
LinkedList<Board> open = new LinkedList<Board>();
history.Add(currBoard);
open.AddLast(new Board(currBoard, string.Empty, playerX, playerY));
while (!open.Count.Equals(0))
{
Board item = open.First();
open.RemoveFirst();
string cur = item.Cur;
string sol = item.Sol;
int x = item.X;
int y = item.Y;
for (int i = 0; i < dirs.GetLength(0); i++)
{
string trial = cur;
int dx = dirs[i, 0];
int dy = dirs[i, 1];
// are we standing next to a box ?
if (trial[(y + dy) * nCols + x + dx] == '$')
{
// can we push it ?
if ((trial = Push(x, y, dx, dy, trial)) != null)
{
// or did we already try this one ?
if (!history.Contains(trial))
{
string newSol = sol + dirLabels[i, 1];
if (IsSolved(trial))
return newSol;
open.AddLast(new Board(trial, newSol, x + dx, y + dy));
history.Add(trial);
}
}
// otherwise try changing position
}
else if ((trial = Move(x, y, dx, dy, trial)) != null)
{
if (!history.Contains(trial))
{
string newSol = sol + dirLabels[i, 0];
open.AddLast(new Board(trial, newSol, x + dx, y + dy));
history.Add(trial);
}
}
}
}
return "No solution";
}
public static void Main(string[] a)
{
string level = "#######," +
"# #," +
"# #," +
"#. # #," +
"#. $$ #," +
"#.$$ #," +
"#.# @#," +
"#######";
System.Console.WriteLine("Level:\n");
foreach (string line in level.Split(','))
{
System.Console.WriteLine(line);
}
System.Console.WriteLine("\nSolution:\n");
System.Console.WriteLine(new SokobanSolver(level.Split(',')).Solve());
}
}
}</lang>
Output:
<pre>
Level:
#######
# #
# #
#. # #
#. $$ #
#.$$ #
#.# @#
#######
Solution:
ulULLulDDurrrddlULrruLLrrUruLLLulD</pre>
=={{header|C++}}==
Line 742 ⟶ 934:
return 0;
}</lang>
=={{header|D}}==
Line 2,719:
Although my code doesn't print out the actual final board, it would be easy enough
to compute from the move list.
=={{header|Phix}}==
Line 3,520 ⟶ 3,405:
"uuulDLLrrrddllUdrruulLrrdLuuulldlDDuuurrrddlLrrddlULrruLdlUUdrruulLulD"
</pre>
=={{header|Raku}}==
(formerly Perl 6)
{{trans|Go}}
<lang perl6>sub MAIN() {
my $level = q:to//;
#######
# #
# #
#. # #
#. $$ #
#.$$ #
#.# @#
#######
say 'level:';
print $level;
say 'solution:';
say solve($level);
}
class State {
has Str $.board;
has Str $.sol;
has Int $.pos;
method move(Int $delta --> Str) {
my $new = $!board;
if $new.substr($!pos,1) eq '@' {
substr-rw($new,$!pos,1) = ' ';
} else {
substr-rw($new,$!pos,1) = '.';
}
my $pos := $!pos + $delta;
if $new.substr($pos,1) eq ' ' {
substr-rw($new,$pos,1) = '@';
} else {
substr-rw($new,$pos,1) = '+';
}
return $new;
}
method push(Int $delta --> Str) {
my $pos := $!pos + $delta;
my $box := $pos + $delta;
return '' unless $!board.substr($box,1) eq ' ' | '.';
my $new = $!board;
if $new.substr($!pos,1) eq '@' {
substr-rw($new,$!pos,1) = ' ';
} else {
substr-rw($new,$!pos,1) = '.';
}
if $new.substr($pos,1) eq '$' {
substr-rw($new,$pos,1) = '@';
} else {
substr-rw($new,$pos,1) = '+';
}
if $new.substr($box,1) eq ' ' {
substr-rw($new,$box,1) = '$';
} else {
substr-rw($new,$box,1) = '*';
}
return $new;
}
}
sub solve(Str $start --> Str) {
my $board = $start;
my $width = $board.lines[0].chars + 1;
my @dirs =
["u", "U", -$width],
["r", "R", 1],
["d", "D", $width],
["l", "L", -1];
my %visited = $board => True;
my $pos = $board.index('@');
my @open = State.new(:$board, :sol(''), :$pos);
while @open {
my $state = @open.shift;
for @dirs -> [$move, $push, $delta] {
my $board;
my $sol;
my $pos = $state.pos + $delta;
given $state.board.substr($pos,1) {
when '$' | '*' {
$board = $state.push($delta);
next if $board eq "" || %visited{$board};
$sol = $state.sol ~ $push;
return $sol unless $board ~~ /<[ . + ]>/;
}
when ' ' | '.' {
$board = $state.move($delta);
next if %visited{$board};
$sol = $state.sol ~ $move;
}
default { next }
}
@open.push: State.new: :$board, :$sol, :$pos;
%visited{$board} = True;
}
}
return "No solution";
}</lang>
{{out}}
<pre>Level:
#######
# #
# #
#. # #
#. $$ #
#.$$ #
#.# @#
#######
Solution:
ulULLulDDurrrddlULrruLLrrUruLLLulD</pre>
=={{header|Ring}}==
| |||