module TenPuzzle
  class Solver
    ALL_NUMBER_COMBINATIONS = [*1..9].combination(4).to_a
    OPERATORS = %i(+ - * /)

    def solve
      count = 0
      ALL_NUMBER_COMBINATIONS.each do |numbers|
        nodes = numbers.map { |n| Node.new(n, n.to_s) }
        formulas = two_two_pattern_formulas(nodes) + two_one_one_pattern_formulas(nodes)

        count += 1 if formulas.any?

        puts "#{numbers.join(',')} : #{formulas.any? ? 'OK' : 'NO'} : example #{formulas.sample}"
      end

      puts "(10になる組み合わせの数) / (全4桁の組み合わせ数) =  #{count} / #{ALL_NUMBER_COMBINATIONS.size}"
    end

    def calculate_result_nodes(node1, node2)
      OPERATORS.flat_map { |operator|
        if %i(- /).include?(operator)
          # 順番で結果が異なる演算子の場合
          [
            node1.calculate(node2, operator),
            node2.calculate(node1, operator)
          ]
        else
          [node1.calculate(node2, operator)]
        end
      }
    end

    def two_two_pattern_formulas(nodes)
      formulas = []
      nodes.combination(2).each do |first_pair|
        nodes_for_first_pair = calculate_result_nodes(*first_pair)

        other_pair = nodes - first_pair
        nodes_for_other_pair = calculate_result_nodes(*other_pair)

        nodes_for_first_pair.product(nodes_for_other_pair).each do |last_pair|
          whole_nodes = calculate_result_nodes(*last_pair)
          formulas += whole_nodes.select(&:ten?).map(&:formula)
        end
      end
      formulas
    end

    def two_one_one_pattern_formulas(nodes)
      formulas = []
      nodes.combination(2).each do |first_pair|
        nodes_for_first_pair = calculate_result_nodes(*first_pair)
        second_node, last_node = nodes - first_pair
        formulas += formulas_merged_one_and_one_nodes(nodes_for_first_pair, second_node, last_node)
        formulas += formulas_merged_one_and_one_nodes(nodes_for_first_pair, last_node, second_node)
      end
      formulas
    end

    def formulas_merged_one_and_one_nodes(nodes_for_first_pair, second_node, last_node)
      second_pair_results = nodes_for_first_pair
        .flat_map { |first_pair_result| calculate_result_nodes(first_pair_result, second_node) }

      second_pair_results.flat_map do |second_pair_result|
        whole_nodes = calculate_result_nodes(second_pair_result, last_node)
        whole_nodes.compact.select(&:ten?).map(&:formula)
      end
    end
  end

  class Node
    attr_reader :val, :formula

    def initialize(arg_val, arg_formula)
      @val = arg_val
      @formula = arg_formula
    end

    def ten?
      @val == 10
    end

    def calculate(node, operator)
      case operator
      when :+
        sum(node)
      when :-
        diff(node)
      when :*
        product(node)
      when :/
        quotient(node)
      end
    end

    def sum(node)
      new_val = @val + node.val
      new_formula = "(#{@formula} + #{node.formula})"
      Node.new(new_val, new_formula)
    end

    def diff(node)
      new_val = @val - node.val
      new_formula = "(#{@formula} - #{node.formula})"
      Node.new(new_val, new_formula)
    end

    def product(node)
      new_val = @val * node.val
      new_formula = "(#{@formula} * #{node.formula})"
      Node.new(new_val, new_formula)
    end

    def quotient(node)
      return nil if node.val.zero?
      new_val = Rational(@val, node.val)
      new_formula = "(#{@formula} / #{node.formula})"
      Node.new(new_val, new_formula)
    end
  end
end

TenPuzzle::Solver.new.solve