Sorting The Exponentials

This is the same approach as Chew. I am comparing the logarithms of the numbers because the actual numbers are expensive to compute.

I wish this was a code golf and I could win for writing the shortest code.

Python Code:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

from math import log
from urllib2 import urlopen

data = urllib2.urlopen('http://pastebin.com/raw.php?i=wPK0513n').read().split(',')
data = [(int(i.split('^')[0]),int(i.split('^')[1])) for i in data]

keyf = lambda (m,n): n*log(m)
sorted_data = sorted(st,key=keyf)

print sum([sorted_data[i][1] for i in xrange(len(sorted_data)) if not i%2])

Outputs the answer

Here's my code:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

>>> import math
>>> n = []
>>> for x in [that big array converted to string]:
        z = x.split('^', 1)
        n.append([int(z[1])* math.log10(int(z[0])), int(z[1])])
>>> n = sorted(n, key=lambda tup: tup[0])
>>> summ = 0
>>> for x in range(0, len(n), 2):
        summ += n[x][1]
>>> print summ

I converted the array to string. If you want to test my code, then here's the array.

I basically did the same thing as others: compare logs.

We can exploit the fact that $\log { { a }^{ b } } =b\log { a }$ . This works because if $\log { x } >\log { y }$ then $x > y$ .

This makes the computation much faster.

I am thinking to stop using python because it's inbuilt libraries are making me lazy :p.

The solution I had in mind is similar to what everyone came up with: to compare two powers $a^b$ and $c^d$ , compare $blog(a)$ and $clog(d)$ instead. However, I want to demonstrate a neat little OOP way of doing the sorting.

We can represent any power as a class ( Power ) , which only stores the base and exponent. We can then implement a __cmp__ method to allow us to compare two Power objects with >,<,= . The beauty of this is we can then employ python's in-built .sort() method to do the sorting.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

from math import log10
class Power:    
    def __init__(self,a,b):
        self.a , self.b = a , b
        self.weight = b*log10(a)        
    def __cmp__(self,other):
        return cmp(self.weight,other.weight)
    def __repr__(self):
        return str(self.a)+'^'+str(self.b)

powers = [Power(3,100),Power(2,140),Power(3,90)]
powers.sort()
print powers

This prints out

1
2

>>> 
[2^140, 3^90, 3^100]

Note: . For some weird reason, python decided to make using comparators slightly slower than using sorted .

Feel the power of the awk:

Put raw paste data into file called o1. Then:

awk -F "," '{for(i=1;i<=NF;++i){print $i}}' o1|awk -F "^" '{print $1,$2}'|awk '{print $2,$2*log($1)}'|sort -g -k 2,2|awk 'NR%2==1'|awk '{s+=$1}END{print s}'

27385518

Solution in C++ Same algorithm as the other 2 answers using logarithm to find the number of digits.

EDIT : I first used notepad and replaced all '^' by space and also ',' by space.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45

#include <fstream.h>
#include <conio.h>
#include <math.h>
#include <iomanip.h>
int main()
{
    clrscr();
    ifstream file("NUMB.TXT",ios::in);
    long double numbers[100][2], value[100],temp,total=0;
    int i=0,j=0;
    if(!file)
    {
        cout << "Error";
        return 1;
    }
    while(file>>numbers[i][0])
    {
        file>>numbers[i][1];
        value[i]=ceil(numbers[i][1]*log10(numbers[i][0]));
        ++i;
    }
   file.close();
   for(i=0;i<100;++i)
    {
        for(j=i+1;j<100;++j)
        {
            if(value[i]>value[j])
            {
                temp=value[i];
                value[i]=value[j];
                value[j]=temp;
                temp=numbers[i][1];
                numbers[i][1]=numbers[j][1];
                numbers[j][1]=temp;
            }
        }
    }
    for(i=0;i<100;i+=2)
    {
        total+=numbers[i][1];
    }
    cout << setprecision(7)<<total;
    getch();
    return 0;
}

Yes, poor sorting method, I know, I was lazy.

Power of Mathematica. We start by converting the string into a newline-separated list of numbers by replacing "," and "^" by newline. Then we pair them together two by two. We sort the list of pairs by first taking the logarithm and then comparing the results. Finally we sum the exponents which are the second part of each pair.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

text = "381600^809197,105964^708702, ..."

lst = 
  Partition[
   ImportString[ StringReplace[ text, {"," -> "\n", "^" -> "\n"} ], 
    "list"]
   , 2];

cmp[a_, b_] := a[[2]] * Log[a[[1]]] < b[[2]] * Log[b[[1]]]

slst = Sort[lst, cmp];

Sum[ slst[[i]][[2]], {i, 1, Length[slst], 2}]

I solve this using an Excel spreadsheet.

1. Extract the data
2. Separate the numbers ( $n$ ) and the exponents ( $k$ )
3. Calculate $k\log{n}$
4. Sort according to $k\log{n}$
5. Sum up the exponents of elements with even indices