양의 유리수는 다음과 같은 과정으로 계산할 수 있습니다.
- 0은 서수 0을 갖습니다.
- 행 a, 열 b에 a / b가 포함되도록 그리드에 다른 숫자를 정렬하십시오.
- 대각선 지그재그를 오른쪽 상단에서 왼쪽 하단으로 플로팅
- 지그재그를 따라 발생하는 고유 번호의 누적 집계
지그재그 사진은 다음과 같습니다.
따라서 숫자는 순서대로
1/1, 2/1, 1/2, 1/3, 2/2, 3/1, 4/1, 3/2, 2/3, 1/4, 1/5, 2/4, 3/3, 4/2, 5/1, 6/1, 5/2, 4/3, 3/4, 2/5, 1/6, 1/7, 2/6, 3/5, 4/4, 5/3 ...
그리고 단순화되고 고유 한 숫자는
1, 2, 1/2, 1/3, 3, 4, 3/2, 2/3, 1/4, 1/5, 5, 6, 5/2, 4/3, 3/4, 2/5, 1/6, 1/7, 3/5, 5/3, ...
도전:
- 두 개의 0보다 큰 정수 p 및 q 가 주어지면 p / q 의 서수를 출력하십시오.
- p와 q는 반드시 공동 프라임 일 필요는 없습니다
- 최단 코드 승리
- 표준 허점 은 금지되어 있습니다
테스트 사례 :
다음은 처음 발견 된 24 개의 유리수와 각각에 대한 원하는 출력입니다.
1/1: 1
2/1: 2
1/2: 3
1/3: 4
2/2: 1
3/1: 5
4/1: 6
3/2: 7
2/3: 8
1/4: 9
1/5: 10
2/4: 3
3/3: 1
4/2: 2
5/1: 11
6/1: 12
5/2: 13
4/3: 14
3/4: 15
2/5: 16
1/6: 17
1/7: 18
2/6: 4
3/5: 19
그리고 추가 테스트 사례의 경우 순서대로 200 개의 첫 번째 양의 유리수가 있습니다.
1, 2, 1/2, 1/3, 3, 4, 3/2, 2/3, 1/4, 1/5,
5, 6, 5/2, 4/3, 3/4, 2/5, 1/6, 1/7, 3/5, 5/3,
7, 8, 7/2, 5/4, 4/5, 2/7, 1/8, 1/9, 3/7, 7/3,
9, 10, 9/2, 8/3, 7/4, 6/5, 5/6, 4/7, 3/8, 2/9,
1/10, 1/11, 5/7, 7/5, 11, 12, 11/2, 10/3, 9/4, 8/5,
7/6, 6/7, 5/8, 4/9, 3/10, 2/11, 1/12, 1/13, 3/11, 5/9,
9/5, 11/3, 13, 14, 13/2, 11/4, 8/7, 7/8, 4/11, 2/13,
1/14, 1/15, 3/13, 5/11, 7/9, 9/7, 11/5, 13/3, 15, 16,
15/2, 14/3, 13/4, 12/5, 11/6, 10/7, 9/8, 8/9, 7/10, 6/11,
5/12, 4/13, 3/14, 2/15, 1/16, 1/17, 5/13, 7/11, 11/7, 13/5,
17, 18, 17/2, 16/3, 15/4, 14/5, 13/6, 12/7, 11/8, 10/9,
9/10, 8/11, 7/12, 6/13, 5/14, 4/15, 3/16, 2/17, 1/18, 1/19,
3/17, 7/13, 9/11, 11/9, 13/7, 17/3, 19, 20, 19/2, 17/4,
16/5, 13/8, 11/10, 10/11, 8/13, 5/16, 4/17, 2/19, 1/20, 1/21,
3/19, 5/17, 7/15, 9/13, 13/9, 15/7, 17/5, 19/3, 21, 22,
21/2, 20/3, 19/4, 18/5, 17/6, 16/7, 15/8, 14/9, 13/10, 12/11,
11/12, 10/13, 9/14, 8/15, 7/16, 6/17, 5/18, 4/19, 3/20, 2/21,
1/22, 1/23, 5/19, 7/17, 11/13, 13/11, 17/7, 19/5, 23, 24,
23/2, 22/3, 21/4, 19/6, 18/7, 17/8, 16/9, 14/11, 13/12, 12/13,
11/14, 9/16, 8/17, 7/18, 6/19, 4/21, 3/22, 2/23, 1/24, 1/25
첫 번째 움직임이 다운 된 반대 질문 을 외치면 답변을 사용하여 추가 테스트 사례를 생성 할 수 없습니다.
답변
젤리 , 21 20 바이트
영리한 수학을 사용하여 여러 바이트로 이길 수 있습니다 …
:g/
ǵSRRUĖ€UÐeẎÇ€Qi
에 [p,q]지정된 자연수를 반환 하는 목록을 수락하는 모나드 링크 p/q.
온라인으로 사용해보십시오! 또는 테스트 스위트를 참조하십시오.
어떻게?
먼저 N 번째 대각선은 분자와 분모의 합이 N + 1 인 그리드의 모든 합리적인 숫자를 포함 하므로 [p,q]쌍을 가장 간단한 형태로 줄이는 함수를 [p/gcd(p,q),q/gcd(p,q)]사용하면 대각선을 만들 수 있습니다. *, 모든 항목을 줄이고, 중복을 제거하고 단순화 된 입력의 색인을 찾아야합니다.
* 실제로 바이트를 저장하기 위해 여기에 하나 더
:g/ - Link 1, simplify a pair: list of integers, [a, b]
/ - reduce using:
g - Greatest Common Divisor -> gcd(a, b)
: - integer division (vectorises) -> [a/gcd(a,b), b/gcd(a,b)]
ǵSRRUĖ€UÐeẎÇ€Qi - Main Link: list of integers, [p, q]
Ç - call last Link as a monad (simplify)
µ - start a new monadic chain (call that V)
S - sum -> the diagonal V will be in plus one
R - range -> [1,2,3,...,diag(V)+1]
R - range (vectorises) -> [[1],[1,2],[1,2,3],...,[1,2,3,...,diag(V)+1]]
U - reverse each -> [[1],[2,1],[3,2,1],[diag(V)+1,...,3,2,1]]
Ė€ - enumerate €ach -> [[[1,1]],[[1,2],[2,1]],[[1,3],[2,2],[3,1]],[[1,diag(V)+1],...,[diag(V)-1,3],[diag(V),2],[diag(V)+1,1]]]
Ðe - apply only to the even indexed items:
U - reverse each -> [[[1,1]],[[2,1],[1,2]],[[1,3],[2,2],[3,1]],[[4,1],[3,2],[2,3],[1,4]],...]
Ẏ - tighten -> [[1,1],[2,1],[1,2],[1,3],[2,2],[3,1],[4,1],[3,2],[2,3],[1,4],...]
Ç€ - for €ach: call last Link as a monad (simplify each)
- -> [[1,1],[2,1],[1,2],[1,3],[1,1],[3,1],[4,1],[3,2],[2,3],[1,4],...]
Q - de-duplicate -> [[1,1],[2,1],[1,2],[1,3],[3,1],[4,1],[3,2],[2,3],[1,4],...]
i - index of V in that list
답변
펄 6 , 94 90 바이트
->\p,\q{(({|(1…($+=2)…1)}…*)Z/(1,{|(1…(($||=1)+=2)…1)}…*)).unique.first(p/q,:k)+1}{(({|(1…($+=2)…1)}…*)Z/(1,{|(1…(($||=1)+=2)…1)}…*)).unique.first($^p/$^q):k+1}기본적으로 전체 값 시퀀스를 생성하고 일치하는 항목을 찾으면 중지합니다.
넓히는:
{ # bare block lambda with placeholder parameters $p,$q
(
( # sequence of numerators
{
|( # slip into outer sequence (flatten)
1 # start at one
…
(
$ # state variable
+= 2 # increment it by two each time this block is called
)
…
1 # finish at one
)
}
… * # never stop generating values
)
Z/ # zip using &infix:« / » (generates Rats)
( # sequence of denominators
1, # start with an extra one
{
|( # slip into outer sequence (flatten)
1
…
(
( $ ||= 1 ) # state variable that starts with 1 (rather than 0)
+= 2 # increment it by two each time this is called
)
…
1
)
}
… * # never stop generating values
)
).unique # get only the unique values
.first( $^p / $^q ) # find the first one that matches the input
:k # get the index instead (0 based)
+ 1 # add one (1 based)
}({1…($+=2)…1}…*)무한한 분자 시퀀스를 생성합니다 ( |(…)위에서 사용하여 평탄화).
(1 2 1)
(1 2 3 4 3 2 1)
(1 2 3 4 5 6 5 4 3 2 1)
(1 2 3 4 5 6 7 8 7 6 5 4 3 2 1)
(1 2 3 4 5 6 7 8 9 10 9 8 7 6 5 4 3 2 1)
…(1,{1…(($||=1)+=2)…1}…*) 무한 분모의 분모를 생성
1
(1 2 3 2 1)
(1 2 3 4 5 4 3 2 1)
(1 2 3 4 5 6 7 6 5 4 3 2 1)
(1 2 3 4 5 6 7 8 9 8 7 6 5 4 3 2 1)
(1 2 3 4 5 6 7 8 9 10 11 10 9 8 7 6 5 4 3 2 1)
…답변
파이썬 (2) , 157 (144) 137 134 126 125 바이트
def f(p,q):a=[((j-i)/(i+1.))**(j%-2|1)for j in range(p-~q)for i in range(j)];return-~sorted(set(a),key=a.index).index(p*1./q)Mr. Xcoder 로 인해 4 바이트가 절약되었습니다 . Jonathon Frech 에서 1 바이트 .
Xcoder가 지적했듯이, 파이썬 3에서는 정수 나누기가 기본적으로 결과를 플로팅하고 더 쉽게 압축을 풀 수 있기 때문에 파이썬 3에서 조금 더 잘 할 수 있습니다 list.
파이썬 3 , 117 바이트
def f(p,q):a=[((j-i)/-~i)**(j%-2|1)for j in range(p-~q)for i in range(j)];return-~sorted({*a},key=a.index).index(p/q)답변
파이썬 3 ,157, 146, 140, 133 바이트
def f(p,q):a=[(i+i-abs(j-i-i))/(abs(j-i-i+.5)+.5)for i in range(p+q)for j in range(4*i)];return sorted(set(a),key=a.index).index(p/q)Jonathan Frech 덕분에 11 바이트 우승
Chas Brown 덕분에 6 바이트 더 획득 한 후 7 원
답변
J, 41 , 35 , 30 바이트
FrownyFrog 덕분에 -11 바이트
%i.~0~.@,@,[:]`|./.[:%/~1+i.@*
설명이있는 원본 41 바이트 게시물
%>:@i.~[:([:~.@;[:<@|.`</.%"1 0)~(1+i.@*)
언 골프
% >:@i.~ [: ([: ~.@; [: <@|.`</. %"1 0)~ 1 + i.@*
설명
+
| Everything to the right of this
| calculates the list
p (left arg) | create the
divided by q | diagonals. yes,
(right) | +this is a +create this list
| | ++ finally rmv ^alternately |primitive ADVERB |1..(p*q), and pass
| + the index | the boxes, |box, or |in J |it as both the left
| | of that | | and remove |reverse and | |and right arg to the
| | in the | | any dups |box, each | |middle verb, where each
| | list on | | |diagonal | |element will divide the
| | the right| | | | +----------+entire list, producing
| | plus 1 | | | | | |the undiagonalized grid
| | | | | | | |
| | | | | | | |
| | + | | | | |
┌+┬──|──────────┬─────────|─────────────|─────────────|───────|──────────|─────────────┐
│%│┌─+───────┬─┐│┌──┬─────|─────────────|─────────────|───────|────────┬─|────────────┐│
│ ││┌──┬─┬──┐│~│││[:│┌────|─────────────|─────────────|───────|─────┬─┐│┌+┬─┬────────┐││
│ │││>:│@│i.││ │││ ││┌──┬|───────┬─────|─────────────|───────|────┐│~│││1│+│┌──┬─┬─┐│││
│ ││└──┴─┴──┘│ │││ │││[:│+──┬─┬─┐│┌──┬─|─────────────|─┬─────|───┐││ │││ │ ││i.│@│*││││
│ │└─────────┴─┘││ │││ ││~.│@│;│││[:│┌|───────────┬─+┐│┌─┬─┬+──┐│││ │││ │ │└──┴─┴─┘│││
│ │ ││ │││ │└──┴─┴─┘││ ││+────────┬─┐│/.│││%│"│1 0││││ ││└─┴─┴────────┘││
│ │ ││ │││ │ ││ │││┌─┬─┬──┐│<││ ││└─┴─┴───┘│││ ││ ││
│ │ ││ │││ │ ││ ││││<│@│|.││ ││ ││ │││ ││ ││
│ │ ││ │││ │ ││ │││└─┴─┴──┘│ ││ ││ │││ ││ ││
│ │ ││ │││ │ ││ ││└────────┴─┘│ ││ │││ ││ ││
│ │ ││ │││ │ ││ │└────────────┴──┘│ │││ ││ ││
│ │ ││ │││ │ │└──┴─────────────────┴─────────┘││ ││ ││
│ │ ││ ││└──┴────────┴────────────────────────────────┘│ ││ ││
│ │ ││ │└──────────────────────────────────────────────┴─┘│ ││
│ │ │└──┴──────────────────────────────────────────────────┴──────────────┘│
└─┴─────────────┴──────────────────────────────────────────────────────────────────────┘
답변
파이썬 3, 121 바이트
import math
def o(x,y):
p=q=n=1
while x*q!=p*y:a=p+q&1;p+=1+a*~-~-(p<2);q+=1-~-a*~-~-(q<2);n+=math.gcd(p,q)<2
return n답변
녹, 244 바이트
: 나는 삼각형 숫자 수식을 사용하여 퍼즐의 제약없이 “일반”지그재그의 “일반”순서를 찾는 간단한 공식을 만들어
https://www.mathsisfun.com/algebra/triangular-numbers.html . 이것은 지그재그가 퍼즐의 각 대각선 행 방향을 뒤집는 것을 설명하기 위해 모듈로 2로 수정되었습니다. 이것은 함수 h ()입니다
그리고 지그재그 트레일에서 3/3 vs 1/1, 4/2 vs 2/1과 같은 반복되는 특정 값을 계산하지 않는 방법. 1-200 예제를 실행하고 일반 지그재그 삼각형 카운터와 퍼즐이 원하는 카운터의 차이가 패턴에 있음을 알았습니다. “누락 된”숫자의 패턴은 5, 12, 13, 14, 23 등으로 OEIS에서 적중했습니다. 3/3, 4/2 및 1/1과 같은 숫자를 “중복 제거”하기 위해 Robert A Stump ( https://oeis.org/A076537 )에 설명되어 있습니다. 지그재그의 모든 “이전”서수 중 x, y 이것은 ‘for’루프이고 gcd 인 g ()는 gcd입니다.
나는 내장 된 gcd로 그것이 더 짧았을 것이라고 생각하지만, 나는 그것을 쉽게 찾을 수 없었습니다 (Rust and Integer에서 새로운 종류의 나를 혼동했습니다). 어떤 종류의 내장이나 라이브러리도 없습니다.
fn f(x:i64,y:i64)->i64 {
fn h(x:i64,y:i64)->i64 {let s=x+y;(s*s-3*s+4)/2-1+(s+1)%2*x+s%2*y}
fn g(x:i64,y:i64)->i64 {if x==0 {y} else {g(y%x,x)}}
let mut a=h(x,y);
for i in 1..x+y {for j in 1..y+x {if h(i,j)<h(x,y) && g(i,j)>1 {a-=1;}}}
a
}