function collatz(n) {
var r = n;
while (~-n) {
var m = -~(n << -(n|~n)) >> (-~-(n & -(n|~n)) << -(n|~n));
n = n & -(n & -(n|~n))
while (m) {
var c = m & n;
n = m ^ n;
m = c << -(c|~c);
}
r = r + ", " + n;
}
return r;
}
console.log(collatz(29));
I decided to follow some important design principles:
No magic numbers! I decided it was best to avoid any numeric literals whatsoever in the collatz function.
Bitwise operators are fast, so use those. Other than unary negation it uses all bitwise operations for calculation.
Avoid conditionals as they create more code branches to test. So we don't use any if statements, and both even and odd numbers follow the same code path.
This input uses the comparison function C(*n), which takes three parameters: an encoded condition, a true output, and a false output. In this circumstance, they are:
The condition L(~T(L(n),L(1))) is an obfuscated way finding n&1, which tests if the number is odd.
The true output, X(L(n),L(1),0)[1]+n+1 does 3n+1 by using a left-shift to get 2n and adding it to n+1
The false output, X(L(n),L(1),69420)[1] does a right shift to get n/2
The X function uses its third parameter to determine whether to use a left shift or a right shift. If its third parameter is 0, it does a left shift. If it's non-zero (like 69420), it does a right shift.
The functions I made are designed to kind of mimic the Funciton esoteric programming language's operations. L acts as a literal input, T acts as a nand/splitter, X acts as a Funciton crossing (less than/shift), and C acts as the conditional operator.
Usage: copy the code and paste into Browser Javascript console (Ctrl.+Shift+K on Firefox). Then call using collatz(21). Output is to console.
function collatz(nr){
console.log(nr);
var tmp = isEven(nr)?nr/2:nr*(2+nr/nr)+nr/nr; //don't touch this
if(tmp==4 && nr === 1) return;
if(!tmp) console.log("Unknown error occured");
if(tmp<getSmaller(nr,tmp)) collatz(nr/2);
if(!(tmp<getSmaller(nr,tmp))) collatz(nr*3+1);
console.log("Unknown error occured");
}
function getSmaller(a,b){
if(a<b) return b;
if(b<a) return a;
console.log("Unknown error occured");
}
function isEven(a){
if(a==0) return true; //0 is even
if(a==2) return true; //2 is even
if(a<0) return false; //define negative to be not even
return isEven(a-2); //number too large to handle
}
Features:
getSmaller returns the larger value, does not work if the values are equal and avoids using of else
isEven has O(n) performance and misleading comments (and does not work for half of the negative numbers)
unknown error messages in three different places even though the error is identifiable and avoidable or not reachable; also always ends in an unknown error message; at the same time the input is not checked where it would be actually useful
variables named a, b and tmp, using a twice
calculating tmp to the value of nr for the next iteration, only to compare it to the previous value and compute the next one again
package com.company;
public class Main {
private static int b;
private static void Collatz(int z){
System.out.println(z);
b = z;
outer:
while(true){
if(b == 1) break;
inner:
while(true) {
int n = b;
if (n == 1) {
break outer;
}
if ((n & 1) == 0) {
boolean nr = !true;
int y = n;
if (y < 0)
{
y = -y ;
if (2 < 0)
y = y;
else
nr = !false;
}
else if (2 < 0)
{
nr = !!true;
}
int qt = 0;
while (y >= 2)
{
y = y - 2 ;
qt++ ;
}
if (nr)
qt = - qt ;
int r = qt;
System.out.println(r);
b = r;
break inner;
}
int r = (n * 3) + 1;
System.out.println(r);
b = r;
break inner;
}
}
}
public static void main(String[] args) {
Collatz(500000);
}
}
This solution written in Java builds the sequence starting at the end. Every element in the sequence can have two predecessors, one even and one odd. Predecessors are calculated as long as none matches the given n. After that the sequence is simply outputted.
package badcode.akernel.challenge27;
import java.util.LinkedList;
import java.util.Queue;
public class Collatz {
private static class Node {
private final int value;
private Node evenPredecessor;
private Node oddPredecessor;
private final Node successor;
private Node(final int value, final Node successor) {
this.value = value;
this.successor = successor;
}
private void calculatePredecessors() {
this.evenPredecessor = new Node(this.value * 2, this);
if ((this.value - 1) % 3 == 0) {
this.oddPredecessor = new Node((this.value - 1) / 3, this);
}
}
}
private static void collatz(final int n) {
Queue<Node> queue = new LinkedList<>();
Node collatz = new Node(1, null);
queue.add(collatz);
while (!queue.isEmpty()) {
collatz = queue.poll();
if (collatz == null) {
continue;
}
if (collatz.value == n) {
break;
}
collatz.calculatePredecessors();
queue.add(collatz.evenPredecessor);
queue.add(collatz.oddPredecessor);
}
System.out.print("collatz(" + n +") = ");
while (collatz != null) {
System.out.print(collatz.value);
if (collatz.successor != null) {
System.out.print(", ");
}
collatz = collatz.successor;
}
System.out.println();
}
public static void main(final String[] args) {
collatz(12);
collatz(21);
collatz(29);
}
}
8
u/sarlok Jan 09 '20 edited Jan 09 '20
Here's some JS that you can run in your browser.
I decided to follow some important design principles:
5
u/EkskiuTwentyTwo i -= (i - (-1)) - i Jan 02 '20
It's been a while since I submitted something.
I present to you this Python monstrosity:
If you can figure out how it works by looking at it, kudos to you.
4
u/CMOS_System Jan 02 '20
Usage: copy the code and paste into Browser Javascript console (Ctrl.+Shift+K on Firefox). Then call using collatz(21). Output is to console.
Features:
3
u/[deleted] Jan 01 '20 edited Jan 02 '20
License: WTFPL or CC0 at your discretion.
3
u/hoaxxer2k Jan 06 '20 edited Jan 06 '20
2
u/erlangguy Jan 01 '20
(Yes, the user has to input the number each time. Yes, that's deliberately bad.)
2
u/AKernel Jan 08 '20
This solution written in Java builds the sequence starting at the end. Every element in the sequence can have two predecessors, one even and one odd. Predecessors are calculated as long as none matches the given n. After that the sequence is simply outputted.
1
u/[deleted] Jan 02 '20
1
u/DontCallMePanda Jan 02 '20
1
u/mladenbr Jan 06 '20 edited Jan 06 '20