Google Foobar Challenge DoomsdayFuelに合格しなかった非表示のテストケース[終了]

3
Guy Wilks 2020-05-06 04:22.

私はGoogleFoobarチャレンジに取り組んでおり、現在レベル3チャレンジのDoomsdayFuelにいます。手順は次のとおりです。

終末の燃料

ラムチョップの炉心の燃料を作ることは、関係するエキゾチック物質のためにトリッキーなプロセスです。それは生の鉱石として始まり、処理中にフォーム間でランダムに変化し始め、最終的に安定したフォームに到達します。サンプルが最終的に到達できる安定した形態が複数存在する可能性がありますが、そのすべてが燃料として役立つわけではありません。

ラムダ司令官は、特定の鉱石サンプルの最終状態を予測することにより、科学者が燃料生成効率を高めるのを支援するようにあなたに依頼しました。あなたは、鉱石がとることができるさまざまな構造と、それが受ける遷移を注意深く研究しました。ランダムではありますが、各構造が変換される確率は固定されているようです。つまり、鉱石が1つの状態になるたびに、次の状態(同じ状態になる可能性があります)に入る確率は同じになります。観測された遷移をマトリックスに記録しました。研究室の他の人々は、鉱石がなり得るよりエキゾチックな形を仮定しましたが、あなたはそれらのすべてを見たわけではありません。

その状態が次の状態に移行した回数を表す非負のintの配列の配列を取り、各端末状態のintの配列を返し、各端末状態の正確な確率を与える関数solution(m)を記述します。各状態の分子、最後に最も単純な形式のすべての状態の分母。マトリックスは最大で10x 10です。鉱石がどの状態にあるかに関係なく、その状態から最終状態へのパスがあることが保証されています。つまり、処理は常に最終的に安定した状態で終了します。鉱石は状態0で始まります。分数が定期的に単純化されている限り、分母は計算中に符号付き32ビット整数内に収まります。

>For example, consider the matrix m:
[
  [0,1,0,0,0,1],  # s0, the initial state, goes to s1 and s5 with equal probability
  [4,0,0,3,2,0],  # s1 can become s0, s3, or s4, but with different probabilities
  [0,0,0,0,0,0],  # s2 is terminal, and unreachable (never observed in practice)
  [0,0,0,0,0,0],  # s3 is terminal
  [0,0,0,0,0,0],  # s4 is terminal
  [0,0,0,0,0,0],  # s5 is terminal
]
So, we can consider different paths to terminal states, such as:
s0 -> s1 -> s3
s0 -> s1 -> s0 -> s1 -> s0 -> s1 -> s4
s0 -> s1 -> s0 -> s5
Tracing the probabilities of each, we find that
s2 has probability 0
s3 has probability 3/14
s4 has probability 1/7
s5 has probability 9/14
So, putting that together, and making a common denominator, gives an answer in the form of
[s2.numerator, s3.numerator, s4.numerator, s5.numerator, denominator] which is
[0, 3, 2, 9, 14].

言語

Javaソリューションを提供するには、Solution.javaを編集します。Pythonソリューションを提供するには、solution.pyを編集します。

Test cases
==========
>Your code should pass the following test cases.
Note that it may also be run against hidden test cases not shown here.

>-- Java cases --
Input:
Solution.solution({{0, 2, 1, 0, 0}, {0, 0, 0, 3, 4}, {0, 0, 0, 0, 0}, {0, 0, 0, 0,0}, {0, 0, 0, 0, 0}})
Output:
    [7, 6, 8, 21]

>Input:
Solution.solution({{0, 1, 0, 0, 0, 1}, {4, 0, 0, 3, 2, 0}, {0, 0, 0, 0, 0, 0}, {0, 0, 0, 0, 0, 0}, {0, 0, 0, 0, 0, 0}, {0, 0, 0, 0, 0, 0}})
Output:
    [0, 3, 2, 9, 14]

>-- Python cases --
Input:
solution.solution([[0, 2, 1, 0, 0], [0, 0, 0, 3, 4], [0, 0, 0, 0, 0], [0, 0, 0, 0,0], [0, 0, 0, 0, 0]])
Output:
    [7, 6, 8, 21]

>Input:
solution.solution([[0, 1, 0, 0, 0, 1], [4, 0, 0, 3, 2, 0], [0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0]])
Output:
    [0, 3, 2, 9, 14]

>Use verify [file] to test your solution and see how it does. When you are finished editing your code, use submit [file] to submit your answer. If your solution passes the test cases, it will be removed from your home folder.

I have written the following code to solve it:
import java.util.ArrayList;
public class Solution {
    public static int[] solution(int[][] m) {
        double[][] mDouble = toDouble(m);
        //TODO: change the double back into an int
        // GOAL ONE: find Q matrix :
        // 1:seperate the input into two 2d arrays
        ArrayList<double[]> ters = new ArrayList<double[]>();
        ArrayList<double[]> nonTers = new ArrayList<double[]>();
        for(int i = 0; i < mDouble.length; i++){
            boolean isTerminal = true;
            int sum = 0;
            for(int j = 0; j < mDouble[0].length; j++){
                sum += mDouble[i][j];
                if(mDouble[i][j] != 0){
                    isTerminal = false;
                }
            }

            if(isTerminal){
                ters.add(mDouble[i]);
            }else{
                for(int j = 0; j < mDouble[0].length; j++){
                    mDouble[i][j] = mDouble[i][j]/sum;
                }
                nonTers.add(mDouble[i]);
            }
        }
        double[][] terminalStates = new double[ters.size()][m.length];
        double[][] nonTerminalStates = new double[nonTers.size()][m.length];

        for(int i = 0; i < ters.size(); i++){
            terminalStates[i] = ters.get(i);
        }
        for(int i = 0; i < nonTers.size(); i++){
            nonTerminalStates[i] = nonTers.get(i);
        }
        // 2: Plug into a function that will create the 2d array
        double[][] QMatrix = getQMatrix(nonTerminalStates);
        // GOAL TWO: find I matrix
        double[][] IMatrix = makeIMatrix(QMatrix.length);
        //GOAL 3: Find F matrix
        //1: subtract the q matrix from the I matrix
        double[][] AMatrix = SubtractMatrices(IMatrix, QMatrix);
        //2: find the inverse TODO WRITE FUNCTION
        double[][] FMatrix = invert(AMatrix);
        //GOAL 4: multiply by R Matrix
        //1: find r Matrx
        double[][] RMatrix = getRMatrix(nonTerminalStates, terminalStates.length);
        //2: use multiply function to get FR Matrix
        double[][] FRMatrix = multiplyMatrices(FMatrix, RMatrix);
        //GOAL 5: find answer array
        //1: get the one dimensional answer
        double[] unsimplifiedAns = FRMatrix[0];
        //2: get fractions for the answers
        int[] ans = fractionAns(unsimplifiedAns);
        return ans;
    }
    public static int[] fractionAns(double[] uAns){
        int[] ans = new int[uAns.length + 1];
        int[] denominators = new int[uAns.length];
        int[] numerators = new int[uAns.length];
        for(int i = 0; i < uAns.length; i++){
            denominators[i] = (int)(convertDecimalToFraction(uAns[i])[1]);
            numerators[i] = (int)(convertDecimalToFraction(uAns[i])[0]);
        }
        int lcm = (int) lcm_of_array_elements(denominators);
        for(int i = 0; i < uAns.length; i++){
            ans[i] = numerators[i]*(lcm/convertDecimalToFraction(uAns[i])[1]);
        }
        ans[ans.length-1] = lcm;
        return ans;
    }

    static private int[] convertDecimalToFraction(double x){
        double tolerance = 1.0E-10;
        double h1=1; double h2=0;
        double k1=0; double k2=1;
        double b = x;
        do {
            double a = Math.floor(b);
            double aux = h1; h1 = a*h1+h2; h2 = aux;
            aux = k1; k1 = a*k1+k2; k2 = aux;
            b = 1/(b-a);
        } while (Math.abs(x-h1/k1) > x*tolerance);

        return new int[]{(int)h1, (int)k1};
    }   
   public static long lcm_of_array_elements(int[] element_array) 
    { 
        long lcm_of_array_elements = 1; 
        int divisor = 2; 

        while (true) { 
            int counter = 0; 
            boolean divisible = false; 

            for (int i = 0; i < element_array.length; i++) { 

                // lcm_of_array_elements (n1, n2, ... 0) = 0. 
                // For negative number we convert into 
                // positive and calculate lcm_of_array_elements. 

                if (element_array[i] == 0) { 
                    return 0; 
                } 
                else if (element_array[i] < 0) { 
                    element_array[i] = element_array[i] * (-1); 
                } 
                if (element_array[i] == 1) { 
                    counter++; 
                } 

                // Divide element_array by devisor if complete 
                // division i.e. without remainder then replace 
                // number with quotient; used for find next factor 
                if (element_array[i] % divisor == 0) { 
                    divisible = true; 
                    element_array[i] = element_array[i] / divisor; 
                } 
            } 

            // If divisor able to completely divide any number 
            // from array multiply with lcm_of_array_elements 
            // and store into lcm_of_array_elements and continue 
            // to same divisor for next factor finding. 
            // else increment divisor 
            if (divisible) { 
                lcm_of_array_elements = lcm_of_array_elements * divisor; 
            } 
            else { 
                divisor++; 
            } 

            // Check if all element_array is 1 indicate  
            // we found all factors and terminate while loop. 
            if (counter == element_array.length) { 
                return lcm_of_array_elements; 
            } 
        } 
    } 
    public static double[][] toDouble(int[][] ma){
        double[][] retArr = new double[ma.length][ma.length];
        for(int i = 0; i < retArr.length; i++){
            for(int j = 0; j < retArr[0].length; j++){
                retArr[i][j] = (ma[i][j]);
            }
        }
        return retArr;
    }
    public static double[][] getRMatrix(double[][] nonTerminals, int terminalLength){
        double[][] retArr = new double[nonTerminals.length][terminalLength];
        for(int i = 0; i < retArr.length; i++){
            for(int j = nonTerminals.length; j < nonTerminals[0].length; j++){
                retArr[i][j-nonTerminals.length] = (nonTerminals[i][j]);
            }
        }
        return retArr;
    }

    public static double[][] multiplyMatrices(double[][] firstMatrix, double[][] secondMatrix){
        int r1 = firstMatrix.length;
        int c1 = firstMatrix[0].length;
        int c2 = secondMatrix[0].length;
        double[][] product = new double[r1][c2];
        for(int i = 0; i < r1; i++) {
            for (int j = 0; j < c2; j++) {
                for (int k = 0; k < c1; k++) {
                    product[i][j] += firstMatrix[i][k] * secondMatrix[k][j];
                }
            }
        }

        return product;
    }
    public static double[][] inverseMatrix(double[][] Amatrix){
        return null;
    }
    public static double[][] SubtractMatrices(double[][] I, double[][] Q){
        double[][] retArr = new double[I.length][I.length];
        for(int i = 0; i < retArr.length; i++){
            for(int j = 0; j < retArr.length; j++){
                retArr[i][j] = I[i][j]-Q[i][j];
            }
        }
        return retArr;
    }
    public static double[][] getQMatrix(double[][] qArr){
        int size = qArr.length;
        double[][] retArr = new double[size][size];
        for(int i = 0; i < size; i++){
            for(int j = 0; j < size; j++){
                retArr[i][j] = qArr[i][j];
            }
        }
        return retArr;
    }
    public static double[][] makeIMatrix(int size){
        double[][] retArr = new double[size][size];
        for(int i = 0; i < size; i++){
            for(int j = 0; j < size; j++){
                if(i == j){
                    retArr[i][j] = 1;
                }else{
                    retArr[i][j] = 0;
                }
            }
        }
        return retArr;
    }
    public static double[][] invert(double a[][]) 
    {
        int n = a.length;
        double x[][] = new double[n][n];
        double b[][] = new double[n][n];
        int index[] = new int[n];
        for (int i=0; i<n; ++i) 
            b[i][i] = 1;

 // Transform the matrix into an upper triangle
        gaussian(a, index);

 // Update the matrix b[i][j] with the ratios stored
        for (int i=0; i<n-1; ++i)
            for (int j=i+1; j<n; ++j)
                for (int k=0; k<n; ++k)
                    b[index[j]][k]
                            -= a[index[j]][i]*b[index[i]][k];

 // Perform backward substitutions
        for (int i=0; i<n; ++i) 
        {
            x[n-1][i] = b[index[n-1]][i]/a[index[n-1]][n-1];
            for (int j=n-2; j>=0; --j) 
            {
                x[j][i] = b[index[j]][i];
                for (int k=j+1; k<n; ++k) 
                {
                    x[j][i] -= a[index[j]][k]*x[k][i];
                }
                x[j][i] /= a[index[j]][j];
            }
        }
        return x;
    }

// Method to carry out the partial-pivoting Gaussian
// elimination.  Here index[] stores pivoting order.

    public static void gaussian(double a[][], int index[]) 
    {
        int n = index.length;
        double c[] = new double[n];

 // Initialize the index
        for (int i=0; i<n; ++i) 
            index[i] = i;

 // Find the rescaling factors, one from each row
        for (int i=0; i<n; ++i) 
        {
            double c1 = 0;
            for (int j=0; j<n; ++j) 
            {
                double c0 = Math.abs(a[i][j]);
                if (c0 > c1) c1 = c0;
            }
            c[i] = c1;
        }

 // Search the pivoting element from each column
        int k = 0;
        for (int j=0; j<n-1; ++j) 
        {
            double pi1 = 0;
            for (int i=j; i<n; ++i) 
            {
                double pi0 = Math.abs(a[index[i]][j]);
                pi0 /= c[index[i]];
                if (pi0 > pi1) 
                {
                    pi1 = pi0;
                    k = i;
                }
            }

   // Interchange rows according to the pivoting order
            int itmp = index[j];
            index[j] = index[k];
            index[k] = itmp;
            for (int i=j+1; i<n; ++i)   
            {
                double pj = a[index[i]][j]/a[index[j]][j];

 // Record pivoting ratios below the diagonal
                a[index[i]][j] = pj;

 // Modify other elements accordingly
                for (int l=j+1; l<n; ++l)
                    a[index[i]][l] -= pj*a[index[j]][l];
            }
        }
    }


}

すべてのテストケースに合格しますが、2つの隠れたテストケースは見えません。

コードで障害を見つけることができる可能性のあるすべてのテストケースを試しましたが、できません。

コードが失敗するテストケースはありますか?

1 answers

4
Ketan Arora 2020-06-02 15:30.

問題は行にあります

double[] unsimplifiedAns = FRMatrix[0];

上記は、状態0が非終了である場合にのみ当てはまります。

それ以外の場合、出力配列は、最初と最後の要素を「1」として除いて、すべて「0」になります。

Related questions

MORE COOL STUFF

「水曜日」シーズン1の中心には大きなミステリーがあります

「水曜日」シーズン1の中心には大きなミステリーがあります

Netflixの「水曜日」は、典型的な10代のドラマ以上のものであり、実際、シーズン1にはその中心に大きなミステリーがあります.

ボディーランゲージの専門家は、州訪問中にカミラ・パーカー・ボウルズが輝くことを可能にした微妙なケイト・ミドルトンの動きを指摘しています

ボディーランゲージの専門家は、州訪問中にカミラ・パーカー・ボウルズが輝くことを可能にした微妙なケイト・ミドルトンの動きを指摘しています

ケイト・ミドルトンは、州の夕食会と州の訪問中にカミラ・パーカー・ボウルズからスポットライトを奪いたくなかった、と専門家は言う.

一部のファンがハリー・スタイルズとオリビア・ワイルドの「非常に友好的な」休憩が永続的であることを望んでいる理由

一部のファンがハリー・スタイルズとオリビア・ワイルドの「非常に友好的な」休憩が永続的であることを望んでいる理由

一部のファンが、オリビア・ワイルドが彼女とハリー・スタイルズとの間の「難しい」が「非常に友好的」な分割を恒久的にすることを望んでいる理由を見つけてください.

エリザベス女王の死後、ケイト・ミドルトンはまだ「非常に困難な時期」を過ごしている、と王室の専門家が明らかにする 

エリザベス女王の死後、ケイト・ミドルトンはまだ「非常に困難な時期」を過ごしている、と王室の専門家が明らかにする&nbsp;

エリザベス女王の死後、ケイト・ミドルトンが舞台裏で「非常に困難な時期」を過ごしていたと伝えられている理由を調べてください.

セントヘレナのジェイコブのはしごを登るのは、気弱な人向けではありません

セントヘレナのジェイコブのはしごを登るのは、気弱な人向けではありません

セント ヘレナ島のジェイコブズ ラダーは 699 段の真っ直ぐ上る階段で、頂上に到達すると証明書が発行されるほどの難易度です。

The Secrets of Airline Travel Quiz

The Secrets of Airline Travel Quiz

Air travel is far more than getting from point A to point B safely. How much do you know about the million little details that go into flying on airplanes?

Where in the World Are You? Take our GeoGuesser Quiz

Where in the World Are You? Take our GeoGuesser Quiz

The world is a huge place, yet some GeoGuessr players know locations in mere seconds. Are you one of GeoGuessr's gifted elite? Take our quiz to find out!

バイオニック読書はあなたをより速く読むことができますか?

バイオニック読書はあなたをより速く読むことができますか?

BionicReadingアプリの人気が爆発的に高まっています。しかし、それは本当にあなたを速読術にすることができますか?

パンデミックは終わったかもしれないが、Covid-19 は終わっていない

パンデミックは終わったかもしれないが、Covid-19 は終わっていない

2021 年 6 月 8 日にニューヨーク市で開催された covid-19 パンデミックで亡くなった人々の命を偲び、祝うために、ネーミング ザ ロスト メモリアルズが主催するイベントと行進の最中に、グリーンウッド墓地の正門から記念碑がぶら下がっています。週末、ジョー・バイデン大統領は、covid-19 パンデミックの終息を宣言しました。これは、過去 2 年以上にわたり、公の場でそうするための長い列の中で最新のものです。

デビル・イン・オハイオの予告編は、エミリー・デシャネルもオハイオにいることを明らかにしています

デビル・イン・オハイオの予告編は、エミリー・デシャネルもオハイオにいることを明らかにしています

オハイオ州のエミリー・デシャネル みんな早く来て、ボーンズが帰ってきた!まあ、ショーボーンズではなく、彼女を演じた俳優. エミリー・デシャネルに最後に会ってからしばらく経ちました.Emily Deschanel は、長期にわたるプロシージャルな Bones の Temperance “Bones” Brennan としてよく知られています。

ドナルド・トランプはFBIのマー・ア・ラーゴ襲撃映像をリリースする予定ですか?

ドナルド・トランプはFBIのマー・ア・ラーゴ襲撃映像をリリースする予定ですか?

どうやら、ドナルド・トランプに近い人々は、今月初めにFBIによって家宅捜索された彼のMar-a-Lago財産からの映像を公開するよう彼に勧めています. 前大統領はテープを公開するかどうかを確認していませんが、息子はフォックス・ニュースにそうなるだろうと語った.

Andor は、他の Star Wars ショーから大きな距離を置きます。

Andor は、他の Star Wars ショーから大きな距離を置きます。

アンドールの一場面。数十年前、ジョージ・ルーカスがスター・ウォーズのテレビ番組を制作するのを妨げた主な理由は、お金でした。

ケイト・ミドルトンとウィリアム王子は、彼らが子供たちと行っているスパイをテーマにした活動を共有しています

ケイト・ミドルトンとウィリアム王子は、彼らが子供たちと行っているスパイをテーマにした活動を共有しています

ケイト・ミドルトンとウィリアム王子は、子供向けのパズルの本の序文を書き、ジョージ王子、シャーロット王女、ルイ王子と一緒にテキストを読むと述べた.

事故で押しつぶされたスイカは、動物を喜ばせ水分補給するために野生生物保護団体に寄付されました

事故で押しつぶされたスイカは、動物を喜ばせ水分補給するために野生生物保護団体に寄付されました

Yak's Produce は、数十個のつぶれたメロンを野生動物のリハビリ専門家であるレスリー グリーンと彼女のルイジアナ州の救助施設で暮らす 42 匹の動物に寄付しました。

デミ・ロヴァートは、新しいミュージシャンのボーイフレンドと「幸せで健康的な関係」にあります: ソース

デミ・ロヴァートは、新しいミュージシャンのボーイフレンドと「幸せで健康的な関係」にあります: ソース

8 枚目のスタジオ アルバムのリリースに向けて準備を進めているデミ ロヴァートは、「スーパー グレート ガイ」と付き合っている、と情報筋は PEOPLE に確認しています。

Plathville の Kim と Olivia Plath が数年ぶりに言葉を交わすことへようこそ

Plathville の Kim と Olivia Plath が数年ぶりに言葉を交わすことへようこそ

イーサン プラスの誕生日のお祝いは、TLC のウェルカム トゥ プラスビルのシーズン 4 のフィナーレで、戦争中の母親のキム プラスと妻のオリビア プラスを結びつけました。

仕事の生産性を高める 8 つのシンプルなホーム オフィスのセットアップのアイデア

仕事の生産性を高める 8 つのシンプルなホーム オフィスのセットアップのアイデア

ホームオフィスのセットアップ術を極めよう!AppExert の開発者は、家族全員が一緒にいる場合でも、在宅勤務の技術を習得しています。祖父や曽祖父が共同家族で暮らしていた頃の記憶がよみがえりました。

2022 年、私たちのデジタル ライフはどこで終わり、「リアル ライフ」はどこから始まるのでしょうか?

20 年前のタイムトラベラーでさえ、日常生活におけるデジタルおよびインターネットベースのサービスの重要性に驚くことでしょう。MySpace、eBay、Napster などのプラットフォームは、高速化に焦点を合わせた世界がどのようなものになるかを示してくれました。

ニューロマーケティングの秘密科学

ニューロマーケティングの秘密科学

マーケティング担当者が人間の欲望を操作するために使用する、最先端の (気味が悪いと言う人もいます) メソッドを探ります。カートをいっぱいにして 3 桁の領収書を持って店を出る前に、ほんの数点の商品を買いに行ったことはありませんか? あなたは一人じゃない。

地理情報システムの日: GIS 開発者として学ぶべき最高の技術スタック

地理情報システムの日: GIS 開発者として学ぶべき最高の技術スタック

私たちが住んでいる世界を確実に理解するには、データが必要です。ただし、空間参照がない場合、このデータは地理的コンテキストがないと役に立たなくなる可能性があります。

Language