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.
Printable View
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.
( a + ib ) * ( c + id ) = X + iYQuote:
Originally Posted by grady
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
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:Quote:
Originally Posted by tecknophreak
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:
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.Code:[ a b ] [ c d ] = [ ac+bg ad+bh ]
[ e f ] [ g h ] = [ ec+fg ed+fh ]
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.Quote:
Originally Posted by bwkaz
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:Do not use a recursive algorithm.Code:./scramble hack
hack
ahkc
kahc
akch
...
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:
I've got another algorithm out there somewhere which does much better, I'll see if I can find it.Code:#include <iostream>
#include <algorithm>
int main() {
char array[10] = "abcdefghi";
while (std::next_permutation(array, &array[9])) {
std::cout << array << std::endl;
}
}
There it is:
next_perm.h
test.cppCode:#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
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.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;
}
}
}
somebody know how can i use shell variable inside sed?
i=string
sed 's/somestring/$i/'
??