Class: Dlx::SparseMatrix

Inherits:
Object
  • Object
show all
Defined in:
lib/dlx/sparse_matrix.rb

Instance Attribute Summary collapse

Instance Method Summary collapse

Constructor Details

#initialize ⇒ SparseMatrix

Returns a new instance of SparseMatrix.



8
9
10
11
12
13
 
# File 'lib/dlx/sparse_matrix.rb', line 8

def initialize
  @root = Dlx::Header.new(0, -1)
  @string_rows = Array.new
  @width = @height = 0
  @headers = Array.new
end

Instance Attribute Details

#headers ⇒ Object (readonly)

Returns the value of attribute headers.



6
7
8
 
# File 'lib/dlx/sparse_matrix.rb', line 6

def headers
  @headers
end

#height ⇒ Object (readonly)

Returns the value of attribute height.



6
7
8
 
# File 'lib/dlx/sparse_matrix.rb', line 6

def height
  @height
end

#root ⇒ Object (readonly)

Returns the value of attribute root.



6
7
8
 
# File 'lib/dlx/sparse_matrix.rb', line 6

def root
  @root
end

#width ⇒ Object (readonly)

Returns the value of attribute width.



6
7
8
 
# File 'lib/dlx/sparse_matrix.rb', line 6

def width
  @width
end

Instance Method Details

#<<(string) ⇒ Object 



15
16
17
 
# File 'lib/dlx/sparse_matrix.rb', line 15

def <<(string)
  add(string)
end

#add(string) ⇒ Object

Raises:

  • (ArgumentError) 


19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
 
# File 'lib/dlx/sparse_matrix.rb', line 19

def add(string)
  raise ArgumentError, "Empty string" if string.empty?
  if @width == 0
    @width = string.length
    create_headers
  elsif string.length != @width
    raise ArgumentError, "Width is: #{string.length}, expected: #{@width}"
  end

  row = []
  string.scan(/./).zip(@headers).each do |l, header|
    if l == "1"
      node = Dlx::Node.new(@height, header.col, header)
      row << node
      header.add(node)
    end
  end

  link_row(row)

  @string_rows << string
  @height += 1
  self
end

#cover(node) ⇒ Object

Removes given node’s column from matrix. Removes each node in same row as given node from their columns



90
91
92
93
94
95
 
# File 'lib/dlx/sparse_matrix.rb', line 90

def cover(node)
  node.header.remove(:row)
  node.header.each_in(:down) do |row|
    row.each_in(:right) { |n| n.remove(:column) }
  end
end

#create_headers ⇒ Object 



44
45
46
47
48
49
50
51
52
53
 
# File 'lib/dlx/sparse_matrix.rb', line 44

def create_headers
  @width.times do |col|
    @headers << Dlx::Header.new(0, col)
  end
  link_row(@headers)
  @root.right = @headers.first
  @root.right.left = @root
  @root.left = @headers.last
  @root.left.right = @root
end

#link_row(row) ⇒ Object 



55
56
57
58
59
60
61
 
# File 'lib/dlx/sparse_matrix.rb', line 55

def link_row(row)
  row_length = row.length
  row.each_with_index do |node, i|
    node.link({ right: row[(i+1) % row_length],
                left:  row[(i-1) % row_length]})
  end
end

#next_header ⇒ Object

Returns header with least total.



78
79
80
81
82
83
84
85
86
 
# File 'lib/dlx/sparse_matrix.rb', line 78

def next_header
  min_header = nil
  @root.each_in(:right) do |header|
    if !min_header || header.total < min_header.total
      min_header = header
    end
  end
  min_header
end

#rows ⇒ Object 



63
64
65
 
# File 'lib/dlx/sparse_matrix.rb', line 63

def rows
  @string_rows
end

#solve(&block) ⇒ Object 



67
68
69
70
71
72
73
74
75
 
# File 'lib/dlx/sparse_matrix.rb', line 67

def solve(&block)
  if block
    search(0, [], &block)
  else
    solutions = Array.new
    search(0, []) { |solution| solutions << solution }
    solutions
  end
end

#uncover(node) ⇒ Object

Reverses cover.



98
99
100
101
102
103
 
# File 'lib/dlx/sparse_matrix.rb', line 98

def uncover(node)
  node.header.each_in(:up) do |row|
    row.each_in(:left) { |n| n.restore(:column) }
  end
  node.header.restore(:row)
end