<commit_before># cython: profile=True
import numpy as np
cimport numpy as np
from collections import namedtuple
import itertools
cimport cython


cdef np.int8_t BLANK = 0
cdef int SEARCH_LIMIT = 80
SOLVED = np.array(
    [[1, 2, 3, 4],
     [5, 6, 7, 8],
     [9, 10, 11, 12],
     [13, 14, 15, BLANK]],
    dtype=np.int8
)

cdef struct index:
    int x
    int y

class Node(namedtuple("Node", ("distance", "cost", "board", "parent"))):
    """
    A `Node` represents a board state which has a `distance` away from
    the starting board state. It has a reference to its `parent` state
    so that the path back to the start can be discovered for any `Node`.
    """
    def __lt__(self, other):
        """
        Necessary so that the numpy array doesn't get compared.
        We don't care about the ordering for equal distances.
        """
        return (self.distance + self.cost) < (other.distance + other.cost)

    def __repr__(self):
        return repr((self.distance, self.board))

    __slots__ = ()


cdef int manhattan_distance(np.ndarray[np.int8_t, ndim=2] board):
    """Manhattan distance finds how many squares out of place each value in
    `board` is. This is also known as "taxicab distance".
    """
    cdef int result = 0
    cdef int i, j, x, y
    cdef index find_result

    for i in range(4):
        for j in range(4):
            find_result = find(SOLVED, board[i, j])
            x = find_result.x
            y = find_result.y
            result += abs(i - x) + abs(j - y)

    return result


@cython.profile(False)
cdef inline index find(np.ndarray[np.int8_t, ndim=2] board, np.int8_t value):
    """`find` finds the indices of `value` in `board` and stores them in `result`."""
    cdef int i, j
    cdef index result
    for i in range(4):
        for j in range(4):
            if board[i, j] == value:
                # find will always find the value; the caller's risk to take.
                result.x = i
                result.y = j
                return result


cpdef search2(queue, set visited):
    """
    `search` iteratively gets `Node`s out of `queue`, adding them to `visited`
    as it goes. For each item, `moves` is called on the node's board. Each
    move is added to the queue if it is not already in the visited set.
    """
    cdef int i, j, cost
    cdef int iter = 0
    while not queue.empty():
        node = queue.get()

        if solved(node.board, SOLVED):
            return node

        visited.add(str(node.board.data))

        for m in moves2(node.board):
            cost = manhattan_distance(m)
            if str(m.data) not in visited:
                queue.put(Node(node.distance + 1, cost, m, node))


cdef bint solved(np.ndarray[np.int8_t, ndim=2] board,
                 np.ndarray[np.int8_t, ndim=2] solved_board):
    """`solved` checks to see if the board in question is the solution."""
    cdef int i, j
    for i in range(4):
        for j in range(4):
            if board[i, j] != solved_board[i, j]:
                return False
    return True


cdef list moves2(np.ndarray[np.int8_t, ndim=2] board):
    """
    `moves` generates the next set of moves for the given board.
    """
    cdef int i, j, x, y
    cdef index find_result
    cdef np.ndarray[np.int8_t, ndim=2] newboard
    cdef index[4] moves = [index(0, 1), index(1, 0), index(0, -1), index(-1, 0)]
    cdef np.int8_t t1, t2

    find_result = find(board, BLANK)
    i = find_result.x
    j = find_result.y

    newboard = np.copy(board)
    cdef list results = []
<commit_msg>Remove find() and inline it instead. At this point solve2 is 9x faster.<commit_after># cython: profile=True
import numpy as np
cimport numpy as np
from collections import namedtuple
import itertools
cimport cython


cdef np.int8_t BLANK = 0
cdef int SEARCH_LIMIT = 80
SOLVED = np.array(
    [[1, 2, 3, 4],
     [5, 6, 7, 8],
     [9, 10, 11, 12],
     [13, 14, 15, BLANK]],
    dtype=np.int8
)


cdef struct index:
    int x
    int y


class Node(namedtuple("Node", ("distance", "cost", "board", "parent"))):
    """
    A `Node` represents a board state which has a `distance` away from
    the starting board state. It has a reference to its `parent` state
    so that the path back to the start can be discovered for any `Node`.
    """
    def __lt__(self, other):
        """
        Necessary so that the numpy array doesn't get compared.
        We don't care about the ordering for equal distances.
        """
        return (self.distance + self.cost) < (other.distance + other.cost)

    def __repr__(self):
        return repr((self.distance, self.board))

    __slots__ = ()


cdef int manhattan_distance(np.ndarray[np.int8_t, ndim=2] board,
                            np.ndarray[np.int8_t, ndim=2] solved_board):
    """Manhattan distance finds how many squares out of place each value in
    `board` is. This is also known as "taxicab distance".
    """
    cdef int result = 0
    cdef int i, j
    cdef int x, y

    # For each tile in the game
    for i in range(4):
        for j in range(4):

            # For each tile in the solved game
            for x in range(4):
                for y in range(4):
                    if board[i, j] == solved_board[x, y]:
                        result += abs(i - x) + abs(j - y)

    return result


cpdef search2(queue, set visited):
    """
    `search` iteratively gets `Node`s out of `queue`, adding them to `visited`
    as it goes. For each item, `moves` is called on the node's board. Each
    move is added to the queue if it is not already in the visited set.
    """
    cdef int i, j, cost
    cdef int iter = 0
    cdef np.ndarray[np.int8_t, ndim=2] solved_board

    solved_board = SOLVED

    while not queue.empty():
        node = queue.get()

        if board_equals(node.board, solved_board):
            return node

        visited.add(str(node.board.data))

        for m in moves2(node.board):
            cost = manhattan_distance(m, solved_board)
            if str(m.data) not in visited:
                queue.put(Node(node.distance + 1, cost, m, node))


cdef bint board_equals(np.ndarray[np.int8_t, ndim=2] a,
                       np.ndarray[np.int8_t, ndim=2] b):
    """`board_equals` checks to see if the boards are equal"""
    cdef int i, j
    for i in range(4):
        for j in range(4):
            if a[i, j] != b[i, j]:
                return False
    return True


cdef list moves2(np.ndarray[np.int8_t, ndim=2] board):
    """
    `moves` generates the next set of moves for the given board.
    """
    cdef int i, j, x, y
    cdef np.ndarray[np.int8_t, ndim=2] newboard
    cdef index[4] moves = [index(0, 1), index(1, 0), index(0, -1), index(-1, 0)]
    cdef np.int8_t t1, t2

    for i in range(4):
        for j in range(4):
            if board[i, j] == BLANK:
                # iteration ends, i and j now point to the blank tile
                break
        else:
            continue
        break

    newboard = np.copy(board)
    cdef list results = []

{'fraction_non_alphanumeric': 0.10990734141126159, 'fraction_numerical': 0.018674269422665715, 'mean_word_length': 2.177536231884058, 'pattern_counts': {'":': 0, '<': 5, '<?xml version=': 0, '>': 3, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '60489', 'n_tokens_mistral': 2401, 'n_tokens_neox': 2289, 'n_words': 847}