12
\$\begingroup\$

This is a new kind of challenge inspired by the Recover the mutated source code problem.

You should write two programs or functions both in the same language. The first one should solve Task #1 and the second one should solve Task #2.

Your score will be the sum of the longer program and the Levenshtein distance between the two programs source code. Lower score is better so you should try to make the two solutions similar while keeping the lengths of the programs short.

Task #1

You are given a positive integer N and you should output the Collatz sequence of N separated by spaces or newline. Trailing separator is allowed.

The first element of the Collatz sequence is N. The rest of the elements are generated based on their successor \$a_{i-1}\$:

$$ a_i = \begin{cases} \frac{a_{i-1}}{2} & \text{ if } a_{i-1} \text{ is even} \\ 3a_{i-1} + 1 & \text{ if } a_{i-1} \text{ is odd} \end{cases} $$

As soon as the sequence reaches 1 no new elements are generated.

Input => Output examples:

6 => 6 3 10 5 16 8 4 2 1
8 => 8 4 2 1
1 => 1

Task #2

A pair of twin primes is a pair of positive integer whose difference is 2 and they are both primes.

You are given a positive integer N and you should output the smallest pair of twin primes where both primes are bigger than N The first number should be the smaller one and the two primes should be separated by spaces or newline. Trailing separator is allowed.

Input => Output examples:

6 => 11 13
42 => 59 61
1 => 3 5

Snippet for calculating the score

(Modification of the one in the Recover the mutated source code problem.)

var f=document.getElementById("f"),g=document.getElementById("s");function h(){var a=f.value,e=g.value,m=Math.max(a.length,e.length);if(10000<a.length)a="<span style='color:red'>First program is too long!</span>";else if(10000<e.length)a="<span style='color:red'>Second program is too long!</span>";else{if(0===a.length)a=e.length;else if(0===e.length)a=a.length;else{var d=[],b;for(b=0;b<=e.length;b++)d[b]=[b];var c;for(c=0;c<=a.length;c++)d[0][c]=c;for(b=1;b<=e.length;b++)for(c=1;c<=a.length;c++)d[b][c]=e.charAt(b-1)===a.charAt(c-1)?d[b-1][c-1]:Math.min(d[b-1][c-1]+1,Math.min(d[b][c-1]+1,d[b-1][c]+ 1));a=d[e.length][a.length]}a="Distance = "+a+"   Longer length = "+m+"   Score = <strong>"+(a+m)+"</strong>"}document.getElementById("d").innerHTML=a}f.onkeyup=h;g.onkeyup=h;
First program<textarea id=f rows=2 cols=80 style="width:100%"></textarea>Second program<textarea id=s rows=2 cols=80 style="width:100%"></textarea><p id=d></p>

Edit

In the answers' header let's use the format

[Language], [longer length] + [distance] = [final score].

E.g.

Python 2, 60 + 32 = 92

\$\endgroup\$
3
\$\begingroup\$

Pyth, 18 + 13 = 31

Collatz Sequence:

QWtQ=Q@,/Q2h*Q3QQ

Twin Primes:

=Qf!ttP*T+T2hQQ+Q2

Try it here.

Some ideas thanks to FryAmTheEggman.

\$\endgroup\$
4
\$\begingroup\$

CJam, 24 + 17 = 41 42

Collatz program:

ri2*{:N2%N3*)N2/?__p(}g;

Twin primes program:

ri_2+]{:)_{mp}/&_+((}gS*

Both take input from STDIN and print space/newline separated numbers to STDOUT

Try them online here

\$\endgroup\$
3
\$\begingroup\$

CJam, 25 + 16 = 41

Collatz program:

l~2*{_2%{3*)}{2/}?_p_(}g;

Twin primes program:

l~_2+]{:)_{mp}/&!_&}gS*

Test it here.

I just golfed both of them for now. I'll see if I can reduce the score somehow.

\$\endgroup\$
2
\$\begingroup\$

Pyth, 20 + 14 = 40 34

Collatz:

QWtQ=Q@,/Q2h*3QQQ

Prime Pairs:

~Q1WttP*Q+Q2~Q1;Q+Q2

Both are programs that take input from STDIN and output the numbers on newlines. Just golfed both answers while using the same looping primitive for now. This could probably be improved quite a bit.

Edit: Added better condition checking stolen from @isaacg. Seems like using filter is still shorter than using a while loop for the prime pairs.

Try it online here.

\$\endgroup\$
  • \$\begingroup\$ This outputs 3 5 for the input 3 on prime pairs. It should output 5 7. \$\endgroup\$ – isaacg Feb 1 '15 at 23:40
  • \$\begingroup\$ @isaacg Fixed it, costed 3 :( \$\endgroup\$ – FryAmTheEggman Feb 2 '15 at 0:54
2
\$\begingroup\$

05AB1E, 14 + 13 10 9 = 27 24 23

-4 score thanks to ASCII-only

Collatz sequence (14 bytes):

[DÉi3*>ë2÷}Ð,#

Try it online!

Twin primes (14 bytes):

[DÅND>>Dp#}s,,

Try it online!


Golfed Twin primes (11 bytes):

[ÅNDÌp#]DÌ»

Try it online!

\$\endgroup\$
  • \$\begingroup\$ Collatz link is incorrect \$\endgroup\$ – ASCII-only Jan 19 at 1:22
  • \$\begingroup\$ Thanks, fixed it! \$\endgroup\$ – Wisław Jan 19 at 1:32
  • \$\begingroup\$ primes, -3 score. probably worth keeping golfed version in the answer as a side note in case there's a different, better golf (what exactly does pair do, btw? like why do i have to do ,,, and why does only Ð, work there) \$\endgroup\$ – ASCII-only Jan 19 at 1:42
  • \$\begingroup\$ -1 more (edit: never mind, first number should be smaller. score 24 for now \$\endgroup\$ – ASCII-only Jan 19 at 1:57
  • \$\begingroup\$ 22? \$\endgroup\$ – ASCII-only Jan 19 at 2:02
1
\$\begingroup\$

Java 8, 118 + 84 = 202

Collatz:

n->{for(System.out.println(n);n>1;System.out.println(n=n%2<1?n/2:3*n+1));}

Twin primes:

n->{t:for(int p,z;;n++){for(z=n;z<n+3;z=z+2)for(p=2;p<z;p++)if(z%p<1)continue t;System.out.print(n+" "+(n+2));break;}}
\$\endgroup\$
  • \$\begingroup\$ mention Java 8 .. \$\endgroup\$ – Optimizer Feb 1 '15 at 21:05
1
\$\begingroup\$

Mathematica, 53 + 29 = 82

Collatz Sequence:

Print/@(NestWhileList[If[OddQ@#,3#+1,#/2]&,#,#>1&]);&

Twin primes program:

Print/@(NestWhile[NextPrime,#,!PrimeQ[#+2]&]+{0,2});&
\$\endgroup\$
1
\$\begingroup\$

><>, 116 + 86 = 202

Collatz program (46):

0i:0(?v$a*$'0'-+!
?v6,>:>~:nao:1=?;3*:2%
 >1+^

Twin primes program (116):

0i:0(?v$a*$'0'-+!
v&2+1~<:-2
<v!?%&+1:&:v?=&:&:
 >&~0$2&2+v>&~143.
:&:1+&%?!v>:&:&=?v
0v?*r$0~&< .561~&<.1
:<;noan-2

Ouch. Both programs start with the same atoi function, but after that twin primes goes downhill. The same piece of code is repeated twice for primality check — it might be slightly shorter to somehow reuse the piece, but the setup for it wouldn't save many bytes.

Could do a lot better by throwing the back half of twin primes into the unused spots of the Collatz program, but I'm not sure if that's allowed.

\$\endgroup\$
  • 3
    \$\begingroup\$ "Golf it, Golf it NAO!" - Noanold Golfzenegger. That said, the question doesn't seem to say that adding in garbage to reduce the Levenshtein distance is taboo, so I would go nuts ;) \$\endgroup\$ – FryAmTheEggman Feb 2 '15 at 4:20
0
\$\begingroup\$

C++ Distance = 114 Longer length = 155 Score = 269

Task 1

void c(int N){while(N>1){cout<<N<<' ';N=(N%2==0)?N/2:N*3+1;}cout<<N;}

Task 2

int p(int x){int z=0;for(int i=2;i<x;i++){if(x%i==0){z=1;break;}}return z;}
void c(int N){N=(N%2==0)?N+1:N+2;int M=N+2;while(p(N)+p(M)>0){N=M;M+=2;}cout<<N<<' '<<M;}

Task 2 improved

int p(int N){int z=0;for(int i=2;i<N;i++){if(N%i==0){z=1;break;}}return z;}
void c(int N){N=(N%2==0)?N+1:N+2;while(p(N)+p(N+2)>0){N+=2;}cout<<N<<' '<<N+2;}
\$\endgroup\$
  • \$\begingroup\$ I think you did not even try to reduce the score. For instance, you have different function names, different argument name different return type and what not which are increasing your distance. \$\endgroup\$ – Optimizer Feb 1 '15 at 11:15
  • \$\begingroup\$ @Optimizer I don't know of another way to test for primes? Other languages have this built in. \$\endgroup\$ – bacchusbeale Feb 1 '15 at 18:24
  • 1
    \$\begingroup\$ I was not even talking about changing the algo. For instance, this code has only 102 distance: int p(int x){int z=0;for(int i=2;1<x;i++){cout<<x<<' ';x=(x%2==0)?x/2:x*3+1;}cout<<x;return z;} \$\endgroup\$ – Optimizer Feb 1 '15 at 18:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.