UPSB v4

Off-topic / A Programming Challenge (lvl 2)

  1. Mats
    Date: Fri, Jan 13 2012 09:07:40

    The program should do the following: -Accept any numbers from 0 - 10 000 from the user. -The user can input a maximum of 7 numbers. -See if any combination of those numbers can be used to make 1000 exactly, by using each number exactly once and the four mathematical operators (+ - * /). Squaring and other operators are not allowed to be used, but brackets are allowed (up to a maximum of 3 pairs). Again, you can post any questions up in the thread and please put code in spoiler tags. Good luck!

  2. webspider
    Date: Fri, Jan 13 2012 09:25:37

    If it weren't for the brackets, I'd write a simple evaluating bruteforcer. So before I start, what is the maximum number of brackets (either brackets in total, amount of layers, ...) one can use?

  3. Mats
    Date: Fri, Jan 13 2012 09:27:25

    webspider wrote: If it weren't for the brackets, I'd write a simple evaluating bruteforcer. So before I start, what is the maximum number of brackets (either brackets in total, amount of layers, ...) one can use?
    Let's say you can use up to a total of 3 pairs of brackets maximum.

  4. Retro-spectre
    Date: Fri, Jan 13 2012 21:15:35

    webspider wrote: If it weren't for the brackets, I'd write a simple evaluating bruteforcer. So before I start, what is the maximum number of brackets (either brackets in total, amount of layers, ...) one can use?
    lol, what a boring solution. gb2freenode

  5. webspider
    Date: Fri, Jan 13 2012 21:43:26

    Retro-spectre wrote: lol, what a boring solution.
    This comes from the right guy, especially after a look at your previous solution. If you need fascinating ones, go and play some perl golf.

  6. Advecticity
    Date: Fri, Jan 13 2012 23:06:38

    This program is based on my conjecture that you never need more than three pairs of brackets. To require the use of a first bracket, you need three numbers of the seven, a +/- operator and a *|/ operator such as (a + b)*c. The to justify the use of a second bracket, you need another two numbers, such as ((a + b)*c + d)*e. By the time you get to the third bracket you've run out of numbers. Then if use division which requires order, then you can always convert stuff like a/(b/c) to a/b*c. Therefore any solution that uses more than three brackets only contains three relevant brackets. I'm too lazy to write something that gets rid of the irrelevant ones, but here's my answer :

    Spoiler[CODE]using System; using System.Collections.Generic; using System.Linq; using System.Text; namespace MatsChallenge2 { class Program { enum Operator { Add, Sub, Mult, Div } class Number { public double value; public virtual string Print() { return Convert.ToString(value); } public Number(double v) { value = v; } } class NumberPair : Number { public Number value1; public Number value2; public Operator op; public override string Print() { string s = "(" + value1.Print(); if (op == Operator.Add) s += " + "; else if (op == Operator.Sub) s += " - "; else if (op == Operator.Mult) s += " * "; else s += " / "; s += value2.Print() + ")"; return s; } public NumberPair(Number v1, Number v2, Operator o, double v) : base(v) { value1 = v1; value2 = v2; op = o; } } static void Main(string[] args) { List numbers = new List(); Console.WriteLine("Please enter up to 7 numbers from 0 to 10000."); Console.WriteLine("Any invalid input will assume you do not wish to enter anymore numbers"); // Input the 7 numbers. while (numbers.Count < 7) { Console.WriteLine("You can still enter up to {0} number(s).", 7 - numbers.Count); string input = Console.ReadLine(); try { double number = double.Parse(input); if (number >= 0 && number < 10000) numbers.Add(new Number(number)); else break; } catch { break; } } if (numbers.Count > 0) Console.WriteLine("You entered {0} numbers.", numbers.Count); else { Console.WriteLine("No numbers entered, can't do anything."); Console.ReadLine(); return; } Permute(numbers); Console.WriteLine("Tried every possible permutation of numbers, operators and brackets."); Console.ReadLine(); } static void Permute(List numbers) { if (numbers.Count == 1) { if (numbers[0].value == 1000) Console.WriteLine("Solution : " + numbers[0].Print()); return; } // Get every combination of two numbers. for (int i = 0; i < numbers.Count; i++) { for (int j = 0; j < numbers.Count; j++) { // Can't use the same number. if (i != j) { List newList; // Try every operator. newList = new List(numbers); newList.Remove(numbers[i]); newList.Remove(numbers[j]); newList.Add(new NumberPair(numbers[i], numbers[j], Operator.Add, numbers[i].value + numbers[j].value)); Permute(newList); newList = new List(numbers); newList.Remove(numbers[i]); newList.Remove(numbers[j]); newList.Add(new NumberPair(numbers[i], numbers[j], Operator.Sub, numbers[i].value - numbers[j].value)); Permute(newList); newList = new List(numbers); newList.Remove(numbers[i]); newList.Remove(numbers[j]); newList.Add(new NumberPair(numbers[i], numbers[j], Operator.Mult, numbers[i].value * numbers[j].value)); Permute(newList); if (numbers[j].value != 0) // Avoid division by 0 { newList = new List(numbers); newList.Remove(numbers[i]); newList.Remove(numbers[j]); newList.Add(new NumberPair(numbers[i], numbers[j], Operator.Div, numbers[i].value / numbers[j].value)); Permute(newList); } } } } } } } [/CODE]
    It uses recursion a lot. If anyone wants an .exe I can upload one.

  7. Mats
    Date: Sat, Jan 14 2012 01:17:19

    I would quite like an .exe since I cannot compile c# to check it and lack the knowledge of c# to know if you are correct or not. I think this challenge doesn't have a standard library thing to help much, in any language.

  8. Advecticity
    Date: Sat, Jan 14 2012 01:30:08

    http://www.mediafire.com/?wcucoaz4x07td4a It will print every possible solution, although most will be equivalent. Oh, and will probably require the .net framework if you don't have it already.

  9. Mats
    Date: Sat, Jan 14 2012 01:35:45

    Advecticity wrote: http://www.mediafire.com/?wcucoaz4x07td4a
    It doesn't output anything for me after 'tried every possible permutation of numbers, operators and brackets.' sometimes and other times it just stops at 'you entered n numbers' and won't do anything. :S

  10. Advecticity
    Date: Sat, Jan 14 2012 01:59:09

    In the former case, it means there is no solution (at least, that's what it's supposed to mean). In the latter case, it means it's still running. The program runs in a very remarkable O(n!*4^n) time, but it prints out solutions as it goes. If nothing gets displayed within a minute there most likely isn't one. Try entering 2, 250, 10, 50 then -1.

  11. Mats
    Date: Sat, Jan 14 2012 02:16:36

    May I suggest two changes? -For the solution to say = at the end (so it can be checked or at least known what number that solution is for. -For the program to stop once it has found a solution* (or at least an option for this). It would make the program much nicer! btw, how did you measure how fast your program runs in? I can rarely manage this. Edit: I believe your program is making errors. For instance, take a look at line 5 printed out when you put in 2,250,10,50, -1 (250 - 50) / (2 / 10) != 1000

  12. Advecticity
    Date: Sat, Jan 14 2012 03:45:19

    (250 - 50) / (2 / 10) = 200 / (1 / 5) = 200 * 5 = 1000 ;) Actually I was wrong for my previous O(). Right now it actually runs in a even worse O(n!*n!*4^n). I think it took 1h30 for my computer to finish running it. What my program does is that it starts by taking every two numbers, say a and b, of of the n initial numbers. It decides to replace those two numbers by either (a + b), (a - b), (a * b) or (a / b). Now you're left with (n - 1) numbers. Then it repeats the process, taking two numbers out of the n - 1 remaining numbers and so on until there is only one number left, and checks if it is equal to 1000. The program basically tries every possible permutation of number pairs with every possible operator. So if I have 7 initial numbers, the number of solutions it attempts is equal to (7*6*4)*(6*5*4)*(5*4*4)*(4*3*4)*(3*2*4)*(2*1*4) = (7*6*5*4*3*2*1)*(6*4*3*2)*(4*4*4*4*4*4) = O(n!*n!*4^n) for large n.