Ear*_*rlz 86 language-agnostic code-golf collatz rosetta-stone
灵感来自http://xkcd.com/710/这里是一个高尔夫代码.
挑战
给定大于0的正整数,打印出该数字的冰雹序列.
冰雹序列
有关更多详细信息,请参阅Wikipedia
用生成的数字重复此操作,直到达到1.(如果在1之后继续,它将进入无限循环1 -> 4 -> 2 -> 1...)
有时代码是最好的解释方式,所以这里有一些来自维基百科
function collatz(n)
show n
if n > 1
if n is odd
call collatz(3n + 1)
else
call collatz(n / 2)
这段代码有效,但我正在增加额外的挑战.程序不能容易受到堆栈溢出的影响.所以它必须使用迭代或尾递归.
此外,如果它可以计算大数字并且语言尚未实现,则奖励积分.(或者如果使用固定长度的整数重新实现大数字支持)
测试用例
Number: 21
Results: 21 -> 64 -> 32 -> 16 -> 8 -> 4 -> 2 -> 1
Number: 3
Results: 3 -> 10 -> 5 -> 16 -> 8 -> 4 -> 2 -> 1
此外,代码高尔夫必须包括完整的用户输入和输出.
Mar*_*tin 129
;
; To assemble and link this program, just run:
;
; >> $ nasm -f elf collatz.asm && gcc -o collatz collatz.o
;
; You can then enjoy its output by passing a number to it on the command line:
;
; >> $ ./collatz 123
; >> 123 --> 370 --> 185 --> 556 --> 278 --> 139 --> 418 --> 209 --> 628 --> 314
; >> --> 157 --> 472 --> 236 --> 118 --> 59 --> 178 --> 89 --> 268 --> 134 --> 67
; >> --> 202 --> 101 --> 304 --> 152 --> 76 --> 38 --> 19 --> 58 --> 29 --> 88
; >> --> 44 --> 22 --> 11 --> 34 --> 17 --> 52 --> 26 --> 13 --> 40 --> 20 --> 10
; >> --> 5 --> 16 --> 8 --> 4 --> 2 --> 1
;
; There's even some error checking involved:
; >> $ ./collatz
; >> Usage: ./collatz NUMBER
;
section .text
global main
extern printf
extern atoi
main:
cmp dword [esp+0x04], 2
jne .usage
mov ebx, [esp+0x08]
push dword [ebx+0x04]
call atoi
add esp, 4
cmp eax, 0
je .usage
mov ebx, eax
push eax
push msg
.loop:
mov [esp+0x04], ebx
call printf
test ebx, 0x01
jz .even
.odd:
lea ebx, [1+ebx*2+ebx]
jmp .loop
.even:
shr ebx, 1
cmp ebx, 1
jne .loop
push ebx
push end
call printf
add esp, 16
xor eax, eax
ret
.usage:
mov ebx, [esp+0x08]
push dword [ebx+0x00]
push usage
call printf
add esp, 8
mov eax, 1
ret
msg db "%d --> ", 0
end db "%d", 10, 0
usage db "Usage: %s NUMBER", 10, 0
Jos*_*Lee 64
&>:.:1-|
>3*^ @
|%2: <
v>2/>+
lun*_*dov 52
LOLCODE:406 CHARAKTERZ
HAI
BTW COLLATZ SOUNDZ JUS LULZ
CAN HAS STDIO?
I HAS A NUMBAR
BTW, I WANTS UR NUMBAR
GIMMEH NUMBAR
VISIBLE NUMBAR
IM IN YR SEQUENZ
MOD OF NUMBAR AN 2
BOTH SAEM IT AN 0, O RLY?
YA RLY, NUMBAR R QUOSHUNT OF NUMBAR AN 2
NO WAI, NUMBAR R SUM OF PRODUKT OF NUMBAR AN 3 AN 1
OIC
VISIBLE NUMBAR
DIFFRINT 2 AN SMALLR OF 2 AN NUMBAR, O RLY?
YA RLY, GTFO
OIC
IM OUTTA YR SEQUENZ
KTHXBYE
JESTIN J. MEZA'S INTERPRETR的 TESTD UNDR .KTHXBYE!
mak*_*puf 51
显然不会产生堆栈溢出.
n=input()
while n>1:n=(n/2,n*3+1)[n%2];print n
jkf*_*kff 23
c 1=[1]
c n=n:c(div(n`mod`2*(5*n+2)+n)2)
main=readLn>>=print.c
用户输入,打印输出,使用常量内存和堆栈,使用任意大整数.
这个代码的示例运行,给出一个80位数的全'1(!)作为输入,看起来非常有趣.
原创,仅限功能版本:
Haskell 51个字符
f n=n:[[],f([n`div`2,3*n+1]!!(n`mod`2))]!!(1`mod`n)
无论如何,@&^#谁需要条件？
(编辑:我是"聪明"并使用修复.没有它,代码下降到54个字符.编辑2:通过分解掉到51 f())
Bra*_*ert 23
我决定有点反竞争,并展示你通常如何在Perl中编写这样的问题.
最后还有一个46(总)char码 - 高尔夫球场.
前三个示例都是从这个标题开始的.
#! /usr/bin/env perl
use Modern::Perl;
# which is the same as these three lines:
# use 5.10.0;
# use strict;
# use warnings;
while( <> ){
chomp;
last unless $_;
Collatz( $_ );
}
简单的递归版本
use Sub::Call::Recur;
sub Collatz{
my( $n ) = @_;
$n += 0; # ensure that it is numeric
die 'invalid value' unless $n > 0;
die 'Integer values only' unless $n == int $n;
say $n;
given( $n ){
when( 1 ){}
when( $_ % 2 != 0 ){ # odd
recur( 3 * $n + 1 );
}
default{ # even
recur( $n / 2 );
}
}
}
简单的迭代版本
sub Collatz{
my( $n ) = @_;
$n += 0; # ensure that it is numeric
die 'invalid value' unless $n > 0;
die 'Integer values only' unless $n == int $n;
say $n;
while( $n > 1 ){
if( $n % 2 ){ # odd
$n = 3 * $n + 1;
} else { #even
$n = $n / 2;
}
say $n;
}
}
优化的迭代版本
sub Collatz{
my( $n ) = @_;
$n += 0; # ensure that it is numeric
die 'invalid value' unless $n > 0;
die 'Integer values only' unless $n == int $n;
#
state @next;
$next[1] //= 0; # sets $next[1] to 0 if it is undefined
#
# fill out @next until we get to a value we've already worked on
until( defined $next[$n] ){
say $n;
#
if( $n % 2 ){ # odd
$next[$n] = 3 * $n + 1;
} else { # even
$next[$n] = $n / 2;
}
#
$n = $next[$n];
}
say $n;
# finish running until we get to 1
say $n while $n = $next[$n];
}
现在,我将展示如何使用v5.10.0之前的Perl版本来完成最后一个示例
#! /usr/bin/env perl
use strict;
use warnings;
while( <> ){
chomp;
last unless $_;
Collatz( $_ );
}
{
my @next = (0,0); # essentially the same as a state variable
sub Collatz{
my( $n ) = @_;
$n += 0; # ensure that it is numeric
die 'invalid value' unless $n > 0;
# fill out @next until we get to a value we've already worked on
until( $n == 1 or defined $next[$n] ){
print $n, "\n";
if( $n % 2 ){ # odd
$next[$n] = 3 * $n + 1;
} else { # even
$next[$n] = $n / 2;
}
$n = $next[$n];
}
print $n, "\n";
# finish running until we get to 1
print $n, "\n" while $n = $next[$n];
}
}
首先,IO始终是缓慢的部分.因此,如果您实际对它们进行基准测试,那么您应该获得相同的速度.
为了测试这些,我打开了一个文件句柄/dev/null($null),并编辑每一个say $n而不是读取say {$null} $n.这是为了减少对IO的依赖.
#! /usr/bin/env perl
use Modern::Perl;
use autodie;
open our $null, '>', '/dev/null';
use Benchmark qw':all';
cmpthese( -10,
{
Recursive => sub{ Collatz_r( 31 ) },
Iterative => sub{ Collatz_i( 31 ) },
Optimized => sub{ Collatz_o( 31 ) },
});
sub Collatz_r{
...
say {$null} $n;
...
}
sub Collatz_i{
...
say {$null} $n;
...
}
sub Collatz_o{
...
say {$null} $n;
...
}
运行10次之后,这是一个有代表性的示例输出:
Rate Recursive Iterative Optimized
Recursive 1715/s -- -27% -46%
Iterative 2336/s 36% -- -27%
Optimized 3187/s 86% 36% --
最后,一个真正的代码高尔夫球场:
perl -nlE'say;say$_=$_%2?3*$_+1:$_/2while$_>1'
共46个字符
如果您不需要打印起始值,则可以删除另外5个字符.
perl -nE'say$_=$_%2?3*$_+1:$_/2while$_>1'
41个字符总共
31个字符用于实际代码部分,但如果没有-n开关,代码将无法工作.所以我把整个例子都包含在我的计数中.
ken*_*ytm 22
~{(}{3*).1&5*)/}/1+`
#
# Usage: echo 21 | ruby golfscript.rb collatz.gs
这相当于
stack<int> s;
s.push(21);
while (s.top() - 1) {
int x = s.top();
int numerator = x*3+1;
int denominator = (numerator&1) * 5 + 1;
s.push(numerator/denominator);
}
s.push(1);
return s;
Car*_*rez 19
我猜这种问题是bc为此发明的:
for(n=read();n>1;){if(n%2)n=n*6+2;n/=2;n}
测试:
bc1 -q collatz.bc
21
64
32
16
8
4
2
1
正确的代码:
for(n=read();n>1;){if(n%2)n=n*3+1else n/=2;print n,"\n"}
bc处理最多INT_MAX数字的数字
编辑:在维基百科的文章中提到这个猜想已经为所有的值被检查高达20X2 58(近似5.76e18).这个程序:
c=0;for(n=2^20000+1;n>1;){if(n%2)n=n*6+2;n/=2;c+=1};n;c
在68秒内测试2 20,000 +1(aprox.3.98e6,020),144,404个周期.
a'r*_*a'r 16
perl -nE 'say$_=$_%2?$_*3+1:$_/2while$_>1'
# 123456789 123456789 123456789 1234567
编辑删除2个不必要的空格.
编辑删除1个不必要的空间.
Lan*_*ney 15
MS Excel,35个字符
=IF(A1/2=ROUND(A1/2,0),A1/2,A1*3+1)
直接来自维基百科:
In cell A1, place the starting number.
In cell A2 enter this formula =IF(A1/2=ROUND(A1/2,0),A1/2,A1*3+1)
Drag and copy the formula down until 4, 2, 1
它只需要复制/粘贴公式111次以获得起始编号为1000的结果.;)
ken*_*ytm 14
main(x){for(scanf("%d",&x);x>=printf("%d,",x);x=x&1?3*x+1:x/2);}
#include <stdlib.h>
#define B (w>=m?d=realloc(d,m=m+m):0)
#define S(a,b)t=a,a=b,b=t
main(m,w,i,t){char*d=malloc(m=9);for(w=0;(i=getchar()+2)/10==5;)
B,d[w++]=i%10;for(i=0;i<w/2;i++)S(d[i],d[w-i-1]);for(;;w++){
while(w&&!d[w-1])w--;for(i=w+1;i--;)putchar(i?d[i-1]+48:10);if(
w==1&&*d==1)break;if(*d&1){for(i=w;i--;)d[i]*=3;*d+=1;}else{
for(i=w;i-->1;)d[i-1]+=d[i]%2*10,d[i]/=2;*d/=2;}B,d[w]=0;for(i=0
;i<w;i++)d[i+1]+=d[i]/10,d[i]%=10;}}
注意:不要#include <stdlib.h>在没有至少原型化malloc/realloc的情况下删除,因为这样做在64位平台上是不安全的(64位void*将转换为32位int).
这个尚未经过大力测试.它也可以使用一些缩短.
之前的版本:
main(x){for(scanf("%d",&x);printf("%d,",x),x-1;x=x&1?3*x+1:x/2);} // 66
(删除了12个字符,因为没有人遵循输出格式...:|)
Ski*_*izz 12
另一个汇编版本.这个不限于32位数字,它可以处理多达10 65534的数字,尽管MS-DOS使用的".com"格式限制为80位数字.为A86汇编程序编写,需要运行Win-XP DOS框.汇编为180字节:
mov ax,cs
mov si,82h
add ah,10h
mov es,ax
mov bh,0
mov bl,byte ptr [80h]
cmp bl,1
jbe ret
dec bl
mov cx,bx
dec bl
xor di,di
p1:lodsb
sub al,'0'
cmp al,10
jae ret
stosb
loop p1
xor bp,bp
push es
pop ds
p2:cmp byte ptr ds:[bp],0
jne p3
inc bp
jmp p2
ret
p3:lea si,[bp-1]
cld
p4:inc si
mov dl,[si]
add dl,'0'
mov ah,2
int 21h
cmp si,bx
jne p4
cmp bx,bp
jne p5
cmp byte ptr [bx],1
je ret
p5:mov dl,'-'
mov ah,2
int 21h
mov dl,'>'
int 21h
test byte ptr [bx],1
jz p10
;odd
mov si,bx
mov di,si
mov dx,3
dec bp
std
p6:lodsb
mul dl
add al,dh
aam
mov dh,ah
stosb
cmp si,bp
jnz p6
or dh,dh
jz p7
mov al,dh
stosb
dec bp
p7:mov si,bx
mov di,si
p8:lodsb
inc al
xor ah,ah
aaa
stosb
or ah,ah
jz p9
cmp si,bp
jne p8
mov al,1
stosb
jmp p2
p9:inc bp
jmp p2
p10:mov si,bp
mov di,bp
xor ax,ax
p11:lodsb
test ah,1
jz p12
add al,10
p12:mov ah,al
shr al,1
cmp di,bx
stosb
jne p11
jmp p2
Car*_*rez 10
dc 是这个序列的好工具:
?[d5*2+d2%*+2/pd1<L]dsLx
dc -f collatz.dc 21 64 32 16 8 4 2 1
另外24个字符使用Golfscript条目中的公式:
?[3*1+d2%5*1+/pd1<L]dsLx
符合规格的57个字符:
[Number: ]n?[Results: ]ndn[d5*2+d2%*+2/[ -> ]ndnd1<L]dsLx
dc -f collatz-spec.dc Number: 3 Results: 3 -> 10 -> 5 -> 16 -> 8 -> 4 -> 2 -> 1
方案:72
(define(c n)(if(= n 1)`(1)(cons n(if(odd? n)(c(+(* n 3)1))(c(/ n 2))))))
这使用递归,但调用是尾递归的,所以我认为它们将被优化为迭代.在一些快速测试中,我无法找到堆栈溢出的数字.仅举例如:
(c 9876543219999999999000011234567898888777766665555444433332222 7777777777777777777777777777777798797657657651234143375987342987 5398709812374982529830983743297432985230985739287023987532098579 058095873098753098370938753987)
......运行得很好.[这是所有一个数字 - 我刚刚打破它以适应屏幕.]
c=NestWhileList[If[OddQ@#,3#+1,#/2]&,#,#>1&]&
基本上直接扯掉了makapuf的Python解决方案:
def c(n)while n>1;n=n.odd?? n*3+1: n/2;p n end end
基本上是直接翻录问题中提供的代码:
def c(n)p n;n.odd?? c(3*n+1):c(n/2)if n>1 end
import java.math.BigInteger;
public class SortaJava {
static final BigInteger THREE = new BigInteger("3");
static final BigInteger TWO = new BigInteger("2");
interface BiFunc<R, A, B> {
R call(A a, B b);
}
interface Cons<A, B> {
<R> R apply(BiFunc<R, A, B> func);
}
static class Collatz implements Cons<BigInteger, Collatz> {
BigInteger value;
public Collatz(BigInteger value) { this.value = value; }
public <R> R apply(BiFunc<R, BigInteger, Collatz> func) {
if(BigInteger.ONE.equals(value))
return func.call(value, null);
if(value.testBit(0))
return func.call(value, new Collatz((value.multiply(THREE)).add(BigInteger.ONE)));
return func.call(value, new Collatz(value.divide(TWO)));
}
}
static class PrintAReturnB<A, B> implements BiFunc<B, A, B> {
boolean first = true;
public B call(A a, B b) {
if(first)
first = false;
else
System.out.print(" -> ");
System.out.print(a);
return b;
}
}
public static void main(String[] args) {
BiFunc<Collatz, BigInteger, Collatz> printer = new PrintAReturnB<BigInteger, Collatz>();
Collatz collatz = new Collatz(new BigInteger(args[0]));
while(collatz != null)
collatz = collatz.apply(printer);
}
}
Python 45 Char
刮掉了makapuf的回答.
n=input()
while~-n:n=(n/2,n*3+1)[n%2];print n
小智 5
不是最短的,而是一种新颖的方法.某些大型序列会大幅减速,但不应该溢出.
PROGRAM:COLLATZ
:ClrHome
:Input X
:Lbl 1
:While X?1
:If X/2=int(X/2)
:Then
:Disp X/2?X
:Else
:Disp X*3+1?X
:End
:Goto 1
:End