ハンディハーバード

コード2020日7の出現

シミュレータをお試しください！

タスク：Xのどこに解決する.

X = the number of bag types (a.k.a. colors) that can contain at least one shiny gold bag

例入力

light red bags contain 1 bright white bag, 2 muted yellow bags.
dark orange bags contain 3 bright white bags, 4 muted yellow bags.
bright white bags contain 1 shiny gold bag.
muted yellow bags contain 2 shiny gold bags, 9 faded blue bags.
shiny gold bags contain 1 dark olive bag, 2 vibrant plum bags.
dark olive bags contain 3 faded blue bags, 4 dotted black bags.
vibrant plum bags contain 5 faded blue bags, 6 dotted black bags.
faded blue bags contain no other bags.
dotted black bags contain no other bags.

It represents:

ラインごとに異なる袋の色

各色袋の必須内容

第1部

ルールの効果的なデータ構造の考察

可能なアルゴリズムの速度を考慮する

各ラインから重要な情報を抽出する

キャプチャマッチの各リストから辞書を構築する

内部アルゴリズムの考察

ワーキングインサイドアウトアルゴリズムの記述

袋のセットを含むシミュレータを構築する

ルールの効果的なデータ構造の考察

どのように辞書、ハッシュテーブルやオブジェクト?

'light red': ['bright white', 'muted yellow'],
'dark orange': ['bright white', 'muted yellow'],
'bright white': ['shiny gold'],
'muted yellow': ['shiny gold', 'faded blue'],
'shiny gold': ['dark olive', 'vibrant plum'],
'dark olive': ['faded blue', 'dotted black'],
'vibrant plum': ['faded blue', 'dotted black'],
'faded blue': [],
'dotted black': []

私たちが各バッグに続くならば、それは最も深いノードになります.

'light red': ['bright white', 'shiny gold', 'dark olive', 'faded blue', 'dotted black', 'vibrant plum', 'muted yellow'],
'dark orange': ['bright white', 'shiny gold', 'dark olive', 'faded blue', 'dotted black', 'vibrant plum', 'muted yellow'],
'bright white': ['shiny gold', 'dark olive', 'faded blue', 'dotted black', 'vibrant plum'],
'muted yellow': ['shiny gold', 'dark olive', 'dotted black', 'vibrant plum', 'faded blue'],
'shiny gold': ['dark olive', 'faded blue', 'dotted black', 'vibrant plum'],
'dark olive': ['faded blue', 'dotted black'],
'vibrant plum': ['faded blue', 'dotted black'],
'faded blue': [],
'dotted black': []

次に、各キーのリストをチェックするshiny gold :

'light red'
'dark orange'
'bright white'
'muted yellow'

4色は、答えは、指示で与えられたと一致する!
しかし、私のパズル入力は数百行です.
したがって、この正確なアプローチはしばらくかかるかもしれません.

可能なアルゴリズムの速度を考慮する

[Must-do] Parse the list to generate the dictionary
[Yikes!] For each bag, expand its containment list to account for unique new entries from the contents of each bag's containment list
[Look-ups seem fast] For each bag, check if `shiny gold` is in each containment list
[No problem] Return the length of the filtered list

各ラインから重要な情報を抽出する

これは正規表現を必要とする場合があります.

Variations:

light red bags contain 1 bright white bag, 2 muted yellow bags.

bright white bags contain 1 shiny gold bag.

dotted black bags contain no other bags.

公式に関する初期の考え

Quasi-english/regex
/word word bags contain [no other bags|(number word word bags?,? ?)+./g

これを試してみましょうRegexr.com
フラッシュその日の後日に.

私は、全体のパズル入力ストリングにマッチするとき、上記の正規表現を働かせませんでした

それはあまりに貪欲であった-それは第2の部分のための部分文字列のあまりに長い一致

しかし、私は各ラインに範囲内で制限されたときに働くために正規表現を得ました

ここでは、1行あたり2 +グループをキャプチャするために使用した正規表現です.

/(\w+\s\w+)\sbags?/g

キャプチャグループ

1以上の文字

スペースが続く

1以上の文字

その他重要人物

スペースが続く

それから手紙'バッグ'

それから、必要に応じて、' s '

以下のような行になります.

light red bags contain 1 bright white bag, 2 muted yellow bags.

マッチ

light red bags
bright white bag
muted yellow bags

キャプチャ

light red
bright white
muted yellow

キャプチャマッチの各リストから辞書を構築する

Create a dictionary, rules, that starts empty
For each list item - which contains two or more elements: 1. the containing bag, 2. either 'no other' or the first of one or more contained bags, 3. additionally contained bags
  Create a key in rules with the label of the first element
    Set as its value an empty list
  As long as the second element is not 'no other'
    Add each subsequent element to the initially empty list associated with the newly created key

今までの例の入力を使用して、最初に作成したキー値のペアとしてこれを持っています.

'light red': [ 'bright white', 'muted yellow' ]

そして、私がこれから始めた場合

faded blue bags contain no other bags.

今、

'faded blue': []

内部アルゴリズムの考察

私の犬を歩いている間、私はこのパズルを解決するためにはるかに一見遠征の方法を発見した.
私が解決していることを思い出す

私は最終的に含むすべてのバッグの種類のカウントが必要ですshiny gold バッグ

おそらく、この単一の要素リストから始めます.

['shiny gold']

それから、その値の包含のために各々のキーの関連リストをチェックします.
それは私に直接含むすべてのバッグのリストを与えるshiny gold バッグ(別名親バッグ).
例の入力を使用すると、そのリストは次のようになります.

['bright white', 'muted yellow']

それから、それぞれのキーの関連リストをチェックします.
それは私にすべてのバッグのリストを与えるgrandparents of shiny gold ハンドバッグ.
例の入力を再度使用すると、そのリストは次のようになります.

['light red', 'dark orange']

それから、それぞれのキーの関連リストをチェックします.
それは私にすべてのバッグのリストを与えるgreat-grandparents of shiny gold ハンドバッグ.
例の入力を再度使用すると、そのリストは次のようになります.

[]

そのリストが空であるので、バッグがどんなものも含むことができないことが現在明らかであるので、私は止まりますgreat-grandparent ハンドバッグ.
今、私は最終的に含めることができる4袋を数えたshiny gold ハンドバッグ.
それは正しい答えだ!

ワーキングインサイドアウトアルゴリズムの記述

Build the dictionary as described earlier

Create a unique set of values, containers, starting with one element: 'shiny gold'
Create another unique set of values, visited, starting empty

Do as long as containers is not empty
  Create a unique set of values, next, starting empty
  For each key-value pair in rules
    If the array associated with the current key contains any of the elements in containers
      Add the key to container, unless it already exists
      Add the key to visited, unless it already exists
  Replace the contents of containers with the unique elements in next

Return the number of unique elements in visited

私が最初にアルゴリズムを書くとき、私が見落とした何かは、第2のユニークなリストなしでそれでしたvisited , アルゴリズムは二重コンテナであった.
このアルゴリズムがすぐ近くに走るのを見るのはすばらしい感じだった.

袋のセットを含むシミュレータを構築する

これは全く時間がなかった

一つの文字列要素で配列を結合するのは、2つ以上の文字列要素を持つ配列を結合するのとは違って動作することを教えてくれました.つ以上で、それは各々のストリングに加わります.望ましい

それは楽しさと洞察力をどのように検索リストの変更と訪問したリストが表示されます

Try the simulator for Part 1

第2部

正規表現の更新

私の規則データ構造の更新

期待したよりも速いアルゴリズムアルゴリズムを書く

シミュレータの出力を元に戻す

正規表現の更新

パート1からの私のregexは以下のように見えました:

/(\w+\s\w+)\sbags?/g

以下のような行になります.

light red bags contain 1 bright white bag, 2 muted yellow bags.

撮影

light red
bright white
muted yellow

これをキャプチャする必要があります.

? light red
1 bright white
2 muted yellow

パート2のための私のregexは、数字を捕えて、任意の桁とスペースをprependsします:

// Part 1:
/(\w+\s\w+)\sbags?/g

// Part 2:
/(\d)?\s?(\w+\s\w+)\sbags?/g

以下のような行になります.

light red bags contain 1 bright white bag, 2 muted yellow bags.

キャプチャ

(nothing, light red)
(1, bright white)
(2, muted yellow)

私の規則データ構造の更新

第1部では、私の規則の辞書は、各バッグの種類のためのキーを特色にし、値はそのバッグに含まれている各バッグの種類で満たされたリストだった.

light red bags contain 1 bright white bag, 2 muted yellow bags.

'light red': ['bright white', 'muted yellow']

第2部では、私の規則の辞書は、各バッグの種類のキーを備え、値は、各バッグの種類とそのバッグの種類の必要な数である値のキーを持つ辞書です

light red bags contain 1 bright white bag, 2 muted yellow bags.

'light red': { 'bright white': 1, 'muted yellow': 2 }

期待したよりも速いアルゴリズムアルゴリズムを書く

私のアルゴリズムはrecursion とreducer 必要な袋の正しい合計数を生成します.

Sub-routine - Count Bags In (bag):
  Expect one parameter, a string
  If the object associated with the key in rules that matches bag is empty (meaning it contains 'no other bags')
    Return 0
  Else
    Generate a list of entries derived from the object where each item in the list contains the bag type in location 1 and the bag quantity in location 2
      For each item in the derived list
        Accumulate a number - starting at 0
          Increment the number by this amount:
            The sum of the count associated with the current bag plus
            And the product of the same count and the result of calling this sub-routine on the current bag's key (a.k.a. 2-word type)

Return the resulting number from calling the sub-routine with 'shiny gold'

シミュレータの出力を元に戻す

私は私の再帰アルゴリズムをシミュレートする方法がわからなかった

代わりに、私は私の累積方程式の文字列を生成し、ボタンをクリックして

この例のように入力された式は次のようになります.

(1 + 1 * (3 + 3 * 0) + (4 + 4 * 0)) + (2 + 2 * (5 + 5 * 0) + (6 + 6 * 0))

2番目の例では、

shiny gold bags contain 2 dark red bags.
dark red bags contain 2 dark orange bags.
dark orange bags contain 2 dark yellow bags.
dark yellow bags contain 2 dark green bags.
dark green bags contain 2 dark blue bags.
dark blue bags contain 2 dark violet bags.
dark violet bags contain no other bags.

以下のようになります.

(2 + 2 * (2 + 2 * (2 + 2 * (2 + 2 * (2 + 2 * (2 + 2 * 0))))))

このパズルを通して私の成果を祝う

正直に言うと、私は1年前にこのパズルの指示を読みました

その時、私はこのパズルに感銘を受けました

私は、パート1を解決しようとさえしませんでした

今回は、第1部では

私は慎重に指示を読む

私は書いたregular expression 複雑な鎖の代わりにsplit() 解析するために必要な入力文字列の部分を抽出する文

私はSet JavaScriptのデータ型は、配列内の重複をチェックするために複雑なコードを書く代わりに、一意の値だけでリストを活用する

私はfor..in とternary 私のコードをよりエレガントで簡潔にする操作

私は、それが終わるのが永遠にかかるように思えた1つのアルゴリズム的アプローチを考慮しました

私は自分自身が他のアルゴリズム的アプローチを考える時間を許しました

私は、書くことが簡単で、正解で終わるのが速いという別の方法を発見しました

それで、私は第1部を解決しました!

パート2 :

私はその例と方程式を密接に研究し、勝利式を抽出した

私は私のregular expression

使用するrecursion

使用するObject.entries() キー値ペアを2つの項目のリストに変換するには

使用するreduce よりエレガントかつ簡潔に1つのコンパクトステートメントで正しい答えを生成する

私は完全にそれを実行する前に私のアルゴリズムでメインサブルーチンを書いた.唯一の期待として働い発見!

それで、私は2部を解決しました!

私がここで成し遂げたことは信じられない感じです。

私は多くのこれらのパズルを完了から学んだ

私は、Performance解決をつくるために直観力を使うことができるということを証明しています

私は、正規表現、再帰と機能的プログラミングのような高度なコンピューターサイエンス技術のより良い理解を示しています