DigitsSolver

This is basically a coding exercise.

The goal of this gem is to solve puzzles à-la NY Times Digits game. You may actually know this game under a different name. In France this looks like the calculation part of an almost 50 year old TV show named 'Les chiffres et les lettres'...

The goal is to use numbers from the draw combined by any basic operation (+ - / *) to reach that goal. You cannot have negative numbers as result of "-" operation, and can only divide number resulting into an integer.

This gem implements a brute-force approach to solve the problem but is ready to host alternate strategies.
Basically this strategy won't work beyond 7 numbers in the draw (it is limited in the command line to 6 numbers but not within the code), as for a 7 numbers draw it already takes few minutes on my machine. Although this strategy does not stop at the first encountered solution but browses the whole tree of possibilities (that could be easily done).

To go beyond, you would probably have to go for a more mathematical approach...

Installation

  1. You need to have the Ruby language working on your machine.

  2. Install this Ruby gem:

    $ gem install digits_solver

Usage

Command line

Once this gem installed, it provides an executable named find_nydigits_solutions(you may potentially have to log-out/in if it is not available in your shell).

  • First script argument is the target number.
  • All subsequent arguments are the numbers to be used in calculations to reach the target. You can specify from 2 to 6 numbers in the "draw".

ex:

$ find_nydigits_solutions 437 3 5 7 13 20 25
Trying to find 437
A best solution has been found (total of 67 found).
Solved in 4 operations:
 => 5 * 7 = 35
 => 35 - 13 = 22
 => 22 * 20 = 440
 => 440 - 3 = 437

This program will only display the "best" solution found (ie the one implying the least number of operations), but code does not (you see here above that 67 solutions were found).

Code usage

You have basically access to the same functions but with more flexibility.

# The interface looks a lot like the command line, here as opposed to the command line
# you are not limited to 6 numbers in the draw, but be aware that 7 takes already few minutes
# and I never tried beyond...
r = DigitsSolver.solve_for 437, 3, 5, 7, 13, 20, 25

# The object returned is a DigitsSolver::SolutionSet
# You can query it
r.size
# => 67

# You can query the "best" solution found. It returns a DigitsSolver::Solution object.
r.best_solution
# => #<DigitsSolver::Solution:0x000055b96f5f97a8
#  Solution: '(5 * 7 - 13) * 20 - 3 = 437',
#  @problem_statement=#<DigitsSolver::ProblemStatement:0x000055b96fe71020 @draw=[3, 5, 7, 13, 20, 25], @max_operations_number=5, @target_number=437>,
#  @operands=[5, 7, 13, 20, 3],
#  @operations_to_apply=[:multiply, :minus, :multiply, :minus]>

# Or you can query the "best" solutions, then it would return an array of DigitsSolver::Solution
# 
r.best_solutions 3
# => [#<DigitsSolver::Solution:0x000055b96f5f97a8
#   Solution: '(5 * 7 - 13) * 20 - 3 = 437',
#   @problem_statement=#<DigitsSolver::ProblemStatement:0x000055b96fe71020 @draw=[3, 5, 7, 13, 20, 25], @max_operations_number=5, @target_number=437>,
#   @operands=[5, 7, 13, 20, 3],
#   @operations_to_apply=[:multiply, :minus, :multiply, :minus]>,
#  #<DigitsSolver::Solution:0x000055b96f663ef0
#   Solution: '(7 * 5 - 13) * 20 - 3 = 437',
#   @problem_statement=#<DigitsSolver::ProblemStatement:0x000055b96fe71020 @draw=[3, 5, 7, 13, 20, 25], @max_operations_number=5, @target_number=437>,
#   @operands=[7, 5, 13, 20, 3],
#   @operations_to_apply=[:multiply, :minus, :multiply, :minus]>,
#  #<DigitsSolver::Solution:0x000055b96f6b2528
#   Solution: '((20 - 3) * 25 + 5) + 7 = 437',
#   @problem_statement=#<DigitsSolver::ProblemStatement:0x000055b96fe71020 @draw=[3, 5, 7, 13, 20, 25], @max_operations_number=5, @target_number=437>,
#   @operands=[20, 3, 25, 5, 7],
#   @operations_to_apply=[:minus, :multiply, :plus, :plus]>]

# DigitsSolver::Solution objects can be printed
puts r.best_solution
# Solved in 4 operations:
#  => 5 * 7 = 35
#  => 35 - 13 = 22
#  => 22 * 20 = 440
#  => 440 - 3 = 437
# => nil

# or debugged
pp r.best_solution
# #<DigitsSolver::Solution:0x000055b96f5f97a8
#  Solution: '(5 * 7 - 13) * 20 - 3 = 437',
#  @problem_statement=#<DigitsSolver::ProblemStatement:0x000055b96fe71020
#   @draw=[3, 5, 7, 13, 20, 25],
#   @max_operations_number=5,
#   @target_number=437>,
#  @operands=[5, 7, 13, 20, 3],
#  @operations_to_apply=[:multiply, :minus, :multiply, :minus]>

# And of course it has other methods, you could use. Ex:
r.sorted_solutions.map(&:to_evaluable_code).take 10
# => ["(5 * 7 - 13) * 20 - 3",
#  "(7 * 5 - 13) * 20 - 3",
#  "((20 - 3) * 25 + 5) + 7",
#  "((20 - 3) * 25 + 7) + 5",
#  "((20 - 5) + 3) * 25 - 13",
#  "((20 - 7) + 5) * 25 - 13",
#  "((3 * 5 + 20) * 13 + 7) - 25",
#  "((3 * 5 + 20) * 13 - 25) + 7",
#  "((3 * 7 * 20 + 5) - 13) + 25",
#  "((3 * 7 * 20 + 5) + 25) - 13"]