My C++ Program (21k), Executable File (224k) and readme.txt

• Key feature: Allow user to change the set of valid binary and unary operation very easily.
• Input:
  • DIGIT: The digit allowed.
  • NUM_DIGIT: Number of the digit allowed.
  • VEC_UNARY: A vector of Unary function
  • VEC_BINARY: A vector of Binary function
• Output:
  • Result for DIGIT = 4, NUM_DIGIT = 4, VEC_UNARY = {sqrt fact (!) percent (%) neg (-)}, VEC_BINARY = {+ - * / ^}
  • Command: puzzle 4 4 500
• Algorithm: (Dynamic Programming with a little twist)
  • Let S(i) = set of all "reasonable" result that can be created with "i" number of DIGIT
  • Let B(i) = set of all numbers that can be created with "i" number of of DIGIT without using any operation. (i.e. for i = 1, DIGIT = 4, 0.4, 0.4' = 0.444444...)
  • S(i) = B(i) Union {Binary operation on S(j) and S(k) where j+k=i} Union {Unary operation on S(i)}
• Data Structure
  • S(i), the set of all valid number, is store in a balanced binary search tree.
  • Each number is hashed to a pointer to a node (that represent its equation). In other words, every nodes is indexed by a hash table. Each node has the following properties,
    • Member:
      • priority: store the priority of each entry, this is used to determine bracket and break tie
      • entry: store the content, such as "*", "fact", "44", etc.
      • ptrLEFT: pointer to left node
      • ptrRIGHT: pointer to right node
    • NOTE: this is not a binary tree, but an acyclic graph, because a single node often has multiple parent
    • This data structure to express equation is prefered over binary tree
      • Use a lot less memory
      • Much easier to update when a simpler representation is found. For instance
        • Assuming we have, 20 = 4 / sqrt(4%), and 80 = 4 * 20 = 4 * (4 / sqrt(4%))
        • In my program, when 20 is updated to 20 = 4! - 4, everything else that use 20 is updated automatically, thus 80 = 4 * (4! - 4). Because 80 is a node where "entry = *" "ptrLEFT = pointer to node 4" "ptrRIGHT = pointer to node 20"
• Extra results:
  • 999.txt:
    • Using three 9's and all built in operations. (+, -, *, /, ^, fact (!), sqrt, percent (%), neg, repeat)
    • Result of "puzzle 9 3 100".
  • 4444basic.txt:
    • Using four 4's.
    • Restrict the operations to + - * /.
    • Result of "puzzle 4 4 100 + - * /".
  • 3333.txt
    • Using four 3's and all built in operations.
    • Result of "puzzle 3 4 100".