Programming Challenges

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.

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

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$

---

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?

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.

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.

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.

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).

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.

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 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

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.

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.

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.

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