Programming Challenges

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! :D 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).

Quote:

---

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. :p

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

Code:

---

if( var < 0) {
    var *= -1;
}

---

[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");       
  }               
}

---

Quote:

---

Originally posted by lagdawg

Code:

---

if( var < 0) {
    var *= -1;
}

---

---

wow that was alot easier than I thought...

How about without an if statement?

In Perl:

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

:D

:D

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.

In C:

Code:

---

x = (x>0) ? x : -x

---

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

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.

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.

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.

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.