Class: CombinatorialPuzzleSolver::Possibilities

Inherits:
Array
  • Object
show all
Defined in:
lib/combinatorial_puzzle_solver/possibilities.rb

Overview

A collection of the possible values an identifier can have. It is reduced by invoking #cannot_be! and #must_be! until it only has one possible value, and thus becomes #resolved?.

Specifications

is an array

Instance Method Summary (collapse)

Constructor Details

- (Possibilities) initialize(solution_space, identifier)

Creates a set of possibilities for a specific identifier, which initially would be all possible symbols of the puzzle.

Parameters:

  • solution_space (SolutionSpace)

    the solution space that this set belongs to.

  • identifier (Identifier)

    the identifier associated with this set of possible values.



15
16
17
18
19
20
# File 'lib/combinatorial_puzzle_solver/possibilities.rb', line 15

def initialize(solution_space, identifier)
  @solution_space = solution_space
  @identifier = identifier

  super(identifier.puzzle.symbols) unless identifier.has_value?
end

Instance Method Details

- (Hash<Identifier,Object>) cannot_be!(value, resolvable = Hash.new)

Reduce the possible values by stating that the identifier cannot have a certain value.

Parameters:

  • value (Object)

    a value that the identifier cannot have.

  • resolvable (Hash<Identifier,Object>) (defaults to: Hash.new)

    an optional Hash to store all identifiers and values that becomes resolvable.

Returns:

  • (Hash<Identifier,Object>)

    the hash of identifiers that becomes resolvable because of this action.

Raises:

  • (Inconsistency)

    if the solution space becomes inconsistent without any possible solution.

Specifications:

should remove the given value

should raise Inconsistency if it becomes empty

should raise Inconsistency if the identifier is set to the given value

should return a Hash

should return the same Hash object as the given one (if it is given)

should return the resolved identifier if it only has one remaining value



71
72
73
74
75
76
77
78
79
# File 'lib/combinatorial_puzzle_solver/possibilities.rb', line 71

def cannot_be!(value, resolvable=Hash.new)
  raise Inconsistency if @identifier.value == value

  if delete(value) then
    raise Inconsistency if empty?
    resolvable[@identifier] = first if resolved?
  end
  resolvable
end

- (Hash<Identifier,Object>) dependent_identifiers_cannot_be!(value, resolvable = Hash.new)

Notifies dependent identifiers that they can't have a certain value.

Parameters:

  • value (Object)

    a value that the dependent identifiers cannot have.

  • resolvable (Hash<Identifier,Object>) (defaults to: Hash.new)

    an optional Hash to store all identifiers and values that becomes resolvable.

Returns:

  • (Hash<Identifier,Object>)

    the hash of identifiers that becomes resolvable because of this action.

Raises:

  • (Inconsistency)

    if the solution space becomes inconsistent without any possible solution.

Specifications:

should reduce possibilities of dependent identifiers



53
54
55
56
57
58
# File 'lib/combinatorial_puzzle_solver/possibilities.rb', line 53

def dependent_identifiers_cannot_be!(value, resolvable=Hash.new)
  @identifier.dependent_identifiers.each{|dependency|
    @solution_space[dependency].cannot_be!(value, resolvable)
  }
  resolvable
end

- (Hash<Identifier,Object>) must_be!(value, resolvable = Hash.new)

Reduce the possible values by stating that the identifier can only have a certain value.

Parameters:

  • value (Object)

    the only possible value the identifier can have.

  • resolvable (Hash<Identifier,Object>) (defaults to: Hash.new)

    an optional Hash to store all identifiers and values that becomes resolvable.

Returns:

  • (Hash<Identifier,Object>)

    a Hash of identifiers that becomes resolvable because of this action.

Raises:

  • (Inconsistency)

    if the solution space becomes inconsistent without any possible solution.

Specifications:

should remove all values except the given value

should return the dependent identifiers that becomes resolved.

Given the solution space:

{[0]=>[1], [1]=>[2], [2]=>[3], [3]=>[4, 5], [4]=>[4, 5]}

It resolves the follwing if [3] must be 4:

{[4]=>5}

should raise Inconsistency if identifier already has different value

should raise Inconsistency if the given value is not part of the set



33
34
35
36
37
38
39
40
41
# File 'lib/combinatorial_puzzle_solver/possibilities.rb', line 33

def must_be!(value, resolvable=Hash.new)
  raise Inconsistency if @identifier.has_value? && @identifier.value != value
  raise Inconsistency unless include?(value)

  clear
  push(value)

  dependent_identifiers_cannot_be!(value, resolvable)
end

- (true, false) resolved?

Returns true if the identifier can only have one possible value, false otherwise.

Returns:

  • (true, false)

    true if the identifier can only have one possible value, false otherwise.

Specifications:

should return true if it only has one possible value, false otherwise



83
84
85
# File 'lib/combinatorial_puzzle_solver/possibilities.rb', line 83

def resolved?
   size == 1
end