6
\$\begingroup\$

A woman works at a lottery ball factory. She's instructed to open up a lottery ball creation kit composed of 1 red rubber ball and n strips of digits from 0 through 9.

She's instructed to do the following:

  1. Starting with 1, write the current number on the ball using the digits available on the n strips.
  2. Put unused digits into a bowl where they can be used later for when she runs out of available digits in step 1.
  3. Open up another lottery ball creation kit and continue to step 1 for the next number.

The question is, at what number will she arrive at before she runs out of digits to write the number? Edited: Given n where n is the number of digit strips from 0 through 9 provided in each lottery ball creation kit, write a program that can solve this (not trivially) in the least amount of time.

Edit: Additional notes - 6 and 9 are different numbers. Assume there are no limits to the number of digits that can be pasted on the ball.

Hint: If she counted in base 2 rather than base 10, how would that change the result and would that be easier to calculate? What could you derive from solutions in base 2?

\$\endgroup\$
27
  • 2
    \$\begingroup\$ Are 6 and 9 considered to be different ? \$\endgroup\$
    – Paul R
    Jun 29, 2011 at 16:25
  • 2
    \$\begingroup\$ @Peter I guess I'm confused about how you can do anything intelligent beyond increment and check without making it trivial. It seems kind of silly to take advantage of various properties of the problem while ignoring the obvious one, that it has a direct and fixed solution. I don't think this is a good question. \$\endgroup\$ Jun 29, 2011 at 17:46
  • 2
    \$\begingroup\$ @Matthew, it should be possible to do something binary-searchy. (If anyone can be bothered to check which Project Euler problem is very similar to this question I might check my solution). But I agree that fixed mathematical problems are bad questions. Perhaps the problem should be fixed by making the number of strips in each kit an input variable? \$\endgroup\$ Jun 29, 2011 at 20:53
  • 2
    \$\begingroup\$ All good points. Making relevant corrections to the question. \$\endgroup\$
    – Neil
    Jun 30, 2011 at 12:03
  • 3
    \$\begingroup\$ I’m voting to close this question because it's tagged fastest-code but is missing details about the specs of the computer on which answers are timed etc. \$\endgroup\$ Mar 30, 2022 at 2:13

3 Answers 3

2
\$\begingroup\$

edit 2: fixed

General solution for n > 1:

-- lottery2.hs

import System
import Control.Monad
import Data.Maybe

main = mapM_ print . map (solve . read) =<< getArgs

rdigits 0 = []
rdigits n = (n `mod` 10) : rdigits (n `div` 10)

digits = reverse . rdigits

undigits = foldl ((+) . (10*)) 0

c1 = c . digits

c [] = 0
c [0] = 0
c [_] = 1
c (0:xs) = c xs
c (1:xs) = d xs + c xs + undigits xs
c (x:xs) = c xs + x * (d xs - 1) + 10 ^ length xs

d xs = ds !! length xs

ds = map d' [0..]
  where d' n = c1 (10 ^ n - 1) + 1

maxVal n =
  fst . head . filter (uncurry $ (<) . (*n))
  . map (liftM2 (,) undigits c . (1:) . flip replicate 9) $ [0..]

search f p q a b = s f (uncurry p) q (a, f a) (b, f b)
  where 
    s f p q a b
      | not (p a) = Nothing
      | fst a + 1 == fst b = guard (not $ p b) >> return (fst a)
      | a >= b = Nothing
      | q a b = maybe (s f p q k b) Just (s f p q a k)
      | otherwise = Nothing
        where k = ((fst a + fst b) `div` 2, f (fst k))

solve n = fromJust $ search c1 ((>=) . (*n)) q 1 m
  where 
    m = maxVal n
    q (a, fa) (b, fb) = (a * n) - fa <= fb - fa

There seems to be a pattern here:

$ ghc -O --make lottery2.hs
Linking lottery2 ...
$ time ./lottery 1 2 3 4 5 6
199990
1999919999999980
19999199999999919999999970
199991999999999199999999919999999960
1999919999999991999999999199999999919999999950
19999199999999919999999991999999999199999999919999999940

real    0m3.580s
user    0m3.508s
sys     0m0.020s
$ time ./lottery 7 8 9 10 11 12
199991999999999199999999919999999991999999999199999999919999999930
1999919999999991999999999199999999919999999991999999999199999999919999999920
19999199999999919999999991999999999199999999919999999991999999999199999999919999999918
199991999999999199999999919999999991999999999199999999919999999991999999999199999999919999999917
1999919999999991999999999199999999919999999991999999999199999999919999999991999999999199999999919999999916
19999199999999919999999991999999999199999999919999999991999999999199999999919999999991999999999199999999919999999915

real    1m10.855s
user    1m3.868s
sys     0m0.324s
\$\endgroup\$
22
  • \$\begingroup\$ What answer did you get and how long did it take to get there ? \$\endgroup\$
    – Paul R
    Jun 30, 2011 at 22:24
  • \$\begingroup\$ 199990 real 0m0.742s user 0m0.532s sys 0m0.020s \$\endgroup\$ Jul 1, 2011 at 2:14
  • \$\begingroup\$ That looks like the answer for only 1 strip of numbers - for 2 strips it should be of the order of 10^20. \$\endgroup\$
    – Paul R
    Jul 1, 2011 at 6:59
  • \$\begingroup\$ Answer for n=1 is 199991 since technically 199990 is the last number she could make. @Paul: For n=2, actually it's a bit less. Mind you, still not a small number.. \$\endgroup\$
    – Neil
    Jul 1, 2011 at 10:21
  • 1
    \$\begingroup\$ It's commendable that you found what seems to be the most efficient solution to solve the problem, though unfortunately the answers aren't correct. If you get it right, you'll see a pattern begin to form. \$\endgroup\$
    – Neil
    Jul 4, 2011 at 10:40
2
\$\begingroup\$

awk (109)

brute force solution

yes|awk -F "" '{c("0123456789",1);c(NR,-1)}function c(C,m,i){for($0=C;NF-i++;)if((t[$i]+=m)<0){print NR-1;exit}}'

The awk does not count in the character count if I understand the rules correctly.
The trick with yes| + NR is a shorter way to define a loop counter than a BEGIN + while or for clause.
Replace ,1 with ,[value of n]. With 1 it returns 199990, with 2 it is still trying to find the answer.

Could write it as:

yes|awk -F "" -v n=1 '{c("0123456789",n);c(NR,-1)}function c(C,m,i){for($0=C;NF-i++;)if((t[$i]+=m)<0){print NR-1;exit}}'

And replace n=1 with n=[whatever value] (now a parameter of the program, for an extra 6 characters plus the number of characters for the value of n. But like I said since it is still trying to compute for n=2, there may be no need to parameterise this version.

I'm sure there must be a much more clever algorithm than plain increment and count. Like a bit of algebra. No time for this... I'll leave that to someone else.

\$\endgroup\$
4
  • \$\begingroup\$ This is code-challenge rather than code-golf, so it doesn't matter whether awk counts or not. \$\endgroup\$ Jul 1, 2011 at 7:30
  • \$\begingroup\$ We're dealing with enormous numbers, so large in fact that I think it makes choice of language irrelevant in the ultimate performance of the program. As for your answer, it's technically 199991, since 199990 is the last number she could make. \$\endgroup\$
    – Neil
    Jul 1, 2011 at 10:13
  • \$\begingroup\$ @Neil: you said "what number she would arrive at before she runs out", so yes, I printed the last number before she ran out. You do not have enough digits to print 199991. \$\endgroup\$
    – asoundmove
    Jul 1, 2011 at 15:45
  • \$\begingroup\$ ... I hate it when I'm wrong. \$\endgroup\$
    – Neil
    Jul 4, 2011 at 10:37
0
\$\begingroup\$

C

Here's a non-golf brute force solution in C which seems to give the right answer for 1 strip, but I haven't had the patience to let it run long enough to see if it gets to a solution for 2 strips (in fact if I extrapolate the progress output I'm not sure it will finish within my life-time !).

#include <stdio.h>
#include <stdint.h>
#include <string.h>
#include <stdlib.h>

int main(int argc, char *argv[])
{
    const int MAX_DIGITS = 24;
    char buff[MAX_DIGITS + 1];
    int num_strips = 1;
    int64_t digits[10] = { 0 };
    int64_t i;

    if (argc > 1)
    {
        num_strips = atoi(argv[1]);
        if (num_strips < 1 || num_strips > 2)
        {
            fprintf(stderr, "num_strips must be 1 or 2\n");
            exit(1);
        }
    }

    memset(buff, ' ', MAX_DIGITS - 1);
    buff[MAX_DIGITS - 1] = '1';
    buff[MAX_DIGITS] = '\0';

    for (i = 1 ; ; ++i)
    {
        int d;

        // add 2 to each remaining digit count

        for (d = 0; d < 10; ++d)
        {
            digits[d] += num_strips;
        }

        // update counts of remaining digits based on current i

        for (d = MAX_DIGITS - 1; d >= 0; --d)
        {
            char ch = buff[d];

            if (ch != ' ')
            {
                int digit = ch - '0';
                digits[digit]--;
            }
            else
            {
                break;
            }
        }

        // check to see whether we found solution

        for (d = 0; d < 10; ++d)
        {
            if (digits[d] < 0)
            {
                printf("Found solution at i = %s, digits = { %24lld %24lld %24lld ... %24lld }\n", buff, digits[0], digits[1], digits[2], digits[9]);
                goto done;
            }
        }

        // log progress when i == 2^n

        if ((i & (i - 1)) == 0)
        {
            printf("i = %s, digits = { %24lld %24lld %24lld ... %24lld }\n", buff, digits[0], digits[1], digits[2], digits[9]);
        }

        // increment "i"

        for (d = MAX_DIGITS - 1; d >= 0; --d)
        {
            char ch = buff[d];

            switch (ch)
            {
                case ' ':
                    buff[d] = '1';
                    break;
                case '9':
                    buff[d] = '0';
                    continue;
                    break;
                default:
                    buff[d] = ch + 1;
                    break;
            }
            break;
        }
    }
done:
    return 0;
}
\$\endgroup\$
1
  • \$\begingroup\$ Nice try, though exceeding n=2 for brute force is a mess. \$\endgroup\$
    – Neil
    Jul 5, 2011 at 7:30

Not the answer you're looking for? Browse other questions tagged or ask your own question.