The Greplin Programming Challenge

[FriedEgg]

Hi Everyone,

It has been a while since I have posted one of the challenges I typically scour the internet looking for.  I found a good new one though that comes in three parts.  I will publish them all here but to be fair to the originator they are all part of the Greplin Coding Challenge (http://challenge.greplin.com).

The Greplin Programming Challenge

Level 1

----------------------------------------

Embedded in this block of text (I have also attached this file to the post) is the password for level 2.

The password is the longest substring that is the same in reverse.

As an example, if the input was "I like racecars that go fast"

the password would be "racecar".

Level 2

----------------------------------------

To get the password for level 3, write code to find the first prime

fibonacci number larger than a given minimum.  For example, the first

prime fibonacci number larger than 10 is 13.

You will receive additional instructions at that time.  For the second portion

of this task, note that for the number 12 we consider the sum of the prime divisors

to be 2 + 3 = 5.  We do not include 2 twice even though it divides 12 twice.

Step 1. Use your code to compute the smallest prime fibonacci number

greater than 227,000.  Call this number X.

Step 2. The password for level 3 is the sum of prime divisors of X + 1.

-- In other words you want to do the following

Step 1. Find smallest prime fibonacci number greater that 227,000

Step 2. Add 1 to the smallest prime fibonacci number found

Step 3. Sum the unique prime divisors of number from step 2

Level 3
----------------------------------------
For the final task, you must find all subsets of an array

where the largest nu mber is the sum of the remaining numbers.

For example, for an input of:

(1, 2, 3, 4, 6)

the subsets would be

1 + 2 = 3

1 + 3 = 4

2 + 4 = 6

1 + 2 + 3 = 6

Here is the list of numbers (I have also attached this file to the post) you should run your code on.

The password is the number of subsets.  In the above case the

answer would be 4.

SPOILER: Below are my answers, I altered the text color so that you should have to highlight the text for it to be visible...  Don't cheat

LEVEL 1:

data _null_;

lengthlen 8 str$ 10;

declarehash ha();

ha.definekey('len');

ha.definedata('len','str');

ha.definedone();

input @;

do s=1 to length(_infile_)-5;

do l=5 to 10;

str=substr(_infile_,s,l);

ifstrip(str)=reverse(strip(str)) then

  do;

   len=length(strip(str));

   ifha.check()>0 thenha.add();

  end;

end;

end;

declarehiter iter('ha');

rc=iter.last();

if rc=0 then put str=;

cards;

FourscoreandsevenyearsagoourfaathersbroughtforthonthiscontainentanewnationconceivedinzLibertyanddedicatedtothepropositionthatallmenarecreatedequalNowweareengagedinagreahtcivilwartestingwhetherthatnaptionoranynartionsoconceivedandsodedicatedcanlongendureWeareqmetonagreatbattlefiemldoftzhatwarWehavecometodedicpateaportionofthatfieldasafinalrestingplaceforthosewhoheregavetheirlivesthatthatnationmightliveItisaltogetherfangandproperthatweshoulddothisButinalargersensewecannotdedicatewecannotconsecratewecannothallowthisgroundThebravelmenlivinganddeadwhostruggledherehaveconsecrateditfaraboveourpoorponwertoaddordetractTgheworldadswfilllittlenotlenorlongrememberwhatwesayherebutitcanneverforgetwhattheydidhereItisforusthelivingrathertobededicatedheretotheulnfinishedworkwhichtheywhofoughtherehavethusfarsonoblyadvancedItisratherforustobeherededicatedtothegreattdafskremainingbeforeusthatfromthesehonoreddeadwetakeincreaseddevotiontothatcauseforwhichtheygavethelastpfullmeasureofdevotionthatweherehighlyresolvethatthesedeadshallnothavediedinvainthatthisnationunsderGodshallhaveanewbirthoffreedomandthatgovernmentofthepeoplebythepeopleforthepeopleshallnotperishfromtheearth

;

run;

LEVEL 2:

proc fcmpoutlib=work.func.cipher;

function isprime(num);

n=0;

j=3;

do while(j<=int(sqrt(num)) and n=0);

  if mod(num,j)=0 then n+1;

  j+2;

end;

if n=0 then return(1);

else return(0);

endsub;

run;

%let cmplib=%sysfunc(getoption(cmplib));

options cmplib=(work.func&cmplib);

data _null_;

f=1;

do until(f>227000 and isprime(f));

f=sum(f,lag(f));

end;

f+1;

j=3;

sum=2;

do while(j<=int(sqrt(f)));

if mod(f,j)=0 and isprime(j) then

  do;

   sum+j;

      output;

  end;

j+2;

end;

put sum=;

run;

LEVEL 3: -- This one turned out to be the shortest answer, but it definitly took me the most thought.

data _null_;

array seq[22] (3 4 914 15 19 28 37 47 50 5456 59 61 70 73 78 81 9295 97 99);

do i=2 to dim(seq);

do n=1 to comb(dim(seq),i) while(n<10000);

  call lexcomb(n,i,of seq

);

  sum=seq[1];

  do s=2 to i;

   sum+seq;

  end;

  if sum in seq then count+1;

end;

end;

put count=;

run;

[Ksharp · Accepted solution]

data _null_;
input have : $2000.;
length pw a $ 2000;
len=0;
do i=1 to length(have)-1;
 do j=2 to length(have)-i+1;
  a=substr(have,i,j); 
  if strip(a)=strip(reverse(a)) then do;
                         if length(a) gt len then do;
                          len=length(a);
                          pw=a;
                         end;
                        end;
 end;
end;
put pw=;
datalines;
FourscoreandsevenyearsagoourfaathersbroughtforthonthiscontainentanewnationconceivedinzLibertyanddedicatedtothepropositionthatallmenarecreatedequalNowweareengagedinagreahtcivilwartestingwhetherthatnaptionoranynartionsoconceivedandsodedicatedcanlongendureWeareqmetonagreatbattlefiemldoftzhatwarWehavecometodedicpateaportionofthatfieldasafinalrestingplaceforthosewhoheregavetheirlivesthatthatnationmightliveItisaltogetherfangandproperthatweshoulddothisButinalargersensewecannotdedicatewecannotconsecratewecannothallowthisgroundThebravelmenlivinganddeadwhostruggledherehaveconsecrateditfaraboveourpoorponwertoaddordetractTgheworldadswfilllittlenotlenorlongrememberwhatwesayherebutitcanneverforgetwhattheydidhereItisforusthelivingrathertobededicatedheretotheulnfinishedworkwhichtheywhofoughtherehavethusfarsonoblyadvancedItisratherforustobeherededicatedtothegreattdafskremainingbeforeusthatfromthesehonoreddeadwetakeincreaseddevotiontothatcauseforwhichtheygavethelastpfullmeasureofdevotionthatweherehighlyresolvethatthesedeadshallnothavediedinvainthatthisnationunsderGodshallhaveanewbirthoffreedomandthatgovernmentofthepeoplebythepeopleforthepeopleshallnotperishfromtheearth
;
run;


/*
ranynar











data _null_;
array p{1000000} _temporary_;
 do i=1 to 1000000;
  p{i}=i;
 end;
do j=2 to int(sqrt(1000000));
if not missing(p{j}) then do;
  do i=j+1 to 1000000;
  if not missing(p{i})  then do; 
     if mod(p{i},p{j})=0 then p{i}=.; end;
  end;
 end;
end;



array f{30} _temporary_;
a=1;b=1; f{1}=2;f{2}=3;
do _i=3 to dim(f);
 f{_i}=f{_i-1}+f{_i-2};
end;

do x=1 to dim(f);
if f{x} gt 227000 and f{x} in p then do;  prime=f{x}+1;leave;end;
end;

do k=2 to 10000;
 if mod(prime,p{k})=0 then sum+k;
end;
put sum=;

run;


/*
prime number=514229

514230

sum=352












data a1(keep=list sum);
array a{22} _temporary_ (3 4 9 14 15 19 28 37 47 50 54 56 59 61 70 73 78 81 92 95 97 99);
length list $ 100;
do i=1 to dim(a);
 do j=i+1 to dim(a);
  list=catx('+',a{i},a{j});sum=a{i}+a{j};if sum le 99 then output;
 end;
end;
run; 
data a2(keep=list sum);
array a{22} _temporary_ (3 4 9 14 15 19 28 37 47 50 54 56 59 61 70 73 78 81 92 95 97 99);
length list $ 100;
do i=1 to dim(a);
 do j=i+1 to dim(a);
  do k=j+1 to dim(a);
  list=catx('+',a{i},a{j},a{k});sum=a{i}+a{j}+a{k};if sum le 99 then output;
 end;
end;
end;
run; 
data a3(keep=list sum);
array a{22} _temporary_ (3 4 9 14 15 19 28 37 47 50 54 56 59 61 70 73 78 81 92 95 97 99);
length list $ 100;
do i=1 to dim(a);
 do j=i+1 to dim(a);
  do k=j+1 to dim(a);
   do l=k+1 to dim(a);
  list=catx('+',a{i},a{j},a{k},a{l});sum=a{i}+a{j}+a{k}+a{l};if sum le 99 then output;
 end;
end;
end;
end;
run;
data a4(keep=list sum);
array a{22} _temporary_ (3 4 9 14 15 19 28 37 47 50 54 56 59 61 70 73 78 81 92 95 97 99);
length list $ 100;
do i=1 to dim(a);
 do j=i+1 to dim(a);
  do k=j+1 to dim(a);
   do l=k+1 to dim(a);
    do m=l+1 to dim(a);
  list=catx('+',a{i},a{j},a{k},a{l},a{m});sum=a{i}+a{j}+a{k}+a{l}+a{m};if sum le 99 then output;
 end;
end;
end;
end;
end;
run;  
data a5(keep=list sum);
array a{22} _temporary_ (3 4 9 14 15 19 28 37 47 50 54 56 59 61 70 73 78 81 92 95 97 99);
length list $ 100;
do i=1 to dim(a);
 do j=i+1 to dim(a);
  do k=j+1 to dim(a);
   do l=k+1 to dim(a);
    do m=l+1 to dim(a);
     do n=m+1 to dim(a);
  list=catx('+',a{i},a{j},a{k},a{l},a{m},a{n});sum=a{i}+a{j}+a{k}+a{l}+a{m}+a{n};if sum le 99 then output;
 end;
end;
end;
end;
end;
end;
run;  
data a6(keep=list sum);
array a{22} _temporary_ (3 4 9 14 15 19 28 37 47 50 54 56 59 61 70 73 78 81 92 95 97 99);
length list $ 100;
do i=1 to dim(a);
 do j=i+1 to dim(a);
  do k=j+1 to dim(a);
   do l=k+1 to dim(a);
    do m=l+1 to dim(a);
     do n=m+1 to dim(a);
      do o=n+1 to dim(a);
  list=catx('+',a{i},a{j},a{k},a{l},a{m},a{n},a{o});sum=a{i}+a{j}+a{k}+a{l}+a{m}+a{n}+a{o};if sum le 99 then output;
 end;
end;
end;
end;
end;
end;
end;
run;  


data list;
 set a1-a6;
run; 

data _null_;
 set list end=last;
array a{22} _temporary_ (3 4 9 14 15 19 28 37 47 50 54 56 59 61 70 73 78 81 92 95 97 99);
if sum in a then do;put list sum;count+1;end;
if last then put count=;
run;
                    
/*
count=179

Ksharp

[FriedEgg]

Very nice work Ksharp!  I can always count on you to have a response to my posts!

Message was edited by: Matthew Kastin

[Ksharp]

My answer is correct. I have passed by http://challenge.greplin.com.

Maybe the data of yours and mine is different.

The following is my winning page.

The Greplin Programming Challenge

The End

----------------------------------------

Congratulations.  You completed the challenge.  Your completion code is 524-16720-86543.

We'd love to talk to you - send your completion code, the code you wrote

during the challenge, and your resume to

jobs+i+solved+the+challenge@greplin.com

Even if you're not looking for a job, we'd love to hear what you thought

     about the challenge.

Ksharp

[FriedEgg]

Totally my mistake, I read your answer wrong I guess???  179 is absolutly the correct answer.

[Ksharp]

Your code for Level 3 is not right.

I run it . It is 172

[FriedEgg]

Yes, the version I posted originally was incorrect, I pasted the wrong one.  The iterations were cut too short, I fixed it with the proper version.

Even so, my program for the third step is not good, right, wrong or indifferent as in my opinion I only happen upon the proper answer by happenstance.  It is probable, in my mind, that should I allow more iterations it will generate count>179 and be wrong again...

[Ksharp]

I tested it again. No problem.

The Greplin Programming Challenge

The End

----------------------------------------

Congratulations.  You completed the challenge.  Your completion code is 93-212-194.

We'd love to talk to you - send your completion code, the code you wrote

during the challenge, and your resume to

jobs+i+solved+the+challenge@greplin.com

Even if you're not looking for a job, we'd love to hear what you thought

     about the challenge.