Code Golf - Output Fit Numbers

发表于   |   分类于

爱下棋的朋友应该对“排局”这个词并不陌生，与“排局”一样，编程领域也有跟这个类似的好玩的东西：有一种故意出一种看起来不切合实际的问题，要求使用尽量短的代码来实现对应的功能。这个叫做“Code Golf”的黑科技却吸引着众多的程序员参与其中，今天我们就来看看其中的一个例子。

本文根据Stack Exchange上的code golf - Output “Fit” numbers翻译/整理而成。

题目

现有这个一个需求，编程实现OEIS数列A090078。

这里简单介绍一下数列A090078，从基数开始，将序号转为二进制，再将二进制中的连在一起的0进行合并，得到的新的二进制再转换为十进制，便就是该数列的值。

示例：

1
2
3
4
5
6
7
8
1 -> 1 -> 1 -> 1
9 -> 1001 -> 101 -> 5
15 ->1111 -> 1111 -> 15
13 ->1101 -> 1101 -> 13
16 -> 10000 -> 10 -> 2
17 -> 10001 -> 101 -> 5
65535 -> 1111111111111111 -> 1111111111111111 -> 65535
65000 -> 1111110111101000 -> 11111101111010 -> 16250

我们姑且把这种转换称之为fit，得到的数值叫做fit number。那么上面提到的需求就可以描述为：

给定一个值，求该值的fit number。

下面就来看看各路大牛各显神通吧！

代码实现

Bash + GNU utilities

1
dc -e2o?p|tr -s 0|dc -e2i?p

仅27字节。

05AB1E

1
b00¬:C

这简直黑科技中的黑科技，仅仅8个字节就实现了。在线测试。

05AB1E这门编程语言，本身也是娱乐品，有兴趣的可以点击访问其项目主页。

Jellyfish

1
2
3
4
5
6
7
p
d
# S
,1
*
\dbi
 2

仅20个字节。又是一款黑魔法，Jellyfish是一款来自于J语言的用Python 3编写的编程语言。

JavaScript

1
n=>+`0b${n.toString(2).replace(/0+/g,0)}`
1
n=>'0b'+n.toString(2).replace(/0+/g,0)-0

这是ES6的语法，走了个捷径，不能算作是正确答案，因为没有输出语句，看不到结果，不过这里也贴出来。

Bash (sed + bc)

1
echo $[2#`bc<<<obase=2\;$1|sed s/00\*/0/g`]

MATL

传说中的MATLAB，看看：

1
BFFOZtXB

仅仅只有8个字节

难以置信吧？看看其解读：

1
2
3
4
5
6
7
    % Implicitly grab input
B   % Convert decimal to binary
FF  % Create the array [0 0]
O   % Number literal
Zt  % Replaces all [0 0] with [0] (will replace any number of 0's with 0)
XB  % Convert binary to decimal
    % Implicitly display

可能你不信，那么请访问在线测试页面。

BoFFOZtXB

o % Convert from logical to double (due to a bug)…有个双精度的BUG

Python 3

1
2
import re
f=lambda x:eval(re.sub('0+','0',bin(x)))

简单直接并粗暴，50字节的Python解决方案奉上。

Perl 6

1
{:2(.base(2)~~{S:g/0+/0/})}

解释：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
-> $_ {
  # convert from base 2
  :2(

    # convert to base 2
    $_.base(2)

    # substitute
    .subst(
      :global,
      / 0+ /,  # all substrings made of 0s
      '0'      # with one 0
    )
  )
}

示例：

1
2
3
4
5
6
7
8
9
10
11
12
13
my &fit-compress = {:2(.base(2)~~{S:g/0+/0/})}
say fit-compress 1;     # 1
say fit-compress 9;     # 5
say fit-compress 15;    # 15
say fit-compress 13;    # 13
say fit-compress 16;    # 2
say fit-compress 17;    # 5
say fit-compress 65535; # 65535
say fit-compress 65000; # 16250

# number created with ｢:2( [~] <0 1>.roll: 256 )｣
say fit-compress 80794946326210692074631955353531749442835289622757526957697718534769445507500
# 4240335298301026395935723255481812004519990428936918

Ruby

1
->n{eval ("0b%b"%n).squeeze ?0}

Ruby的解决方案，31字节实现，在线测试。

Jelly

1
BŒgḄBFḄ

黑科技无疑，代码里面有叫不出名字的字母。在线测试。

这个Jelly是个什么鬼？请参阅其项目主页：DennisMitchell/jelly。

PHP

1
<?=bindec(preg_replace("/0+/",0,decbin($argv[1])));

PHP作为一个有逼格的编程语言，自然不能示弱，51字节实现，虽然跟Javascript一样很尴尬。

C

1
int x(int x)=>Convert.ToInt32(Regex.Replace(Convert.ToString(x,2),"0+","0"),2);

Java

1
int f(Integer x){return x.valueOf(x.toString(x,2).replaceAll("0+","0"),2);}

java不甘寂寞，也来一份，但也只有语法实现，并不能愉快的直接测试。

测试代码：

1
2
3
4
5
6
7
8
public class Fit {
    int f(Integer x){return x.valueOf(x.toString(x,2).replaceAll("0+","0"),2);}

    public static void main(final String... args) {
        final Fit x = new Fit();
        System.out.println(x.f(65000));
    }
}

这里还有一份很短的Java代码：

1
interface C{static void main(String[]b){Integer i=0;System.out.print(i.parseInt(i.toString(i.parseInt(b[0]),2).replaceAll("0+","0"),2));}}

PowerShell v2+

1
[convert]::ToInt32(([convert]::ToString($args[0],2)-replace'0+',0),2)

年长的PowerShell同样的不敢寂寞，然而这测试过程也是有点无奈：

1
2
3
4
5
6
7
8
9
PS C:\Tools\Scripts\golfing> 1,9,15,13,16,17,65535,65000|%{"$_ -> " +(.\output-fit-number.ps1 $_)}
1 -> 1
9 -> 5
15 -> 15
13 -> 13
16 -> 2
17 -> 5
65535 -> 65535
65000 -> 16250

Pyth

1
i:.BQ"0+"\02

这什么语言瞅着眼熟的很，然而这并不是Python，该语言的项目主页：Pyth。

代码解释：

1
2
3
  .BQ            # Convert input from base 10 to base 2
 :   "0+"\0      # Replace multiple zeroes with single zero
i          2     # Convert back from base 2 to base 10

在线测试。

Retina

1
2
3
4
5
6
7
8
.+
$*1;
+`(1+)\1
$1;
1;
1
;+
0

讲真，我已经目瞪口呆。Retina似乎又是一款自编编程语言。在线测试。

Dyalog APL

Dyalog APL来露个脸，19字节：

1
{2⊥⍵/⍨~0 0⍷⍵}2∘⊥⍣¯1

明显黑科技

CJam

1
q~2b1+0a%0a*);2b

CJam，在线测试。

代码解释：

1
2
3
4
5
6
7
q~     read and evaluate the input number
2b     convert to base 2 (array of 1s and 0s)
1+     append a 1 to deal with trailing zeros
0a%    split by [0], dropping empty pieces; only chunks of 1s are left
0a*    join by [0]
);     discard the 1 we appended before
2b     convert back from base 2

后记

抄了这么多的编程语言的实现之后，颇有一种井底之蛙的感觉。还有很多编程语言也可以很简洁的实现该需求，这里就不再继续贴出了，有兴趣的可自行访问该页面的源地址。

全文完~