找到将计数器提前到一定数目的最短方法
我有个柜台。这是一个看起来像这样的小型设备：
显示从0000到9999。它的顶部有一个小按钮，使计数增加1，右边有一个小旋钮，其目的是将计数器重新设置为0。
现在，关于这个小旋钮的问题是，如果你把它向后转，你可以让它增加你想要的任何数字，一旦你再次把它向前转动。因此，如果我按下计数器按钮10次，使计数器显示0010，那么我就可以将旋钮向后转动，直到听到一个小小的点击，然后再将它向前转，然后直接转到0090。
但是，每次将数字向前推时，旋钮都会将所有相同数字的出现次数增加1。因此，如果计数器显示6060，则只能将其增加到7070，而不是6070或7060。此外，旋钮将把9s翻到0而不携带，因此0990将前进到0000，而不是1000或1100。
我想知道最有效的方法，把柜台设置为一定的数字。您的任务是编写一个程序或函数，以确定按钮按下和旋钮前进的最短顺序。
您的程序将以从0000到9999的4位数字作为输入，并以下列格式返回一系列步骤：
> 0001
C
> 0093
C12345678C12345678CCC
> 1000
C12345678C12345678C12345678C12345678C12345678C12345678C12345678C
> 9999
012345678其中，C代表“按下计数器按钮”，而任何数字D从0到9表示“使用旋钮将D的所有出现次数提前1”。
您的程序必须为所有可能的四位数组合生成有效的步骤序列，并且将按所有10,000种情况所需的步骤总数来评分。在平分的情况下(最有可能是在找到最优算法时)，较短的代码将获胜。
回答 4
Code Golf用户
发布于 2016-04-02 10:54:02
Lua，327763步(最优，276个字节)
金色版本：
a={[0]=""}t=tonumber for i=0,52 do A={}for k,v in pairs(a)do A[k]=v L=("%04d"):format(k)for i=1,4 do c=L:sub(i,i)d=L:gsub(c,(t(c)+1)%10)e=a[t(d)]A[d]=(not e or #e>#v)and v..c or e end b=k+1 if k<9999then e=a[b]A[b]=(not e or #e>#v)and v.."C"or e end end a=A endprint(a[(...)])有关示例的改进版本(只改进了1000 )：
0001:C
0093:CCCCCCCCCC12345678CCC
1000:0CCCCCCCCCCC2345678C23456789
(0000>1111>1122>1199>1200>1000)
9999:012345678非高尔夫版本：
a = {[0]=""}
for i=0,52 do
A = {}
for k,v in pairs(a) do
A[k] = v
L=("%04d"):format(k)
for i=1,4 do
c=L:sub(i,i)
d=L:gsub(c,(tonumber(c)+1)%10)
e=a[tonumber(d)]
A[d] = (not e or #e > #v) and v..c or e
end
b=k+1
if k < 9999 then
e=a[b]
A[b] = (not e or #e > #v) and v.."C" or e
end
end
a=A
end
print(a[93],a[1000],a[9999])Code Golf用户
发布于 2016-04-02 13:52:52
Mathematica，得分512710
Unprotect[StringRepeat]
StringRepeat[x_String, 0]:=""
Protect[StringRepeat]
#<>StringRepeat["C",#3-#2*1111]&[Array[ToString@#&,#,0],##]&[If[#<10^3,0,Quotient[#,1111]],#]&用StringRepeat修复一个错误(StringRepeat[x_String,0]的行为不正确)
Code Golf用户
发布于 2016-04-02 14:26:48
Pyth，327763步(最优，130个字节)
由于在线编译器无法处理如此庞大的任务，所以我给它的工作量较少，因此它只生成0、1和1111。但是，它可以从理论上解决这个问题，因为它使用了与上面的Lua算法相同的算法。
=Y.d((0k;V53=ZYFGY XZG=k@YG=N%"%04d"GV4=b@NH=di:Nb%"%d"ehibTT XZd.x?>l@Ydlk+kb@Yd+kb)=bhGI<G9999 XZb.x?>l@Yblk+k\C@Yb+k\C))=YZ;@YQ它的工作原理：
=Y.d((0k;V53=ZYFGY XZG=k@YG=N%"%04d"GV4=b@NH=di:Nb%"%d"ehibTT XZd.x?>l@Ydlk+kb@Yd+kb)=bhGI<G9999 XZb.x?>l@Yblk+k\C@Yb+k\C))=YZ)@YQ
assign_copy('Q',eval_input())
=Y.d((0k; assign_copy('Y',dict(0=k))
V53 for N in range(0,53):
=ZY assign_copy('Z',Y)
FGY for G in num_to_range(Y):
XZG=k@YG no_print(Z[G] = assign_copy('k',lookup(Y,G)))
=N%"%04d"G assign_copy('N',format("%04d",G))
V4 for H in range(0,4):
=b@NH assign_copy('b',lookup(N,H))
=di:Nb%"%d"ehibTT assign_copy('d',base(replace(N,b,format("%d",mod10(increment(base(b,10))))),10))
XZd.x?>l@Ydlk+kb@Yd+kb no_print(Z[d]=try_and_catch(greater_than(Plen(lookup(Y,d)),Plen(k)) ? concat(k,b) : lookup(Y,d)), lambda:plus(k,b))
) <anti-indent>
=bhG assign_copy('b',head(G))
I<G9999 if less_than(G,9999):
XZb.x?>l@Yblk+k\C@Yb+k\C no_print(Z[b]=try_and_catch(greater_than(Plen(lookup(Y,b)),Plen(k)) ? concat(k,"C") : lookup(Y,b)), lambda:plus(k,"C"))
) <anti-indent>
) <anti-indent>
=YZ assign('Y',Z)
) <anti-indent>
@YQ print(lookup(Y,Q))https://codegolf.stackexchange.com/questions/76866
复制相似问题
腾讯云开发者
