codegolf

最近没啥事情，刷了刷 codegolf 。虽然每题都用了很多的字符，但还是记录一下。(我就只写了python的，其它语言不大会)

Fizz Buzz

题目：

Print the numbers from 1 to 100 inclusive, each on their own line.

If, however, the number is a multiple of three then print Fizz instead, and if the number is a multiple of five then print Buzz.

If multiple conditions hold true then all replacements should be printed, for example 15 should print FizzBuzz.

exp：

for i in range(100):print(i%3//2*"Fizz"+i%5//4*"Buzz"or-~i)

思路：

要求很简单，3的倍数为Fizz，4的倍数为Buzz，如果既是3的倍数又是4的倍数就输出FizzBuzz。

首先要短的话肯定要一个range只能就解决掉，它要的是1~100的情况。但是如果直接range(100)的话会是0~99，比要求的少了1。

但是其实这个没有啥影响，无非就是变成了2的倍数和4的倍数罢了。我们计算 $i\%3$ 和 $i\%5$ 的值，如果它们分别为2或者4的倍数的话，那就是模数减一，那我们再整除模数减一就好了。这样子做的话就只要用两个运算符就解决这个问题了，然后对于其它的情况我们正常来说是要输出 i+1 的。但是如果接在 or 后面的话要加个空格。那么我们可以考虑一个奇技淫巧，我们输出 -~1 这样子就不用加空格了 XD

(但是为啥还可以少一个字符，根本想不出来，希望有人可以教教/(ㄒoㄒ)/~~)

Foo Fizz Buzz Bar

题目：

Print the numbers from 1 to 1,000 inclusive, each on their own line.

If, however, the number is a multiple of two then print Foo instead, if the number is a multiple of three then print Fizz, if the number is a multiple of five then print Buzz, and if the number is a multiple of seven then print Bar.

If multiple conditions hold true then all replacements should be printed, for example 15 should print FizzBuzz.

exp：

for i in range(1000):print(i%2*"Foo"+i%3//2*"Fizz"+i%5//4*"Buzz"+i%7//6*"Bar"or-~i)

思路：

和 Fizz Buzz 完全一样，但是明明完全一样，我这个 exp 却是最短的，好神奇。

Quine

题目：

A quine is a non-empty computer program which takes no input and produces a copy of its own source code as its only output. Produce such a program.

Trailing whitespace is NOT stripped from the output for this hole. (Consequently, if your submission doesn't pass, try adding a line break at the end.)

exp：

_='_=%r;print(_%%_)';print(_%_)

思路：

其实直接参考 https://stackoverflow.com/questions/6223285/shortest-python-quine 就好了。

不过很显然这个仍然不是最短的，因为相比第一它还是多了一个byte，但是我目前还没有找到方法。

Fibonacci

题目：

The Fibonacci numbers are a numerical sequence in which each number is the sum of the two preceding numbers: 0, 1, 1, 2, 3, 5, 8, 13…

Print the first 31 Fibonacci numbers from F0 = 0 to F30 = 832040 (inclusive), each on a separate line.

exp：

a,b=0,1
while a<9e5:print(a);a,b=b,a+b

思路：

我觉得这个也没啥可以优化的，小细节可能就是可以用 9e5 这种科学记数法来替代 832040。然后再使用 a,b=b,a+b 来替代传统的交换字符的方式。不过这个仍然比最短的 exp 多了2bytes。

Prime Numbers (Long)

Prime Numbers 和 Prime Numbers (Long) 我用了同样的方式，不过 Prime Numbers 要的值很小应该可以优化好多地方，这个等以后再说了。

题目：

Print all the prime numbers from 1 to 10,000 (不是 Long 的话是 100) inclusive, each on their own line.

exp：

k=P=1
while k<1e4:P%k>0==print(k);P*=k*k;k+=1

思路：

首先我们写一个10000以内质数生成的代码

k = 1
P = 1
while k < 10000:
    if P % k > 0:
        print(k)
    P *= k * k
    k += 1

这个算法利用了如果 k 为质数，那么它不会被任何小于其的质数整除的性质。所以我们让 P 为所有小于 k 的质数的平方的乘积，通过判断 P%k 是否为 0 来得到质数。

首先我们可以先进行简单的压缩，我们可以改写代码为

k=P=1
while k<1e4:
 if P%k>0:print(k)
 P*=k*k;k+=1

然后我们可以发现，这个判断语句的存在会导致要多加一行，如何可以去掉这个判断语句肯定可以再次缩短代码。这时候我们可以考虑一下短路运算。我们首先要知道一件事情，对于 python 来说，在执行 A and B 的时候，如果 A 为Flase 那么它就不会再计算 B 了。而对于 A or B 的话，如果 A 为 True 的话，它也不会计算 B 了。而在代码中，如果要打印 k 的话，必须要满足 P%k>0 成立，那么如果代码可以改成类似 P%k and print(k) 的话，那么就可以满足 P%k>0 成立后才可以打印 k，但是直接 P%k>0 and print(k) 的话还是会多两个空格，是否有更加好的方式呢？其实我们可以考虑 P%k>0==print(k)

为何这个可以实现短路呢，因为对于 python 来说，python的比较运算符支持链式规则。啥是链式规则呢？举个例子，对于比价判断 a<b<c ，其实它是被解释为 a<b and b<c 来执行。那么对于上面的代码来说，其实就是解释为 P%k>0 and 0==print(k)，故只有满足前面的才会执行后面的代码，其实后面是什么都无所谓了，因为必然要执行 print(k) 来输出 k。

不过这仍然不是最短的，最短的代码比我这个还要再少一个字符。

Collatz

题目：

The Collatz conjecture states that, for any positive integer n, it will eventually reach 1 by repeatedly applying the following procedure:

• If n is even, divide it by 2.
• If n is odd, multiply by 3 and then add 1.

The number of steps needed for n to reach 1 is called its stopping time. For example, the stopping time of 10 is six:

10 → 5 → 16 → 8 → 4 → 2 → 1

Print the stopping times of all the numbers from 1 to 1,000 inclusive, each on their own line.

exp：

for i in range(1,1001):
 t=0
 while~-i:i=[i//2,3*i+1][i&1];t+=1
 print(t)

思路：

首先我们先简单写一个解决题目的代码

for i in range(1,1001):
 t=0
 while i>1:i=3*i+1 if i&1 else i//2;t+=1
 print(t)

其实这个优化思路挺直观的，直接把 while i>1:i=3*i+1 if i&1 else i//2;t+=1 就可以减少一大串了，首先我们关注这个判断语句，i 的值由 i&1 来决定。我们要知道，对于 python 来说，True 其实就是1，False 其实就是0，0和1可以想到什么呢？其实就是列表，为何这么说呢，我们可以考虑一个这样子的判断语句 i=[i//2,3*i+1][i&1]。我们可以发现，当 i&1 为 True 时，i 为 3*i+1，反之就是另一个，这个很显然和之前的实现方式完全一样，但是省去了好多的字符。再后面，我想了好久也没想到哦可以优化啥。最后突然想到，while i>1 其实可以省去一个空格，我们可以改写为 while~-i，这样子在 i 为1的时候就是 while 0 了直接结束了这个循环语句。

当然，这个肯定还可以优化许多，不过那是未来的事情了。

Niven Numbers (Long)

和 Prime Numbers 一样，Niven Numbers 和 Niven Numbers (Long) 我用了同样的思路

题目：

A Niven number is a positive integer that is divisible by the sum of its digits.

Print all the Niven numbers from 1 to 10,000 (or 100) inclusive, each on their own line.

exp：

i=0
while i<1e4:i+=1;i%sum(map(int,str(i)))or print(i)

思路：

其实这个感觉还是挺直观的，基本上把基础的一些压缩方式用到了就可以很短了。

不过最短只要50个bytes，那可能要用到一些很深奥的位运算了。

(其实还有个 idea 就是在 i=0\n while i<1e4:i+=1;i%eval('+'.join(f'{i}'))or print(i) 的基础上压缩，但是似乎还不如我现在这个)

Tutorial

题目：

Output the same output as the sample code would produce. The string "Hello, World!", the integers 0 to 9, and any number of arguments. Everything on an individual line.

exp：

import sys;[*map(print,['Hello, World!',*range(10)]+sys.argv[1:])]

思路：

这个算是入门题目了，就是优化最开始的例子

我们看一下例子里的python代码是什么

import sys

# Printing
print('Hello, World!')

# Looping
for i in range(10):
    print(i)

# Accessing arguments
for arg in sys.argv[1:]:
    print(arg)

那首先肯定要把注释符去掉，该压缩的全部压缩了。就可以拿到

import sys;print('Hello, World!')
for i in range(10):print(i)
for arg in sys.argv[1:]:print(arg)

然后我们可以发现，其实可以把它们都看成列表的话，如果可以合到一起那肯定可以大大减少代码量。这时候就可以改写一下代码，全部丢在一块

import sys;[print(i) for i in ['Hello, World!',*range(10)]+sys.argv[1:]]

但是这样子就要调用循环语句了，那我们可以想到 map 函数，利用起来进行二次压缩就可以得到最终的版本了。

不过这仍然不是最短的(榜上那些都是什么神仙(T_T))，还可以往下压1个字符。