태그 보관물: graph-theory

graph-theory

익스트림 화이트 워터 카누 개척하기로 결정했습니다. 그러나 카누의 측면에는 프로그램을 작성할

당신은 상당히 빠른 급류 강 아래로 카누를 젓고 있습니다. 갑자기 외륜이 터지고 외륜이없이 급류를 밟아 위험한 상황에 처하게됩니다. 운 좋게도 여전히 프로그래밍 기술을 보유하고 있으므로 카누 옆에 급류에서 살아남을 수 있도록 프로그램을 개척하기로 결정했습니다. 그러나 카누의 측면에는 프로그램을 작성할 표면적이 많지 않으므로 가능한 짧게 프로그램을 작성해야합니다.

강은 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