Гольф кода: догадка Collatz
69 ответов
Python:
def collatz(n):
if (n%2) == 0:
return n/2
else:
return 3*n+1
def do_collatz(n):
while n > 1:
print n
n = collatz(n)
print n
do_collatz(int(input("Start number: ")))
Не уязвима к переполнению стека, но не завершается на последовательности, не сходящейся к 1. (правка: забыл часть про ввод)
MATLAB 7.8.0 (R2009a): 58 символов
n=input('');while n>1,n=n/2+rem(n,2)*(n*5+2)/2;disp(n);end
Тестовый пример:
>> n=input('');while n>1,n=n/2+rem(n,2)*(n*5+2)/2;disp(n);end
21
64
32
16
8
4
2
1
VBScript: 105 символов
По-видимому, я обжора наказания.
c(InputBox("?"))
Public Sub c(i)
msgbox(i)
If i>1 Then
If i mod 2=0 Then
c(i/2)
Else
c(3*i+1)
End If
End If
End Sub C #, кажется, 88 символов. Рекурсивный
void T(int i,string s){Console.Write("{0}{1}",s,i);if(i!=1)T(i%2==0?i/2:(i*3)+ 1,"->");}
Плюс этот начальный вызов
T(171, "");
Вот нерекурсивный метод, 107 символов, я думаю
void T2(int i){string s="";while(i>=1){Console.Write("{0}{1}",s,i);i=i==1?-1:i=i%2==0?i/2:(i*3)+1;s="->";}}
На основе кода ar, вот версия perl, которая фактически соответствует требованиям вывода
perl -E 'print"Number: ";$_=<STDIN>;chomp;print"Results: $_";$_=$_%2?$_*3+1:$_/2,print" -> ",$_ while$_!=1;say""'
Длина: 114 с учетом вызовов perl и кавычек, 104 без
] Я уверен, что какой-нибудь опытный гольфист сможет еще больше уменьшить эту грубую версию.
VB.Net, около 180 символов
Sub Main()
Dim q = New Queue(Of Integer)
q.Enqueue(CInt(Console.ReadLine))
Do
q.Enqueue(CInt(If(q.Peek Mod 2 = 0, q.Dequeue / 2, q.Dequeue * 3 + 1)))
Console.WriteLine(q.Peek)
Loop Until q.Peek = 1
End Sub
забавная вещь - преобразование этого кода в c# создает еще больше символов
чтобы заставить его работать в пустом .vb файле (около 245 символов)
Imports System.Collections.Generic
Imports System
Module m
Sub Main()
Dim q = New Queue(Of Integer)
q.Enqueue(CInt(Console.ReadLine))
Do
q.Enqueue(CInt(If(q.Peek Mod 2 = 0, q.Dequeue / 2, q.Dequeue * 3 + 1)))
Console.WriteLine(q.Peek)
Loop Until q.Peek = 1
End Sub
End Module
PHP
function Collatz($n)
{
$i = 0;
while($n>1)
{
if($n % 2)
{
$n = (3*$n) + 1;
$i++;
echo "step $i: $n <br/>";
}
else
{
$n = $n/2;
$i++;
echo "step $i: $n <br/>";
}
}
}
Bash, 130, включая пробелы и символы новой строки:
#!/bin/bash
if [ $1 == 1 ]; then echo $1
else if [ $(($1%2)) == 0 ]; then n=$(($1/2))
else n=$(($1*3+1))
fi
echo "$1 -> `c $n`"
fi
Предполагается, что c - это имя файла сценария, и оно находится на пути пользователя, запустившего сценарий.
PHP, 78 72 67 символов
На самом деле я написал эту программу около двух лет назад, после того как прочитал о последовательности в книге Pickover. Я немного почистил его, и это наименьшее количество, которое я могу сделать, при этом пользовательский ввод и приятный, читаемый вывод все еще сохраняются:
<?$n=fgets(STDIN);while($n!=1){$n=(($n&1)==0)?($n/2):(($n*3)+1);echo"$n\n";}?>
Можно предположить, что короткие теги включены, и я не уверен, что ввод будет работают на всех консолях. Но он отлично работает на моей машине с Windows.
Обновление: Немного обманув математику, мы можем избавиться от некоторых символов:
<?$n=fgets(STDIN);while($n!=1){$n=(($n&1)==0)?$n/2:$n*3+1;echo"$n\n";}?>
Обновление:
- Учитывая, что
$ n & 1возвращает либо1] или0, мы можем воспользоваться слабой типизацией PHP и удалить еще пару символов. - Кроме того, включив комментарий Кристиана ниже (с небольшими изменениями для предотвращения бесконечного зацикливания), мы можем удалить еще один.
- Наконец, поскольку скриптам PHP не нужен завершающий
?>, мы можем избавиться еще от двух символов:
Конечный результат:
<?$n=fgets(STDIN);while($n>1){$n=(!($n&1))?$n/2:$n*3+1;echo"$n\n";}
Powershell : 80 символов
Однострочник:
"Results: $(for($x=read-host Number;1%$x;$x=@($x/2;3*$x+1)[$x%2]){""$x ->""}) 1"
Pretty-printed:
"Results: $( for( $x = read-host Number; 1%$x; $x = @( $x/2; 3*$x+1 )[ $x%2 ] )
{
""$x ->""
}
) 1"
Без подсказки ввода и форматирования вывода - 44 символа:
for($x=read-host;1%$x;$x=@($x/2;3*$x+1)[$x%2]){$x}1
bash 57/61/60
Еще одна запись в bash. Не выполняет математику бесконечной точности и может переполняться.
#!/bin/bash
x=$1;echo $x;((x>1))&&$0 $((x%2?x*3+1:x/2))
Версия, которая не должна переполняться, может быть
#!/bin/bash
x=$1;echo $x;((x>1))&&exec $0 $((x%2?x*3+1:x/2))
(edit) Итеративная версия:
#!/bin/bash
for((x=$1;x>1;x=x%2?x*3+1:x/2));do echo $x;done
PHP. 69 Персонажи
Спасибо Данко Дурбичу за fgets (STDIN), надеюсь, вы не против :)
<?$i=fgets(STDIN);while($i!=1){echo ($i=$i%2?$i*3+1:$i/=2),"\r\n";}?>
Microsoft Small Basic
TextWindow.Write( "Number: " )
n = TextWindow.ReadNumber()
TextWindow.Write( "Results: " )
While ( n > 1 )
TextWindow.Write( n + " -> " )
If Math.Remainder( n, 2 ) = 0 Then
n = n / 2
Else
n = n * 3 + 1
EndIf
EndWhile
TextWindow.WriteLine(1)
Вы можете запустить его по адресу: http://smallbasic.com/program/?ZZR544
Javascript, 67 56 символов
for(a=[i=prompt()];i-1;a.push(i=i%2?i*3+1:i/2));alert(a)
C ++ 113 100 95
#include <iostream>
int main(int i){for(std::cin>>i;i>1;i=i&1?i*3+1:i/2)std::cout<<i<<" -> ";}
Миранда (101 символ)
c n=" 1",if n=1
=" "++shownum(n)++c(n*3+1),if n mod 2=1
=" "++shownum(n)++c(n div 2),otherwise
(пробелы синтаксически важны)
F # 82 Chars
let rec f n=printfn "%A" n;if n>1I then if n%2I=0I then f(n/2I)else f(3I*n+1I)
Фактор :
без игры в гольф
USE: math
: body ( n -- n ) >integer dup . "->" . dup odd? = [ 3 * 1 + ] [ 2 / ] if ;
: hailstone ( n -- ) dup 1 > [ body hailstone ] [ . ] if ;
21 hailstone
в гольф:
21 [ dup 1 > ] [ >integer dup . "->" . dup 2 mod 1 = [ 3 * 1 + ] [ 2 / ] if ] while .
Результат:
21
"->"
64
"->"
32
"->"
16
"->"
8
"->"
4
"->"
2
"->"
1
JavaScript, 61 70 символ с вводом
Итеративный, точность зависит от ограничений JS
var i=prompt('');while(i>1){console.log(i);i=(i%2)?3*i+1:i/2}
Perl, 59 символов:
sub c{print my$x="@_\n";@_=$x&1?$x*3+1:$x/2,goto&c if$x!=1}
J, 45 символов
(-: * 0 & = @ (2 & |)) + (1 + 3 & *) * -. @ (0 & = @ (2 & |))
Я не эксперт in J. Поскольку функция для среднего значения равна + /% #, я уверен, что это можно сделать короче.
C: 63 символа
main(x){scanf("%d",&x);while(x>printf("%d ",x=x&1?3*x+1:x/2));}
Это основано на ответе KennyTM. Цикл for был заменен на цикл while, а код перенесен внутрь while.
Ruby, 41 символ
n=gets.to_i
p n=[n/2,n*3+1][n%2]while n>1
GW-BASIC - 54 символа
1INPUT N
2N=(N+(N*5+2)*(N MOD 2))/2:?N:IF N>1GOTO 2
Вперед, 130 символов
package main
import(."os"
."strconv")
func main(){n,_:=Atoi(Args[1])
println(n)
for n>1{if n%2!=0{n=n*3+1}else{n/=2}
println(n)}}
Пример
./collatz 3
3
10
5
16
8
4
2
1
Fortran: 71 символ
n=1
1 if(n==1)read*,n
n=merge(n/2,3*n+1,mod(n,2)==0)
print*,n
goto1
end
Потому что кто-то должен был это сделать :)
Счетчик включает обязательные символы новой строки. Полностью соответствующий код Fortran 95 (и более поздние версии). Включает полный ввод / вывод и выполняет столько раз, сколько вы хотите!
Правка: на один символ меньше, используя goto (очки за стиль!)
Фортран - 60 символов
read*,n
1 if(n/2*2<n)n=6*n+2
n=n/2
print*,n
if(n>1)goto1
end
JavaScript - 68 символов
В отличие от других JS (и большинства других языков) этот фактически соответствует -> в выводе.
for(s='',c=' -> ',i=readline();i>1;i=i%2?i*3+1:i/2)s+=i+c
print(s+1)
Если этого избежать, это альтернатива 53 символа , печатающая по одному числу в строке:
for(p=print,i=readline(),p(i);i>1;)p(i=i%2?i*3+1:i/2)
Предназначен для работы с SpiderMonkey:
echo 21 | js thisfile.js
21 -> 64 -> 32 -> 16 -> 8 -> 4 -> 2 -> 1
Windows cmd - 68 символов
@set/pd=
:l
@set/ad=(d+d%%2*(d*5+2))/2&echo %d%&if %d% NEQ 1 goto:l
Поскольку решение LOLCODE, похоже, вызывает некоторый интерес, я решил сравнить реализации двух подходов к решению (итеративного и хвостового рекурсивного) в этом языке.
Во-первых, итеративное решение на 203 символах:
HAI 1.2
I HAS A n
GIMMEH n
IM IN YR l
VISIBLE n
BOTH SAEM 1 BIGGR OF 1 n
O RLY?
YA RLY
GTFO
OIC
MOD OF n 2
WTF?
OMG 0
n R QUOSHUNT OF n 2
GTFO
OMG 1
n R SUM OF 1 PRODUKT OF 3 n
OIC
IM OUTTA YR l
KTHXBYE
Чтобы дать вам суть происходящего:
- Вход считывается из STDIN с помощью ключевого слова
GIMMEH - Цикл выполняется между операторами
IM IN YRиIM OUTTA YR VISIBLEиспользуется для печати в STDOUT- Операторы
O RLY?,YA RLYиOICобрабатывают условную логику If/Then/Else - Операторы
WTF?,OMG <выражение>иOICобрабатывают условную логику Switch/Case - Присваивание выполняется с помощью
<переменная> R <значение> - GTFO прерывает цикл или условный Switch/Case
А затем есть хвостовое рекурсивное решение, которому удается сбрить 2 дополнительных символа для окончательного счета 201:
HAI 1.2
HOW DUZ I c YR n
VISIBLE n
DIFFRINT 1 BIGGR OF 1 n
O RLY?
YA RLY
MOD OF n 2
WTF?
OMG 0
c QUOSHUNT OF n 2
GTFO
OMG 1
c SUM OF 1 PRODUKT OF 3 n
OIC
OIC
IF U SAY SO
I HAS A i
GIMMEH i
c i
KTHXBYE
Разница здесь заключается в определении функции между утверждениями HOW DUZ I и IF U SAY SO. Функции вызываются с помощью