NYTimes Digits Game (aka Countdown) Solver written in Crystal by Erik Berlin

digits_cli.cr

require "option_parser"

class CountdownGame
  OPERATORS = [:+, :-, :*, :/]

  def initialize(@numbers : Array(Int32), @target : Int32)
  end

  def solve
    result = solve_recursively(@numbers.map { |n| {n, n.to_s} }).find { |result, _| result == @target }
    result.try &.[1]
  end

  private def solve_recursively(numbers : Array({Int32, String}))
    return numbers if numbers.size == 1

    results = [] of {Int32, String}
    numbers.combinations(2).each do |comb|
      a, b = comb[0], comb[1]
      OPERATORS.each do |operator|
        next if operator == :/ && b[0] == 0 # Prevent division by zero
        next if operator == :/ && a[0] % b[0] != 0 # Only allow integer division

        remaining_numbers = numbers - [a, b]
        new_number = case operator
                     when :+ then a[0] + b[0]
                     when :- then a[0] - b[0]
                     when :* then a[0] * b[0]
                     when :/ then a[0] / b[0]
                     else 0
                     end.to_i
        new_steps = "(#{a[1]} #{operator} #{b[1]})"

        # Only add valid new numbers to avoid duplicates
        if new_number > 0 && new_number.to_i == new_number
          # Pruning condition
          if new_number <= @target
            results << {new_number, new_steps}
            results.concat(solve_recursively(remaining_numbers + [{new_number, new_steps}]))
          end
        end
      end
    end

    results
  end
end

options = OptionParser.parse do |parser|
  parser.banner = "Usage: countdown_game.cr [options] target_number integers..."
  parser.on "-h", "--help", "Show help message" do
    puts parser
    exit
  end
end

if ARGV.size < 2
  puts "Please provide at least two arguments: a target number and an array of integers."
  puts options
  exit
end

target = ARGV[0].to_i
numbers = ARGV[1..-1].map(&.to_i)

game = CountdownGame.new(numbers, target)
puts game.solve