本次挑战基于。
编写最短的程序或函数,当给定一些自然数时nnn,输出年代(名词)年代(n)S(n),这是生成至少包含 nnn原始字符串的副本,仅使用全选、复制和粘贴操作。
在数学答案中,年代(名词)年代(n)S(n)满足公式
S(n) = \min_{i=1, \ldots, 8} 5 \lceil \log_4(n/u_i) \rceil+c_i
在哪里(C我,你我)(C我,你我)(c_i, u_i)是来自元组集合的元组我= { (0,1 ),(3,2 ),(7,6 ),(4,3 ),(8,9 ),(12,27 ),(16,81 ),(6,5 )}我={(0,1),(3,2),(7,6),(4,3),(8,9),(12,二十七),(16,81),(6,5)} I = \{ (0,1), (3,2), (7,6), (4,3), (8,9), (12,27), (16,81), (6,5) \}。
测试用例
1 => 0
2 => 3
4 => 5
8 => 8
16 => 10
32 => 13
64 => 15
128 => 18
256 => 20
512 => 23
1024 => 25
2048 => 28
4096 => 30
8192 => 33
16384 => 35
32768 => 38
65536 => 40
131072 => 43
262144 => 45
524288 => 48
1048576 => 50
2097152 => 53
100000 => 42
\endgroup
14
10 个回答
10
3,48 字节
f=lambda n:n>1and-~min(i+f(n/i)for i in b"")
50 字节
f=lambda n:n>1and min(i+1+f(n/i)for i in[2,3,4,5])
不必考虑公式。相反,它实现了,其中每个步骤都会为该数量的操作加上一个创建 2、3、4 或 5 个字符串副本。
输出与 4 的幂的公式得出的测试用例不匹配,但正如 Bubbler 指出的那样,这是由于数学 SE 帖子中的公式拼写错误造成的。
\endgroup
3
-
\begingroup
您可以使用 在第二个中保存一个字节i-~f
。
\endgroup
– -
\begingroup
@Shaggy 我将其包含在内只是为了作为 48 字节的更易读的版本。
\endgroup
– -
\begingroup
啊,好的。48b" "
字节中的内容是做什么的?我不明白。
\endgroup
–
|
Google 表格,68 字节
=SORTN(5*CEILING(LOG(A1/{1;2;6;3;9;27;81;5},4))+{1;3;7;4;8;12;16;6})
\endgroup
|
JavaScript(ES6),98 字节
基本上是挑战中给出的(固定)公式的直接实现。
with(Math)f=n=>min(...[81,27,9,6,5,3,2,1].map((v,i)=>ceil(log(n/v)/log(4))*5-~(37115838>>i*4&15)))
\endgroup
|
,15
xnor 的 50 字节 Python 解决方案的端口。
f ©5ò2ÈÒßU/XÃrm
\endgroup
|
,41字节
f(1)=0.
f(N)=[f(N/>I)+I+1:I in 2..5].min.
相同的方法:递归遍历情况以ctrl+A C V{1,4}
获得至少 N 个字符作为结果。
在标题部分的帮助下table
,它几乎立即计算了所有测试用例。由于/>
执行 ceil-ed 整数除法的运算符,所有中间参数都是整数,没有任何复杂性,我们可以简单地将 1 作为基本情况进行模式匹配。
Picat 中存在按位非运算符~
,但它不喜欢将两个符号-~
并排放置,因此通常的-~
技巧不会节省任何字节。
\endgroup
|
,23
"D1›Di4L+DŠ/®δ.V+>ß"©.V
的移植,因此请务必也为该答案点赞。
仍然很长,因为 05AB1E 对于递归函数来说非常冗长。
或(在输出所有测试用例之前它会超时)。
使用给定的公式将改为32 个:
•¬òÃ,v₅aw°Üÿ∊•82в2ôε`Š/4.nî5*+}ß
或。
解释:
使用递归方法:
f(n) = \begin{cases}
0, & \text{if $n\leq1$} \\
\min(f(\frac{n}{2})+3, f(\frac{n}{3})+4, f(\frac{n}{4})+5, f(\frac{n}{5})+6), & \text{if $n>1$}
\end{cases}
"..." # Define the recursive string explained below
© # Store it in variable `®` (without popping)
.V # Pop and evaluate it as 05AB1E code
# (after which the result is output implicitly)
D # Duplicate the current value n
# (which will use the implicit input in the first iteration)
1› # Pop and check whether it's larger than 1
D # Duplicate this check
i # Pop the copy, and if it's truthy:
4L # Push list [1,2,3,4]
+ # Add the truthy check that's still on the stack: [2,3,4,5]
D # Duplicate this list
Š # Tripleswap to [2,3,4,5],n,[2,3,4,5]
/ # Divide [n/2,n/3,n/4,n/5]
δ # Map over each value:
® .V # And do a recursive eval to `®`
+ # Then add the values in the two lists together:
# [2+f(n/2),3+f(n/3),4+f(n/4),5+f(n/5)]
> # Increase each by 1
# [3+f(n/2),4+f(n/3),5+f(n/4),6+f(n/5)]
ß # Pop and leave the minimum
# (implicit else: use the duplicated falsey check, aka 0)
•¬òÃ,v₅aw°Üÿ∊• # Push compressed integer 50972899172091152076282460330
82в # Convert it to base-82 as list:
# [1,0,2,3,3,4,5,6,6,7,9,8,27,12,81,16]
2ô # Split it into pairs:
# [[1,0],[2,3],[3,4],[5,6],[6,7],[9,8],[27,12],[81,16]]
ε # Map over each pair [u,c]:
` # Pop and push both values to the stack
Š # Triple-swap u,c to c,i,u, where i is the implicit input
/ # Divide the input by u
4.n # Take log_4 of it
î # Ceil it
5* # Multiply by 5
+ # Add c
}ß # After the map: pop and leave the minimum
# (which is output implicitly as result)
以了解为什么•¬òÃ,v₅aw°Üÿ∊•
是50972899172091152076282460330
和•¬òÃ,v₅aw°Üÿ∊•82в
是[1,0,2,3,3,4,5,6,6,7,9,8,27,12,81,16]
。
\endgroup
|
,49 45字节
f:$->n->(n>1)?[2..5|map=>[+1+f//n<=&]|min]->0
xnor 的 50 字节的端口。
,71字节
$->n->min map[0 1 3 2 7 6 4 3 8 9 12 27 16 81 6 5]=>[&+5*ceil log//n&4]
OP中的公式。
\endgroup
|
,24字节
FN⊞υ∨¬ι⁺³⌊E⁴⁺κ§υ÷ι⁺²κI⊟υ
链接为代码的详细版本。说明:基于 @xnor 的方法,但使用动态规划而不是递归。
FN
1
计算到 的所有结果n
。请注意,循环变量1
小于正在计算的结果的索引,但这实际上节省了字节,因为⌈i/k-1⌉=(i-1)//k
这只是整数除法。
⊞υ∨¬ι⁺³⌊E⁴⁺κ§υ÷ι⁺²κ
的结果1
刚刚好1
,而其他迭代的结果是之前四次计算结果中最好的。
I⊟υ
输出的结果n
。
\endgroup
|
,51 字节
f=(n,i=6)=>n>1&&Math.min(i+f(n/--i),i>2?f(n,i):1/0)
\endgroup
|
,26 个半字节(13 个字节)
`; 1 -@$ 0 `/ . +~,4 + _ * @$ +$~ [
另一种递归方法“在每个步骤尝试 1、2、3 或 4 次粘贴”。
Nibbles 仅具有整数算术,因此我们不能(轻松地)在每个递归步骤中倒数并除以目标(如在中使用)。
但是,Nibbles 确实将程序输入作为所有递归调用中的全局变量记住,因此我们可以简单地计算迄今为止的字符串副本(从 1 开始)并在到达程序输入时停止,无论如何,这对我来说更直观。
`; 1 -@$ 0 `/ . +~,4 + _ * @$ +$~ [ # full program; input is stored in variable @
`; 1 # launch recursive function starting with copies=1
# (stored in variable $)
-@$ # stop when input <= copies-so-far
0 # and return zero
# otherwise return
`/ [ # minimum of
. # map over
+~,4 # i in 2..5
+ # sum of
_ # recursive call using
* @$ # copies-so-far * i
+$~ # and i+1 (steps needed to multiply copies by i)
\endgroup
|
我认为当您全选、复制然后粘贴时,粘贴不会覆盖选择内容而是附加到它?
\endgroup
–
“包含原始字符串的 n 个副本”是指至少 n 个,还是正好 n 个?
\endgroup
–
我不明白为什么F(4 )= 6F(4)=6f(4)=6。难道你不能通过全选、复制、粘贴、粘贴、粘贴这 5 个操作将数量翻四倍吗?由于粘贴操作如你所说是附加的,因此这里只需要 3 个。
\endgroup
–
我浏览了 math.se 帖子,我认为公式中有一个拼写错误:(1,1) 应该是 (0,1)。此更改会影响所有采用 4^k 形式的测试输入。也在 math.se 帖子上添加了一条关于此问题的评论。
\endgroup
–
固定公式与最多 1e6 的算法解决方案
\endgroup
–
|