LebGeeks

A community for technology geeks in Lebanon.

You are not logged in.

#1 June 14 2012

Joe
Member

[Exercise] Russian lucky bus ticket

In Russia, bus tickets have 6 digits. A ticket is believed to be "lucky" if the sum of its first 3 digits equals the sum of its last 3 digits. For example:

• 132501 lucky
• 436922 lucky
• 873012 not lucky

The goal of the exercise is to calculate the number of lucky tickets.

(I did not come up with this problem, it is somewhat famous in mathematical circles. This blog post traces back the introduction of this problem to professor A. A. Kirillov, from University of Pennsylvania).

Offline

#2 June 14 2012

xterm
Moderator

Re: [Exercise] Russian lucky bus ticket

Cool exercise! I can think of many ways to deal with it that i'll write up tonight.

Meanwhile, here's a brute forced ugly one liner.

len([i for i in range(1,999999) 
       if sum(map(int,('%(#)06d' % {'#':i})[:3])) ==  
          sum(map(int,('%(#)06d' % {'#':i})[3:]))
])

Last edited by xterm (June 14 2012)

Offline

#3 June 14 2012

Joe
Member

Re: [Exercise] Russian lucky bus ticket

Here's my first version. It's a little less brute-force-y than xterm's.

totsize = 6

def firsthalf(size=totsize/2, s=[]):
''' This function generates all the permutations of 0-9 digits repeated totsize/2 times'''
    if size == 0:
        return s

    if len(s) == 0:
        t = [ [x] for x in xrange(10)]
    else:
        t = [ i + [j] for i in s
              for j in xrange(10)]
    
    
    return firsthalf(size-1, t)


def luckynbs(size=totsize/2, s=firsthalf()):
''' This function will append 0-9 digits to the above generated list.
Each iteration will append one digit to the existing, filtering out all the wrong
cases as it detects them.
 - If the new digit makes the right sum greater than the left sum, it is directly dismissed
 - If the new digit makes the right sum so little than even filling the rest with 9s is too low than it is dismissed.
'''

    if size == 0:
        return s

    t = [ i + [j] for i in s for j in xrange(10)
          if sum(i[:totsize/2]) >= sum(i[totsize/2:])+j
          if sum(i[:totsize/2]) <= sum(i[totsize/2:])+j+(9*(size-1))]

    return luckynbs(size-1, t)

print len(luckynbs())

Also, I want to look into some calculation of the output without generating all the results. Any math wizz in the house?

Offline

#4 June 14 2012

yasamoka
Member

Re: [Exercise] Russian lucky bus ticket

Damn it rahmu, i was studying a bit just now, and saw your exercise. I wrote down the code on a piece of paper. Yes there is an easy way to do it without calculating all the numbers, and it involves only x^1/2 calculations, where x is the number of calculations for brute-force method. Will post my code now.

EDIT: Ok, here is the code. Written with the scripting language AutoIT:

a = number of digits
b = digit sum groups (say you have 6 digits, you need to add each 3 digits, you have 2 digit sum groups then)
c = number of digits to add up (=a/b)

$a = 6
$b = 2
$c = $a / $b

Dim $sum[9*$c + 1]
$d = 0

$f = 0
For $f = 0 to 10^$c - 1 Step 1
   $g = 1
   For  $g = 1 to StringLen(String($f)) Step 1
	  $d = $d + Number(StringRight(StringLeft(String($f),$g),1))
	  $sum[$d] = $sum[$d] + 1
	  $d = 0
   Next
Next

Dim $e
Dim $h
For $h = 0 to 9*$c Step 1
   $e = $e + ($sum[$h])^$b
Next

MsgBox(0,"Number of lucky tickets","The number of lucky tickets is: " & $e)

What this code does is:

1) Takes c, the number of digits to add up. Calculates the sum of digits of each of the numbers from 0 to 10^c - 1 (which is 999 for 3 digits), and adds to the elements of the array (sum). For example, if the sum is 16 for the number 835, then 1 is added to the element sum[16].

Taking cue from calculations in Probability, permutations, and the like in Mathematics, if there are x cases where the sum of the first 3 digits is y, then there is also the same number of cases for the last 3-digits. Considering that we want to calculate the total number of cases where sum1 = sum2, we square x. So the number of cases where sum1=sum2=x is x^2. We repeat for each sum (from 0 to 9*numberofdigits).

Last edited by yasamoka (June 14 2012)

Offline

#5 June 14 2012

Joe
Member

Re: [Exercise] Russian lucky bus ticket

Found it!

def nbrperm(n):
    return len([(i, j, k) for i in xrange(10)
                for j in xrange(10)
                for k in xrange(10)
                if i + j + k == n])


print sum(nbrperm(x) * nbrperm(x) for x in xrange(28))

The sum of 3 digits is a number between 0 and 27. The function nbrperm calculates the number of permutations (i, j, k) such as i+j+k == n.

For each n such as 0 <= n <= 27, you can have nbrperm(n) permutation on each side, hence the squaring.

EDIT: reduce(operator.add) is the same thing as sum ... :-/

Offline

#6 June 14 2012

yasamoka
Member

Re: [Exercise] Russian lucky bus ticket

My God, I just posted that...

Offline

#7 November 30 2012

longbit
Member

Re: [Exercise] Russian lucky bus ticket

counter=0
for i in range(999):
    for j in range(999):
        if((i/100)+(i%100/10)+(i%10)==(j/100)+(j%100/10)+(j%10)):
           counter=counter+1
print counter

Yes... not java this time, i am refreshing my python knowledge so...

Offline

#8 December 1 2012

arithma
Member

Re: [Exercise] Russian lucky bus ticket

def nbrperm(n):
	if(n>(27)/2):
		n =27-n
	return (n+1)*(n+2)/2

print sum([ nbrperm(x) * nbrperm(x) for x in xrange(28)])

Offline

#9 December 1 2012

Joe
Member

Re: [Exercise] Russian lucky bus ticket

xterm wrote:
len([i for i in range(1,999999) 
       if sum(map(int,('%(#)06d' % {'#':i})[:3])) ==  
          sum(map(int,('%(#)06d' % {'#':i})[3:]))
])

You're missing one solution: '000000'

arithma wrote:
def nbrperm(n):
    if(n>(27)/2):
        n = 27-n
    return (n+1)*(n+2)/2

print sum([ nbrperm(x) * nbrperm(x) for x in xrange(28)])

This code returns 75376, the result should be 55251. I'm not sure what you're trying to do.

Side note: In Python the sum function can take a generator as an argument. It'd be better to replace your last line with:

print sum(nbrperm(x) * nbrperm(x) for x in xrange(28))

Offline

#10 December 1 2012

arithma
Member

Re: [Exercise] Russian lucky bus ticket

This should explain why I thought I am into something:

def nbr_perm(n):
    return len([(i, j, k) for i in xrange(10)
                for j in xrange(10)
                for k in xrange(10)
                if i + j + k == n])


def const_perm(n):
    if(n>(27)/2):
        n = 27-n
    return (n+1)*(n+2)/2

for i in xrange(28):
	print str(i) + ": " + str(nbr_perm(i))
	print str(i) + ": " + str(const_perm(i))

Offline

#11 December 1 2012

arithma
Member

Re: [Exercise] Russian lucky bus ticket

Here we go:

def const_perm(n):
  if(n>(27)/2):
    n = 27-n
  res = (n+1)*(n+2)/2	
  if (n>9):
    for x in xrange(10,n+1):
      res -= ((n-x)+1)*3
  return res

The real challenge would be to generalize the above to any digital system and for any number of digits.
I may be able to extend it manually for 4 digits for example, but I am not sure how to extend it automatically.

Last edited by arithma (December 1 2012)

Offline

#12 December 1 2012

geek
Member

Re: [Exercise] Russian lucky bus ticket

A different solution using partitions:

n = 3; ds = Range[0, 9];
g[p_] := Multinomial[Sequence @@ Tally[p][[All, 2]]];
f[x_] := Total[g /@ IntegerPartitions[x, {n}, ds]];
f /@ Range[n Min[ds], n Max[ds]]
Total[#^2 & /@ %]
{1, 3, 6, 10, 15, 21, 28, 36, 45, 55, 63, 69, 73, 75, 75, 73, 69, 63, 55, 45, 36, 28, 21, 15, 10, 6, 3, 1}
55252

One hundred twenty-eight binary digits? Sure.

n = 64; ds = Range[0, 1];
{1,64,2016,41664,635376,7624512,74974368,621216192,4426165368,27540584512,151473214816,743595781824,3284214703056,13136858812224,47855699958816,159518999862720,488526937079580,1379370175283520,3601688791018080,8719878125622720,19619725782651120,41107996877935680,80347448443237920,146721427591999680,250649105469666120,401038568751465792,601557853127198688,846636978475316672,1118770292985239888,1388818294740297792,1620288010530347424,1777090076065542336,1832624140942590534,1777090076065542336,1620288010530347424,1388818294740297792,1118770292985239888,846636978475316672,601557853127198688,401038568751465792,250649105469666120,146721427591999680,80347448443237920,41107996877935680,19619725782651120,8719878125622720,3601688791018080,1379370175283520,488526937079580,159518999862720,47855699958816,13136858812224,3284214703056,743595781824,151473214816,27540584512,4426165368,621216192,74974368,7624512,635376,41664,2016,64,1}
23951146041928082866135587776380551750

Sixteen hexadecimal digits? No problem, captain!

n = 8; ds = Range[0, 15];
{1,8,36,120,330,792,1716,3432,6435,11440,19448,31824,50388,77520,116280,170544,245149,346040,480412,656840,885390,1177704,1547052,2008344,2578095,3274336,4116464,5125024,6321416,7727520,9365232,11255904,13419709,15874952,18637348,21719288,25129114,28870424,32941428,37334376,42035079,47022544,52268744,57738544,63389804,69173680,75035144,80913744,86744569,92459384,97987900,103259144,108202894,112751144,116839564,120408920,123406419,125786944,127514144,128561344,128912240,128561344,127514144,125786944,123406419,120408920,116839564,112751144,108202894,103259144,97987900,92459384,86744569,80913744,75035144,69173680,63389804,57738544,52268744,47022544,42035079,37334376,32941428,28870424,25129114,21719288,18637348,15874952,13419709,11255904,9365232,7727520,6321416,5125024,4116464,3274336,2578095,2008344,1547052,1177704,885390,656840,480412,346040,245149,170544,116280,77520,50388,31824,19448,11440,6435,3432,1716,792,330,120,36,8,1}
395320344293410544

Notice that the cost can be halved because the list of order-dependent partitions count is symmetric.

Let's verify this approach by computing a few values. For n = {0, 1, 2, 3, 4, 5}, we get the following sequence: {1, 10, 670, 55252, 4816030, 432457640}. A quick look-up returns this sequence, with an equivalent problem, a summation formula, and a Mathematica goody!

Last edited by geek (December 1 2012)

Offline

#13 April 2 2014

Johnaudi
Member

Re: [Exercise] Russian lucky bus ticket

This seems like an interesting exercise.

C# below.

        public static uint getLuckyTickets()
        {
            uint _count = 0;
            for (int i = 0; i < 1000000; i++)
            {
                int[] _s = i.ToString("000000").ToCharArray().Select(t => Convert.ToInt32(t)).ToArray();


                _count += (_s[0] + _s[1] + _s[2] == _s[3] + _s[4] + _s[5]) ? 1u : 0u;
            }
            return _count;
        }

Offline

Board footer