LeetCode 18. 4Sum
LeetCode Problem No.18
No.17 is here
18. 4Sum
Given an array nums of n integers, return an array of all the unique quadruplets [nums[a], nums[b], nums[c], nums[d]] such that:
- 0 <= a, b, c, d < n
- a, b, c, and d are distinct.
- nums[a] + nums[b] + nums[c] + nums[d] == target
You may return the answer in any order.
Example 1:
Input: nums = [1,0,-1,0,-2,2], target = 0
Output: [[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]]
Example 2:
Input: nums = [2,2,2,2,2], target = 8
Output: 2,2,2,2
Code 1
object Solution { def fourSum(nums: Array[Int], target: Int): List[List[Int]] = { nums.sorted.combinations(4).flatMap(x => if(x.sum == target) Some(x.toList) else None).toList } }
Methods
Make all combinations and check sum.
Results
Memory Limit Exceeded 241 / 294 testcases passed
Code 2
object Solution { def fourSum(nums: Array[Int], target: Int): List[List[Int]] = { val sorted = nums.sorted val length = nums.length var result = List.empty[List[Int]] for ( i <- 0 until length - 3 if !(i > 0 && sorted(i - 1) == sorted(i)) && (sorted(i).toLong + sorted(length - 1) + sorted(length - 2) + sorted(length - 3) >= target) && (sorted(i).toLong + sorted(i + 1) + sorted(i + 2) + sorted(i + 3) <= target) ) { val a = sorted(i).toLong for ( j <- i + 1 until length - 2 if !(j > i + 1 && sorted(j - 1) == sorted(j)) && (a + sorted(j) + sorted(length - 1) + sorted(length - 2) >= target) && (a + sorted(j) + sorted(j + 1) + sorted(j + 2) <= target) ) { val b = sorted(j).toLong var left = j + 1 var right = length - 1 while (left < right) { val c = sorted(left).toLong val d = sorted(right).toLong val sum = a + b + c + d if (sum == target) { result = List(a.toInt, b.toInt, c.toInt, d.toInt) +: result left += 1 right -= 1 while (left < right && sorted(left) == c) left += 1 while (left < right && sorted(right) == d) right -= 1 } else if (sum < target) { left += 1 } else { right -= 1 } } } } result } }
Methods
- Sort given array.
- Fix two elements (a, b)
- Find remaining two elements (c, d)
- Skip equal values
Results
Runtime 32ms Beats100.00%
Memory 61.61MB Beats28.57%
Code 3
import scala.util.control.Breaks._ object Solution { def fourSum(nums: Array[Int], target: Int): List[List[Int]] = { val sorted = nums.sorted val length = nums.length var result = List.empty[List[Int]] breakable { for(i <- 0 until length-3) { if(i > 0 && sorted(i-1) == sorted(i)) { } else { val i_max = sorted(i).toLong + sorted(length-1) + sorted(length-2) + sorted(length-3) val i_min = sorted(i).toLong + sorted(i+1) + sorted(i+2) + sorted(i+3) if(i_min > target) break() if(i_max < target) { } else { val a = sorted(i).toLong breakable { for(j <- i+1 until length-2) { if(j > i+1 && sorted(j-1) == sorted(j)) { } else { val j_max = a + sorted(j) + sorted(length-1) + sorted(length-2) val j_min = a + sorted(j) + sorted(j+1) + sorted(j+2) if(j_min > target) break() if(j_max < target) { } else { val b = sorted(j).toLong var left = j+1 var right = length-1 while(left < right) { val c = sorted(left).toLong val d = sorted(right).toLong val sum = a+b+c+d if(sum == target) { result = List(a.toInt, b.toInt, c.toInt, d.toInt) +: result left = left + 1 right = right - 1 while(left < right && sorted(left) == c) left = left + 1 while(left < right && sorted(right) == d) right = right - 1 } else if(sum < target) { left = left + 1 } else { right = right - 1 } } } } } } } } } } result } }
Methods
- Use breakable instead of for-guard
Results
Runtime 25ms Beats100.00%
Memory 61.97MB Beats21.43%
aws_cloudwatch_event_ruleのstateでデフォルト値が反映されないパターン
tl;dr
- aws_cloudwatch_event_ruleの
state引数を"DISABLED"にした後、設定から削除してもルールは"DISABLED"のまま。 - 設定を削除した場合、管理が放棄されるのみでデフォルト値は適用されない
事象
aws_cloudwatch_event_ruleリソースでCloudWatch Event Ruleを管理する際、以下の状況に遭遇した。
初期設定で、ルールの状態を明示的に無効化するため、
state = "DISABLED"と記述し、terraform applyを実行した。resource "aws_cloudwatch_event_rule" "example" { name = "my-event-rule" description = "My example event rule" event_pattern = jsonencode({ source = ["aws.s3"] }) state = "DISABLED" # ここでDISABLEDに設定 }state引数のデフォルト値は"ENABLED"であるため、ルールを有効化する意図でstate引数を削除した。resource "aws_cloudwatch_event_rule" "example" { name = "my-event-rule" description = "My example event rule" event_pattern = jsonencode({ source = ["aws.s3"] }) // state引数を削除 }この状態で
terraform applyを実行したが、ルールは無効("DISABLED")のままだった。
原因
Terraformが一度管理した引数を設定ファイルから削除した場合の挙動にある。
- デフォルト値の適用タイミング: Terraformの引数におけるデフォルト値は、その引数を設定ファイルに明示的に記述しなかった場合にのみ適用される。
- 管理の放棄: 一度
state = "DISABLED"と明示的に記述してterraform applyを実行すると、Terraformはaws_cloudwatch_event_ruleのstate属性を管理対象として認識する。その後、設定ファイルからstate引数を削除した場合、Terraformは「もうこのstate属性はTerraformの設定で管理しない」と判断し、その属性に対する変更操作を行わない。 - 既存状態の維持: 結果として、AWS上に存在するCloudWatch Event Ruleの
stateは、以前に"DISABLED"に設定された状態のまま維持される。Terraformは、設定ファイルに記述されていない属性については、AWS上の既存の状態を変更しようとしないため、デフォルト値に戻ることはない。
これは、Terraformが「設定ファイルに記述された状態」にAWSリソースを収束させようとする性質から生じる挙動だ。設定ファイルに存在しないものは、Terraformの管理外となるため、既存の状態が温存される。
解決方法
state引数のデフォルト値が"ENABLED"であっても、DISABLEDからENABLEDへ戻したい場合は、明示的にstate = "ENABLED"と記述し、terraform applyを実行する必要があった。
resource "aws_cloudwatch_event_rule" "example" { name = "my-event-rule" description = "My example event rule" event_pattern = jsonencode({ source = ["aws.s3"] }) state = "ENABLED" # 明示的にENABLEDに設定 }
詳解
Terraformのでリソースを定義する際、Optionalな引数（記述しなくてもよい引数）やComputedな引数（Terraformの実行中にAWSから値が返される引数）の扱いに注意が必要。
aws_cloudwatch_event_ruleにおけるstate引数では、
- 定義時: ドキュメントの記載上、
stateはOptionalであり、デフォルト値は"ENABLED"。- 初回デプロイで
stateを省略した場合 →ENABLED - 初回デプロイで
state = "DISABLED"と記述した場合 →DISABLED
- 初回デプロイで
- 更新時: 一度Terraform Stateファイルに
state = "DISABLED"という情報が記録されると、Terraformは次回以降のterraform planやterraform applyで、この値を管理対象として比較する。- 設定ファイルから
stateを削除 Terraformは設定ファイルにstateの記述がないため、stateに関する変更は「計画」されない。Terraform Stateファイルに記録されているstateの値と、AWS上の実際のstateの値が合致しているため、「変更なし」と判断される。結果として、AWS上のルールはDISABLEDのまま。 - 設定ファイルを
state = "ENABLED"に変更 Terraformは設定ファイル上のstate = "ENABLED"と、Terraform Stateファイルに記録されているstate = "DISABLED"を比較し、差分を検出する。この差分を解消するため、AWS上のルールをENABLEDに更新する「計画」を立て、apply時に実行する。
- 設定ファイルから
Terraformは「最終的にどういう状態になってほしいか」を宣言するツールであり、その宣言から外れたものは管理対象外となる。デフォルト値は「宣言を省略した場合の便宜的な値」であり、一度明示的に宣言したものを後で削除しても、Terraformは「以前の宣言状態に戻れ」とは指示しない。
「デフォルト値」と「管理対象からの離脱」の概念の理解が浅かった。
direnvで.envrcに設定した環境変数が読み込まれない場合
tl;dr
- シェル設定ファイルの
direnv hookの設定を確認- ex).
.bashrcや.zshrcを確認
- ex).
事象
原因
シェル設定ファイルにhookする設定の追加が漏れていた。
解決方法
手元の環境はzshなので、.zshrcにeval "$(direnv hook zsh)"を追加することで、direnvが正常に機能するようになった。
詳解
direnv hookはdirenvをシェルに統合するためのコマンドで、各shに対する初期化スクリプトのコードを出力する。このコードが実行されることで、direnvが自動的に動作し、環境変数のロード・アンロードを行う。
zshの場合のdirenv hookの出力
_direnv_hook() { trap -- '' SIGINT eval "$("/Users/hoge/.asdf/installs/direnv/2.34.0/bin/direnv" export zsh)" trap - SIGINT } typeset -ag precmd_functions if (( ! ${precmd_functions[(I)_direnv_hook]} )); then precmd_functions=(_direnv_hook $precmd_functions) fi typeset -ag chpwd_functions if (( ! ${chpwd_functions[(I)_direnv_hook]} )); then chpwd_functions=(_direnv_hook $chpwd_functions) fi
_direnv_hook関数
direnvを呼び出し、環境変数を更新する。
1行目のtrapでSIGINTを無視し、処理中に中断されないようにしている。
direnv export zshで.envrcを読み込み、3行目のtrapでSIGINTに対する処理をデフォルトに戻している。
precmd_functions
precmd_functionsに_direnv_hookが含まれない場合、precmd_functionsに追加。
こうすることで、プロンプトが表示される直前に_direnv_hookが実行される。
chpwd_functions
chpwd_functionsに_direnv_hookが含まれない場合、chpwd_functionsに追加。
こうすることで、カレントディレクトリが変更された場合に_direnv_hookが実行される。
Warpのショートカットが反応しない問題
Pythonのcsvモジュールの挙動とRFC4180
出力されたCSVファイルでカンマズレが発生する事象の調査をしたときの小ネタな話
事象
CSVファイルでカンマ「,」を含むデータがカンマの位置で分割され、かつ、カンマが増殖していた
ex.)
山田,太郎
が、
,山田,,太郎,
に変換されていた
原因
原因自体はとても単純で以下のような誤設定だった
csv.writer(delimiter=',', quotechar=',', quoting=csv.QUOTE_MINIMAL)
本来は「"」が設定されるはずのquotecharが「,」になっていたため、delimiterである「,」を含むフィールドが「,」でクオートされてしまい、文字列の先頭・末尾に「,」が付加されていた。
しかし、ここでもう一つ謎なのが、文字列中に含まれた「,」が「,,」になっていたこと。
csvモジュールのドキュメントを読んで行くと、以下のような仕様が記述されていました。
Dialect.doublequote
以下引用
フィールド内に現れた quotechar のインスタンスで、クオートではないその文字自身でなければならない文字をどのようにクオートするかを制御します。 True の場合、この文字は二重化されます。 False の場合、 escapechar は quotechar の前に置かれます。デフォルトでは True です。
doublequoteのデフォルトはTrueなのでデフォルトの挙動ではquotecharはquotecharでエスケープされるということ。
ちなみに doublequoteをFalseに設定するとescapechar(デフォルトは「\」)でエスケープされる。
ダブルクオートでエスケープするという慣れ親しんだエスケープと異なる挙動で混乱しますが、これにより文字列中に含まれた「,」がquotecharである「,」でエスケープされ「,,」になっていたことがわかりました。
気になったのでさらにCSVの仕様について調べると、以下の記述を見つけました。
RFC4180
2. Definition of the CSV Formatより以下引用
7. If double-quotes are used to enclose fields, then a double-quote appearing inside a field must be escaped by preceding it with another double quote. For example:
"aaa","b""bb","ccc"
ダブルクオートで囲まれるフィールドの中にダブルクオートが含まれる場合、ダブルクオートはダブルクオートでエスケープされる、となっていました。
ダブルクオートでのエスケープはCSVの御作法だったようです。
もろもろ話をまとめると、
クオート文字が「,」に設定されていたため、「,」を含むフィールドが「,」で囲まれ、かつ、フィールド内の「,」がクオート文字の「,」でエスケープされ「,,」になった
ということで、quotecharを「"」にすることで、期待通りの挙動になりました。(quotecharのデフォルトは「"」なので、quotechar指定を省略してもOK)
Amazon EventBridgeのcron expressionで最終日(月末/週末)指定がValidationExceptionになる問題
事象
毎月14日および月末日2日前の1:00 のようなたルールを登録する場合、ValidationExceptionでエラーとなる
> aws events put-rule --schedule-expression "cron(0 1 14,L-2 * ? *)" --name samplerule1 An error occurred (ValidationException) when calling the PutRule operation: Parameter ScheduleExpression is not valid.
原因
末日(週末日や月末日)を表すLワイルドカードは、同じくDay-of-monthフィールドに指定している,(カンマ)と併用が不可
ちなみに-(ダッシュ)とも併用できないことを確認
> aws events put-rule --schedule-expression "cron(0 1 10-L-2 * ? *)" --name samplerule1 An error occurred (ValidationException) when calling the PutRule operation: Parameter ScheduleExpression is not valid.
対策
単一のルールでは登録できないので、ルールを分割することで対応した
> aws events put-rule --schedule-expression "cron(0 1 14 * ? *)" --name samplerule1 > aws events put-rule --schedule-expression "cron(0 1 L-2 * ? *)" --name samplerule2
