15 Puzzle in Python

Question

This is a playable 15 puzzle game in Python and Curses. It consists of 2 files, a backend called fifteen.py and a frontend called curses_frontend.py. The idea is that different frontends could be built for different purposes.

fifteen.py:

from enum import Enum
from collections import namedtuple
import random
Coordinates = namedtuple("Coords",["x","y"])
Direction = Enum("Direction","UP DOWN LEFT RIGHT")
class FifteenPuzzle:
 initial_board = (("1","2","3","4"),
 ("5","6","7","8"),
 ("9","A","B","C"),
 ("D","E","F"," "))
 def __init__(self):
 self.board = [list(row) for row in self.initial_board] # tuple to list
 self.shuffle()
 def shuffle(self):
 for _ in range(100):
 self.move(random.choice(list(Direction)))
 def findzero(self):
 for y,row in enumerate(self.board):
 for x,v in enumerate(row):
 if v == " ":
 return Coordinates(x,y)
 def move(self,direction):
 p = self.findzero()
 if direction == Direction.UP:
 if p.y == 3: return False
 self.board[p.y][p.x] = self.board[p.y+1][p.x]
 self.board[p.y+1][p.x] = " "
 if direction == Direction.DOWN:
 if p.y == 0: return False
 self.board[p.y][p.x] = self.board[p.y-1][p.x]
 self.board[p.y-1][p.x] = " "
 if direction == Direction.LEFT:
 if p.x == 3: return False
 self.board[p.y][p.x] = self.board[p.y][p.x+1]
 self.board[p.y][p.x+1] = " "
 if direction == Direction.RIGHT:
 if p.x == 0: return False
 self.board[p.y][p.x] = self.board[p.y][p.x-1]
 self.board[p.y][p.x-1] = " "
 return True
 def is_win(self):
 return tuple(tuple(row) for row in self.board) == self.initial_board
 def __str__(self):
 ret = ""
 for row in self.board:
 for val in row:
 ret += val
 ret += "\n"
 return ret[:-1] # strip trailing newline

curses_frontend.py

#!/usr/bin/env python3
from fifteen import FifteenPuzzle, Direction
from pathlib import Path
import time
import os
import curses
DEFAULT_HIGHSCORE = 999
SAVE_LOCATION = Path.home()/".15scores"
class CursesApp():
 KEYS_UP = [ord('w'),ord('W'),ord('j'),ord('J'),curses.KEY_UP]
 KEYS_DOWN = [ord('s'),ord('S'),ord('k'),ord('K'),curses.KEY_DOWN]
 KEYS_LEFT = [ord('a'),ord('A'),ord('h'),ord('H'),curses.KEY_LEFT]
 KEYS_RIGHT = [ord('d'),ord('D'),ord('l'),ord('L'),curses.KEY_RIGHT]
 def __init__(self):
 pass
 def __enter__(self):
 self.stdscr = curses.initscr()
 curses.noecho()
 curses.cbreak()
 self.stdscr.keypad(True)
 curses.curs_set(False)
 
 self.puzzle_win = curses.newwin(4,5,0,0) # extra space for newlines
 self.score_win = curses.newwin(1,curses.COLS - 1,4,0)
 self.message_win = curses.newwin(1,curses.COLS - 1,5,0)
 self.stdscr.refresh()
 self.score_win.addstr(0,0,"Moves: ")
 self.score_win.refresh()
 
 return self
 def __exit__(self,typ,val,tb):
 curses.nocbreak()
 self.stdscr.keypad(False)
 curses.curs_set(True)
 curses.echo()
 curses.endwin()
 def draw_puzzle(self,puzzle):
 self.puzzle_win.clear()
 self.puzzle_win.addstr(0,0,str(puzzle))
 self.puzzle_win.refresh()
 def draw_message(self,s):
 self.message_win.clear()
 self.message_win.addstr(0,0,s)
 self.message_win.refresh()
 def draw_score(self,score):
 self.score_win.addstr(0,7," ") # clear regular score
 self.score_win.addstr(0,7,str(score)) 
 self.score_win.refresh()
 def draw_highscore(self,score):
 self.score_win.addstr(0,11,"High Score: ")
 self.score_win.addstr(0,23,str(score))
 self.score_win.refresh()
def gethighscore():
 try:
 with open(SAVE_LOCATION, 'r') as f:
 return int(f.readline().rstrip())
 except FileNotFoundError:
 return DEFAULT_HIGHSCORE
 except ValueError:
 os.remove(str(SAVE_LOCATION))
 return DEFAULT_HIGHSCORE+1
 
def sethighscore(s):
 with open(SAVE_LOCATION, 'w') as f:
 f.write(str(s))
 
def main(app):
 puzzle = FifteenPuzzle()
 highscore = gethighscore()
 while True:
 puzzle.shuffle()
 score = 0
 app.draw_score(0)
 if highscore < DEFAULT_HIGHSCORE:
 app.draw_highscore(highscore)
 if highscore == DEFAULT_HIGHSCORE+1:
 app.draw_message("High score file corrupted. Erasing")
 time.sleep(1)
 while not puzzle.is_win():
 app.draw_puzzle(puzzle)
 app.draw_message("arrows/hjkl/wasd:Move|q:quit")
 c = app.stdscr.getch()
 direction = None
 if c in app.KEYS_UP:
 direction = Direction.UP
 if c in app.KEYS_DOWN:
 direction = Direction.DOWN
 if c in app.KEYS_LEFT:
 direction = Direction.LEFT
 if c in app.KEYS_RIGHT:
 direction = Direction.RIGHT
 if direction:
 if puzzle.move(direction):
 score+=1
 app.draw_score(score)
 else:
 app.draw_message("Invalid move")
 time.sleep(0.5)
 if c in (ord('q'),ord('Q')):
 app.draw_message("Press q again to quit")
 if app.stdscr.getch() in (ord('q'),ord('Q')):
 return
 app.draw_puzzle(puzzle) 
 while True:
 if score < highscore:
 highscore = score
 app.draw_highscore(score)
 app.draw_message("New high score!")
 sethighscore(score)
 time.sleep(0.5)
 app.draw_message("Play again? (y/n)")
 c = app.stdscr.getch()
 if c in (ord('y'),ord('Y')):
 break # from inner loop to return to outer loop
 if c in (ord('n'),ord('N')):
 return # from entire function
 
if(__name__ == "__main__"):
 with CursesApp() as app:
 main(app)
 print("Thanks for playing!")

Answer 1

fifteen.py

__init__

• For easier testing, consider adding a way to initialize the board to a certain state. Something like this would be nice:

  """
  2 81
  73B6
  A4EC
  59DF
  """
  puzzle = FifteenPuzzle("2 8173B6A4EC59DF")
  

  You would need to validate the input and transform it into a 4x4 grid (and of course omit the call to shuffle() for this flow) which is a bit of extra work, but it will prove very useful when writing unit tests.
• You should initialize an instance variable to track the coordinates of the blank space (more on this below).

shuffle

• You're repeatedly calling list(Direction) within the loop when you could instead call it once outside the loop and bind it to a local variable. Also it doesn't need to be a list because we're not mutating it in any way, and random.choice accepts any sequence. So I would do directions = tuple(Direction) before the loop to get a sequence of all the directions.
• To avoid doing a bunch of repeated attribute lookups (e.g. self.move, random.choice) in a loop, we can instead do the lookups once and save the results in local variables for a speedup:

  def shuffle(self) -> None:
   directions = tuple(Direction)
   move = self.move
   random_choice = random.choice
   for _ in range(100):
   move(random_choice(directions))
  

  Source is this page on Python speed:

  In functions, local variables are accessed more quickly than global variables, builtins, and attribute lookups. So, it is sometimes worth localizing variable access in inner-loops. For example, the code for random.shuffle() localizes access with the line, random=self.random. That saves the shuffling loop from having to repeatedly lookup self.random. Outside of loops, the gain is minimal and rarely worth it.

findzero

• A more apt name for this is probably find_blank since we're actually finding the blank space (missing tile) in the puzzle.

move

• findzero is called every time move is called, which means we do a full scan of the board to find the blank space each time before stepping into the move logic. This is inefficient. Instead, track the coordinates of the blank space as an instance variable, e.g. self.blank_space. Then we only need to call findzero once, right after board initialization. After self.blank_space is initialized, on every move we can update self.blank_space accordingly.
• There is a lot of duplicated logic here that essentially swaps a designated adjacent tile with the current blank space based on the given direction. I would refactor some of this logic into a helper method that takes in the coordinates of the designated tile, and does the swapping and updating of the blank space position for you:

  def move_tile_to_blank(self, t: Coordinates) -> None:
   board = self.board
   b = self.blank_space
   board[b.y][b.x], board[t.y][t.x] = board[t.y][t.x], board[b.y][b.x]
   self.blank_space = t
  

is_win

• A better name for this method is probably is_solved.
• This is a prime candidate for the @property decorator so you can retrieve this status like you would an attribute:

  >>> puzzle = FifteenPuzzle("2 8173B6A4EC59DF")
  >>> puzzle.is_solved
  False
  >>> puzzle = FifteenPuzzle("123456789ABCDEF ")
  >>> puzzle.is_solved
  True
  

• Instead of converting the whole board to a tuple of tuples and comparing it to initial_board, it's more time- and memory-efficient to compare the boards tile-by-tile with iterators:

  @property
  def is_solved(self) -> bool:
   return all(
   tile == expected_tile
   for tile, expected_tile in zip(
   itertools.chain.from_iterable(self.board),
   itertools.chain.from_iterable(self.initial_board)
   )
   )
  

__str__

• Use join() to concatenate strings. From the same page on Python speed:

  String concatenation is best done with ''.join(seq) which is an O(n) process. In contrast, using the '+' or '+=' operators can result in an O(n**2) process because new strings may be built for each intermediate step. The CPython 2.4 interpreter mitigates this issue somewhat; however, ''.join(seq) remains the best practice.

  So this can actually be refactored to the following one-liner:

  def __str__(self) -> str:
   return "\n".join("".join(row) for row in self.board)
  

Style

The following comments can be addressed by hand, or if you don't mind delegating that responsibility to a tool, you can use a code formatter like Black which will do it for you.

• Leave whitespace in between method declarations, it makes the code easier to read.

• Leave a space after commas, e.g.

  # Yes:
  ("1", "2", "3", "4")
  # No:
  ("1","2","3","4")
  # Yes:
  def move(self, direction):
  # No:
  def move(self,direction):
  

curses_frontend.py

Dependency injection

Your frontend logic exists in both the CursesApp class and the main() method, but I think it would be cleaner for all the logic to live in CursesApp instead. Dependencies such as FifteenPuzzle could then be initialized and injected into CursesApp. More on this below.

High score management

I would create a separate class dedicated to score management with the following responsibilities:

• loading the high score from a file
• tracking the current score and high score
• incrementing the current score
• resetting the current score
• saving the high score to a file

Then this score tracker could be initialized and injected into CursesApp as a dependency, just like FifteenPuzzle.

curses.wrapper

Your CursesApp is a context manager that does proper setup/teardown of the curses application via methods like curses.noecho(), curses.cbreak(), etc. The curses module actually provides a nice convenience method curses.wrapper() which does the same thing without all of that boilerplate code.

time.sleep

I would generally avoid using time.sleep here; it blocks the main thread, and combined with input buffering, if we make enough (let's say k) "invalid moves" in rapid succession, we end up with an unresponsive application for k * SLEEP_TIME seconds. This is not a great user experience.

Instead, I would recommend giving the keyboard controls text its own line and moving the message window to its own line. Then you can use the pattern of displaying messages, blocking on any user input, and clearing the message once you've received that user input.

draw_score and draw_highscore

These should honestly be combined into one method, i.e. any time you print the current score, you should also print the high score as well. One advantage of doing things this way is we avoid brittle logic like

self.score_win.addstr(0,7," ") # clear regular score
self.score_win.addstr(0,7,str(score))

where we are implicitly assuming the current score will never exceed four digits.

Mapping keyboard input to a Direction

Use a map of ASCII values to Directions instead of using four separate lists and if statements. So instead of this

direction = None
if c in app.KEYS_UP:
 direction = Direction.UP
if c in app.KEYS_DOWN:
 direction = Direction.DOWN
if c in app.KEYS_LEFT:
 direction = Direction.LEFT
if c in app.KEYS_RIGHT:
 direction = Direction.RIGHT
if direction:
 # ...

you could have a map that starts out like this

KEY_TO_DIRECTION = {
 curses.KEY_UP: Direction.UP,
 curses.KEY_DOWN: Direction.DOWN,
 curses.KEY_LEFT: Direction.LEFT,
 curses.KEY_RIGHT: Direction.RIGHT,
}

a separate map for custom key aliases for up/down/left/right

DIRECTION_TO_CUSTOM_KEYS = {
 Direction.UP: ("w", "j"),
 Direction.DOWN: ("s", "k"),
 Direction.LEFT: ("a", "h"),
 Direction.RIGHT: ("d", "l"),
}

then you can populate KEY_TO_DIRECTION like so

for direction, keys in DIRECTION_TO_CUSTOM_KEYS.items():
 for key in keys:
 KEY_TO_DIRECTION[ord(key.lower())] = direction
 KEY_TO_DIRECTION[ord(key.upper())] = direction

and use it like so

if direction := KEY_TO_DIRECTION.get(c, None):
 # do something with `direction`

Style

• PEP8 recommends the following order for imports, with a blank line between each group of imports:

  1. Standard library imports
  2. Related third party imports
  3. Local application/library specific imports

• Same issues here with lack of whitespace between methods and lack of whitespace after commas

• Drop unnecessary parentheses for the __main__ guard, i.e. if __name__ == "__main__":

Refactored version

Here's a refactored version (Python 3.8) of curses_frontend.py with the above suggestions incorporated:

#!/usr/bin/env python3
import curses
from pathlib import Path
from typing import Tuple
from fifteen import FifteenPuzzle, Direction
DEFAULT_HIGHSCORE = 999
SAVE_LOCATION = Path.home() / ".15scores"
DIRECTION_TO_CUSTOM_KEYS = {
 Direction.UP: ("w", "j"),
 Direction.DOWN: ("s", "k"),
 Direction.LEFT: ("a", "h"),
 Direction.RIGHT: ("d", "l"),
}
class Scoreboard:
 score: int
 high_score: int
 save_file: Path
 def __init__(self, save_file: Path) -> None:
 self.save_file = save_file
 self._load_high_score()
 self.score = 0
 def _load_high_score(self) -> None:
 try:
 self.high_score = int(self.save_file.read_text().strip())
 except (FileNotFoundError, ValueError):
 self.high_score = DEFAULT_HIGHSCORE
 def increment(self, k: int = 1) -> None:
 self.score += k
 def reset(self) -> None:
 self.score = 0
 @property
 def current_and_high_score(self) -> Tuple[int, int]:
 return (self.score, self.high_score)
 def publish(self) -> bool:
 if self.score < self.high_score:
 self.save_file.write_text(str(self.score))
 self.high_score = self.score
 return True
 return False
class CursesApp:
 QUIT_KEYS = (ord("q"), ord("Q"))
 YES_KEYS = (ord("y"), ord("Y"))
 NO_KEYS = (ord("n"), ord("N"))
 KEY_TO_DIRECTION = {
 curses.KEY_UP: Direction.UP,
 curses.KEY_DOWN: Direction.DOWN,
 curses.KEY_LEFT: Direction.LEFT,
 curses.KEY_RIGHT: Direction.RIGHT,
 }
 def __init__(self, stdscr, puzzle, scoreboard):
 self.stdscr = stdscr
 self.puzzle = puzzle
 self.scoreboard = scoreboard
 curses.curs_set(False)
 curses.use_default_colors()
 self.puzzle_win = curses.newwin(4, 5, 0, 0)
 self.score_win = curses.newwin(1, curses.COLS - 1, 4, 0)
 self.stdscr.addstr(5, 0, "arrows/hjkl/wasd:move | q:quit")
 self.message_win = curses.newwin(1, curses.COLS - 1, 6, 0)
 self.stdscr.refresh()
 _ord = ord
 key_map = self.KEY_TO_DIRECTION
 for direction, keys in DIRECTION_TO_CUSTOM_KEYS.items():
 for key in keys:
 key_map[_ord(key.lower())] = direction
 key_map[_ord(key.upper())] = direction
 def start(self):
 while self.play():
 self.scoreboard.reset()
 self.puzzle.shuffle()
 def play(self):
 while self.refresh() and not self.puzzle.is_solved:
 c = self.stdscr.getch()
 if c in self.QUIT_KEYS:
 self.draw_message("Press q again to quit")
 if self.stdscr.getch() in self.QUIT_KEYS:
 return False
 self.clear_message()
 elif direction := self.KEY_TO_DIRECTION.get(c, None):
 if self.puzzle.move(direction):
 self.scoreboard.increment()
 if self.scoreboard.publish():
 self.draw_scores()
 self.draw_message("New high score!")
 self.block_on_input()
 return self.wants_to_play_again()
 def wants_to_play_again(self):
 while True:
 self.draw_message("Play again? (y/n)")
 c = self.stdscr.getch()
 if c in self.YES_KEYS:
 self.clear_message()
 return True
 elif c in self.NO_KEYS:
 self.clear_message()
 return False
 def draw_scores(self):
 current_score, high_score = self.scoreboard.current_and_high_score
 scores = f"Moves: {current_score} | High Score: {high_score}"
 self.score_win.clear()
 self.score_win.addstr(0, 0, scores)
 self.score_win.refresh()
 def refresh(self):
 self.puzzle_win.addstr(0, 0, str(self.puzzle))
 self.puzzle_win.refresh()
 self.draw_scores()
 return True
 def draw_message(self, s):
 self.message_win.clear()
 self.message_win.addstr(0, 0, s)
 self.message_win.refresh()
 def clear_message(self):
 self.message_win.clear()
 self.message_win.refresh()
 def block_on_input(self):
 return self.stdscr.getch()
def main(stdscr):
 puzzle = FifteenPuzzle()
 scoreboard = Scoreboard(SAVE_LOCATION)
 CursesApp(stdscr, puzzle, scoreboard).start()
if __name__ == "__main__":
 curses.wrapper(main)
 print("Thanks for playing!")