Konkret geht es um die Modellierung eines Reversi-Spiels, um die Aufgabe 3 von HP Codewars 2012 zu lösen.
Mich würde interessieren, wie ihr das Spielfeld modellieren würdet? Es sollte so gestaltet sein, dass später das parsen um die Move-Bedingungen zu prüfen, erleichtert wird.
In einem anderen Fall - Minenlayer - habe ich eine Liste gebastelt und das Feld (Höhe * Breite) nur in der Ausgabe formatiert. Hier finde ich die Aufgabe komplexer.
Mich würde interessieren: Wie würdet ihr das Spielfeld modellieren? Liste, Wörterbuch oder anders?
Ansatzproblem Reversi
@pixewakb: Ich würde wohl einfach eine verschachtelte Liste verwenden. Und die eventuell in einer Klasse kapseln.
Prüfen muss man die Spielzüge laut Aufgabe gar nicht, nur ausführen.
Prüfen muss man die Spielzüge laut Aufgabe gar nicht, nur ausführen.
Dummerweise muss man schon irgendwie prüfen und zwar, ob Spielsteine umgedreht werden müssen und das ist richtig, richtig Sch****. Jedenfalls habe ich das für mich noch nicht klar, wie ich das einerseits möglichst einfach, andererseits aber gut machen kann.
Gibt es eine bessere Möglichkeit als Listen in einer Liste zu erzeugen??? In C++ geht wohl etwas wie:
Gibt es so etwas in Python vergleichbar???
Objektorientierung beherrsche ich noch nicht - ebenso wie Graphentheorie, folglich steht das momentan leider noch nicht an.
Gibt es eine bessere Möglichkeit als Listen in einer Liste zu erzeugen??? In C++ geht wohl etwas wie:
Code: Alles auswählen
feld[8][8]
Objektorientierung beherrsche ich noch nicht - ebenso wie Graphentheorie, folglich steht das momentan leider noch nicht an.
@pixewakb: Nein etwas vergleichbares geht mit Python's Listen nicht. Da wirst Du schon zwei verschachtelte Schleifen schreiben müssen. Beziehungsweise Dich mit „Rechenoperationen” auf Listen für die inneren Listen (wenn die Elemente dort unveränderbar sind) und „list comprehensions” für die äussere Liste auseinandersetzen. Dann bekommt man das recht kompakt in einer Zeile hin.
Das prüfen ist eigentlich recht einfach. Man muss das nur auf Teilprobleme herunterbrechen.
Edit: Ein Versuch in JavaScript (falls der furchtbar sein sollte, ist meine Entschuldigung, dass es schon spät ist ):
Testlauf:
Das prüfen ist eigentlich recht einfach. Man muss das nur auf Teilprobleme herunterbrechen.
Edit: Ein Versuch in JavaScript (falls der furchtbar sein sollte, ist meine Entschuldigung, dass es schon spät ist ):
Code: Alles auswählen
_ = require("underscore")
Coordinate = function(x, y) {
return {
x: x,
y: y,
add: function(other) {
return Coordinate(this.x + other.x, this.y + other.y);
}
};
}
Coordinate.fromString = function(string) {
return Coordinate(
string.charCodeAt(0) - "a".charCodeAt(0), parseInt(string.charAt(1)) - 1
);
}
Reversi = function() {
var N = 8, BLACK = "B", WHITE = "W", EMPTY = ".";
var deltas = [];
for (var di = -1; di <= 1; di++) {
for (var dj = -1; dj <= 1; dj++) {
if (di | dj != 0) {
deltas.push(Coordinate(di, dj));
}
}
}
var fields = [];
for (var i = 0; i < N; i++) {
var row = [];
for (var j = 0; j < N; j++) row.push(EMPTY);
fields.push(row);
}
getOpposite = function(player) {
switch (player) {
case BLACK:
return WHITE;
case WHITE:
return BLACK;
default:
throw Error("unknown player " + player);
}
}
withinBoard = function(coordinate) {
return coordinate.x >= 0 || coordinate.x < N
|| coordinate.y >= 0 || coordinate.y < N;
}
var result = {
currentPlayer: WHITE,
get: function(coordinate) {
return fields[coordinate.y][coordinate.x];
},
set: function(coordinate, value) {
fields[coordinate.y][coordinate.x] = value;
},
move: function(coordinate) {
var currentPlayer = this.currentPlayer;
var otherPlayer = getOpposite(currentPlayer);
var checkLine = _.bind(function(coordinate) {
var current, result = [];
while (true) {
coordinate = coordinate.add(delta);
if (!withinBoard(coordinate)
|| (current = this.get(coordinate)) != otherPlayer) {
return (current == currentPlayer) ? result : [];
}
result.push(coordinate);
}
}, this);
this.set(coordinate, currentPlayer);
for (var i = 0; i < deltas.length; i++) {
var delta = deltas[i];
var toTurn = checkLine(coordinate);
for (var j = 0; j < toTurn.length; j++) {
this.set(toTurn[j], currentPlayer);
}
}
this.currentPlayer = otherPlayer;
},
toString: function() {
return _.map(
fields, function(row) {return row.join("");}
).join("\n");
}
}
//
// Initial board pieces.
//
result.set(Coordinate(3, 3), WHITE);
result.set(Coordinate(4, 3), BLACK);
result.set(Coordinate(3, 4), BLACK);
result.set(Coordinate(4, 4), WHITE);
return result;
}
main = function() {
var readline = require("readline");
var rl = readline.createInterface(process.stdin, process.stdout);
var reversi = Reversi();
console.log(reversi.toString(), "\n");
rl.on("line", function(line) {
if (line == "END") {
process.exit(0);
} else {
reversi.move(Coordinate.fromString(line));
console.log(reversi.toString(), "\n");
}
});
}
main();
Code: Alles auswählen
........
........
........
...WB...
...BW...
........
........
........
f4
........
........
........
...WWW..
...BW...
........
........
........
f5
........
........
........
...WWW..
...BBB..
........
........
........
f6
........
........
........
...WWW..
...BWW..
.....W..
........
........
g5
........
........
........
...WWW..
...BBBB.
.....W..
........
........
h6
........
........
........
...WWW..
...BBBW.
.....W.W
........
........
f7
........
........
........
...WWW..
...BBBW.
.....B.W
.....B..
........
e6
........
........
........
...WWW..
...BWBW.
....WB.W
.....B..
........
END
Eine Lösung die das Problem auf Funktionen herunterbricht:
Code: Alles auswählen
#!/usr/bin/env python
"""Program to replay a given sequence of Reversi moves.
A solution with functions only.
Main data structures are coordinates represented by tuples of x and y values
and the board represented by nested lists of field values for black, white,
and empty fields. Then there is a tuple represanting the current player
(first element) and the other player (second element).
The assignment guarantees valid moves as input, so there is virtually no
validation of the input in the program.
"""
BLACK, WHITE, EMPTY = 'B', 'W', '.'
#
# Relative coordinates used for moving one step in any of the eight directions.
#
DELTAS = [
(i, j)
for i in xrange(-1, 2) for j in xrange(-1, 2)
if not (i == 0 and j == 0)
]
def coordinate_add(coordinate_a, coordinate_b):
"""Adds two coordinates and return the resulting coordinate.
>>> coordinate_add((42, 23), (-1, 1))
(41, 24)
"""
return tuple(a + b for a, b in zip(coordinate_a, coordinate_b))
def coordinate_from_string(string):
"""Converts a string in the format given in the assignment into
a coordinate used by this program.
>>> coordinate_from_string('a1') # Upper left corner.
(0, 0)
>>> coordinate_from_string('f4') # Sixth column, fourth row.
(5, 3)
"""
return (ord(string[0]) - ord('a'), int(string[1]) - 1)
def create_board():
"""Creates the start configuration with the four pieces in the middle.
>>> from pprint import pprint
>>> pprint(create_board())
[['.', '.', '.', '.', '.', '.', '.', '.'],
['.', '.', '.', '.', '.', '.', '.', '.'],
['.', '.', '.', '.', '.', '.', '.', '.'],
['.', '.', '.', 'W', 'B', '.', '.', '.'],
['.', '.', '.', 'B', 'W', '.', '.', '.'],
['.', '.', '.', '.', '.', '.', '.', '.'],
['.', '.', '.', '.', '.', '.', '.', '.'],
['.', '.', '.', '.', '.', '.', '.', '.']]
"""
size = 8
result = [[EMPTY] * size for _ in xrange(size)]
for x, y in [(3, 4), (4, 3), (3, 3), (4, 4)]:
result[y][x] = WHITE if x == y else BLACK
return result
def board2string(board):
"""Converts the board into a string represantation required by the
assignment.
"""
return '\n'.join(''.join(row) for row in board)
def board_get(board, coordinate):
"""Gets the field value at given coordinate.
>>> board = create_board()
>>> board_get(board, (0, 0))
'.'
>>> board_get(board, (3, 3))
'W'
"""
x, y = coordinate
return board[y][x]
def board_set(board, coordinate, value):
"""Sets the field value at given coordinate."""
x, y = coordinate
board[y][x] = value
def is_within_board(board, coordinate):
"""Checks if given coordinate is within board.
>>> board = create_board()
>>> [is_within_board(board, c) for c in [(0, 0), (-1, 1), (7, 7), (8, 6)]]
[True, False, True, False]
"""
size = len(board)
return all(0 <= n < size for n in coordinate)
def _check_line(board, coordinate, delta, players):
"""Checks a line starting at given coordinate and advancing in the
direction of given delta for pieces to turn.
Returns a possibly empty sequence of coordinates of the pieces that have
to be turned.
"""
current_player, other_player = players
result = list()
while True:
coordinate = coordinate_add(coordinate, delta)
if is_within_board(board, coordinate):
current = board_get(board, coordinate)
if current != other_player:
return result if current == current_player else []
else:
return []
result.append(coordinate)
def move(board, players, coordinate):
"""Makes a move by placing a piece for the current player at the given
coordinate and the turning the tiles affected by this move.
Returns the players ordered for the next move.
"""
current_player, other_player = players
board_set(board, coordinate, current_player)
for delta in DELTAS:
for to_turn in _check_line(board, coordinate, delta, players):
board_set(board, to_turn, current_player)
return (other_player, current_player)
def main():
"""Reads moves from stdin until 'END' is read, executes the moves,
and prints the board state after each move.
"""
players = WHITE, BLACK
board = create_board()
print board2string(board), '\n'
for line in iter(raw_input, 'END'):
players = move(board, players, coordinate_from_string(line))
print line
print board2string(board), '\n'
if __name__ == '__main__':
main()
@jerch: Ja, OOP beeinflusst einen nachhaltig. Andererseits hatte ich das so auch schon ohne OOP zu kennen mal bei Pascal gelernt, dass man sich RECORDs mit den Daten definiert und dann Prozeduren und Funktionen die damit operieren. Es ist auf jeden Fall recht nah an einer Lösung mit Klassen:
Code: Alles auswählen
#!/usr/bin/env python
"""Program to replay a given sequence of Reversi moves.
This time with classes.
The assignment guarantees valid moves as input, so there is virtually no
validation of the input in the program.
"""
class Coordinate(object):
def __init__(self, x, y):
self.x = x
self.y = y
def __repr__(self):
return '%s(%r, %r)' % (self.__class__.__name__, self.x, self.y)
def __add__(self, other):
return Coordinate(self.x + other.x, self.y + other.y)
@classmethod
def from_string(cls, string):
"""Converts a string in the format given in the assignment into
a coordinate used by this program.
>>> Coordinate.from_string('a1') # Upper left corner.
Coordinate(0, 0)
>>> Coordinate.from_string('f4') # Sixth column, fourth row.
Coordinate(5, 3)
"""
return cls(ord(string[0]) - ord('a'), int(string[1]) - 1)
class Reversi(object):
BLACK, WHITE, EMPTY = 'B', 'W', '.'
#
# Relative coordinates used for moving one step in any of the eight
# directions.
#
DELTAS = [
Coordinate(i, j)
for i in xrange(-1, 2) for j in xrange(-1, 2)
if not (i == 0 and j == 0)
]
def __init__(self):
"""Creates the start configuration with the four pieces in the middle.
"""
self.players = (self.WHITE, self.BLACK)
size = 8
self.board = [[self.EMPTY] * size for _ in xrange(size)]
for x, y in [(3, 4), (4, 3), (3, 3), (4, 4)]:
self[Coordinate(x, y)] = self.WHITE if x == y else self.BLACK
@property
def current_player(self):
return self.players[0]
@property
def other_player(self):
return self.players[1]
def __str__(self):
return '\n'.join(''.join(row) for row in self.board)
def __getitem__(self, coordinate):
"""
>>> reversi = Reversi()
>>> reversi[Coordinate(0, 0)]
'.'
>>> reversi[Coordinate(3, 3)]
'W'
"""
return self.board[coordinate.y][coordinate.x]
def __setitem__(self, coordinate, value):
self.board[coordinate.y][coordinate.x] = value
def __contains__(self, coordinate):
"""Checks if given coordinate is within board.
>>> reversi = Reversi()
>>> [c in reversi
... for c in (Coordinate(*t) for t in [(0, 0), (-1, 1), (7, 7), (8, 6)])]
[True, False, True, False]
"""
size = len(self.board)
return all(0 <= n < size for n in [coordinate.x, coordinate.y])
def _check_line(self, coordinate, delta):
"""Checks a line starting at given coordinate and advancing in the
direction of given delta for pieces to turn.
Returns a possibly empty sequence of coordinates of the pieces that
have to be turned.
"""
result = list()
while True:
coordinate = coordinate + delta
if coordinate in self:
current = self[coordinate]
if current != self.other_player:
return result if current == self.current_player else []
else:
return []
result.append(coordinate)
def move(self, coordinate):
"""Makes a move by placing a piece for the current player at the given
coordinate and the turning the tiles affected by this move.
"""
self[coordinate] = self.current_player
for delta in self.DELTAS:
for to_turn in self._check_line(coordinate, delta):
self[to_turn] = self.current_player
self.players = (self.other_player, self.current_player)
def main():
"""Reads moves from stdin until 'END' is read, executes the moves,
and prints the board state after each move.
"""
reversi = Reversi()
print reversi, '\n'
for line in iter(raw_input, 'END'):
reversi.move(Coordinate.from_string(line))
print line
print reversi, '\n'
if __name__ == '__main__':
main()
Worauf Kenntnisse und Erfahrung mit objektorientierter Programmierung anscheinend so gar gar keinen Einfluss haben, ist CBM BASIC. Hier der schön kurze und gnadenlos unübersichtliche Beweis:
Eine Java-Lösung bringt nicht wirklich etwas neues, ausser das man für die Konstanten für die Felder den ``enum``-Typ verwenden kann:
Edit: OOP hatte ebenfalls wenig Einfluss auf diese 6510-Assembler-Lösung (ACME Assembler-Format, Zielplattform C64): http://pastebin.com/VKFqKVm1
Ich glaube jetzt höre ich besser auf mit dem Thema.
Edit2: Habe die Assembler-Version noch einmal neu geschrieben für den ca65-Assembler weil ich einen Blogbeitrag zum Syntaxhighlighting für CBM-BASIC und ca65-Assembler in Pygments geschrieben habe.
Code: Alles auswählen
10 CP$="W":OP$="B":DIM B$(7,7):FOR I=0 TO 7:FOR J=0 TO 7:B$(I,J)=".":NEXT:NEXT
20 B$(3,3)="W":B$(4,3)="B":B$(3,4)="B":B$(4,4)="W":DIM TX(7),TY(7):GOTO 140
30 INPUT L$:IF L$="END" THEN END
40 Y=ASC(LEFT$(L$,1))-ASC("A"):X=VAL(RIGHT$(L$,1))-1:B$(Y,X)=CP$
50 FOR XD=-1 TO 1:FOR YD=-1 TO 1:IF(XD OR YD)=0 THEN 130
60 XT=X:YT=Y:TC=0
70 XT=XT+XD:YT=YT+YD
80 IF XT<0 OR XT>7 OR YT<0 OR YT>7 THEN TC=0:GOTO 120
90 T$=B$(YT,XT):IF T$<>OP$ THEN 110
100 TX(TC)=XT:TY(TC)=YT:TC=TC+1:GOTO 70
110 IF T$<>CP$ THEN TC=0
120 IF TC>0 THEN FOR I=0 TO TC-1:B$(TY(I),TX(I))=CP$:NEXT
130 NEXT:NEXT:T$=CP$:CP$=OP$:OP$=T$
140 FOR I=0 TO 7:FOR J=0 TO 7:PRINT B$(J,I);:NEXT:PRINT:NEXT:PRINT:GOTO 30
Code: Alles auswählen
private static enum Field {
BLACK('B'), WHITE('W'), EMPTY('.');
private final char character;
Field(char c) {
character = c;
}
public Field getOpposite() throws RuntimeException {
switch (this) {
case BLACK:
return WHITE;
case WHITE:
return BLACK;
case EMPTY:
throw new RuntimeException("No opposite of empty field.");
}
return null; // Should never happen.
}
@Override
public String toString() {
return Character.toString(character);
}
}
Ich glaube jetzt höre ich besser auf mit dem Thema.
Edit2: Habe die Assembler-Version noch einmal neu geschrieben für den ca65-Assembler weil ich einen Blogbeitrag zum Syntaxhighlighting für CBM-BASIC und ca65-Assembler in Pygments geschrieben habe.