Page 1 of 2 12 LastLast
Results 1 to 10 of 17

Thread: Weekly Programming Challenge: February 2, 2007

  1. #1
    Join Date
    Jan 2006
    Beans
    4,208
    Distro
    Ubuntu 7.04 Feisty Fawn

    Weekly Programming Challenge: February 2, 2007

    Okay so once again I have the honor of setting this week's problem. As regular followers will be aware, the preceding challenges have covered a broad range of tasks and skill levels, and this week's challenge will be aimed at the more elementary level:

    A common task in board games or role-playing games is to roll a number of dice and do one of the following:
    (a) take the total of all dice rolled.
    (b) take the total of the highest n dice rolled.
    (c) note how many of the dice rolled achieved a target number t or higher.

    for example, if I rolled 4 six-sided dice and got [1, 2, 5, 5]
    (a) the total is 13
    (b) taking the highest three, the total is 12
    (c) if I was aiming for a target of 5 or higher, I would score 2 "hits"

    Your task is to write a program which will roll any required number of dice and process the result with parameters passed at runtime. If you wish to limit yourself to six-sided dice, that's fine. For "bonus marks" (yeah, right, believe me I am NOT marking this!) you could write your program to accept any number and combination of n-sided dice (numbered from 1 to n, of course).

    For those who feel this task is too trivial, I have another challenge (although I rather suspect there's a library/module out there that will achieve this one easily):
    Given a list of n items [1, 2, 3, ..., n], generate combinations and/or permutations of r objects selected from the list, i.e. spell out P(n,r) and C(n,r)

    Good luck.

  2. #2
    Join Date
    Apr 2006
    Beans
    1,979
    Distro
    Ubuntu 8.10 Intrepid Ibex

    Re: Weekly Programming Challenge: February 2, 2007

    Quote Originally Posted by meng View Post
    Okay so once again I have the honor of setting this week's problem. As regular followers will be aware, the preceding challenges have covered a broad range of tasks and skill levels, and this week's challenge will be aimed at the more elementary level:

    A common task in board games or role-playing games is to roll a number of dice and do one of the following:
    (a) take the total of all dice rolled.
    (b) take the total of the highest n dice rolled.
    (c) note how many of the dice rolled achieved a target number t or higher.

    for example, if I rolled 4 six-sided dice and got [1, 2, 5, 5]
    (a) the total is 13
    (b) taking the highest three, the total is 12
    (c) if I was aiming for a target of 5 or higher, I would score 2 "hits"

    Your task is to write a program which will roll any required number of dice and process the result with parameters passed at runtime. If you wish to limit yourself to six-sided dice, that's fine. For "bonus marks" (yeah, right, believe me I am NOT marking this!) you could write your program to accept any number and combination of n-sided dice (numbered from 1 to n, of course).

    For those who feel this task is too trivial, I have another challenge (although I rather suspect there's a library/module out there that will achieve this one easily):
    Given a list of n items [1, 2, 3, ..., n], generate combinations and/or permutations of r objects selected from the list, i.e. spell out P(n,r) and C(n,r)

    Good luck.
    Are we allowed to use random number generator functions, or should we just write one of our own, to add a little more complexity?

  3. #3
    Join Date
    Jun 2006
    Location
    CT, USA
    Beans
    5,267
    Distro
    Ubuntu 6.10 Edgy

    Re: Weekly Programming Challenge: February 2, 2007

    Quote Originally Posted by Tomosaur View Post
    Are we allowed to use random number generator functions, or should we just write one of our own, to add a little more complexity?
    Knuth has really good story about "homemade" random numbers generators (and why numbers they generate are not random) - I know I would not trust any random quick-and-dirty hobby random number generator. IMHO, YMMV.

    It might be separate task - to write really good random number generator, and write program comparing it to the one from library.

  4. #4
    Join Date
    Jan 2006
    Beans
    4,208
    Distro
    Ubuntu 7.04 Feisty Fawn

    Re: Weekly Programming Challenge: February 2, 2007

    Quote Originally Posted by Tomosaur View Post
    Are we allowed to use random number generator functions, or should we just write one of our own, to add a little more complexity?
    Your choice! I assumed most would use an already available randomizing module. But if that's too simple, feel free to add complexity.

  5. #5
    Join Date
    Jan 2007
    Beans
    768
    Distro
    Ubuntu 18.04 Bionic Beaver

    Re: Weekly Programming Challenge: February 2, 2007

    Ok, here's my first go at it. Written in C. Compile with gcc.

    To emulate the example:
    for example, if I rolled 4 six-sided dice and got [1, 2, 5, 5]
    (a) the total is 13
    (b) taking the highest three, the total is 12
    (c) if I was aiming for a target of 5 or higher, I would score 2 "hits"
    run it with the following parameters: -s 6 -n 4 -p 3 -t 5

    Parameters are:

    -n NUMDICE (specifies number of dice to roll, no default, parameter must be specified)
    -s SIDES (specifies number of sides on the dice, default 6)
    -s and -n can be repeated, to roll dice of different sizes. Make sure to specify -s before -n, since -s sets the number of sides for dice specified in later -n options.
    -t TARGET (counts number of dice rolled with at least TARGET value)
    -p N (totals values of top N dice. Obviously N must be <= the total number of dice rolled)

    Since I used a fixed allocation, there is a maximum of 100 dice that can be rolled per invocation. I figured that pre-calculating the number of dice and then allocating the array dynamically was outside the scope of this exercise.

    Code:
    #include <stdio.h>
    #include <stdlib.h>
    #include <malloc.h>
    #include <time.h>
    
    #define NUM_DICE 1
    #define NUM_SIDES 2
    #define NUM_TARGET 3
    #define NUM_TOP 4
    #define MAXDICE 100
    
    struct s_die {
      int sides;
      int value;
    };
    
    static int dice_compare(const void *d1, const void *d2);
    void usage(void);
    void createAndRollDie(struct s_die *d, int sides);
    
    main(int argc, char **argv)
    {
      int i, j, target = 0, work, numDice = 0, nextParm = 0, topNumToTotal = 0;
      int hits = 0, total = 0, topTotal = 0, lastSides = 0;
      time_t t;
      struct s_die *dice, *p, **sortarray, **s;
      int numCurrSides = 6, numCurrDice = 2;
    
      /* Allocate space for up to 100 dice (for simplicity's sake) */
      if ((dice = (struct s_die *)malloc(sizeof(struct s_die) * MAXDICE)) == NULL)
      {
        fprintf(stderr, "Unable to allocate space for dice structures\n");
        exit(1);
      }
      p = dice;
      /* Seed random number generator */
      time(&t);
      srand(t);
      /* Parse arguments */
      for (i = 1; i < argc; i++)
      {
        if (*argv[i] == '-')
        {
           switch(*(argv[i] + 1))
           {
             case 'n':   /* Number of dice */
               nextParm = NUM_DICE;
               break;
             case 's':   /* Number of sides */
               nextParm = NUM_SIDES;
               break;
             case 't':   /* Target number */
               nextParm = NUM_TARGET;
               break;
             case 'p':   /* Total top p dice  */
               nextParm = NUM_TOP;
               break;
             default:
               fprintf(stderr, "Invalid parameter: %s\n", argv[i]);
               usage();
           }
        }
        else
        {
           switch(nextParm)
           {
             case NUM_DICE:
               numCurrDice = atoi(argv[i]);
               numDice += numCurrDice;
               if (numDice > MAXDICE)
               {
                 fprintf(stderr, "Maximum of %d dice allowed\n", MAXDICE);
                 exit(1);
               }
               for (j = 0; j < numCurrDice; j++)
                 createAndRollDie(p++, numCurrSides);
               break;
             case NUM_SIDES:
               numCurrSides = atoi(argv[i]); break;
             case NUM_TARGET:
               target = atoi(argv[i]); break;
             case NUM_TOP:
               topNumToTotal = atoi(argv[i]); break;
             default:
               usage();
           }
        }
      }
      if (numDice < 1) usage();
      /*  Allocate array of pointers to sort dice */
      if ((sortarray = (struct s_die **)malloc(sizeof(struct s_die *) * numDice)) == NULL)
      {
        fprintf(stderr, "Unable to allocate space for sort array structures\n");
        exit(1);
      }
      /*  Print value of dice and build array for sorting, and calculate target hits */
      for (i = 0, p = dice, s = sortarray; i < numDice; i++, p++, s++)
      {
        *s = p;
        if (target > 0 && p->value >= target) hits++;
        if (p->sides == lastSides)
          printf(", ");
        else
        {
          printf("\nRoll %d-sided dice: ", p->sides);
          lastSides = p->sides;
        }
        printf("%d", p->value);
        total += p->value;
      }
      /*  Sort array */
      qsort(sortarray, numDice, sizeof(struct s_die *), dice_compare);
      /* Get total of top N dice */
      if (topNumToTotal > numDice) topNumToTotal = numDice;
      for (i = 0, s = sortarray; i < topNumToTotal; i++, s++)
        topTotal += (*s)->value;
      /* Print totals */
      printf("\nTotal of all dice = %d\n", total);
      if (topNumToTotal) printf("Total of top %d dice = %d\n", topNumToTotal, topTotal);
      if (target) printf("Total dice > %d = %d\n", target, hits);
      /* Clean up */
      free(sortarray);
      free(dice);
      return 0;
    }
    
    /* Compare function for qsort.  Returns are reversed so that sort is in descending order */
    static int dice_compare(const void *d1, const void *d2)
    {
       int v1 = (*(const struct s_die **)d1)->value;
       int v2 = (*(const struct s_die **)d2)->value;
       if (v1 < v2)
         return 1;
       else if (v1 > v2)
         return -1;
       else
         return 0;
    }
    
    /*  Initializes a die structure, and "rolls" the dice using rand() */
    void createAndRollDie(struct s_die *d, int sides)
    {
      d->sides = sides;
      d->value = rand() % sides + 1;
    }
    
    /* A little help blurb */
    void usage()
    {
      fprintf(stderr, "Usage: dice [-t target] [-p toptotal] [ [-s sides] [-n numdice] ] ...\n\n \
    Rolls numdice dice of s sides.  Returns number of dice with value at least\n\
    target, and total for toptotal dice.\n\
    -s and -n can be repeated to roll multiple dice of different sizes.\n\
    When -s and -n are used together, put -s first.\n");
      exit(1);
    }

  6. #6
    Join Date
    Apr 2006
    Beans
    1,979
    Distro
    Ubuntu 8.10 Intrepid Ibex

    Re: Weekly Programming Challenge: February 2, 2007

    Quote Originally Posted by pmasiar View Post
    Knuth has really good story about "homemade" random numbers generators (and why numbers they generate are not random) - I know I would not trust any random quick-and-dirty hobby random number generator. IMHO, YMMV.

    It might be separate task - to write really good random number generator, and write program comparing it to the one from library.
    I know all that, but past challenges have mostly been 'wary' of using libraries, just wanted to clarify the situation

  7. #7
    Join Date
    Dec 2006
    Beans
    37

    Re: Weekly Programming Challenge: February 2, 2007

    In Python:
    Code:
    import random
    
    dices = int(raw_input("How many dices? "))
    sides = int(raw_input("How many sides? "))
    target = int(raw_input("Target: "))
    
    eyes = [ random.randint(1,sides) for dice in range(dices) ]
    top_3 = sorted(eyes)[-3:]
    hits = len( [ i for i in eyes if i == target ] )
    
    print "Rolled dices: ", eyes
    print "Total: %s" % sum(eyes)
    print "Top 3: %s" % top_3
    print "Hits: %s" % hits

  8. #8
    Join Date
    Dec 2006
    Location
    Sacramento, CA
    Beans
    284
    Distro
    Ubuntu 6.10 Edgy

    Re: Weekly Programming Challenge: February 2, 2007

    Generating permutations and combinations is a great way to show off the power of Python's generators. A generator, if you're not familiar with them, is a very useful construct that allows a function to return a value, but maintain state, and continue from the return (or yield) point on the next call. The most basic example I can think of is a generator which mimics the behavior of range for a step value of 1:

    Code:
    def range_generator(start, stop):
       while start < stop:
           yield start
           start += 1
    By creating recursive generators, you can *easily* generate all permutations of combination of a list:

    Code:
    def perm(l):
        if len(l)==1: yield l
        else: for item in l:
                sl=list(tuple(l))
                sl.remove(item)
                for subperm in perm(sl): yield [item]+subperm
    
    def comb(l):
        if len(l)==1: yield l
        else:
            sl=list(tuple(l))
            for item in l:
                yield [item]
                sl.remove(item)
                for subcomb in comb(sl): yield [item]+subcomb
    These examples simply return all permutations of full size, and all combinations in the same rank order as the list passed in. It should be a simple exercise to extend these functions to return all permutations of a given size, or all combinations of a given size. I leave these exercises to the readers who have just discovered generators and want to play around with them a bit more.
    Last edited by jblebrun; February 3rd, 2007 at 06:55 AM.

  9. #9
    Join Date
    Dec 2006
    Beans
    37

    Re: Weekly Programming Challenge: February 2, 2007

    I'm currently trying to learn Haskell (2 days now), so I thought this challenge would be an easy exercise. I was so wrong. The function getrand allone took 3 headaches.
    Code:
    module Main where
    
    import IO
    import List
    import Random
    import Text.Printf
    
    getrand :: Int -> Int -> IO [Int]
    getrand num sides = do
      g <- newStdGen
      let dices = randomRs (1::Int, sides) g
      return (take num dices)
    
    prettifyDices :: (Show a) => [a] -> String
    prettifyDices lst = concat $ intersperse "-" $ map (show) lst
    
    main = do
      hSetBuffering stdin LineBuffering
      putStrLn "How many dices? "
      num <- getLine
      putStrLn "How many sides? "
      sides <- getLine
      putStrLn "Target: "
      target <- getLine
      rands <- getrand (read num) (read sides)
      let sorted = sort rands
      printf "Dices: %s\n" $ prettifyDices rands
      printf "Sum: %s\n"   $ show $ sum sorted
      printf "Top 3: %s\n" $ prettifyDices $ take 3 (reverse sorted)
      printf "Hits: %s\n"  $ show $ length $ filter (== (read target)) sorted
    Any Haskell hackers out there who can show me how to really do this in Haskell?

    Regards, mawe

  10. #10
    Join Date
    Nov 2006
    Location
    Udine, Italy
    Beans
    28

    Re: Weekly Programming Challenge: February 2, 2007

    Code:
    permutation l = h id l [1..l] 
      where
        h g 0 _ = [g[]]    
        h g len_1 list = f g list len_1 
          where 
            f _ _ 0 = []
            f g b@(y:ys) len_2 = (h (g . (y:)) (len_1 -1) ys) ++ (f g (swap b) (len_2-1))  
            swap [] = []
            swap (x:xs) = xs ++ [x]
    Hi, this is my solution, even if I haven't understood very well what you meant by
    Given a list of n items [1, 2, 3, ..., n], generate combinations and/or permutations of r objects selected from the list, i.e. spell out P(n,r) and C(n,r)
    Especially for the r parameter. Anyway, this piece of function computes all the possible permutation of a given list from 1 to n, which it is chosen by the user...
    I hope it is quite close to what you meant.
    Bye.

Page 1 of 2 12 LastLast

Bookmarks

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •