<commit_before># maze.rb is licensed under the Apache Software License, version 2.0 
# and Copyright (c) 2010 <NAME> (http://willbenton.com)

class Maze
  def initialize(x,y)
    @cg = CellGraph.new(x,y)
  end
  
  attr_reader :cg
  
  def size 
    [@cg.x,@cg.y]
  end
  
  def gen
    reset
    while @walls.size > 0
      source,dest = @walls.delete_at(rand(@walls.size))
      unless @maze_cells.include? dest
        @maze_cells << dest
        @cg.add_edge(source=>dest)
        @walls = @walls + walls_for(dest)
      end
    end
  end
  
  def walls_for(cell)
    @cg.neighbors(cell).map {|nbc| [cell,nbc]} - @cg.edges_from(cell)
  end
  
  def closed_sides(cell)
    cx,cy = @cg.coords_for_cell(cell)
    positions = {:left=>[-1,0], :right=>[+1,0], :top=>[0,-1], :bottom=>[0,+1]}
    result = positions.inject([]) do |acc, pair| 
      dir = pair[0]
      dx,dy = pair[1]
      candidate_coords = [cx+dx,cy+dy]
      acc << dir if !(cg.in_graph(*candidate_coords)) || (!cg.edges_from(cell).map {|s,d| d}.include? @cg.cell_for_coords(*candidate_coords))
      acc
    end
    
    result -= [:top] if cell == @startcell
    result -= [:bottom] if cell == @endcell
    
    result
  end
  
  private
  def reset
    @cg.reset_edges
    
    @maze_cells = (Set.new << 0)
    @walls = walls_for(0)
    
    @startcell = 0
    @endcell = (@cg.x * @cg.y) - 1
  end
end
<commit_msg>Added recursive-backtracking maze generator<commit_after># maze.rb is licensed under the Apache Software License, version 2.0 
# and Copyright (c) 2010 <NAME> (http://willbenton.com)

# common infrastructure
module MazeBase
  def initialize(x,y)
    @cg = CellGraph.new(x,y)
    @startcell = 0
    @endcell = (@cg.x * @cg.y) - 1
  end
  
  attr_reader :cg
  
  def size 
    [@cg.x,@cg.y]
  end
  
  def walls_for(cell)
    @cg.neighbors(cell).map {|nbc| [cell,nbc]} - @cg.edges_from(cell)
  end
  
  def closed_sides(cell)
    cx,cy = @cg.coords_for_cell(cell)
    positions = {:left=>[-1,0], :right=>[+1,0], :top=>[0,-1], :bottom=>[0,+1]}
    result = positions.inject([]) do |acc, pair| 
      dir = pair[0]
      dx,dy = pair[1]
      candidate_coords = [cx+dx,cy+dy]
      acc << dir if !(cg.in_graph(*candidate_coords)) || (!cg.edges_from(cell).map {|s,d| d}.include? @cg.cell_for_coords(*candidate_coords))
      acc
    end
    
    result -= [:top] if cell == @startcell
    result -= [:bottom] if cell == @endcell
    
    result
  end
end

# Prim algorithm maze generator
class MazePrim
  include MazeBase
  
  def gen
    reset
    while @walls.size > 0
      source,dest = @walls.delete_at(rand(@walls.size))
      unless @maze_cells.include? dest
        @maze_cells << dest
        @cg.add_edge(source=>dest)
        @walls = @walls + walls_for(dest)
      end
    end
  end

  private
  def reset
    @cg.reset_edges
    
    @maze_cells = (Set.new << 0)
    @walls = walls_for(0)
  end
end

# recursive-backtracking maze generator
class MazeRB
  include MazeBase

  def gen
    reset
    gen_from(@startcell)
  end
  
  private
  def reset
    @cg.reset_edges
    
    @maze_cells = Set.new << @startcell
  end

  def gen_from(cell)
    @maze_cells << cell
    neighbor_set = (Set[*@cg.neighbors(cell)] - @maze_cells)

    while not neighbor_set.empty?
      dest = neighbor_set.to_a.delete_at(rand(neighbor_set.size))
      neighbor_set.delete(dest)
      @cg.add_edge(cell=>dest)
      gen_from(dest)
      neighbor_set -= @maze_cells
    end
  end
end
    
{'fraction_non_alphanumeric': 0.14364161849710982, 'fraction_numerical': 0.012138728323699421, 'mean_word_length': 2.6508438818565403, 'pattern_counts': {'":': 0, '<': 21, '<?xml version=': 0, '>': 18, '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': '2100760', 'n_tokens_mistral': 1384, 'n_tokens_neox': 1321, 'n_words': 286}