당신의 작업은 integer를 취하는 프로그램을 만들고 단면 다이 n > 1의 롤을 출력하는 n것입니다. 그러나이 주사위는 주사위를 폭발 시키기위한 규칙을 따릅니다 .
주사위를 굴릴 때 어떤 값을 굴 렸는지 확인하십시오. 해당 종류의 다이에 대한 최대 값 (d6의 경우 4 또는 6 인 표준 d4 등)을 최대로 얻은 경우 다시 굴려서 새 롤을 해당 합계에 추가하십시오. 더 이상 최대 수를 구르지 않을 때까지 각 롤에 총계가 계속 추가됩니다. 최종 번호는 여전히 추가됩니다.
프로그램은 단일 정수를 취하고 n폭발 n성형 주사위를 굴려야합니다 . 여기에 어떻게 보이는지 보여주는 배포 예제가 n=4있습니다. 의 배수 n는 항상 분해되므로 절대로 배수를 출력해서는 안됩니다 .
재귀의 스택 크기가 무한하다고 가정 할 수 있으며 임의의 함수 는 임의성에 대한 표준 (내장 임의 생성기 또는 시간 / 날짜 )을 충족해야합니다 . 랜덤 함수는 우리가 말하는 주사위이기 때문에 기하 분포와 같은 가능한 한 균일해야합니다.
답변
x86 머신 코드 (Intel Ivy Bridge 이상용), 17 바이트
31 C9 0F C7 F0 31 D2 F7 F6 42 01 D1 39 F2 74 F2 C3
위의 바이트 코드는 폭발 다이를 시뮬레이트하는 함수를 정의합니다. ESI레지스터에 전달 된 단일 입력을 사용 하여 최대 다이 수를 나타냅니다. ECX롤의 결과 인 레지스터에 단일 값을 반환합니다 .
내부적으로, 그것은 사용 지시 난수를 생성한다. Intel Ivy Bridge 프로세서 이상의 하드웨어에 내장 된 난수 생성기 (RNG)를 사용합니다 (일부 AMD CPU도이 명령을 지원합니다).RDRAND
함수의 논리는 그렇지 않으면 매우 간단합니다. 생성 된 난수는 표준 기술 ( (rand % dieSize) + 1)을 사용하여 원하는 범위 내에 놓 이도록 조정 된 다음 폭발이 발생하는지 확인합니다. 최종 결과는 누산기 레지스터에 유지됩니다.
다음은 어셈블리 언어 니모닉을 보여주는 주석이 달린 버전입니다.
unsigned int RollExplodingDie(unsigned int dieSize)
31 C9 xor ecx, ecx ; zero-out ECX, which accumulates the final result
Roll:
0F C7 F0 rdrand eax ; generate a random number in EAX
31 D2 xor edx, edx ; zero-out EDX (in preparation for unsigned division)
F7 F6 div esi ; divide EDX:EAX by ESI (the die size)
; EAX receives the quotient; EDX receives the remainder
42 inc edx ; increment the remainder
01 D1 add ecx, edx ; add this roll result to the accumulator
39 F2 cmp edx, esi ; see if this roll result should cause an explosion
74 F2 jz Roll ; if so, re-roll; otherwise, fall through
C3 ret ; return, with result in ECX register
나는 약간의 바람을 피우고 있다 . 모든 표준 x86 호출 규칙은 EAX레지스터 의 함수 결과를 반환합니다 . 그러나 실제 머신 코드에는 호출 규칙이 없습니다. 입 / 출력에 원하는 레지스터를 사용할 수 있습니다. ECX출력 레지스터를 사용하면 1 바이트가 절약되었습니다. 을 사용하려면 명령어 바로 앞에 EAX1 바이트 XCHG eax, ecx명령어를 삽입하십시오 ret. 그러면 EAX및 ECX레지스터 의 값이 바뀌어에 결과가 ECX에 효과적으로 복사 되고의 이전 값으로 EAX휴지통이 비워 ECX집니다 EAX.
다음 은 명령어 를 생성하기 위해 GCC, Clang 및 ICC에서 지원 하는 __builtin_ia32_rdrand32_step내장 함수를 사용하여 C로 작성된 동등한 함수입니다 RDRAND.
#include <immintrin.h>
unsigned int RollExplodingDie(unsigned int dieSize)
{
unsigned int result = 0;
Roll:
unsigned int roll;
__builtin_ia32_rdrand32_step(&roll);
roll = ((roll % dieSize) + 1);
result += roll;
if (roll == dieSize) goto Roll;
return result;
}
흥미롭게도, 플래그 가있는 GCC는 -Os이를 거의 동일한 머신 코드로 변환합니다 . 그것은 EDI대신에 입력을 취하는데 ESI, 이것은 완전히 임의적이며 코드에 관한 내용은 전혀 변경하지 않습니다. EAX앞에서 언급했듯이 결과를으로 반환해야 하며보다 효율적인 (그러나 더 큰) MOV명령을 사용하여 RET. 그렇지 않으면 samezies. 프로세스가 완전히 뒤집을 수 있으면 항상 재미 있습니다. 어셈블리에서 코드를 작성하고 C로 복사하고 C 컴파일러를 통해 실행하고 원래 어셈블리를 다시 가져옵니다!
답변
파이썬 2 , 66 64 61 바이트
xnor 덕분에 -3 바이트
f=lambda n,c=0:c%n or c+f(n,randint(1,n))
from random import*
이전 롤은에 저장되어 c있으므로 파이썬 람다에서는 수행 할 수없는 변수에 저장하지 않고도 여러 번 액세스 할 수 있습니다. 재귀마다, 우리는 폭발 주사위를 굴 렸는지 확인합니다.
c0으로 초기화되므로 c%n거짓입니다. 다음 반복에서는 폭발하는 주사위를 굴린 경우에만 거짓이됩니다.
파이썬 2 , 55 바이트
f=lambda n:randint(1,n)%n or n+f(n)
from random import*
내 다른 대답은 약간 과도하게 설계된 것 같습니다.
답변
답변
펄 6 , 26 바이트
{sum {roll 1..$_:}...*-$_}설명
{ } # Anonymous block
... # Sequence constructor
{roll 1..$_:} # Next elem is random int between 1 and n
# (Called as 0-ary function with the original
# $_ for the 1st elem, then as 1-ary function
# with $_ set to the previous elem which
# equals n.)
*-$_ # Until elem not equal to n (non-zero difference)
sum # Sum all elements답변
J , 16 11 바이트
(+$:)^:=1+?
설명
TL; DR 1+? 은 다이 롤을 수행 (+$:)^:=하고 입력과 같을 때만 반복합니다.
이 함수는 4 동사의 기차입니다.
┌─ +
┌───┴─ $:
┌─ ^: ─┴─ =
│
──┤ ┌─ 1
└──────┼─ +
└─ ?
기차는 두 개 이상의 동사가 연결될 때입니다. 대답은 다음과 같습니다 f g h j.
(+$:)^:= 1 + ?
f g h j
소위 “4 트레인”은 후크와 포크로 구문 분석됩니다.
f g h j ⇔ f (g h j)
따라서 답은 다음과 같습니다.
(+$:)^:= (1 + ?)
후크 : (f g) x및x (f g) y
인수가 주어지면 두 동사의 모나 딕 (1 인수) 후크 x는 다음과 같습니다.
(f g) x ⇔ x f (g x)
예를 들어로 (* -) 5평가하면 5 * (- 5)로 평가됩니다 _25.
이는 4의 트레인 인 f및 의 후크 (g h j)가 다음에 해당함을 의미합니다.
(f (g h j)) x ⇔ x f ((g h j) x)
그러나 f여기서 무엇을합니까? 전원 연결을 (+$:)^:=사용하는 두 개의 동사 : 다른 후크 ( )와 동사 ( )입니다. 여기에 참고 인 이항 – 그것은 두 개의 인수가 ( 하고 ). 그래서 우리는 어떻게 행동하는지 살펴 봐야합니다 . 전원 연결 은 동사 와 동사 또는 명사 (명사는 데이터의 일부 임)를 취하여 시간을 적용 합니다. 예를 들어 보자 . 다음과 같은 내용이 유지됩니다.^:(+$:)=fx(g h j) x^:f^:ofof oo = 3
(f^:3) x ⇔ f (f (f x))
x (f^:3) y ⇔ x f (x f (x f y))
경우 o동사는, 전원 연결은 단순히 평가합니다 o인수를 통해와 반복 횟수로 명사 결과를 사용합니다.
우리의 동사를 들어, o이다 =, 평등 동사. 0다른 인수와 1동일한 인수로 평가됩니다 . (+$:)동일한 인수에 대해서는 후크를 한 번 반복하고 다른 인수에 대해서는 후크를 반복 하지 않습니다. 설명을 쉽게하기 위해을 보자 y ⇔ ((g h j) x). 초기 후크는 다음과 같습니다.
x (+$:)^:= ((g h j) x)
x (+$:)^:= y
연결을 확장하면 다음과 같이됩니다.
x ((+$:)^:(x = y)) y
경우 x와 y동일하며,이된다 :
x (+$:)^:1 y ⇔ x (+$:) y
그렇지 않으면 다음과 같이됩니다.
x (+$:)^:0 y ⇔ y
이제 모나 딕 포크를 보았습니다. 여기, 우리는 2 단 포크를 가지고 있습니다 :
x (f g) y ⇔ x f (g y)
따라서 언제 x와 y동일하면 다음을 얻습니다.
x (+$:) y ⇔ x + ($: y)
무엇입니까 $:? 전체 동사 자체를 나타내며 재귀를 허용합니다. 이것은 언제 x그리고 y are the same, we apply the verb toy and addx` 라는 의미입니다 .
포크 : (g h j) x
이제, 내부 포크는 무엇을합니까? 이것은 y우리의 마지막 예였습니다. 세 가지 동사의 모나드 포크의 경우 인수가 주어지면 x다음과 같은 동등성이 유지됩니다.
(g h j) x ⇔ (g x) h (j x)
이 다음에 예를 들어, 우리가 동사라는 이름의 한 가정 SUM, DIVIDE그리고 LENGTH당신은 그들이 수도 무엇을 생각 않는. 세 가지를 포크로 연결하면 다음과 같은 결과를 얻습니다.
(SUM DIVIDE LENGTH) x ⇔ (SUM x) DIVIDE (LENGTH x)
이 포크는 평균으로 평가됩니다 x( x수치 라고 가정 ). J에서는 실제로 이것을 예제로 작성 +/ % #합니다.
포크에 관한 마지막 것. 가장 왼쪽의 “tine”(위의 상징적 인 경우 g)이 명사 인 경우 해당 값을 반환하는 상수 함수로 처리됩니다.
이 모든 것을 갖추면 위의 포크를 이해할 수 있습니다.
(1 + ?) x ⇔ (1 x) + (? x)
⇔ 1 + (? x)
?
[1,x]
함께 모아서
이 모든 것을 감안할 때 동사는 다음과 같습니다.
((+$:)^:=1+?) x ⇔ ((+$:)^:= 1 + ?) x
⇔ ((+$:)^:= (1 + ?)) x
⇔ x ((+$:)^:=) (1 + ?) x
⇔ x ((+$:)^:=) (1 + (? x))
⇔ x (+$:)^:(x = (1 + (? x))
(let y = 1 + (? x))
if x = y ⇒ x + $: y
otherwise ⇒ y
이것은 원하는 기능을 나타냅니다.
답변
젤리 , 7 바이트
X+ß}¥=¡
재귀를 사용합니다. 프로그램을 다시 실행하고 ( ) 난수 ( )가 프로그램 입력 과 같으면 ( ) ß추가합니다 ( +) . 브랜드는 프로그램 입력 및 행동 을 결합 하는 단일 링크로 소비한다.¡X=}ߥ+ß}¡
여기 에이 프로그램을 사용하여 수집 한 n = 6의 1000 출력 분포가 있습니다. python / matplotlib로 플로팅되었습니다.
다음은 (대략?) 지수 분포를 보여주는 세미 로그 플롯의 n = 3에서 5000 개의 데이터 포인트입니다.
답변
Pyth- 12 11 바이트
기능적으로 사용합니다. 분포를 시뮬레이트하는 더 똑똑한 대답이 있어야한다고 생각합니다.
-.W!%HQ+hOQ
- (Q) Subtract Q. This is because we start Z at Q to save a char
.W While, functionally
! Logical not. In this case, it checks for 0
%HQ Current val mod input
+ (Z) Add to current val
h Plus 1
OQ Random val in [0, input)