I started learning racket and I'm using arbitrary arity trees and generative recursion to get every possible version of the board from a given board.
So let's say I have this board, where false means empty:
(list "X" "X" "O" "O" "X" "O" "X" #false "X")
The solution for this according to the requirements would be:
(list
(list "X" "X" "O" "O" "X" "O" "X" "X" "X")
(list "X" "X" "O" "O" "X" "O" "X" "O" "X"))
The solution in racket works great. I tried the same thing in Python, but it doesn't quite work as expected.
I keep getting outputs like these:
[['X', 'X', 'O', 'O', 'X', 'O', 'X', 'X', 'X'], [['X', 'X', 'O', 'O', 'X', 'O', 'X', 'O', 'X'], []]]
or
['X', 'X', 'O', 'O', 'X', 'O', 'X', 'X', 'X', 'X', 'X', 'O', 'O', 'X', 'O', 'X', 'O', 'X']
or worse.
I can't seem to get it to give me the output I want.
I was thinking of doing some post processing on the output if nothing else works, but I would like to avoid that.
What I need is this:
[['X', 'X', 'O', 'O', 'X', 'O', 'X', 'X', 'X'], ['X', 'X', 'O', 'O', 'X', 'O', 'X', 'O', 'X']]
In any case, let me know if you can help.
Here is my python code:
"""
Brute force solution for tic-tac-toe.
"""
"""
Data definitions:
;; Value is one of:
;; - false
;; - "X"
;; - "O"
;; interp. a square is either empty (represented by false) or has and "X" or an "O"
;; Board is (listof Value)
;; a board is a list of 9 Values
"""
#
## CONSTANTS
#
B0 = [False for i in range(9)]
B1 = [
False, "X", "O",
"O", "X", "O",
False, False, "X"
]
B2 = [
"X", "X", "O",
"O", "X", "O",
"X", False, "X",
]
B3 = [
"X", "O", "X",
"O", "O", False,
"X", "X", False,
]
"""
PROBLEM 1
In this problem we want you to design a function that produces all
possible filled boards that are reachable from the current board.
In actual tic-tac-toe, O and X alternate playing. For this problem
you can disregard that. You can also assume that the players keep
placing Xs and Os after someone has won. This means that boards that
are completely filled with X, for example, are valid.
"""
def fill_board(index, bd):
"""
Returns a list of 2 board versions with
the index filled with "X" and "O"
:param index: int; index of position in list to be filled
:param bd: Board
:return: (listof Board)
"""
return [
bd[:index] + ["X"] + bd[index+1:],
bd[:index] + ["O"] + bd[index + 1:],
]
assert fill_board(0, B1) == [
[
"X", "X", "O",
"O", "X", "O",
False, False, "X"
],
[
"O", "X", "O",
"O", "X", "O",
False, False, "X"
],
]
assert fill_board(5, B3) == [
[
"X", "O", "X",
"O", "O", "X",
"X", "X", False,
],
[
"X", "O", "X",
"O", "O", "O",
"X", "X", False,
],
]
def find_blank(bd):
"""
Return the index of the
first empty (False) value
in the board.
ASSUME: there is at least one
empty cell.
:param bd: Board
:return: Index
"""
return bd.index(False)
assert find_blank(B0) == 0
assert find_blank(B2) == 7
assert find_blank(B3) == 5
def next_boards(bd):
"""
Produce the next version of initial board.
Finds the first empty (False) cell, and produces
2 versions of the board; one with X and one with O
:param bd: Board
:return: (listof Board)
"""
return fill_board(find_blank(bd), bd)
assert next_boards(B0) == [
["X"] + B0[1:],
["O"] + B0[1:],
]
assert next_boards(B3) == [
[
"X", "O", "X",
"O", "O", "X",
"X", "X", False,
],
[
"X", "O", "X",
"O", "O", "O",
"X", "X", False,
],
]
def solve(bd):
"""
Produce all possible filled boards that are
reachable from the current board.
:param bd: Board (listof Value)
:return: (listof Board)
"""
def is_full(bd):
"""
Returns true if board is full; meaning
if every value on the board is a string.
:param bd: Board (listof Value)
:return: Boolean
"""
return all(type(i) is str for i in bd)
def solve__bd(bd):
"""
Mutually refential function with
solve__lobd. This is where all the actual
computation takes place.
The two functions are responsible for
generating and operating on the tree.
The tree (arbitraty arity tree) represents
another version of the board filled with an
additional X or O.
:param bd: Board (listof Value)
:return: (listof Board)
"""
if is_full(bd):
return list(bd)
return solve__lobd(next_boards(bd))
def solve__lobd(lobd):
"""
Helper function of solve, alongside solve__bd
:param lobd: (listof Board)
:return: (listof Board)
"""
if not lobd:
return []
return [solve__bd(lobd[0]), solve__lobd(lobd[1:])]
return solve__bd(bd)
assert solve(B2) == [
[
"X", "X", "O",
"O", "X", "O",
"X", "X", "X",
],
[
"X", "X", "O",
"O", "X", "O",
"X", "O", "X",
],
]
assert solve(B3) == [
[
"X", "O", "X",
"O", "O", "X",
"X", "X", "X",
],
[
"X", "O", "X",
"O", "O", "X",
"X", "X", "O",
],
[
"X", "O", "X",
"O", "O", "O",
"X", "X", "X",
],
[
"X", "O", "X",
"O", "O", "O",
"X", "X", "O",
],
]
This looks like a cons-like confusion. I have not tested this, but I'm betting that your issue arises here:
I'm guessing you want
... instead.
BUT: Python lists are not linked lists.
consis an efficient and reasonable way to add an element to a list in Racket, but forming a list using Python's+operator on a one-element list and a longer list will require copying all later elements of the list.For short lists (linear operations on lists of less than, say, 10K elements or quadratic operations on lists of less than 100 elements or so), it won't matter. For longer ones, it will. Python people will tell you that you're doing it wrong, that you should use mutation on existing arrays. Racket people will then tell you that the Python people are stuck in the past. Welcome to the wonderful world of programming!