Goでのスタックの実装
概要
Goの標準パッケージにはスタックは含まれていない様です。
そこでスライスを使ってintを格納するスタックを実装してみました。
環境
golang v1.12.5
実装したメソッド
- Push: 値をトップに追加
- Pop: 値をトップから削除して返す
- Peek: トップの値を返す
- Size: サイズを返す
- Empty: 空の場合にtrueを返す
コード
package main import ( "fmt" ) // Stackは[]intのエイリアス type Stack []int // Push adds an element func (s *Stack) Push(v int) { *s = append(*s, v) } // Pop removes the top element and return it func (s *Stack) Pop() (int, error) { if s.Empty() { return 0, fmt.Errorf("stack is empty") } v := (*s)[len(*s)-1] *s = (*s)[:len(*s)-1] return v, nil } // Peek returns the top value func (s *Stack) Peek() (int, error) { if s.Empty() { return 0, fmt.Errorf("stack is empty") } return (*s)[len(*s)-1], nil } // Size returns the length of stack func (s *Stack) Size() int { return len(*s) } // Empty returns true when stack is empty func (s *Stack) Empty() bool { return s.Size() == 0 } // NewStack generates stack func NewStack() *Stack { s := new(Stack) return s } func main() { s := NewStack() s.Push(0) s.Push(1) fmt.Println(*s) // [0 1] fmt.Println(s.Size()) // 2 fmt.Println(s.Empty()) // false if v, err := s.Pop(); err == nil { fmt.Println(v) // 1 } else { fmt.Println(err) os.Exit(1) } fmt.Println(*s) // [0] if v, err := s.Peek(); err == nil { fmt.Println(v) // 0 } else { fmt.Println(err) os.Exit(1) } s.Pop() fmt.Println(s.Empty()) // true }
解説
PushやPop等のスタックを変更するメソッドは、ポインタレシーバとしてStackを受け取る必要があります。
この理由は、(Stackは[]intのエイリアスなので)スライスを関数に渡すときの挙動に由来します。
スライスを関数に渡したときの挙動についてはこの記事が分かりやすかったです。
簡単にまとめると、
- スライスは配列へのポインタを持つ
- スライス構造体自体は値渡しされるとコピーされるが、参照先は不変
- スライスのappend時にcapacityが足りない場合は参照先配列を再配置する
つまり、スライスを値渡ししてappendしても、capacityが足りなかった場合は異なる配列に値が追加されてしまい、元のスライスが指す配列は変更されないということです。
Stackを生成する際に多めにcapacityを取っておけば問題はないのですが、それもちょっと気持ち悪いので、スライスをポインタ渡しすることで再配置されても大丈夫な実装にしました。
ポインタ渡しされているので、[]intの操作をしたい場合はデリファレンス(*s)する必要があります。
PopやPeekはスタックが空の場合はerrorを返すようにしています。
障害物のあるグリッドの最短経路
前置き
Cracking the Coding Interviewの8.2に以下のような問題がありました。
世界で闘うプログラミング力を鍛える本 コーディング面接189問とその解法
- 作者:Gayle Laakmann McDowell
- 出版社/メーカー: マイナビ出版
- 発売日: 2017/02/27
- メディア: Kindle版
問題: グリッド状を動くロボット
r行とc列のグリッド状の左上にロボットが座っています。ロボットは右と下の2つの方向にしか進むことができません。ロボットが通ることのできない「立ち入り禁止」のセルがあるとした場合、左上の地点から右下の地点まで移動する道順を見つけるアルゴリズムを設計してください。
この問題の解法として、スタートからゴールまでたどり着く、どれか一つのパスを見つけるアルゴリズムが紹介されていました。 しかし、どうせなら全てのパスを見つける方が一般的だろうと思い実装してみました。
アルゴリズム
(c, r)にたどり着くことを考えたとき、基本的には(c, r-1)もしくは(c-1, r)から遷移する2通りがあります。つまり、(c, r)への経路は、(c, r-1)までの経路に"↓"方向を1つ加えたものと、(c-1, r)までの経路に"→"方向を1つ加えたものをマージしたものになります。しかし、この問題には障害物があるため、正確には2通り以下となります。
以上の遷移を持つ動的計画法を用いることで(0, 0)から(c, r) (実際には(c-1, r-1))までの全ての経路を (文字列連結の時間を無視した場合)で求めることができます。
コード
言語はGoです。
package main import ( "fmt" "strings" ) type point struct { x int y int } var dp map[point][]string var locked map[point]bool func appendToAll(bases []string, as string) []string { strs := make([]string, 0) for _, base := range bases { // lockedが含まれていたら更新しない&&含まない if !strings.Contains(base, "[locked]") { strs = append(strs, base+as) } } return strs } func solve(p point, routes []string) []string { if val, ok := dp[p]; ok { return val } x := p.x y := p.y dx := point{x - 1, y} dy := point{x, y - 1} if locked[dx] && locked[dy] { rts := appendToAll(routes, "[locked]") dp[p] = rts return dp[p] } else if locked[dy] { rtsdx := solve(dx, routes) rtsX := appendToAll(rtsdx, "→") rtsY := appendToAll(rtsdx, "[locked]") dp[p] = append(rtsX, rtsY...) return dp[p] } else if locked[dx] { rtsdy := solve(dy, routes) rtsX := appendToAll(rtsdy, "[locked]") rtsY := appendToAll(rtsdy, "↓") dp[p] = append(rtsX, rtsY...) return dp[p] } rtsdx := solve(dx, routes) rtsX := appendToAll(rtsdx, "→") rtsdy := solve(dy, routes) rtsY := appendToAll(rtsdy, "↓") dp[p] = append(rtsX, rtsY...) return dp[p] } func main() { var r, c int fmt.Scan(&r, &c) var k int fmt.Scan(&k) locked = make(map[point]bool, k) for i := 0; i < k; i++ { var lx, ly int fmt.Scan(&lx, &ly) locked[point{lx, ly}] = true } // 枠外もlockedに加える for i := 0; i < c; i++ { locked[point{-1, i}] = true } for i := 0; i < r; i++ { locked[point{i, -1}] = true } dp = make(map[point][]string) dp[point{0, 0}] = make([]string, 1) routes := solve(point{c - 1, r - 1}, make([]string, 1)) for _, route := range routes { fmt.Println(route) } }
実行例
入力
3 3 1 1 0
出力
↓↓→→
↓→↓→
↓→→↓
コメント
【回文の順列】ビット列の中で1が一個であるか判別する方法
前置き
ある問題を解いているときに、ビット列の中で1が一個であるか判別する方法で、なるほど！と思った解法が載っていたので、忘れないよう書き留めておきます。
結論
if checker&(checker-1) == 0 { // 1が一個だけ } else { // それ以外 }
チェックしたいビット列から1を引いた数と元の数の論理和と取ったとき、0になれば1は一個だけとなります。
解説
例えば、00010000というビット列を考えたとき、1を引いた数は00001111となりますよね。この二つの論理和は00000000です。
逆に、00010100という1を複数個含むビット列の場合は、1を引くと00010011となり、論理和は0にはなりません。
つまり、繰り上がり(繰り下がり)の原理を使ってます。
実際の問題: 回文の順列
以下は、このテクニックを使える実際の問題についてです。
この問題は、"Cracking the Coding Interview"という本の1.4です。
世界で闘うプログラミング力を鍛える本 コーディング面接189問とその解法
- 作者:Gayle Laakmann McDowell
- 出版社/メーカー: マイナビ出版
- 発売日: 2017/02/27
- メディア: Kindle版
問題
文字列が与えられたとき、その文字列が回文の順列であるかを判別せよ。回文とは前から読んでも後ろから読んでも同じになる単語やフレーズのことである。空白は無視し、大文字小文字の区別はしないものとする。
例
入力: Tact Coa
出力: True (順列: "taco cat", "atco cta" 等)
解法
回文では、文字列の長さが奇数のときに中央に来る文字を除いて、全ての文字が偶数回現れているはずです。
よって、各文字の登場回数を記録していけば、で解けます。
記録する方法としては、ハッシュかビットベクトルが考えられますが、今回はビットベクトルを使って解いてみます。言語はGoです。
package main import ( "bufio" "fmt" "os" "strings" ) func main() { scanner := bufio.NewScanner(os.Stdin) scanner.Scan() str := scanner.Text() lstr := strings.ToLower(str) checker := 0 for _, c := range lstr { if c != ' ' { // 排他的論理和で偶数個か奇数個かをチェック checker ^= (1 << uint(c-'a')) } } /* テクニック */ if checker&(checker-1) == 0 { fmt.Println("True") } else { fmt.Println("False") } }
解説
ビット列の各桁にそれぞれの文字の登場回数を0, 1で記録しています。排他的論理和を使っているので、偶数回のときは0、奇数回のときは1となります。奇数回となる文字は少なくとも1個であるべきなので、最後に先ほど紹介したテクニックを使って、ビット列の中の1の個数が一個であるかをチェックしています。
今はcheckerのオーバーフローは考えていません。
おまけ
ハッシュを使った解法も載せておきます。(おそらくこれが最も思いつきやすい)
package main import ( "bufio" "fmt" "os" "strings" ) func main() { scanner := bufio.NewScanner(os.Stdin) scanner.Scan() str := scanner.Text() lstr := strings.ToLower(str) counter := make(map[rune]int) for _, c := range lstr { if c != ' ' { counter[c]++ } } odd := 0 for _, cnt := range counter { if cnt%2 == 1 { odd++ if odd > 1 { fmt.Println("False") return } } } fmt.Println("True") }
AtCoder【ARC061 C, ABC045 C】たくさんの数式 - Many Formulas
問題
'1'~'9'の数字からなる文字列が与えられるとき、文字の間に任意の数の'+'を入れて表される数式の値の和を求めよ。
制約
前置き
各数字の間に'+'を入れるか入れないかを考えると、全部で通りとなります。
一つの解法として、bit全探索が考えられますが、その解答例はググるといくつか出てくると思います。
そこで今回は、再帰を用いた深さ優先探索で解いてみました。
言語はGoです。
ソースコード
package main import ( "fmt" "strconv" ) func dfs(s string, i int, lasti int, sum int) int { if i == len(s)-1 { last, _ := strconv.Atoi(s[lasti:len(s)]) // 最後に残った項 return sum + last } n, _ := strconv.Atoi(s[lasti : i+1]) sum1 := dfs(s, i+1, lasti, sum) // i番目の数字の右横に'+'を入れない場合 sum2 := dfs(s, i+1, i+1, sum+n) // i番目の数字の右横に'+'を入れる場合 return sum1 + sum2 } func main() { var s string fmt.Scan(&s) sum := dfs(s, 0, 0, 0) fmt.Println(sum) }
おまけ: bit全探索
Goでのbit全探索の回答例も載せておきます。
package main import ( "fmt" "strconv" ) func solve(s string) int { sum := 0 l := len(s) - 1 // 数字の間の数 for bit := 0; bit < (1 << uint(l)); bit++ { // bitの1が立っている位置に'+'を入れる lasti := 0 // 各bitについて'+'を入れていってできる数式を計算 for i := 0; i < l; i++ { if bit&(1<<uint(i)) != 0 { n, _ := strconv.Atoi(s[lasti : i+1]) sum += n lasti = i + 1 } } last, _ := strconv.Atoi(s[lasti:]) sum += last } return sum } func main() { var s string fmt.Scan(&s) sum := solve(s) fmt.Println(sum) }
サイボウズ サマーインターンシップ2019に参加してきました
はじめに
サイボウズのサマーインターンシップ2019のWebサービス開発コースに参加してきました．
サイボウズとは
ワークライフバランスや働き方改革の文脈で有名かもしれません．
kintone
参加したきっかけ
Webの開発ができるサマーインターンを探していたところ，大学でサイボウズの社員さんによるスクラム開発の授業があって，そこで宣伝されていたことがきっかけです．
サイボウズでは実際の開発でスクラムを取り入れていて，モブプロなども行われていると聞いたのでおもしろそうと思い、応募しました．
選考
書類と面接でした． 書類には今までの開発やインターンの経験を中心に書いたと思います．
面接は東京オフィスに行きました．オフィスビルに50人乗りくらいのクソでかエレベーターがあって驚いたことをよく覚えています．
面接は1:3の形式で，基本的に今やっている研究や開発，過去の経験などについての話が多かったと思います．
当日
1日目
初日はオリエンテーションが中心でした．
セキュリティテストを受けて合格しなければ呼び出されるという怖い事象がありましたが，無事クリアしました．
Webコースは東京5人/大阪2人で全コースの中で一番多かったと思います．
コース別オリエンテーションではkintoneのコードの構造を理解するための練習問題が何問か用意されており，それを解いていってその後に解説を聞いたりしました．
終わりには歓迎会があり，おいしいご飯をいただきました．
昼ごはんは毎日ごちそうになりました．
2日目
2日目からいよいよ開発開始です．
7人を3人と4人チームに分け，私のチームは東京2人/大阪1人という内訳．
実際のお客様からいただいたフィードバックをもとにした課題が多数用意されており，その中からそれぞれチームで1つ選ぶという形式でした．
サイボウズでは毎朝朝会があり，インターン中もチームメンバーとメンターさんでその日にやることをみんなで話し合ったり，技術に関する講義を受けたりしました．
2日目は仕様書についてです． 講義が終わるとさっそく学んだことをもとに課題の機能の仕様書を書いていきました．
ここで初めてのリモートでのモブプロを体験しました． 私のチームのメンバーの1人は大阪オフィスにいたので，zoomでビデオ通話しながらVSCodeのLive Share機能を使って書いていくといった感じです(VSCodeすごいです)．
最初は慣れず，またVSCodeもバグり始めてこれは結構辛いかも…と思いましたが，慣れてくると1人でやるよりも全然早く作業が進んでいきました．モブプロ楽しいですね．
2日目の終わりにはアクセシビリティ勉強会に参加しました．
サイボウズではこのような勉強会が色々開催されてるみたいです． エンジニアにとってはとても良い環境ですね！
3日目
朝の講習会ではkintoneのスクラム開発について学びました．
その後は昨日に引き続き開発を進めていきました．
大規模開発には型とIDEは必須ということを痛感した1日でした．
また，コードを書いていくときはVSCodeのLive Shareではなく，zoomの画面共有を使って1人のPCで編集するといった形式でした(つまり本当のモブプロスタイル)． モブプロはめちゃくちゃ体力を使いましたが，その分どんどん開発も進んでとても良いスタイルだと実感しました．
今も他のインターンなどでチーム開発してるとモブプロでやりたいなと思ったりします．
また，社内ではkintoneやGaroonなどの自社製品を社内ツールとしてもフル活用していてとても良い印象でした．
4日目
この日は自動テストについて学びました． コードの規模が大きくなるとテストも指数関数的に大変になりそうだなと感じました．
この日はひたすら実装できて楽しかったです．
そして何とか課題の実装が終わりました👏👏👏
業務が終わったあとは社員さんの高専についてのLTを聞きました．
「高専生は高専について語りがち」という言葉に激しく共感しました．
5日目
朝は午後の成果発表会のためのスライド作りとデモ準備をひたすらしていました．
そんな中，残り30分のところで障害が発生してめちゃくちゃ焦ります． しかしながら，強いメンターさんのおかげでなんとか時間内に解消することができました．
お昼は社長の青野さんとみんなでいただきました．
午後の成果発表会には思った以上にたくさんの人がいましたが，他のチームの話を聞くこともでき勉強になりました．
感想
とにかく社員の皆さんが楽しそうに働いているなと思いました． 社内勉強会やLTなども盛んに行われており，コミュニケーションが活発に取られていました．
エンジニアの方々もとても優秀でメンターとして心強かったです．
toB向けの製品を出している企業だと普段どんなことをやっているかわかりづらい部分がありますが，今回のインターンで実際に働いているところを体感できて何をやっているかが明確になったと思います．
とても楽しかったので興味のある人はぜひ参加してみてください！
