Programming Challenges - Page 11


Page 11 of 19 FirstFirst ... 789101112131415 ... LastLast
Results 151 to 165 of 279

Thread: Programming Challenges

  1. #151
    Join Date
    Jan 2003
    Location
    Austin, Texas
    Posts
    683
    Hey Ratboy...here's a little snippet of Java code (apparently we gotta represent!) that would work for your letter matching thing. It's basically a function that takes in a sorted array, and produces every single permutation of it while it still has one. It keeps testing hasNext() for the while loop condition and if it returns true and enters the loop, we call next to get the next "word". Then each "word" would have to be checked against a dictionary. So here's the permutation code...

    Code:
        boolean hasNext()
        {return hasAnother;}  //where hasAnother is just a boolean
        
        
        Object next()
        {
            hasAnother = nextPermutation(tempArray);
            return "";  //yeah so it's sloppy code (real one is all static too)...sue me
        }                  // it was only written to play word whomp!
        
        boolean nextPermutation (char[] a) 
        {
            if (a.length <= 1)
            {return false;}
    
            int i = a.length - 1;
            while (true)
            {
                int j = i--;
    
                if (a[i] < a[j])
                {
                    int k = a.length;
                    while (!(a[i] < a[--k])) {}
                    swap(a, i, k);
                    reverse(a, j);
                    return true;
                }
    
                if (i == 0)
                {
                    reverse(a, 0);
                    return false;
                }
            }
        }
    
        void reverse (char[] a, int i)
        {
            int j = a.length - 1;
            while (i < j)
            {swap(a, i++, j--);}
        }
    
        void swap (char[] a, int i, int j)
        {
            char tmp = a[i];
            a[i] = a[j];
            a[j] = tmp;
        }
    I had to write a program a few semesters ago that solved crypt arithmetic problems (if you don't know what that is, check it out here ), so it had to make all permutations of a set of letters and another that played boggle (so it had to check words against a dictionary..and recursively search the board to see if it exists) so I just kinda borrowed from both.

    Interestingly enough, I have already written something very similar to what you're describing several months ago. My dad really likes playing this game called "Word Whomp" where they jumble up 6 letters and you have to find all the valid words of length 3, 4, 5, or 6...so I just wrote a program to do it for me! It's specifically designed for those length words though and won't work for more than that. If you're interested, all necessary files can be found here. The above methods are used in it (and Words.java contains the main method used to run everything).
    "The author of that poem is either Homer or, if not Homer, somebody else of the same name."

  2. #152
    Join Date
    Nov 2003
    Posts
    53
    Originally posted by bwkaz
    [B]Um... no it isn't...

    First, it would require, at MINIMUM, 16 billion gigabytes of code space (since it'll be at least one byte for each value of a and b, that's 4 billion, squared, possibilities).
    Oops. My bad, you're right it's NOT very practical. I mean, when you read it back it almost looks like it was joking.
    Whatever it is I'm asking no doubt someone will find the answer in some obvious place and accuse me of not STWFing or RTFMing.

    I swear I did, I'm just stupid.

  3. #153
    Join Date
    Dec 2003
    Location
    Colorado
    Posts
    149
    heres a new one for you.

    I was just in math class thinking about it when I thought...

    is it possible to find the apsolute value of an integer without using a dummy variable and obviously another method or function.

    GlennaclawZ
    Registered Linux User: #342515

    Slackware 10 - kernel 2.6.10

    AMD Athlon 3000+
    512 RAM pc2700
    NVIDIA GeForce2 Integrated

    www.rex-pro.com For life!!!

  4. #154
    Join Date
    Jun 2003
    Posts
    173
    Code:
    if( var < 0) {
        var *= -1;
    }

  5. #155
    Join Date
    Dec 2003
    Location
    Colorado
    Posts
    149
    [QUOTE]Originally posted by gamblor01
    [B]Hey Ratboy...here's a little snippet of Java code (apparently we gotta represent!) [QUOTE]

    better Permutation:
    Code:
    public class Permutation
    {
      ArrayList arrayList;	//declaring variables
      Random random; 
      Double wrapper;
      int array[];
      int arraySpot;
      Permutation()			//constructors
      {
          random = new Random();
          arrayList = new ArrayList();
          array = new int[10];	
      }
    	
      public int[] fillArray()	//filling array
      {
          for(int i = 0; i < 10; i++)
          {
               int number = 1;
               array[i] = number;			
          }
          return array;
      }
    	
      public void generatePerm()	//generating permutation
      {		
          for(int k = 0; k <= 10; k++)
          {
              arraySpot = random.nextInt(10) + 1;
              wrapper = new Double(arraySpot);
              arrayList.add(wrapper);
              System.out.print(arrayList.get(k) + " ");
          }
          initList(arrayList);	
      }
    	
      public void initList(ArrayList list) 	//filling array back up
      {
          list.add("1");
          list.add("2");
          list.add("3");
          list.add("4");
          list.add("5");
          list.add("6");
          list.add("7");
          list.add("8");
          list.add("9");
          list.add("10");	
      }		
    }
    Last edited by GlennaclawZ; 04-07-2004 at 10:00 AM.
    Registered Linux User: #342515

    Slackware 10 - kernel 2.6.10

    AMD Athlon 3000+
    512 RAM pc2700
    NVIDIA GeForce2 Integrated

    www.rex-pro.com For life!!!

  6. #156
    Join Date
    Dec 2003
    Location
    Colorado
    Posts
    149
    Originally posted by lagdawg
    Code:
    if( var < 0) {
        var *= -1;
    }
    wow that was alot easier than I thought...
    Registered Linux User: #342515

    Slackware 10 - kernel 2.6.10

    AMD Athlon 3000+
    512 RAM pc2700
    NVIDIA GeForce2 Integrated

    www.rex-pro.com For life!!!

  7. #157
    Join Date
    Mar 2001
    Posts
    729
    How about without an if statement?

  8. #158
    Join Date
    Aug 2002
    Location
    Essex, UK
    Posts
    937
    In Perl:

    unless( var > 0) {
    var *= -1;
    }

    Registered Linux User #325947

    Check out Feather Linux, my distro.
    (Yes, it's shameless self promotion, deal with it )

  9. #159
    Join Date
    Apr 2001
    Location
    SF Bay Area, CA
    Posts
    14,936


    I can do it without an if, but I need a dummy variable:

    Code:
    int y = ((int)(x & 0x800000000u)) >> 31;
        /* y is all 1 bits now if x was negative, and 0 otherwise */
    
    x ^= y;   /* either flip all the bits (y all 1 bits) or leave them alone (y = zero) */
    x += (y & 1);   /* either add 1 or 0 */
    Assuming x is a signed, two's complement, 32-bit int, that is (which is the case on x86). If x86 used sign-magnitude numbers instead of two's complement, then it'd be as easy as:

    Code:
    x &= ~(0x7fffffff);
    to turn off the sign bit, but that's not the case.

  10. #160
    Join Date
    Aug 2002
    Location
    Cayman Islands
    Posts
    681
    In C:
    Code:
    x = (x>0) ? x : -x
    Scotty: Captain, we din' can reference it!
    Kirk: Analysis, Mr. Spock?
    Spock: Captain, it doesn't appear in the symbol table.
    Kirk: Then it's of external origin?
    Spock: Affirmative.
    Kirk: Mr. Sulu, go to pass two.
    Sulu: Aye aye, sir, going to pass two.

  11. #161
    Join Date
    Apr 2004
    Posts
    1
    god....i'll be going to UTA in the fall for computer science, hopefully by the time i get out i know what the hell you guys are talking about in this thread

  12. #162
    Join Date
    Jul 2003
    Location
    Scott, Louisiana
    Posts
    206
    Okay, I read this book "Archimede's Revenge" a couple weeks ago and it has a buttload of stuff like this, basically all this number and geometry thoery and stuff. Good reading. Here's one of the problems:
    "Suppose there are 100 people in a group, and you want to find out if 50 of them know each other".

    This can be done on paper by drawing 100 dots, connecting lines between people that know each other, and looking for all the people that know 49 others that all know the other 49.

    Yeah, it's one of those problems that as the set of people gets larger, the amount of work that it would require to find the answer increases exponentially.

    Find an algorithm that finds the answer in a manner such that the answer is found in an amount of work like n * number of people, rather than number of people ^ n.

    I was working on a method where you make a table, with all the people in the columns and all the people in the rows. Mark an X in the appropriate spot where people know one another(including that person knowing themself). Then remove all people that have less than the needed number of associations. Then you are left with all the people knowing the amount of people needed to associate with. Then, if all the spaces are filled, the answer is 'yes', they all know each other. I belive this approach is not exponential, but I could be wrong.
    Registered Linux User #328016
    I cna ytpe 300 wrods pre mniute

    Slackware 10.0
    Shuttle AN35N nForce2 mobo
    AMD Athlon XP 2600
    512 MB DDR RAM
    XFX GeForce FX 5200 256 MB
    40 GB Western Digital HDD

  13. #163
    Join Date
    Jun 2003
    Posts
    173
    duncanbojangles:

    This problem is basically for a group of n people find out if n/2 people know each other.

    The method you propose will only work in O(n^2) time. Or number of people ^ 2.



    First: To find all of the people in the group who know at least (n/2 - 1) you will have to visit every person and at the least for every peson you will have to visit is (n/2 - 1) if they now the first (n/2-1) people. There fore just to find all the people who know more than (n/2 - 1) people requires a minimum time of: n * (n/2 - 1) or 1/2 n^2 - n which is on the order of n^2.

    Edit
    I just realized the the First part of your solution can be accomplished like the second part with an upper triangular adjacency matrix and would only require the following number of visits if you kept a count along the way for each person:

    (n^2 - n) / 2 = 1/2 n^2 - 1/2 n which is less than 1/2 n^2 - n but it is still on the order of O(n^2).



    Second: To check whether all the people who know n/2-1 people know all the others you have to check whether the resulting upper triangular adjacency matrix is full.

    (example for n = 10 and n/2 = 5)

    x x x x x
    0 x x x x
    0 0 x x x
    0 0 0 x x
    0 0 0 0 x

    This matrix could be the result of removing rows from the original table / matrix, but since the lower triangle (everything under the diagonal) is the same as the upper triangle you only need to look at the upper triangle not including the diaganol and you must visite each one of those to see if they are x or not so we must visit

    (5^2 - 5) / 2 or ((n/2)^2 - n) / 2 or 1/4 (n^2) - 1/2 n

    which is of order O(n^2) as well

    so your solution is exponential in nature.
    Last edited by lagdawg; 04-12-2004 at 11:34 AM.

  14. #164
    Join Date
    Jul 2003
    Location
    Scott, Louisiana
    Posts
    206
    Darn. Oh well. The problem applies to any amount of people knowing any number of people...it didn't necessarily have to be 50 out of 100, that was just the example they used in the book. Thanks for pointing that out to me, guess I'm just not MathGenius material

    Edit!: After I thought about it, you may be able to reduce the amount of twork it requires to see who one person knows. If, for person A you find out they know B, C, D, and E, then B, C, D, and E will not have to check if they know A. This reduces a lot of work in theory, but in code you'd still have to check on the status of "knowingness of A". As long as the search is done in order, though, A, B, C, D, E, then you know that at E, they already know whether or not they know A, B, C, or D, so they don't have to check. This reduces a lot of overhead by only making E start looking at F.
    Last edited by duncanbojangles; 04-12-2004 at 06:27 PM.
    Registered Linux User #328016
    I cna ytpe 300 wrods pre mniute

    Slackware 10.0
    Shuttle AN35N nForce2 mobo
    AMD Athlon XP 2600
    512 MB DDR RAM
    XFX GeForce FX 5200 256 MB
    40 GB Western Digital HDD

  15. #165
    Join Date
    Jun 2003
    Posts
    173
    This problem can be solved recursively but it is slow on the order of O(n^2) or greater. But I beleive you could use dynamic programming to solve the recursion from the bottom up. Basically you only do each calculation once. Not sure how to do it right now but I'm working on it.

Posting Permissions

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