Programming Challenges - Page 17


Page 17 of 19 FirstFirst ... 713141516171819 LastLast
Results 241 to 255 of 279

Thread: Programming Challenges

  1. #241
    Wow, I am amazed the last post on this thread is in 2006. Can anyone recall me? I was on this forum in 2003 last.
    i was once trapped by windows, but linux set me free...

  2. #242
    Join Date
    Oct 2006
    Posts
    1
    Quote Originally Posted by grady
    Compute the complex product ( a + ib ) * ( c + id ) using only three real multiplications
    ( a + ib ) * ( c + id ) = X + iY
    X=a*c-b*d

    let i=a*c ; j=b*d;

    Y=b*c+a*d=(a+b)*(c+d)-a*c-b*d=(a+b)*(c+d)-i-j
    three multiplications:
    1 : (a+b)*(c+d)
    2 : a*c
    3 : b*d

  3. #243
    Join Date
    Feb 2004
    Location
    austin, tx
    Posts
    145
    Quote Originally Posted by tecknophreak
    Ok, here's one. You know a quote has a ceaser(sp?) cipher on it, you just don't know what is is. You have to run a program/script and have the program figure out what the correct cipher is for the quote. The program will have two outputs the cipher, i.e. Shift +24, and the answer.

    Here's a fun quote: zypr: "ufyr'q qylry'q jgrrjc fcjncp bmgle rm rfyr bme? jmmiq jgic fc'q rpwgle rm hskn mtcp, zsr fc ayl'r osgrc kyic gr."

    I'd really like to see the script for this one since I'm sure it's quicker/easier than c/c++.
    i hacked something up. and i'm not using "hacked" lightly here, i'm sure it's pretty volatile. the only easy way i could think of is by making sure all the words in the possibly decrypted strings have vowels in them. words like "in, a, is, are" fail this pretty easily if they aren't shifted to the correct alphabet character, so it works fairly well. a dictionary lookup would be less volatile though. if it can't decrypt the line using that test, then it simply skips it and moves on to the next. what's the key is found all subsequent lines are decrypted in the same manner:

    Code:
    #!/usr/bin/perl
    
    my $shiftAmount = 0;
    my $cryptFound = 0;
    
    while(<>) {
      my @chars = split //;
      my $string;
    
      if ($cryptFound == 1) {
        @chars = shiftChars($shiftAmount, @chars);
        print join ('', @chars);
        next;
      }
      for(1..26) {
        ++$shiftAmount;
        @chars = shiftChars(1, @chars);
        $string = join('',@chars);
        print $string;
        if( isEnglish((split(/\s+/,$string))) == 1 ) {
          $cryptFound = 1;
          print "DECRYPTED: Shift +$shiftAmount\n";
          print $string;
          last;
        }
      }
    }
    
    sub isEnglish {
      my (@words) = @_;
      for(@words) {
        if (not /[aeiou]/g) {
          return 0;
        }
      }
      return 1;
    }
    
    sub shiftChars {
      my $shiftAmount = shift;
      my @chars = @_;
      for(1..$shiftAmount) {
        for(@chars) {
          next if(/\W/);
          if($_ eq "z") {
            $_ = a;
            next;
          }
          if($_ eq "Z") {
            $_ = A;
            next;
          }
          ++$_;
        }
      }
      return @chars;
    }
    Code:
    fluxion@serenity:~/source$ cat caesar.in 
    ufyr'q qylry'q jgrrjc fcjncp bmgle rm rfyr bme? jmmiq jgic fc'q rpwgle rm hskn mtcp, zsr fc ayl'r osgrc kyic gr.
    wms
    ypc y
    kmlicwdyac
    fluxion@serenity:~/source$ ./caesarCipher.pl caesar.in 
    vgzs'r rzmsz'r khsskd gdkodq cnhmf sn sgzs cnf? knnjr khjd gd'r sqxhmf sn itlo nudq, ats gd bzm's pthsd lzjd hs.
    what's santa's little helper doing to that dog? looks like he's trying to jump over, but he can't quite make it.
    DECRYPTED: Shift +2
    what's santa's little helper doing to that dog? looks like he's trying to jump over, but he can't quite make it.
    you
    are a
    monkeyface
    fluxion@serenity:~/source$
    Roses are red, violets are blue. All my base, are belong to you.

  4. #244
    Join Date
    Jul 2003
    Posts
    28
    You've all had three years to strengthen your Kung Fu by pondering the reduction of the complex multiply from four multplications to three. Many have either moved up to management or lost their skill by writing reams of code that runs on a flatulent virtual machine. Is there one left among you whose Kung Fu is strong enough for this challenge:

    A 2x2 matrix multiply requires 8 multiplications and 4 additions. Can you make a computer do a 2x2 matrix multiply by issuing only 3 arithmetic instructions?

  5. #245
    Join Date
    Mar 2003
    Location
    Tampa, FL USA
    Posts
    2,193
    You have awaken the beast...

    Can you define what a "2x2 matrix" is, for those of us that may not know. I have a couple of ideas, but I'm not sure if they match what you're thinking.

  6. #246
    Join Date
    Feb 2004
    Location
    Singapore
    Posts
    2,171
    The 2x2 matrix is the 2-row 2-column square matrix, and 8 multiplications and 4 additions are correct. Its the standard def of matrix. Check out wikipedia for it.
    Come under the reign of the Idiot King...
    Come to me ... I love linux!

    Registered Linux user: Idiot King #350544

  7. #247
    Join Date
    Apr 2001
    Location
    SF Bay Area, CA
    Posts
    14,947
    Well, the matrix multiplication algorithm looks like:

    Code:
    [ a b ] [ c d ] = [ ac+bg ad+bh ]
    [ e f ] [ g h ] = [ ec+fg ed+fh ]
    Now, I don't see any way to simplify this to three instructions -- at least not in general. Unless your particular CPU does vectored arithmetic (can do independent operations on many operands at the same time), in which case, you're cheating. It still does all 8 multiplications and all 4 additions, it just does some of them at the same time as others.

  8. #248
    Join Date
    Jul 2003
    Posts
    28
    Quote Originally Posted by bwkaz
    Unless your particular CPU does vectored arithmetic (can do independent operations on many operands at the same time), in which case, you're cheating.
    It's OK to use vector instructions. The challenge is: can you do the multiply by "issuing only 3 arithmetic instructions" - as in machine instructions. It's very likely that the computer in front of you can do this.

    Another challenge:
    Reverse this apropos quote ".esnesnon dna skcirt elpmis fo tol a lla s'tI"... on the GPU (your video card's processor).
    Last edited by grady; 12-03-2006 at 03:19 PM.

  9. #249
    Join Date
    Mar 2003
    Location
    Tampa, FL USA
    Posts
    2,193
    Here's a new challenge. I was posed this problem earlier today, and it took me a lot longer to figure out than I originally thought it would. I have yet to put it into code myslef.

    Create a program that takes a word, then outputs all possible scrambles of that word. A sample of its output might look similar to this:
    Code:
    ./scramble hack
    hack
    ahkc
    kahc
    akch
    ...
    Do not use a recursive algorithm.

  10. #250
    Join Date
    Mar 2005
    Location
    asdhsadgas
    Posts
    197
    the following works only for 9 digit words or less
    Code:
    #include <iostream>
    #include <string>
    using namespace std;
                                                  /* takes the j-th digit from 
    						 left to right */
    const unsigned long P10[]=
    	{1,10,100,
    	1000,10000,100000,
    	1000000,10000000,
    	100000000};
    typedef int* vec;
    
    #define dig(i,j,len) (i/P10[len-j])%10
    
    inline bool rep(unsigned long K,int l){
    	int rep_hash[10]={0,0,0,0,0,0,0,0,0,0}; 
    	bool okay=false; 
    	int U; 
    	for(U=1;U<=l;U++){
    		if( dig(K,U,l) > l || dig(K,U,l) ==0 ){
    			okay=true;break;
    		};
    	       	if(rep_hash[ dig(K,U,l) ] == 1){ 
    			okay=true;break; 
    		};
    		rep_hash[ dig(K,U,l) ]=1; 
    	}; 
    	return okay;
    }
                                                    /* returns true if repeating digit
    						and returns false if no repeating
    						digit is found */
                                                    /* also needs to check for
    						digits that should not be larger
    						than l and the digit should be
    						 different from 0*/
    inline void print_perm(char* a,unsigned long T,int len){
    	for(int i=1;i<=len;i++)
    		cout<<a[ dig(T,i,len) - 1 ];
    	cout<<endl;
    }
    
    
    
    void    all_scrambles(char* scramble){
    	int len=strlen(scramble);
    	unsigned long T=123456789;
    	unsigned long UPPERLIM=999999999;
    	T/=P10[9-len];
    	UPPERLIM/=P10[9-len];
    	while(++T<=UPPERLIM)
    		if(rep(T,len)==false)
    			print_perm(scramble,T,len);
    }
    
    
    
    int main(int argc,char** argv){
    	if(argc>1)
    		all_scrambles(argv[1]);
    	return 0;
    }
    i'm stupid

  11. #251
    Join Date
    Mar 2005
    Location
    asdhsadgas
    Posts
    197
    i forgot to brag about it,actually that it does the job for 9 letters pretty fast
    on a 1.6ghz, that is...

    spx2@asfasfadgf ~
    $ time ./blah.exe abcdefgh > blah.txt

    real 0m27.601s
    user 0m0.015s
    sys 0m0.000s
    i'm stupid

  12. #252
    Join Date
    Mar 2005
    Location
    asdhsadgas
    Posts
    197
    the code needs trivial modifications to reach the general purpose of the challenge(for an arbitrary length word)

    now some explanations on the algorithm used wichis also trivial.
    one can understand the "ideea" behind the algorithm if he thinks at
    the way a number is increased by on unit,if he can understand the
    mecanism of transport for addition and all that concerns it then,then
    it will be easy to understand the ++T line.
    after that one must think the digits of T are actually the possitions
    of the letters inside a new scramble of argv[1].
    those positions have to meet some constraints described in the comments
    wich are included in the source.
    that is all

    P.S. the typedef int* vec; i forgot to delete this
    its useless,at first i wanted to use it but figgured that id be
    better off without.
    Last edited by spx2; 01-03-2007 at 02:01 AM. Reason: forgot something
    i'm stupid

  13. #253
    Join Date
    May 2001
    Location
    Uh, I'm somewhere where I don't know where I am.
    Posts
    1,228
    I thought we did this one a while ago. Anywho, it's fun:

    Code:
    #include <iostream>
    #include <algorithm>
    
    int main() {
    	char array[10] = "abcdefghi";
    	while (std::next_permutation(array, &array[9])) {
    		std::cout << array << std::endl;
    	}
    }
    I've got another algorithm out there somewhere which does much better, I'll see if I can find it.
    if (i_forgot && this_is_about_code)
    language = c++;

  14. #254
    Join Date
    May 2001
    Location
    Uh, I'm somewhere where I don't know where I am.
    Posts
    1,228
    There it is:

    next_perm.h
    Code:
    #ifndef NEXT_PERM_H
    #define NEXT_PERM_H
    
    template<class T>
    inline void swap(T *lh, T *rh) {
         T tmp(*lh);
         *lh = *rh;
         *rh = tmp;
    }
     
    template<class T>
    inline void reverse(T *array, int size) {
    	int lh(0), rh(size - 1);
    	while (lh < rh) {
    		swap(&array[lh], &array[rh]);
    		++lh;
    		--rh;
    	}
    }
    
    
    template<class T>
    bool next_perm(T *array, int length) {
    	int len(length - 1), replace(len), current;
    	while (--replace != -1) { 
    		for (current = len; current != replace; --current) { 
    			if (array[current] > array[replace]) {
    				swap(&array[current], &array[replace]);
    				reverse(&array[replace + 1], len - replace);
    				return true;
    			}
    		}
    	}
    	reverse(array, length);
    	return false;
    }
    
    #endif     // NEXT_PERM_H
    test.cpp
    Code:
    #include <iostream>
    #include "next_perm.h"
    
    
    int main(int argc, char **argv) {
    	if (argc == 2) {
    		char *array(argv[1]);
    		int len(strlen(array));
    		std::cout << array << std::endl;
    		while (next_perm(array, len)) {
    			std::cout << array << std::endl;
    		}
    	}
    }
    takes ~24 sec to do 9 on a 3.0 ghz machine, however, ABCDEFGH is only 8 letters, ABCDEFGHI is 9 letters, I don't know if that was a miss type.
    if (i_forgot && this_is_about_code)
    language = c++;

  15. #255
    Join Date
    Jan 2007
    Posts
    1

    shell variable with sed

    somebody know how can i use shell variable inside sed?
    i=string
    sed 's/somestring/$i/'
    ??

Posting Permissions

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