Programming Challenges - Page 17

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

2. Registered User
Join Date
Oct 2006
Posts
1
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. 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\$```

4. Registered User
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. 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. 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.

7. Registered User
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. Registered User
Join Date
Jul 2003
Posts
28
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. 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.

Join Date
Mar 2005
Location
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;
}```

Join Date
Mar 2005
Location
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...

\$ time ./blah.exe abcdefgh > blah.txt

real 0m27.601s
user 0m0.015s
sys 0m0.000s

Join Date
Mar 2005
Location
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

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.

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.

15. Registered User
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
•