Initial commit
[trapthecap.git] / lib / .svn / text-base / libttc.rb.netbeans-base
1 # == Synopsis
2 #
3 # Library to support Trap the Cap play
4 #
5 # == Author
6 # Neil Smith
7 #
8 # This program is free software: you can redistribute it and/or modify
9 # it under the terms of the GNU General Public License as published by
10 # the Free Software Foundation, either version 3 of the License, or
11 # (at your option) any later version.
12 #
13 # This program is distributed in the hope that it will be useful,
14 # but WITHOUT ANY WARRANTY; without even the implied warranty of
15 # MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
16 # GNU General Public License for more details.
17 #
18 # You should have received a copy of the GNU General Public License
19 # along with this program. If not, see <http://www.gnu.org/licenses/>.
20 #
21 # == Change history
22 # Version 1.1:: 07 Sep 2007
23 # * Changed format for showing moves via bases.
24 # * Raise error when moving via base without captured pieces
25 # * Raise error when moving onto a safe space with 3 or more
26 # pieces already there
27 # Version 1.2:: 10 Sep 2007
28 # * Incorporated changes in move legality above into
29 # Game#possible_moves
30 # Version 1.3:: 25 Mar 2008
31 # * Fixed bug to detect a winner, and also eliminate players
32 # that have no uncaptured pieces.
33
34 # Errors for a game
35
36 # Pieces can only capture pieces that they're on.
37 class InvalidCaptureError < StandardError
38 end
39
40 # Moves can only be [1..6] spaces
41 class InvalidMoveError < StandardError
42 end
43
44 # Game is won when only one player has uncaptured pieces
45 class GameWonNotice < StandardError
46 end
47
48
49 # Each possible position for a piece is an object
50 # Each neighbour is another position object
51 class Position
52 attr_reader :place # the name of this place
53 attr_accessor :contains # the pieces it contains
54 attr_accessor :neighbours # the positions that neighbour it
55
56 def initialize(place, safety, base)
57 @place = place
58 @safe = safety
59 @base = base
60 @neighbours = Array.new
61 end
62
63 # is this position a safety one (i.e. no captures allowed)?
64 def safe?
65 @safe
66 end
67
68 # Is this position a base?
69 def base?
70 @base
71 end
72
73 def to_s
74 @place
75 end
76
77 def to_str
78 to_s
79 end
80
81 end
82
83
84 # The game board
85 class Board
86
87 attr_reader :positions
88 attr_reader :valid_moves
89 attr_reader :distance_between
90 attr_reader :centre
91
92
93 # A laborious procedure to create all the positions and tie them all together
94 def initialize(spokes, spoke_length, arc_length)
95 # A hash of all positions, indexed by position names
96 @positions = Hash.new
97 @centre = Position.new('ac' + spoke_length.to_s, false, false)
98 @positions['ac' + spoke_length.to_s] = centre
99 a1_corner = nil
100 end_of_previous_arc = nil
101
102 # Do each arc-spoke-base set
103 (?a...(?a + spokes)).each do |arc_code|
104 arc = arc_code.chr
105 base = Position.new(arc, false, true)
106 this_arc = Array.new
107
108 # build the arc
109 (1..arc_length).each do |arc_position|
110 position_name = arc + arc_position.to_s
111 arc_place = Position.new(position_name, arc_position == 4, false)
112 arc_place.neighbours = []
113 @positions[position_name] = arc_place
114 this_arc << arc_place
115 a1_corner = a1_corner || arc_place
116 end
117 (0...arc_length).each do |arc_position|
118 if arc_position > 0
119 this_arc[arc_position].neighbours << this_arc[arc_position - 1]
120 end
121 if arc_position < (arc_length - 1)
122 this_arc[arc_position].neighbours << this_arc[arc_position + 1]
123 end
124 end
125
126 # build the spoke
127 this_spoke = Array.new
128 (1..(spoke_length - 1)).each do |spoke_position|
129 position_name = arc + "c" + spoke_position.to_s
130 spoke_place = Position.new(position_name, spoke_position == 3, false)
131 spoke_place.neighbours = []
132 @positions[position_name] = spoke_place
133 this_spoke << spoke_place
134 end
135 (0...(spoke_length - 1)).each do |spoke_position|
136 if spoke_position > 0
137 this_spoke[spoke_position].neighbours << this_spoke[spoke_position - 1]
138 end
139 if spoke_position < spoke_length - 2
140 this_spoke[spoke_position].neighbours << this_spoke[spoke_position + 1]
141 end
142 end
143
144 # tie the spoke and arc together,
145 this_arc[0].neighbours << this_spoke[0]
146 this_spoke[0].neighbours << this_arc[0]
147
148 # tie the spoke to the centre, and
149 this_spoke[-1].neighbours << @centre
150 @centre.neighbours << this_spoke[-1]
151
152 # tie the base to the arc
153 base = Position.new(arc, false, true)
154 @positions[arc] = base
155 base.neighbours << this_arc[0]
156 this_arc[0].neighbours << base
157
158 # record the ends of the arc for tying to adjacent arcs
159 if end_of_previous_arc
160 end_of_previous_arc.neighbours << this_arc[0]
161 this_arc[0].neighbours << end_of_previous_arc
162 end
163 end_of_previous_arc = this_arc[-1]
164
165 end # arc
166
167 # tie both ends of the rim together
168 a1_corner.neighbours << end_of_previous_arc
169 end_of_previous_arc.neighbours << a1_corner
170
171 cache_valid_moves
172
173 end # def
174
175 def to_s
176 layout
177 end
178
179 def to_str
180 to_s
181 end
182
183
184 # For each position, show its name and what it touches
185 def layout
186 out_string = ""
187 @positions.keys.sort.each do |position|
188 out_string << sprintf("%s touches ", @positions[position])
189 @positions[position].neighbours.each do |neighbour|
190 out_string << sprintf("%s, ", neighbour)
191 end
192 out_string << sprintf("\n")
193 end
194 out_string
195 end
196
197
198 # Precompute the valid moves for this board, and the distances between each
199 # pair of positions
200 def cache_valid_moves
201 # A hash of arrays. The has key is the name of a positions. The array
202 # element [i] stores the positions that are i spaces from here
203 @valid_moves = Hash.new
204 # A hash of hashes. Given two names, return the shortest distance between
205 # the two locations
206 @distance_between = Hash.new
207 @positions.each do |place, position|
208 @valid_moves[place] = Array.new
209 @distance_between[place] = Hash.new
210 @valid_moves[place][0] = [@positions[place]]
211 @distance_between[place][place] = 0
212 # Find the shortest routes by Dijkstra's algorithm
213 agenda = [position]
214 closed_list = [position]
215 i = 1
216 while not agenda.empty?
217 @valid_moves[place][i] = []
218 new_agenda = []
219 agenda.each do |pos|
220 valid_extensions = pos.neighbours.reject {|new_position| closed_list.include?(new_position) }
221 @valid_moves[place][i] += valid_extensions
222 valid_extensions.each {|ext| @distance_between[place][ext.place] ||= i }
223 closed_list += valid_extensions
224 new_agenda += valid_extensions
225 end
226 agenda = new_agenda
227 i += 1
228 end
229 end
230 end
231
232 end
233
234
235 # Each piece on the board is an object
236 class Piece
237 attr_reader :colour
238 attr_accessor :position, :contains, :captured
239
240 def initialize(number, position, colour)
241 @number = number
242 @position = position
243 @colour = colour
244 @captured = false
245 @contains = []
246 end
247
248 def name
249 @colour + @number.to_s
250 end
251
252 def to_s
253 self.name
254 end
255
256 def to_str
257 to_s
258 end
259
260 def move_to(new_position)
261 @position = new_position
262 @contains.each {|c| c.move_to(new_position)}
263 end
264
265 # Caputre another piece
266 def capture(other_piece)
267 if @position = other_piece.position
268 @contains << other_piece
269 @contains += other_piece.contains
270 other_piece.contains = []
271 other_piece.captured = true
272 else
273 raise(InvalidCaptureError,
274 "Piece #{self.name} cannot capture #{other_piece.name}: different locations")
275 end
276 end
277
278 end
279
280
281 # A move in a game
282 class Move
283 attr_reader :piece, :destination
284
285 def initialize(piece, destination, via_base = false)
286 @piece = piece
287 @destination = destination
288 @via_base = via_base
289 end
290
291 def via_base?
292 @via_base
293 end
294
295 # Write a move to a string
296 # Note the inverse, String#to_move, is defined below
297 def to_s
298 if @via_base
299 if @destination.base?
300 @piece.to_s + " " + @destination.to_s
301 else
302 @piece.to_s + " " + piece.colour + " " + @destination.to_s
303 end
304 else
305 @piece.to_s + " " + @destination.to_s
306 end
307 end
308
309 def to_str
310 to_s
311 end
312
313 end
314
315
316
317 # A class to record each of the states previously found in a game.
318 # Note that this is a deep copy of the pieces and what they've captured, so
319 # you'll need to convert back
320 class GameState
321 attr_accessor :move, :player, :pieces_after_move
322
323 def initialize(move, player, pieces)
324 @move = move
325 @player = player
326 @pieces_after_move = Hash.new
327 pieces.each {|k, p| @pieces_after_move[k] = p.dup}
328 @pieces_after_move.each_value {|p| p.contains = []}
329 # and now to make the captured pieces point to the copies
330 pieces.each do |k, p|
331 p.contains.each do |captured_piece|
332 @pieces_after_move[k].capture(@pieces_after_move[captured_piece.name])
333 end
334 end
335 end
336
337 def ==(other)
338 @move.to_s == other.move.to_s and
339 @player == other.player and
340 @piece_after_move == other.pieces_after_move
341 end
342
343 end
344
345
346 # A game of Trap the Cap. It keeps a history of all previous states.
347 class Game
348
349 attr_reader :history
350 attr_reader :current_player, :players
351 attr_reader :board
352 attr_reader :pieces
353
354 # Create a new game
355 def initialize(players = 6, spokes = 6, spoke_length = 6, arc_length = 6,
356 pieces_each = 6)
357 @board = Board.new(spokes, spoke_length, arc_length)
358 @history = []
359 @pieces = Hash.new
360 @players = case
361 when players == 2 ; ['a', 'd']
362 when players == 3 ; ['a', 'c', 'e']
363 when players == 4 ; ['a', 'b', 'd', 'e']
364 when players == 5 ; ['a', 'b', 'c', 'd', 'e']
365 when players == 6 ; ['a', 'b', 'c', 'd', 'e', 'f']
366 end
367 @current_player = 'a'
368 @players.each do |player|
369 players_base = @board.positions[player]
370 (1..pieces_each).each do |count|
371 piece = Piece.new(count, players_base, player)
372 @pieces[player + count.to_s] = piece
373 end
374 end
375 end
376
377
378 # Apply a single move to a game.
379 def apply_move!(move, player = @current_player)
380 # Check the move is a valid one
381 raise(InvalidMoveError, "Piece #{move.piece} does not exist") unless @pieces.has_key?(move.piece.name)
382 raise(InvalidMoveError, "Player #{player} moving piece #{move.piece}") unless move.piece.colour == player
383 raise(InvalidMoveError, "Attempting to move captured piece #{move.piece}") if move.piece.captured
384 raise(InvalidMoveError, "Attempting to move #{move.piece} onto or via base without captured pieces") if move.via_base? and move.piece.contains.empty?
385 if move.destination.safe?
386 if (@pieces.find_all {|k, p| p.position == move.destination}).length >= 3
387 raise(InvalidMoveError, "Attempting to move #{move.piece} onto safe position #{move.destination} when there are already three or more pieces there")
388 end
389 end
390 if move.via_base?
391 moved_distance = board.distance_between[move.piece.position.place][player] +
392 board.distance_between[player][move.destination.place]
393 else
394 moved_distance = board.distance_between[move.piece.position.place][move.destination.place]
395 end
396 raise(InvalidMoveError, "Attempting to move piece #{move.piece} #{moved_distance} places (from #{move.piece.position} to #{move.destination})") if moved_distance < 1 or moved_distance > 6
397
398 # Apply this move
399 move.piece.move_to(move.destination)
400
401 # Capture anything already there (unless it's a safe place or a base,
402 # or our own colour, or already captured)
403 unless move.destination.safe? or move.destination.base?
404 @pieces.each do |name, target_piece|
405 if target_piece.position == move.destination and
406 target_piece != move.piece and
407 not move.piece.contains.member?(target_piece) and
408 target_piece.colour != player and
409 not target_piece.captured
410 move.piece.capture(target_piece)
411 end
412 end
413 end
414
415 # If the move was via our base, drop all captured pieces
416 if move.via_base?
417 capturers_base = board.positions[move.piece.colour]
418 move.piece.contains.each do |captured_piece|
419 captured_piece.move_to capturers_base
420 captured_piece.captured = false if captured_piece.colour == move.piece.colour
421 end
422 move.piece.contains = []
423 end
424
425 # Record the new stae
426 this_game_state = GameState.new(move, player, @pieces)
427 @history << this_game_state
428
429 # Retain only players that have uncaptured pieces.
430 # If there's only one player with uncaptured pieces, declare a win.
431 potential_players = []
432 @players.each do |p|
433 if (@pieces.values.select {|piece| piece.colour == p}).any? {|piece| not piece.captured}
434 potential_players << p
435 end
436 # potential_players << p if (@pieces.values.select {|p| p.colour == @current_player}).any? {|p| not p.captured}
437 end
438 if potential_players.length <= 1
439 raise(GameWonNotice, "Game won by #{potential_players[0]}")
440 end
441 @players = potential_players.sort
442 end
443
444 # Undo a move
445 def undo_move!
446 if @history.length > 1
447 # general case
448 state_to_restore = @history[-2]
449 @current_player = @history[-1].player
450 @pieces.each do |name, piece|
451 copy_piece = state_to_restore.pieces_after_move[name]
452 piece.position = copy_piece.position
453 piece.captured = copy_piece.captured
454 piece.contains = []
455 copy_piece.contains.each do |p|
456 # piece.capture(@pieces[p.name])
457 piece.contains << @pieces[p.name]
458 end
459 end
460 @history.pop
461 elsif @history.length == 1
462 # reset to start
463 @current_player = 'a'
464 @pieces.each do |name, piece|
465 piece.position = @board.positions[piece.colour]
466 piece.captured = false
467 piece.contains = []
468 end
469 @history.pop
470 end
471 end
472
473 # Apply a list of moves in order
474 def apply_moves!(moves)
475 moves.each do |move|
476 if move.via_base?
477 moved_distance = board.distance_between[move.piece.position.place][@current_player] +
478 board.distance_between[@current_player][move.destination.place]
479 else
480 moved_distance = board.distance_between[move.piece.position.place][move.destination.place]
481 end
482 self.apply_move!(move, @current_player)
483 next_player! unless moved_distance == 6
484 end
485 end
486
487
488 # Set the current player to be the next player
489 def next_player!
490 original_player = @current_player
491 begin
492 if @current_player == @players[-1]
493 @current_player = @players[0]
494 else
495 @current_player = @players[@players.index(@current_player) + 1]
496 end
497 end while (@pieces.values.select {|p| p.colour == @current_player}).all? {|p| p.captured} and @current_player != original_player
498 @current_player
499 end
500
501
502 # Return an array of all possible moves from this state, given the die roll
503 # and the active player
504 def possible_moves(die_result, player = @current_player)
505 moves = []
506 @pieces.each do |key, piece|
507 # only move current player's pieces, and only if they're not captured
508 if piece.colour == player and (not piece.captured)
509 (@board.valid_moves[piece.position.place][die_result]).each do |destination|
510 if destination.safe?
511 if (@pieces.find_all {|k, p| p.position == destination}).length < 3
512 moves << Move.new(piece, destination, false)
513 end
514 else
515 moves << Move.new(piece, destination, false) unless destination.base?
516 end
517 end
518 # if we can move to our base (but not already on it), add moves via that...
519 if @board.distance_between[piece.position.place][player] <= die_result and
520 not piece.position.place == player and
521 not piece.contains.empty?
522 distance_after_base = die_result - @board.distance_between[piece.position.place][player]
523 (@board.valid_moves[player][distance_after_base]).each do |destination|
524 if destination.safe?
525 if (@pieces.find_all {|k, p| p.position == destination}).length < 3
526 moves << Move.new(piece, destination, true)
527 end
528 else
529 moves << Move.new(piece, destination, true)
530 end
531 end
532 end
533 end
534 end
535 moves
536 end
537
538
539 def build_state_string
540 outstr = "Current player = #{@current_player}\n"
541 @pieces.keys.sort.each do |piece_name|
542 if @pieces[piece_name].captured
543 outstr << "Piece #{piece_name} captured, at #{@pieces[piece_name].position}\n"
544 else
545 outstr << "Piece #{piece_name} is at #{@pieces[piece_name].position}, holds #{(@pieces[piece_name].contains.collect{|c| c.name}).join(' ')}\n"
546 end
547 end
548 outstr
549 end
550
551 # Show the state of the board
552 def show_state
553 puts build_state_string
554 # @pieces.keys.sort.each do |piece_name|
555 # if @pieces[piece_name].captured
556 # puts "Piece #{piece_name} captured, at #{@pieces[piece_name].position}"
557 # else
558 # puts "Piece #{piece_name} is at #{@pieces[piece_name].position}, holds #{(@pieces[piece_name].contains.collect{|c| c.name}).join(' ')}"
559 # end
560 # end
561 end
562
563 def to_s
564 show_state
565 end
566
567 def to_str
568 to_s
569 end
570
571
572 # Given a set of lines from an input file, turn them into a Game object and
573 # a set of Move objects.
574 # Note the multiple return values.
575 # Class method
576 def Game.read_game(gamelines)
577 gamelines.each {|l| l.chomp!}
578 game = Game.new(gamelines[0].to_i, 6, 6, 6, 6)
579 moves = []
580 gamelines[1..-2].each {|m| moves << m.to_move(game)}
581 return game, moves, gamelines[-1].to_i
582 end
583
584
585 end
586
587
588 # Extension to String class to convert a move-description string into a Move object.
589 # This is the inverse of the Move#to_s method
590 class String
591 def to_move(game)
592 move_elements = self.downcase.split
593 piece_name = move_elements[0]
594 destination_name = move_elements[-1]
595 if destination_name.length > 2 and
596 destination_name[-2,2] == game.board.centre.place[-2,2]
597 destination_name = game.board.centre.place
598 end
599 raise(InvalidMoveError, "Invalid piece in move read") unless game.pieces.has_key?(piece_name)
600 raise(InvalidMoveError, "Invalid destination in move read") unless game.board.positions.has_key?(destination_name)
601 # Deal with the synonyms for the centre position
602 via_base = (destination_name.length == 1 or move_elements.length > 2)
603 Move.new(game.pieces[piece_name], game.board.positions[destination_name], via_base)
604 end
605 end
606
607
608 # Read a game description file and convert it into a Game object and set of Move objects.
609 # Note that Game.read_game method returns multiple values, so this one does too.
610 class IO
611 def IO.read_game(filename)
612 gamelines = IO.readlines(filename)
613 return Game.read_game(gamelines)
614 end
615 end