개요
자릿수 목록이 주어지면 100을 만드는 가장 적은 연산을 찾으십시오.
입력
숫자 순서 일 수도 있고 아닐 수도있는 숫자 문자열. 숫자의 순서는 변경할 수 없지만 더하기 (+) 또는 빼기 (-) 연산자를 사이에 더하여 총 합이 100이되도록 할 수 있습니다.
산출
추가 된 연산자 수와 전체 숫자 및 연산자 순서가 뒤 따릅니다. 공백, 탭 또는 줄 바꿈 순서로 두 개를 분리 할 수 있습니다.
예
유효한
입력 : 123456789
출력 :3 123–45–67+89
유효하지 않은
입력 : 123456789
출력 :
6
1+2+34-5+67-8+9
(더 적은 작업으로이를 해결하는 방법이 있습니다)
답변
자바 스크립트 (ES6) 153 176 바이트
편집 : 엄격하지 않은 모드에서 JS는 0 접두사 숫자 표현식을 8 진수 017로 해석합니다 (예 : 10 진수로 15로 구문 분석 됨). 이것은 선행 0을 지원하는 고정 버전입니다.
let f =
s=>[...Array(3**(l=s.length,l-1))].map((_,n)=>m=eval((x=s.replace(/./g,(c,i)=>c+['','+','-'][o=(n/3**i|0)%3,j-=!o,o],j=l)).replace(/\b0+/g,' '))-100|j>m?m:(S=x,j),m=l)&&m+' '+S
console.log(f("123456789"))
console.log(f("20172117"))답변
MATL , 37 36 바이트
n'+-'OhZ^!t2\s&SZ)"G@!vXzU100=?@z3M.
테스트 케이스는 TIO에서 약 6 초가 걸립니다.
작동 원리
n % Implicitly input a string. Number of elements, say k
'+-' % Push this string
Oh % Append char 0. This is treated like ' ' (space)
Z^ % Cartesian power of the three-char string '+- ' raised to k.
% Gives a matrix where each row is a Cartesian k-tuple
! % Transpose
t % Duplicate
2\ % Modulo 2. This turns '+' and '-' into 1, and ' ' into 0
s % Sum of each column: number of '+' and '-' symbols
&S % Sort and push the indices of the sorting
Z) % Apply as column indices. This sorts the columns (k-tuples)
% by the number of '+' and '-' they contain
" % For each column, i.e. each k-tuple formed by '+', '-' and ' '
G % Push input string again
@! % Push k-tuple as row vector (string)
v % Concatenate vertically into a 2×k char array
Xz % Remove space (and char 0). Gives a string as result. In this
% process, the 2×k array is linearized in column major order
% (down, then across). So the '+' and '-' signs are between
% digits of the input, or at the end
U % Convert to number. This performs the operation determined by
% by the '+' and '-' signs and returns the result. A trailing
% '+' or '-' sign makes the input invalid, which causes an
% empty result
100= % Is it equal to 100?
? % If so
@ % Push current k-tuple
z % Number of nonzeros, i.e. of '+' and '-' signs
3M % Push linearized string without spaces again
. % Break for loop
% Implicit end
% Implicit end
% Implicitly dispplay stack
답변
[파이썬 2], 164158 바이트
from itertools import*
f=lambda N:min((len(s)-len(N),s)for s in(''.join(sum(zip(N,p+('',)),()))for p in product(('+','-',''),repeat=len(N)-1))if eval(s)==100)N을 문자열로 취하십시오. 튜플 (numOps, expressionString)을 반환합니다.
기본적으로 다른 것과 같은 접근법; itertools.product를 사용하여 개별 “케이스”를 구성합니다. 예를 들어 N == ‘1322’의 경우 “case”는 ('-','','+')‘1-32 + 2’입니다.
입력이 유효하지 않으면 ValueError를 던집니다 (그러나 OP는 유효하지 않은 입력을 얻지 못했다고 생각합니다).
답변
PHP, 166 171 바이트
for(;$n<3**$e=strlen($x=$argn);eval("return $s;")-100?:$r[]=sprintf("%2d $s",strlen($s)-$e))for($i=0,$s="",$k=$n++;a&$c=$x[$i];$k/=3)$s.="+-"[$i++?$k%3:2].$c;echo min($r);파이프로 실행 -nR하거나 온라인으로 테스트하십시오 .
서식이 지정된 숫자를 사용하여 결과를 정렬합니다.->
선행 공백을 인쇄 할 수 있습니다 (99 자리를 초과하는 입력에는 실패 할 수 있습니다; %2d수정 하려면 숫자를 늘리십시오 ).
10 자리 이하, 161 바이트
for(;$n<3**$e=strlen($x=$argn);eval("return $s;")-100?:$r[]=(strlen($s)-$e)." $s")for($i=0,$s="",$k=$n++;a&$c=$x[$i];$k/=3)$s.="+-"[$i++?$k%3:2].$c;echo min($r);고장
for(;$n<3**$e=strlen($x=$argn); # loop $n up
eval("return $s;")-100?: # 2. evaluate term, if 100 then
# prepend number of operations, add to results
$r[]=sprintf("%2d $s",strlen($s)-$e)
)
# 1. create term
for($i=0,$s="",$k=$n++; # init variables, increment $n
a&$c=$x[$i];$k/=3) # loop through digits/operator index
$s.="+-"[$i++?$k%3:2].$c; # prepend operator for base-3 digit (nothing for 2)
echo min($r); # print lowest result답변
젤리 , 32 바이트
L’⁾+_ṗż@€
ŒṖÇ€ẎµFV=ȷ2µÐfLÞḢFṄḟ³L
Jelly 연산자를 사용하여 표시되는 전체 프로그램입니다 ( _대신 -).
참고 : (필수 아님) -대신 출력에 표시하려면 and 사이를 _추가하십시오 ( 문자 쌍 리터럴 이며 2 진 “번역”아톰).⁾_-yFṄ⁾_-['_','-']y
어떻게?
L’⁾+_ṗż@€ - Link 1, form all sums from a partition: list of lists of characters
e.g. ["12","345","67"]
L - length 3
’ - decremented 2
⁾+_ - literal ['+','_']
ṗ - Cartesian power ["++","+_","_+","__"]
ż@€ - zip for €ach (swap @rguments) ["12+345+67","12+345_67","12_345+67","12_345_67"]
ŒṖÇ€ẎµFV=ȷ2µÐfLÞḢFṄḟ³L - Main link: list of characters
ŒṖ - all partitions
Ç€ - call the last link (1) as a monad for €ach
Ẏ - tighten (flatten by 1 level)
µ µÐf - filter keep if:
F - flatten
V - evaluate as Jelly code (perform the sum)
ȷ2 - literal 100
= - equal?
Þ - sort by:
L - length
Ḣ - head
F - flatten
Ṅ - print that and a newline
ḟ³ - filter out the characters from the input
L - length (number of operators)
- implicit print
답변
매스 매 티카, 136 146 149 156 165 166 바이트
#&@@Sort[{StringLength@#-e+9!(ToExpression@#-100)^2,#}&/@StringJoin/@(Riffle[b,#]&)/@Tuples[{"","+","-"},(e=Length[b=Characters@#])-1]]&
{3, 123-45-67+89}예를 들어 반환 합니다.
테스트 케이스를 완료하는 데 약 0.09 초가 걸립니다.
답변
파이썬 (2) , 256 (230) 208 205 172 171 170 165 바이트 반복법
- 33 개 차스 브라운 덕분에
- 교체 할 때 하나는 바이트를 저장
len(a)하여w - 교체 할 때 하나는 바이트를 저장
z-=1;d=z하여d=z=z-1
q=[];a=input()
w=len(a);z=n=3**w
while z-n/3:
d=z=z-1;j=0;b=''
while d:r=d%3;d/=3;b+=a[j]+chr(r+43)*(d>0!=r-1);j+=1
if eval(b)==100:q+=[(len(b)-w,b)]
print min(q)간단한 설명
밑줄 3의 표현을 사용하여 코드는 가능한 모든 조합에 따라 숫자를 연산자 { ‘+’, ‘-‘, concatenation}으로 인터리브합니다.
파이썬 2 , 167 바이트, 재귀 적 방법
def f(s):
if len(s)==1:return[s]
b=s[0];q=[]
for z in f(s[1:]):q+=[b+'+'+z,b+'-'+z,b+z]
return q
a=input()
print min((len(x)-len(a),x)for x in f(a)if eval(x)==100)일부 출력
"399299" --> (1, '399-299')
"987654321" --> (4, '98-76+54+3+21')
"1111111" --> (3, '1+111-1-11')