FRIHOST FORUMS SEARCH FAQ TOS BLOGS COMPETITIONS
You are invited to Log in or Register a free Frihost Account!


Programming Challenge





restonpiston
Hi, I was looking at youtube videos haphazardly and stumble upon this one:


Here they explain a cool way to decompose numbers but they don't know the method to do that.
The decomposition rules are as follows:

    You can only use one type of number from 1 to 9

    You can only use operations of sum, subtraction, multiplication, division, exponentiation and concatenation

    You must look for the shortest expression

Using this rules you can decompose 814 in:
22*(2+2+2)^2+22

I thought about it for a bit and realize that it would be an interesting challenge for many people.

So here is my idea, post your solution of the problem if you have one and we will discuss it against the others.
I dont have the solution myself, so it would be challenge for me. Also, use your favourite language,
but if you don't mind, make it in python so we all have a common syntaxis.

Have fun!
jestoy0514
Hi restonpiston, have you solve the problem yourself. If so can you please share it with us. It is quite interesting.
restonpiston
Unfortunately, my junior year of CS is keeping me pretty busy, but I will give it a try whenever I have enough time
restonpiston
I have a proof of concept of it. It doesn't work yet, but you can see the basics behind it.
Code:
import re;
import math;
import itertools as it
def count(operandos):
    d=["+","-","*","/","^","."];
    solucion=operandos[-1]
    operandos=operandos[:-1]#https://stackoverflow.com/questions/509211/explain-slice-notation
    for op in it.permutations(operandos):
        #print(op)
        for o in comb_general(d,len(operandos)-2):
            a=""
            if op[0]==1 and op[1]==3 and op[2]==5 and op[3]==7:
                pass;
            if o[0]=="+" and o[1]=="^" and o[2]=="+" and o[3]==".":
                pass;
            if op[0]==1 and op[1]==3 and op[2]==5 and op[3]==7 and op[4]==8 and o[0]=="+" and o[1]=="^" and o[2]=="+" and o[3]==".":
                print("Help")
#             for i in range(len(o)):
#                 a=a+str(op[i])+str(o[i])
#             a=a+str(op[len(op)-1])
            conto=0;
            contop=0;
            salida=True;
            while (conto<len(o) and contop<len(op)):
                if o[conto]=="(":
                    a=a+"("
                    a=a+str(op[contop])
                    conto=conto+1
                    a=a+str(o[conto])
                elif o[conto]==")":
                    a=a+str(op[contop])
                    a=a+")"
                    conto=conto+1
                    try:
                        a=a+str(o[conto])
                    except:
                        salida=False;
                        break;
                   
                else:
                    a=a+str(op[contop])
                    a=a+str(o[conto])
                conto=conto+1
                contop=contop+1;
            if salida:
                a=a+str(op[len(op)-1])
            try:
                var=recurs(a)
            except:
                var=float("inf")
            if var==solucion:
                var=recurs(a)
                a=""
                for i in range(len(o)):
                    a=a+str(op[i])+" "+str(o[i])+" "
                a=a+str(op[len(op)-1])+" = "+str(solucion)
                return a;
def comb(it,num):
    if num==0:
        for e in it:
            yield [e]
    else:
        for e in it:
            for c in comb(it,num-1):
                yield [e]+c
def comb_par(it):
    for i in range(len(it)):
        l=it[:]
        l.insert(i,"(")
        for j in range(i+2,len(it)+2):
            aux=l[:]
            aux.insert(j,")")
            yield aux
def comb_general(it,num):
    for o in comb(it,num):
        for e in comb_par(o):
            yield e;



def recurs(cadena):
    aux=0;
    if is_number(cadena):
        return int(cadena)
    for i in range(len(cadena)):

        if i>=len(cadena):
            return aux;
#         a=cadena[i]
#         if a=="(":
#             for j in range(i+1,len(cadena)):
#                 if cadena[j]==")":
#                     aux=recurs(cadena[i+1:j])
#                     s1=""
#                     s2=""
#                     if i-1>0:
#                         s1=cadena[:i-1]
#                     if j+1<len(cadena):
#                         s2=cadena[j+1:]
#                     s=s1+str(aux)+s2
#                     cadena=s
#                     break;
        try:
            aux=0;
            i=cadena.index("(");
            for j in range(i+1,len(cadena)):
                if cadena[j]==")":
                    aux=recurs(cadena[i+1:j])
                    s1=""
                    s2=""
                    if i-1>0:
                        s1=cadena[:i]
                    if j+1<len(cadena):
                        s2=cadena[j+1:]
                    s=s1+str(aux)+s2
                    cadena=s
                    break;
            #return aux;
        except ValueError:
            pass;
        try:
            i=cadena.index("+")
            return recurs(cadena[:i])+recurs(cadena[i+1:])
        except ValueError:
            pass;
        try:
            i=cadena.index("-")
            return recurs(cadena[:i])-recurs(cadena[i+1:])
        except ValueError:
            pass;
        try:
            i=cadena.index("*")
            return recurs(cadena[:i])*recurs(cadena[i+1:])
        except ValueError:
            pass;
        try:
            i=cadena.index("/")
            return recurs(cadena[:i])//recurs(cadena[i+1:])
        except ValueError:
            pass;
        try:
            i=cadena.index("^")
            return recurs(cadena[:i])**recurs(cadena[i+1:])
        except ValueError:
            pass;
        try:
            i=cadena.index(".")
            n=math.ceil(math.log10(int(cadena[i+1:])))
            num1=int(cadena[:i])*(10**n)
            return num1+int(cadena[i+1:])
        except ValueError:
            pass;

#         if a=="+":
#             return recurs(cadena[:i])+recurs(cadena[i+1:])
#         elif a=="-":
#             return recurs(cadena[:i])-recurs(cadena[i+1:])
#         elif a=="*":
#             return recurs(cadena[:i])*recurs(cadena[i+1:])
#         elif a=="/":
#             return recurs(cadena[:i])//recurs(cadena[i+1:])
#         elif a=="^":
#             return recurs(cadena[:i])**recurs(cadena[i+1:])
#         elif a==".":
#             n=math.ceil(math.log10(int(cadena[i+1:])))
#             num1=int(cadena[:i])*(10**n)
#             return num1+int(cadena[i+1:])
def quita_par(cadena):
    for i in range(len(cadena)):
        if cadena[i]=="(":
            for j in range(i,len(cadena)):
                if cadena[j]==")":
                    aux=recurs(cadena[i+1:j])
                    cadena=cadena[:i-1]+str(aux)+cadena[j+1:]
def is_number(s):
    try:
        int(s)
        return True
    except ValueError:
        return False
def recurs_re(cadena):#Analizador recursivo descendente
    aux=re.search('([^+\-*\/]*?)(\+|\-)(.*)',cadena)
    #print(cadena)
    if (aux):
        if (aux.group(2)=="+"):
            return recurs(aux.group(1))+recurs(aux.group(3))
        elif (aux.group(2)=="-"):
            return recurs(aux.group(1))-recurs(aux.group(3))
    aux=re.search('([^+\-*\/]*?)(\*|\/)(.*)',cadena)
    if (aux):
        if (aux.group(2)=="*"):
            return recurs(aux.group(1))*recurs(aux.group(3))
        elif (aux.group(2)=="/"):
            return recurs(aux.group(1))/recurs(aux.group(3))
    aux=re.search('([^+\-*\/]*?)(\^)(.*)',cadena)
    if (aux):
        return recurs(aux.group(1))**recurs(aux.group(3))
    aux=re.search('([^+\-*\/]*?)(\.)(.*)',cadena)
    if (aux):
        n=math.ceil(math.log10(int(aux.group(3))))
        num1=int(aux.group(1))*(10**n)
        return num1+int(aux.group(3))
    return int(cadena)
Related topics
[Visual Basic] Divide X equation
13-digit Palindromic Primes
How To : Improve Your PHP Programming
Java Programming Introductory
Laws of Computer Programming
Programming Help & Support Guidelines
Programming
Programming links, info, and tutorials
xcode programming
falling in love
A wonderful place to learn CGI-programming
programming
basic tutorials on most forms of web programming
Games programming...
Reply to topic    Frihost Forum Index -> Scripting -> Others

FRIHOST HOME | FAQ | TOS | ABOUT US | CONTACT US | SITE MAP
© 2005-2011 Frihost, forums powered by phpBB.