Script to convert 3CNF_Sat problems in to 3 colorability problems.

convert.rb

#!/usr/bin/ruby -w

# Please see http://engineering.linkedin.com/49/linkedin-coding-competitions-graph-coloring-haskell-c-and-java for background

$variableHash = Hash.new

class Clause
  def initialize (input, name)
    inputArray = input.split('|')
    @varANegated = inputArray[0][0,1] == "!"
    @varBNegated = inputArray[1][0,1] == "!"
    @varCNegated = inputArray[2][0,1] == "!"
    if @varANegated then
      @varAName = inputArray[0][1,inputArray[0].length]
    else
      @varAName = inputArray[0][0,inputArray[0].length]
    end
    if @varBNegated then
      @varBName = inputArray[1][1,inputArray[1].length]
    else
      @varBName = inputArray[1][0,inputArray[1].length]
    end
    if @varCNegated then
      @varCName = inputArray[2][1,inputArray[2].length]
    else
      @varCName = inputArray[2][0,inputArray[2].length]
    end
    if (! $variableHash.has_key?("VAR#{@varAName}")) then
      $variableHash["VAR#{@varAName}"] = Array.new << "NEGVAR#{@varAName}"
      $variableHash["NEGVAR#{@varAName}"] = Array.new << "VAR#{@varAName}"
    end
    if (! $variableHash.has_key?("VAR#{@varBName}")) then
      $variableHash["VAR#{@varBName}"] = Array.new << "NEGVAR#{@varBName}"
      $variableHash["NEGVAR#{@varBName}"] = Array.new << "VAR#{@varBName}"
    end
    if (! $variableHash.has_key?("VAR#{@varCName}")) then
      $variableHash["VAR#{@varCName}"] = Array.new << "NEGVAR#{@varCName}"
      $variableHash["NEGVAR#{@varCName}"] = Array.new << "VAR#{@varCName}"
    end
    @name = name
  end

  def first_var_name
    result = ""
    if (@varANegated) then
      result << "NEGVAR" << @varAName
    else
      result << "VAR" << @varAName
    end
    result
  end

  def second_var_name
    result = ""
    if (@varBNegated) then
      result << "NEGVAR" << @varBName
    else
      result << "VAR" << @varBName
    end
    result
  end

  def third_var_name
    result = ""
    if (@varCNegated) then
      result << "NEGVAR" << @varCName
    else
      result << "VAR" << @varCName
    end
    result
  end

  def name
    @name
  end
end

puts "About to read from file #{ARGV[0]}"
puts "About to read write file #{ARGV[1]}"

clauses = Array.new
counter = 0
input = IO.read(ARGV[0]).delete(" \r\n\(\)")
input.split('&').each { |info| 
  clauses[counter] = Clause.new(info, "CLS#{counter}")
  if ($variableHash.has_key?(clauses[counter].first_var_name())) then
    varArray = $variableHash[clauses[counter].first_var_name()]
    varArray << "#{clauses[counter].name}A"
  end
  if ($variableHash.has_key?(clauses[counter].second_var_name())) then
    varArray = $variableHash[clauses[counter].second_var_name()]
    varArray << "#{clauses[counter].name}D"
  end
  if ($variableHash.has_key?(clauses[counter].third_var_name())) then
    varArray = $variableHash[clauses[counter].third_var_name()]
    varArray << "#{clauses[counter].name}E"
  end
  counter = counter+1
}

outfile = File.open(ARGV[1], "w")
outfile.puts("FALSE:TRUE,META")
meta = "META:"
$variableHash.keys.each { |key| meta << key << "," }
meta << "TRUE,FALSE"
outfile.puts(meta)
tru = "TRUE:"
clauses.each { |clause| 
  tru << "#{clause.name}A,"
  tru << "#{clause.name}B,"
}
tru << "FALSE,META"
outfile.puts(tru)
$variableHash.keys.each { |key| 
  variable = key + ":"
  $variableHash[key].each { |conn|
    variable << conn << ","
  }
  variable << "META"
  outfile.puts(variable)
}
clauses.each { |clause|
  pta = clause.name + "A:" + clause.first_var_name() + "," + clause.name + "B,TRUE"
  outfile.puts(pta)
  ptb = clause.name + "B:" + clause.name + "A," + clause.name + "C,TRUE"
  outfile.puts(ptb)
  ptc = clause.name + "C:" + clause.name + "B," + clause.name + "D," + clause.name + "E"
  outfile.puts(ptc)
  ptd = clause.name + "D:" + clause.second_var_name() + "," + clause.name + "C," + clause.name + "E"
  outfile.puts(ptd)
  pte = clause.name + "E:" + clause.third_var_name() + "," + clause.name + "C," + clause.name + "D"
  outfile.puts(pte)
} 
  
outfile.close()