導(dǎo)入

コードの出現(xiàn)から 5 日目ですが、今日はページの順序付けという興味深い問題があります。この問題と、私がどのようにそれに取り組んだのかを見ていきましょう。冷靜に考えれば非常に単純な問題ですが、そうでないとマップ、リスト、インデックスが混亂してしまいます。

ここ GitHub で私のソリューションをチェックできます。

入力

5 日目の入力には 2 つのセクションがあります。最初のセクションでは、ページの順序付けのルール、具體的にはどのページをどのページの前に置くかを定義し、2 番目のセクションには実際のページの順序が含まれます。

47|53
97|13
97|61
97|47
75|29
61|13
75|53
29|13
97|29
53|29
61|53
97|53
61|29
47|13
75|47
97|75
47|61
75|61
47|29
75|13
53|13

75,47,61,53,29
97,61,53,29,13
75,29,13
75,97,47,61,53
61,13,29
97,13,75,29,47

最初のセクションにはマッピングされたルールがあり、もう 1 つのセクションにはページの順序があり、各行は処理する実際のデータとしてのクエリまたはページのリストです。パート 1 と 2 の処理で使用する必要があります。

読書セクション

したがって、これらのセクションを解析し、アクセスしやすいデータ構(gòu)造で読み取る必要があります。

そのための 1 つの方法は次のとおりです

• 2 つのセクションからなるリスト

• 最初のセクションはリストになります

  • リストは 2 つの整數(shù)を保持するための整數(shù)のリスト、つまりルール用です

• 2 番目のセクションはリストになります

  • リストはページリストを保持する整數(shù)のリストになります

したがって、データ構(gòu)造は整數(shù)のリストのリストのリストのようになります。

func ReadFileSections(path string) [][][]int {

    fileBytes := ReadFileBytes(path)
    lines := []string{}
    separator := []byte("\n\n")
    for _, line := range bytes.Split(fileBytes, separator) {
        if string(line) != "" {
            lines = append(lines, string(line))
        }
    }

    sections := [][][]int{}
    for i, section := range lines {
        nums := [][]int{}
        lineStrs := strings.Split(section, "\n")
        separator := ","
        if i == 0 {
            separator = "|"
        }
        for _, lineStr := range lineStrs {
            if lineStr == "" {
                continue
            }
            numL := []int{}
            for _, numStr := range strings.Split(lineStr, separator) {
                num, _ := strconv.Atoi(numStr)
                numL = append(numL, num)
            }
            nums = append(nums, numL)
        }
        sections = append(sections, nums)
    }
    return sections
}

ReadFileSections と呼ばれる上記の関數(shù)は、入力ファイルへのパスを受け取り、説明したように整數(shù)のリストのスライス/配列を返します。まずファイルを読み取り、バイトをセクションの區(qū)切りとなる 2 つの改行文字に分割します。行を文字列のリストとして保存します。最初の行にはルール行が含まれ、2 番目の行にはページ リスト行が含まれます。

次に、セクションを反復(fù)処理し、それぞれの區(qū)切り文字を使用してセクションの個々の行を個別に分割します。つまり、 |最初のセクションには (空白) が 2 番目のセクションに使用されます。各行を解析して整數(shù)のリストを取得し、それらをそれぞれのセクションに追加します。

これで、問題の処理に役立つルールとページの構(gòu)築に使用できるデータが得られました。

ルールの構(gòu)築

ここで、アクセスしやすいようにルール リストを処理する必要があります。特定のページの後に表示されるページ番號を取得する必要があるため、整數(shù)のリストを持つ整數(shù)のマップを使用します。キーは次のとおりです。最初の番號と値の 1 つは 2 番目の番號 (ページ順で後に表示される番號) になります。

func ConstructRules(rulesList [][]int) map[int][]int {
    rules := make(map[int][]int)
    for _, rule := range rulesList {
        rules[rule[0]] = append(rules[rule[0]], rule[1])
    }
    return rules
}

単純に整數(shù)のリストを反復(fù)処理し、リスト內(nèi)の最初の要素をキーとして、値を 2 番目の要素としてマップします。これにより、次のことが視覚化されます。

FROM

[][]int

[
    [47,53]
    [97,13]
    [97,61]
]

TO

map[int][]int
{
    47: [53]
    97: [13,61]
}

それで、ルールを整數(shù)と整數(shù)のマップとして作成しました。

インデックスの構(gòu)築

ここで、最初と 2 番目の部分を簡単にするために、ページ リストに表示されるインデックスを使用して、ルール セクションの各番號のマップを作成する必要があります。

そこで、整數(shù)と整數(shù)のマップであるルールを反復(fù)処理し、ルールから一意の整數(shù)リストを作成するのに役立つ整數(shù)のマップを作成します。

ルールから整數(shù)のリストを取得したら、すべての數(shù)値を反復(fù)処理し、ページの各行で、どのインデックスが表示されるかを確認(rèn)して、整數(shù) (インデックス) のリストを作成します。

そこで、ページの行にあるすべての數(shù)値を反復(fù)処理します。ページのリストでその數(shù)値が見つかった場合はインデックスを追加しますが、見つからなかった場合は -1 を追加します。したがって、各行について次のようにします。次のようにその番號にインデックスを追加する必要があります:

47|53
97|13
97|61
97|47
75|29
61|13
75|53
29|13
97|29
53|29
61|53
97|53
61|29
47|13
75|47
97|75
47|61
75|61
47|29
75|13
53|13

75,47,61,53,29
97,61,53,29,13
75,29,13
75,97,47,61,53
61,13,29
97,13,75,29,47

上記の例では、參照として 75 を取得し、ページ番號の各リストのインデックスを取得し、75 が出現(xiàn)するインデックスのリストを取得します。

これは次の関數(shù)で実行できます:

func ReadFileSections(path string) [][][]int {

    fileBytes := ReadFileBytes(path)
    lines := []string{}
    separator := []byte("\n\n")
    for _, line := range bytes.Split(fileBytes, separator) {
        if string(line) != "" {
            lines = append(lines, string(line))
        }
    }

    sections := [][][]int{}
    for i, section := range lines {
        nums := [][]int{}
        lineStrs := strings.Split(section, "\n")
        separator := ","
        if i == 0 {
            separator = "|"
        }
        for _, lineStr := range lineStrs {
            if lineStr == "" {
                continue
            }
            numL := []int{}
            for _, numStr := range strings.Split(lineStr, separator) {
                num, _ := strconv.Atoi(numStr)
                numL = append(numL, num)
            }
            nums = append(nums, numL)
        }
        sections = append(sections, nums)
    }
    return sections
}

これで、ルールに基づいて各ページ番號リストにインデックスがマッピングされました。

パート 1

パート 1 では、各ページ更新 (行) を反復(fù)する必要があります。次に、ページ番號がルールに従っているかどうかを確認(rèn)する必要があります。各番號はルールに従っている必要があります。これは、番號が特定の番號の後であるが、ルールでは前にあるべきであると規(guī)定されている場合、その更新でページ番號付けルールに違反しているため、それを正しい順序のページと見なすことができず、中央のページを追加する必要があることを意味します。パート 1 の回答として正しく順序付けされた各更新の番號。

これを行うには、各ページ更新を反復(fù)し、次にそのページ更新の各數(shù)値を反復(fù)する必要があります。その數(shù)値 (現(xiàn)在の數(shù)値と呼ぶことにします) に関連付けられたすべてのルールを取得します。整數(shù)のリストを含む整數(shù)のマップ。ここで、現(xiàn)在いる番號がそのルールの番號より前であるかどうかを確認(rèn)する必要があります。そこで、作成した數(shù)値インデックス (整數(shù)のリストをインデックスとして持つ數(shù)値のマップ) を使用して、現(xiàn)在の數(shù)値のインデックスを確認(rèn)します。したがって、現(xiàn)在の番號をマップのキーとして使用し、リスト內(nèi)のインデックスを現(xiàn)在いる行/ページの更新數(shù)としてマップのインデックスのリストを取得します。

現(xiàn)在の番號のインデックスを取得したら、そのルール內(nèi)のすべての番號である 2 番目の番號についても同じものを取得します。また、ルール內(nèi)のその番號がそのページ行/更新に存在するかどうか、つまり、 -1 ではなく、その場合は、同様にそのインデックスを取得し、ルールに従って現(xiàn)在の番號の後に出現(xiàn)するかどうかを確認(rèn)します。したがって、番號がルールに違反している場合は、ページの更新を正しくないものとしてマークする必要があります。注文します。

そのページ更新のインデックス ルールに違反していることがわかったので、注文を false としてマークします。順序付きフラグがまだ true であることが確認(rèn)された場合は、そのページ更新の中央の要素でスコアを更新します。

func ConstructRules(rulesList [][]int) map[int][]int {
    rules := make(map[int][]int)
    for _, rule := range rulesList {
        rules[rule[0]] = append(rules[rule[0]], rule[1])
    }
    return rules
}

繰り返しになりますが、整數(shù)のリストを含む整數(shù)のマップとしてルールと番號のインデックスを備えた GetOrderedPage という関數(shù)と、ページ更新としての整數(shù)のリストであるページを作成します。この関數(shù)の出力としてスコアを返します。

各ページの更新を繰り返し、更新內(nèi)の各ページ番號でその番號のルールを確認(rèn)し、その番號のインデックスが現(xiàn)在の番號より小さい場合は、その番號を順序付けされていないとしてマークします。順序が正しければ、各ページ更新の最後にページ更新の中央要素でスコアを更新します。

これがパート 1 の要約になります。必要なのは、正しい順序で更新されたページのスコアを取得することだけです。

パート 2

パート 2 では、ページの更新が適切に行われているかどうかを確認(rèn)する必要があり、そうでない場合は、順番に更新する必要があります。

パート 2 でも同様のことを行います。各ページ更新を繰り返す必要があります。また、そのページ更新の各數(shù)値について、ルールに違反しているかどうかを確認(rèn)する必要があります。任意の數(shù)でルールに違反している場合は、順序付けられたフラグを false としてマークし、これをページ更新の順序を修正するために使用します。そのページ行/更新のページを更新した後、修正されたページ更新順序の中間要素でスコアを追加する必要があります。

47|53
97|13
97|61
97|47
75|29
61|13
75|53
29|13
97|29
53|29
61|53
97|53
61|29
47|13
75|47
97|75
47|61
75|61
47|29
75|13
53|13

75,47,61,53,29
97,61,53,29,13
75,29,13
75,97,47,61,53
61,13,29
97,13,75,29,47

ページ行またはページ更新とルールを取り込む CorrectPageOrder 関數(shù)を?qū)g裝する必要があります。すべてのルールに従うページを設(shè)定する新しいページ更新を作成する必要があります。

そこで、まず初期化された要素のインデックスを追跡し、その前に要素を移動する必要がある場合はインデックスを更新します。

そこで、ページ更新のすべての數(shù)値を反復(fù)処理し、ルール內(nèi)の數(shù)値の前にインデックスを設(shè)定します。ルール マップ內(nèi)でそのような數(shù)値が見つかった場合は、その數(shù)値のインデックスでインデックスを更新する必要があります。

要素の交換先のインデックスを取得したら、そのインデックスの前にスライスを作成してその番號をそれに追加し、そのインデックスの後にすべてを追加します。

func ReadFileSections(path string) [][][]int {

    fileBytes := ReadFileBytes(path)
    lines := []string{}
    separator := []byte("\n\n")
    for _, line := range bytes.Split(fileBytes, separator) {
        if string(line) != "" {
            lines = append(lines, string(line))
        }
    }

    sections := [][][]int{}
    for i, section := range lines {
        nums := [][]int{}
        lineStrs := strings.Split(section, "\n")
        separator := ","
        if i == 0 {
            separator = "|"
        }
        for _, lineStr := range lineStrs {
            if lineStr == "" {
                continue
            }
            numL := []int{}
            for _, numStr := range strings.Split(lineStr, separator) {
                num, _ := strconv.Atoi(numStr)
                numL = append(numL, num)
            }
            nums = append(nums, numL)
        }
        sections = append(sections, nums)
    }
    return sections
}

したがって、この関數(shù)は數(shù)値のインデックスを見つけて、その數(shù)値のルールに違反しないように最も左端 (リストの先頭) に配置します。その後、その數(shù)値を前に追加するスライスを作成します。そのインデックスを作成し、そのインデックスの後にすべてを追加します。

パート 2 はここまでです。ページの順序に矛盾があった場合は、ページの順序を更新しました。

ここ GitHub で私のソリューションをチェックできます。

結(jié)論

Golang の Advent of Code の 5 日目は以上です。何か提案があれば、またどのようにアプローチしたかを教えてください。何か良い解決策はありますか?

ハッピーコーディング:)

以上がCode ay n Golang の出現(xiàn): ページの注文の詳細(xì)內(nèi)容です。詳細(xì)については、PHP 中國語 Web サイトの他の関連記事を參照してください。