당신은 상당히 빠른 급류 강 아래로 카누를 젓고 있습니다. 갑자기 외륜이 터지고 외륜이없이 급류를 밟아 위험한 상황에 처하게됩니다. 운 좋게도 여전히 프로그래밍 기술을 보유하고 있으므로 카누 옆에 급류에서 살아남을 수 있도록 프로그램을 개척하기로 결정했습니다. 그러나 카누의 측면에는 프로그램을 작성할 표면적이 많지 않으므로 가능한 짧게 프로그램을 작성해야합니다.
강은 8 x 16 그리드로 표현 될 수 있습니다. 우리는 숫자 열을 라벨됩니다 0
에 7
와 숫자 행 0
에 15
.
y
--------15
--------14
--------13
--------12
--------11
--------10
--------9
--------8
--------7
--------6
--------5
--------4
--------3
--------2
--------1
--------0
01234567
x
위 : 장애물이없는 완전히 평온하고 평범한 강. 당연히 이것은 강이 아닙니다.
좌표 (4, 0)에서 시작 (0,1)
하여 바위에서 닿을 때까지 ( o
예제에서로 표시) 강 (즉, vector )을 제어 할 수없이 움직 입니다. 바위에 부딪히면 바위를지나 왼쪽으로 움직일 확률이 55 %이고 (예 : 벡터 (-1,1)
) 바위를지나 오른쪽으로 움직일 확률이 45 %입니다 (예 : 벡터 (1,1)
). 카누가 가장 왼쪽 또는 오른쪽 열에 있으면 항상 중앙으로 이동합니다. 바위가 없으면 위로 똑바로 움직입니다.
y
----x---15
----xo--14
-o--x---13
----x---12
---ox---11
---x----10
---xo---9
---ox---8
----xo--7
-----x--6
----ox--5
-o--x---4
----x---3
----xo--2
----x---1
----x---0
01234567
위 : 캐릭터를 사용하여 카누를 타는 가능한 경로 x
강의지도가 주어지면 주어진 열에서 카누 마무리의 가능성을 출력하는 프로그램을 작성하십시오.
프로그램에 편리한 방법 (예 : STDIN, 명령 행 인수, raw_input()
파일에서 읽기 등)을 입력하십시오. 입력의 첫 번째 부분은 0에서 7까지의 단일 정수이며 프로그램이 찾을 확률을 나타내는 열을 나타냅니다. 다음 x,y
은 돌의 위치를 나타내는 형태의 튜플 목록입니다 .
예를 들면 :
입력:
4 4,1 5,5 3,5
이것은 (4,1), (5,5) 및 (3,5) 위치에 바위가있는 강을 나타내고 4 번째 열에서 카누가 끝날 확률을 요구합니다.
산출:
0.495
이 예에서 암석의 위치는 대칭이므로 이항 분포로 문제를 해결할 수 있습니다. 항상 그런 것은 아닙니다!
또한 강은 항상 교차 가능합니다. 즉, 서로 수평으로 인접하여 위치한 두 개의 암석은 없습니다. 불가능한 사례의 예는 Glenn의 의견 을 참조하십시오 .
이것은 코드 골프이므로 문자 수가 가장 적습니다. 사양이 명확하지 않은 경우 의견에 자유롭게 질문하십시오.
답변
GolfScript, 105 자
~](\2/:A;8,{4=}%15,{:B;{20*}%A{~B={[\\,.1,*\[2$=..20/9*:C-\~)C]+(1,\+1,6*2$8>+]zip{{+}*}%.}*;}/}/=20-15?*
의도 한 것보다 훨씬 길어진 GolfScript 버전이지만 다른 접근 방식을 사용하는 각 시도는 훨씬 길었습니다. 입력은 STDIN에 제공되어야합니다.
예:
> 4 4,1 5,5 3,5
99/200
주석이 달린 코드 :
# Evaluate the input
# - stack contains the first number (i.e. column)
# - variable A contains the rock coordinates (pairs of X y)
# where X is an array of length x (the coordinate itself)
~](\2/:A;
# Initial probabilities
# - create array [0 0 0 0 1 0 0 0] of initial probabilities
8,{4=}%
# Loop over rows
15,{:B; # for B = 0..14
{20*}% # multiply each probability by 20
A{ # for each rock
~B={ # if rock is in current row then
# (prepare an array of vectors [v0 vD vL vR]
# where v0 is the current prob. before rocks,
# vD is the change due to rocks,
# vL is a correction term for shifting out to the left
# and vR the same for the right side)
[\\ # move v0 inside the array
, # get x coordinate of the rock
.1,* # get [0 0 ... 0] with x terms
\[2$= # get x-th item of v0
..20/9*:C- # build array [0.55P -P 0.45P]
\~)C]+ # and append to [0 0 ... 0]
(1,\+ # drop the leftmost item of vD and prepend [0] again
# which gives vL
1,6*2$8>+ # calculate vR using the 8th item of vD
] #
zip{{+}*}% # sum the columns of this list of vectors
. # dummy dup for end-if ;
}*; # end if
}/ # end for
}/ # end for
# take the n-th column and scale with 20^-15
=
20-15?*
답변
루비 204 개 191 172 문자
c,*r=gets.split
o=[0]*8
s=->x,y,p{y>14?o[x]+=p :(r.index("#{x},#{y+=1}")?(x<1?s[x+1,y,p]:(x>6?s[x-1,y,p]:(s[x-1,y,p*0.55]+s[x+1,y,p*0.45]))):s[x,y,p])}
s[4,0,1]
p o[c.to_i]
각 개별 결과의 확률을 추적하면서 가능한 모든 결과를 재귀 적으로 시뮬레이션 한 다음 해당 확률을 누적 카운터에 추가합니다 y == 15
.
멋진 트릭 :
-
c,*r=gets.split
– “splat”연산자 (*
)는 나머지 모든 요소를 가져 와서 배열에gets.split
붙입니다.r
-
next {something} if {condition}
: 본질적으로if {condition} {something} return end
에서 진화에 의해 “발견”if condition; something; return; end
에return something if condition
에break something if condition
, 그리고 나는 그것이 작동한다면 (이것은 물론 않았다)를 참조하기 위해 짧은 “루프 연산자를”시도 할 생각. -
@ MartinBüttner에게 연결 된 삼항 연산자 (위의 골프 코드에서 거대한 세 번째 줄이 됨)를 제안하고 위의 포인트 (19 (!) 문자 절약)를 제거하도록 제안 해 주셔서 감사합니다.
그래도 다소 멋진 트릭을 사용했지만
s[foo],s[bar]
루비에서는 한 명령문에서 두 개의 메소드 호출에 대해 작동하지 않는다는 것을 깨달았습니다 . 처음(_=s[foo],s[bar])
에는 변수를 더미 변수로 변경 했지만 반환 값을 추가하고 버릴 수 있다는 것을 깨달았습니다s[foo]+s[bar]
. 이 호출s
은 다른 호출s
이나 숫자 (o[x]+=p
) 만 “반환” 하기 때문에 작동 합니다nil
. 따라서 확인에 대해 걱정할 필요가 없습니다 . -
기타 다양한 최적화 :
p
대신puts
, 숫자를 인쇄하는<1
대신==0
다른 곳과 유사한 비교 (카누 강을 결코 떠나지 않는다 때문에)[0]*8
항상 “값에 의해 전달”하는 루비의 번호와 같은 초기 확률에 대한
언 골프 드 :
column, *rocks = gets.chomp.split
outcomes = Array.new(8, 0)
simulate = -> x, y, probability {
if y == 15
outcomes[x] += probability
elsif rocks.index("#{x},#{y + 1}")
case x
when 0 then simulate[x + 1, y + 1, probability]
when 7 then simulate[x - 1, y + 1, probability]
else
simulate[x - 1, y + 1, probability * 0.55]
simulate[x + 1, y + 1, probability * 0.45]
end
else
simulate[x, y + 1, probability]
end
}
simulate[4, 0, 1.0]
p outcomes
puts outcomes[column.to_i]
답변
C # 418 364 바이트
STDIN의 입력을 기대하는 완전한 C # 프로그램. 강을 따라 강의 모든 위치의 배열로 바위를 읽고 효과적으로 맵을 만든 다음 결과를 출력하기 전에 8 너비의 십진 배열을 중심으로 16 번의 이동 확률을 반복합니다.
using C=System.Console;class P{static void Main(){var D=C.ReadLine().Split();int i=0,j=D.Length;var R=new int[8,16];var p=new decimal[8];for(p[4]=1;--j>0;)R[D[j][0]-48,int.Parse(D[j].Substring(2))]=1;for(;i<16;i++){var n=new decimal[j=8];for(;j-->0;)if(R[j,i]>0){n[j<1?1:j-1]+=p[j]*0.55M;n[j>6?6:j+1]+=p[j]*0.45M;}else n[j]+=p[j];p=n;}C.WriteLine(p[D[0][0]-48]);}}
형식화 된 코드 :
using C=System.Console;
class P
{
static void Main()
{
var D=C.ReadLine().Split();
int i=0,j=D.Length;
var R=new int[8,16];
var p=new decimal[8];
for(p[4]=1;--j>0;) // read rocks into map (R)
R[D[j][0]-48,int.Parse(D[j].Substring(2))]=1;
for(;i<16;i++) // move up the river
{
var n=new decimal[j=8];
for(;j-->0;)
if(R[j,i]>0)
{ // we hit a rock!
n[j<1?1:j-1]+=p[j]*0.55M;
n[j>6?6:j+1]+=p[j]*0.45M;
}
else
n[j]+=p[j];
p=n; // replace probability array
}
C.WriteLine(p[D[0][0]-48]); // output result
}
}
답변
하스켈, 256 바이트
import Data.List
m=map;v=reverse
a p n x=take n x++(x!!n+p:drop(n+1)x)
l=abs.pred
o[_,n]s=n#(s!!n)$s
n#p=a(11*p/20)(l n).a(9*p/20)(7-(l$7-n)).a(-p)n
b=0:0:0:0:1:b
k(c:w)=(foldl1(.)$m o$v$sort$m(v.read.('[':).(++"]"))w)b!!read c
main=getLine>>=print.k.words
여기에 사용 된 몇 가지 트릭과 함께 매우 골치 아픈 버전이 있습니다.
import Data.List
-- Types to represent the distribution for the canoe's location
type Prob = Double
type Distribution = [Prob]
-- Just for clarity..
type Index = Int
-- An Action describes some change to the probability distribution
-- which represents the canoe's location.
type Action = Distribution -> Distribution
-- Helper to add k to the nth element of x, since we don't have mutable lists.
add :: Index -> Prob -> Action
add n k x = take n x ++ [p] ++ drop (n + 1) x
where p = k + x!!n
-- A trick for going finding the index to the left of n,
-- taking the boundary condition into account.
leftFrom n = abs (n - 1)
-- A trick for getting the other boundary condition cheaply.
rightFrom = mirror . leftFrom . mirror
where mirror = (7 -)
-- Make the action corresponding to a rock at index n.
doRock :: Index -> Action
doRock n p = (goLeft . goRight . dontGoForward) p
where goLeft = (leftFrom n) `add` (p_n * 11/20)
goRight = (rightFrom n) `add` (p_n * 9/20)
dontGoForward = (at n) `add` (-p_n)
p_n = p!!n
at = id
initialProb = [0,0,0,0,1,0,0,0]
-- Parse a pair "3,2" ==> (3,2)
readPair :: String -> (Index,Index)
readPair xy = read $ "(" ++ xy ++ ")"
-- Coordinate swap for the sorting trick described below.
swap (x,y) = (y,x)
-- Put it all together and let it rip!
main = do
input <- getLine
let (idx : pairs) = words input
let coords = reverse . sort $ map (swap . readPair) pairs
let rockActions = map (doRock . snd) coords
let finalProb = (foldl1 (.) rockActions) initialProb
print $ (finalProb !! read idx)
마지막으로 사용한 트릭은 단일 행의 암석이 실제로 무한한 양만큼 분리 된 것처럼 행동 할 수 있다는 것입니다. 다시 말해, 모든 암석에 대한 확률 분포 변환기를 동일한 행의 모든 암석에 동시에 적용하는 것이 아니라 원하는 순서대로 순차적으로 적용 할 수 있습니다. 이 문제는 수평으로 인접한 두 개의 바위가 문제로 인해 허용되지 않기 때문에 작동합니다.
따라서 프로그램은 각 암석의 위치를 암석의 y 좌표로 정렬 된 확률 분포 변환기로 바꿉니다. 그런 다음 변환기는 순서대로 연결되어 초기 확률 분포에 적용됩니다. 그게 다야!
답변
펄 169 바이트
STDIN에서 읽습니다.
$_=<>;s/ (.),(\d+)/$s{$1,$2}=1/eg;/./;$x{4}=1.0;for$y(1..15){for$x(0..7){if($s{$x,$y}){$x{$x-1}+=$x{$x}*($x%7?.55:1);$x{$x+1}+=$x{$x}*($x%7?.45:1);$x{$x}=0}}}print$x{$&}
아주 간단하게, -1 및 8 열을 암시 적으로 사용하여 경계 사례를 부드럽게합니다. 인접한 돌이 없기 때문에 확률은 다음 단계로 안전하게 전파 될 수 있으므로 단일 실행으로 충분합니다.
답변
PHP, 358
가능한 경로와 확률을 결정하기 위해 brainpower를 사용하는 것은 어렵고 아마도 1,000,000 개의 카누 사고를 시뮬레이션하는 것보다 더 많은 코드가 필요할 것입니다. 오, 인류!
define('MX',7);
define('MY',16);
define('IT',1000000);
error_reporting(0);
function roll(){return rand()%100 > 44;}
function drift($rocks,$print=false) {
for($px=4,$py=0;$py<MY;$py++) {
if(isset($rocks[$px][$py])){
if(roll()) $px--;
else $px++;
}
else if($px==0) $px++;
else if($px==MX) $px--;
if($print) {
for($i=0;$i<MX;$i++){
if($i==$px) echo 'x';
else if(isset($rocks[$i][$py])) echo 'o';
else echo '-';
}
echo " $py\n";
}
}
return $px;
}
$input = $argv[1];
$tmp = explode(' ',$input);
$end_target = array_shift($tmp);
$rocks = array();
array_map(function($a) use(&$rocks) {
list($x,$y) = explode(',',$a);
$rocks[$x][$y]=1;
}, $tmp);
$results=array();
for($i=0;$i<IT;$i++) {
$results[drift($rocks)]++;
}
drift($rocks, true); // print an example run
foreach($results as $id=>$result) {
printf("%d %0.2f\n", $id, $result/IT*100);
}
예:
php river.php "4 4,1 5,5 3,3 6,2 9,4 12,3 13,5"
----x-- 0
---xo-- 1
---x--o 2
--xo--- 3
--x---- 4
--x--o- 5
--x---- 6
--x---- 7
--x---- 8
--x---- 9
--x---- 10
--x---- 11
--x---- 12
--x---- 13
--x---- 14
--x---- 15
4 49.53
2 30.18
6 20.29
골프 :
<? function d($r){for($x=4,$y=0;$y<16;$y++){if(isset($r[$x][$y])){if(rand()%100>44)$x--;else $x++;}elseif($x==0)$x++;elseif($x==7)$x--;}return $x;}$t=explode(' ',$argv[1]);$e=array_shift($t);$r=array();array_map(function($a)use(&$r){list($x,$y)=explode(',',$a);$r[$x][$y]=1;},$t);$c=0;for($i=0;$i<1000000;$i++){if(d($r)==$e)$c++;}printf("%.4f", $c/1000000);
이 버전은 예쁜 인쇄를 수행하지 않고 지정된 위치에 카누 착륙의 부동 확률을 출력합니다.
# php river_golf.php "4 4,1 5,5 3,3 6,2 9,4 12,3 13,5"
0.4952
답변
PHP, 274
인생을 살리기 위해 GolfScript를 읽거나 쓸 수는 없지만 @Howard의 제출물을 살펴보면 단순히 백만 카누 사고를 시뮬레이션하는 것보다 더 나은 방향으로 나아갔습니다.
시작 위치에 대한 확률의 배열로 시작하여 바위가 발생할 때마다 그 숫자를 간단히 나눌 수 있습니다.
function psplit($i){ return array(.55*$i,.45*$i); }
function pt($a) {
foreach($a as $p) {
printf("%1.4f ", $p);
}
echo "\n";
}
$input = $argv[1];
$tmp = explode(' ',$input);
$end_target = array_shift($tmp);
$rocks = array();
array_map(function($a) use(&$rocks) {
list($x,$y) = explode(',',$a);
$rocks[$x][$y]=1;
}, $tmp);
$state = array(0,0,0,0,1,0,0,0);
pt($state);
for($y=1;$y<16;$y++){
for($x=0;$x<8;$x++){
if(isset($rocks[$x][$y])){
echo(' o ');
list($l,$r)=psplit($state[$x]);
$state[$x]=0;
$state[$x-1]+=$l;
$state[$x+1]+=$r;
} else { echo ' - '; }
}
echo "\n";
pt($state);
}
출력 예 :
# php river2.php "4 4,1 5,5 3,3 6,2 9,4 12,3 13,5"
0.0000 0.0000 0.0000 0.0000 1.0000 0.0000 0.0000 0.0000
- - - - o - - -
0.0000 0.0000 0.0000 0.5500 0.0000 0.4500 0.0000 0.0000
- - - - - - o -
0.0000 0.0000 0.0000 0.5500 0.0000 0.4500 0.0000 0.0000
- - - o - - - -
0.0000 0.0000 0.3025 0.0000 0.2475 0.4500 0.0000 0.0000
- - - - - - - -
0.0000 0.0000 0.3025 0.0000 0.2475 0.4500 0.0000 0.0000
- - - - - o - -
0.0000 0.0000 0.3025 0.0000 0.4950 0.0000 0.2025 0.0000
- - - - - - - -
0.0000 0.0000 0.3025 0.0000 0.4950 0.0000 0.2025 0.0000
- - - - - - - -
0.0000 0.0000 0.3025 0.0000 0.4950 0.0000 0.2025 0.0000
- - - - - - - -
0.0000 0.0000 0.3025 0.0000 0.4950 0.0000 0.2025 0.0000
- - - - - - - -
0.0000 0.0000 0.3025 0.0000 0.4950 0.0000 0.2025 0.0000
- - - - - - - -
0.0000 0.0000 0.3025 0.0000 0.4950 0.0000 0.2025 0.0000
- - - - - - - -
0.0000 0.0000 0.3025 0.0000 0.4950 0.0000 0.2025 0.0000
- - - - - - - -
0.0000 0.0000 0.3025 0.0000 0.4950 0.0000 0.2025 0.0000
- - - - - - - -
0.0000 0.0000 0.3025 0.0000 0.4950 0.0000 0.2025 0.0000
- - - - - - - -
0.0000 0.0000 0.3025 0.0000 0.4950 0.0000 0.2025 0.0000
- - - - - - - -
0.0000 0.0000 0.3025 0.0000 0.4950 0.0000 0.2025 0.0000
골프 :
<? $t=explode(' ',$argv[1]);$e=array_shift($t);$r=array();foreach($t as $n){list($j,$k)=explode(',',$n);$r[$j][$k]=1;}$s=array(0,0,0,0,1,0,0,0);for($y=1;$y<16;$y++){for($x=0;$x<8;$x++){if(isset($r[$x][$y])){$s[$x-1]+=$s[$x]*.55;$s[$x+1]+=$s[$x]*.45;$s[$x]=0;}}}echo $s[$e];
예제 실행 :
# php river2_golf.php "4 4,1 5,5 3,3 6,2 9,4 12,3 13,5"
0.495