mols.cr

# a transversal is an array of Int32.
# 


# utilities

# print a square
def p(s, depth = 0)
  indent = " " * depth
  s.each do |line|
    puts indent + line.inspect
  end
  puts
  nil
end

#converts an orthogonal diagram to a square
def reconstitute(o)
 representation = (0..25).to_a
 
  size = o[0].size
  
  square = Array(Array(Int32)).new(size) { Array(Int32).new(size) { 0 } }
  
  o.each_with_index do |row, val|
    row.each_with_index do |y,x|
      square[x][y] = representation[val]
    end
  end
  square
end

def square(size, candidate_groups, buffer, depth, &block : Array(Array(Int32)) -> _)
  if (depth == size)
    block.call buffer
  else
    candidate_groups[depth].each do |candidate|
      if valid(buffer, candidate)
        buffer << candidate
        square(size, candidate_groups, buffer, depth+1, &block)
        buffer.pop
      end
    end
  end
end


def valid(buffer, candidate)
  candidate.each_with_index do |val, i|
    return false if (buffer.map do |c|
      c[i]
    end).includes?(val)
  end
  return true  
end



def create_candidate_groups(n)
  candidates = (0..n-1).to_a.permutations(n)
  candidate_groups = candidates.reduce(Array(Array(Array(Int32))).new(n) { [] of Array(Int32) }) do |groups, candidate|
    i = candidate[0]
    groups[i] << candidate
    groups
  end
  candidate_groups[0] = [candidate_groups[0][0]] #only need to evaluate first case due to symmetry
  
  # this randomizes the search space. useful when searching a small space
  (1..n-1).to_a.each do |i|
    candidate_groups[i] = candidate_groups[i].shuffle
  end
  
  candidate_groups
end


#create orthogonals
def create_value_groups(size)
  groups = Array(Array(Array(Int32))).new
  
  # builds an array of every possible transversal in square of size 'size'
  transversals = (0..size-1).to_a.permutations(size).to_a
  
  #need to determine the size of the group in order to accurately slice them up.
  group_size = (1..size-1).to_a.permutations(size-1).size
  
  # slices the list of every possible transversal so they are in groups organized
  # by the first value
  size.times do |i|
    beginning = group_size * i
    ending = (group_size * (i+1)) - 1
	
    groups << transversals[beginning..ending]
  
  end
  
  groups
end

#
def convert_to_transversal(s, v) : Array(Int32)
  candidate = v.map_with_index do |val, i|
    s[i].index(val).not_nil!
  end
end




def transversal_groups_for(square) : Array(Array(Array(Int32)))
  groups = create_value_groups(square[0].size)
  transversals = groups.map do |value_group|
    transversal = value_group.map { |values| convert_to_transversal(square, values) }
    valid_transversal = transversal.select { |row| row.size == row.uniq.size}
  end
end



def valid?(scratch, width)
  width.times do |i|
    column = scratch.map do |c|
      c[i]
    end
    return false if column.size != column.uniq.size
  end
  return true
end


def orthogonal_search(groups : Array(Array(Array(Int32))), scratch, max, &block : Array(Array(Int32)) -> _)
  
  depth = scratch.size
  if (depth == max)
    block.call scratch
  else
    groups[depth].each do |transversal|
      scratch << transversal
      if valid?(scratch, max)
        orthogonal_search(groups, scratch, max, &block)
      end
      scratch.pop
    end
  end
end

def orthogonals_for(square : Array(Array(Int32)), &block : Array(Array(Int32)) -> _)
  groups = transversal_groups_for(square)
  scratch = Array(Array(Int32)).new
  
  orthogonal_search(groups, scratch, square[0].size, &block)
end



# solve for latin squares
def deep_solve(n, &block : Array(Array(Int32)) -> _)
  candidate_groups = create_candidate_groups(n)
  square(n, candidate_groups, Array(Array(Int32)).new, 0, &block)
end


size = 10

deep_solve(size) { |square|
  puts "Square:"
  p square
  orthogonals_for(square) do |transversal|
    orthogonal = reconstitute(transversal)
    puts "Orthogonal:"
    p orthogonal
  end
}