- 投稿日：2021-03-22T21:04:09+09:00
Goで暗号化する備忘録（AES-128-CBC）
はじめに
Goで暗号化・復号の処理を書いたときに（主にパディングで）手こずったのでメモ。
暗号化
流れ
AES-128-CBCによる暗号化は以下のような流れで行う。
- 秘密鍵 (128 bit) の用意
- IV (128 bit) の生成
- パディング
- 暗号化
秘密鍵 (128 bit) の用意
省略。
IV (128 bit) の生成
IVは長さ16のランダムな
byte配列になる。この長さはAESにおけるブロックサイズなので、定数aes.BlockSizeが使える。ivimport ( "crypto/aes" "crypto/rand" ) func GenerateIV() ([]byte, error) { iv := make([]byte, aes.BlockSize) if _, err := rand.Read(iv); err != nil { return nil, err } return iv, nil }パディング
平文
[]byteの長さが16の倍数ではない可能性がある場合、16の倍数にするためにパディングする必要がある（パディングする場合は16の倍数でも16 byte足す必要がある）。
PKCS#7はlbytes のパディングを行うときにl個のlを追加する方式。paddingimport ( "bytes" "crypto/aes" ) func Pkcs7Pad(data []byte) []byte { length := aes.BlockSize - (len(data) % aes.BlockSize) trailing := bytes.Repeat([]byte{byte(length)}, length) return append(data, trailing...) }暗号化
ここまでで用意した
GenerateIV()とPkcs7Pad()を使って実際に暗号化処理を行う。encryptimport ( "crypto/aes" "crypto/cipher" ) func Encrypt(data []byte, key []byte) (iv []byte, encrypted []byte, err error) { iv, err = GenerateIV() if err != nil { return nil, nil, err } block, err := aes.NewCipher(key) if err != nil { return nil, nil, err } padded := Pkcs7Pad(data) encrypted = make([]byte, len(padded)) cbcEncrypter := cipher.NewCBCEncrypter(block, iv) cbcEncrypter.CryptBlocks(encrypted, padded) return iv, encrypted, nil }復号
復号するときも
BlockMode構造体を作ってCryptBlocks()を呼ぶのは暗号化時と同じ。
パディングの削除は、最後の要素をintキャストした個数分だけ削ればよい。decryptimport ( "crypto/aes" "crypto/cipher" ) func Pkcs7Unpad(data []byte) []byte { dataLength := len(data) padLength := int(data[dataLength-1]) return data[:dataLength-padLength] } func Decrypt(data []byte, key []byte, iv []byte) ([]byte, error) { block, err := aes.NewCipher(key) if err != nil { return nil, err } decrypted := make([]byte, len(data)) cbcDecrypter := cipher.NewCBCDecrypter(block, iv) cbcDecrypter.CryptBlocks(decrypted, data) return Pkcs7Unpad(decrypted), nil }動作確認
opensslコマンドと比較する。
main.goimport ( "encoding/base64" "encoding/hex" "fmt" ) func main() { text := "this is test message" fmt.Println("Input:", text) plain := []byte(text) keyString := "645E739A7F9F162725C1533DC2C5E827" key, _ := hex.DecodeString(keyString) fmt.Println("Key:", keyString) iv, encrypted, _ := Encrypt(plain, key) fmt.Println("IV:", hex.EncodeToString(iv)) fmt.Println("Encrypted:", base64.StdEncoding.EncodeToString(encrypted)) decrypted, _ := Decrypt(encrypted, key, iv) fmt.Printf("Decrypted: %s", decrypted) }$ go run main.go Input: this is test message Key: 645E739A7F9F162725C1533DC2C5E827 IV: 71fbf00383b6e214dc08b8b94183cf30 Encrypted: z41UoV93PIS0OYElzUd7nwA9TO6XxSDlf9N+P4nFuJw= Decrypted: this is test messageopensslコマンド。
echoに-nをつけないと改行で結果がずれる。$ echo -n 'this is test message' | openssl aes-128-cbc -e -base64 -nosalt -K 645E739A7F9F162725C1533DC2C5E827 -iv 71fbf00383b6e214dc08b8b94183cf30 z41UoV93PIS0OYElzUd7nwA9TO6XxSDlf9N+P4nFuJw=同じ結果が得られた。
参考文献
- 投稿日：2021-03-22T20:55:38+09:00
TinyGo の開発版のビルド方法と、ビルドせずに開発版バイナリを手に入れる方法
TinyGo に限らず、ですが、リリース版が出た後も開発は続いています。
リリース版では動かなくて、その後の開発版では修正された、というケースも多々あるのが現状です。WASI の ABI 変更により tinygo 0.17 だと動かないようです。以下の PR で wasi_unstable から wasi_snapshot_preview1 にする変更が行われ、これの merge 後だと手元で動作しました。とはいえ開発版が必要になるので手軽には試せないのが現状で、 0.18 待ちになりそうです。https://t.co/IinpOusmqg
— takasago (@sago35tk) March 22, 2021このページでは、 TinyGo の開発版バイナリを手に入れるためにの方法を説明します。
結論
タイトル通りですが、以下のいずれかを行うとよいです。
- 自分でビルドする
- PR 内で作成されたバイナリを使う (できればマージされたものを)
自分でビルドする
以下に手順が書かれています。
LLVM のビルドに時間がかかりますが、それ以外はぼちぼちという所。
windows でもすんなりビルドできますが、現時点で注意点があります (後述) 。
なお、 macos は試していません。
- linux
- macos
- windows
windows 版で LLVM をビルドするときの注意点
chocolateyを使ってchoco install mingwで gcc をインストールするように書かれていますが、 2021/03/22 時点の最新版である mingw 10.2.0 ではビルドできません。
以下のようにして 8.1.0 をインストールするようにしてください。
choco install mingw -Version 8.1.0 or choco install mingw -Version 8.1.0 --allow-downgradeLLVM ビルド時間
core / thread が少なめだと 1h ～ 2h 程度かかるかと思います。
気長に待ってください。
windows だと time の結果が real しかでないので参考程度に。# Ryzen 7 3700X + 32GB + windows 10 real 18m15.488s user 0m0.000s sys 0m0.000s # Ryzen 7 PRO 4750GE + 32GB + ubuntu 20.04 (clang-11) real 16m5.010s user 240m7.789s sys 6m37.188s # Ryzen 7 PRO 4750GE + 32GB + windows 10 real 21m7.242s user 0m0.000s sys 0m0.015s # Ryzen 7 PRO 3700U + 16GB + windows 10 real 66m8.359s user 0m0.000s sys 0m0.031s # Intel Core i5-5200U + ubuntu (データが残ってないけど 120min 前後だった気がします)PR 内で作成されたバイナリを使う
自分ではビルドしたくないけど、最新版を使いたいという人はこちら。
とはいえ開発版なので、何かあった時は issue 書くなり twitter で#tinygoつけてつぶやくなりしてみて欲しいところ。基本的には merge された PR を以下から探して、一番新しい PR の結果を取得するのが良いです。
上記リンクから
Mergedになっている (紫色のアイコンがついているもの) 最新のものを選びます。
その後は OS 毎に分岐します。
linux + macos
まずは上記で調べた最後に Merge された PR を開きます。
開いた PR 内の下のほうから、以下の場所にあるView detailsをクリックします。
ci/circleci: build-linuxあるいはci/circleci: build-macosの右側のDetailsをクリックします。
Log in with GitHubなどでログインします。
ARTIFACTSをクリックします。
開発版のバイナリがあります。
windows
上記で調べた最後に Merge された PR 番号が必要です。
今回は#1699でした。
以下のページから最後に実行された#1699の CI ページを探します。
画面右のほうの
1 publishedをクリックします。
画面右のほうの
・・・的なボタンからDownload artifactsからダウンロードできます。
カーソルを近くに合わせないとボタンが現れないので注意。
まとめ
TinyGo の開発版のビルド方法と、ビルドせずに開発版バイナリを手に入れる方法は以下になります。
- 自分でビルドする
- PR 内で作成されたバイナリを使う (できればマージされたものを)
最後に
TinyGo について不具合や分からないところがあれば、できれば報告してほしいです。
あるいは、 #tinygo をつけて tweet してくれればある程度拾います。
- 投稿日：2021-03-22T18:49:00+09:00
Goで見るHTTP/2
HTTP/3も出てきて、QUICトランスポートを使っていこうという時期ですが、
そもそもHTTP/2も知らないでHTTP/3に進めるのか？
ということでHTTP/2を理解するためにあれこれやってみた事を記事にしました。また、HTTP/3はそもそもまだ仕様も策定中(まもなく確定？)でライブラリ等で気楽に使える状況にも無いので、
この先プロジェクトで使っていくことがあるとしたらまずはHTTP/2かなというのも調べてみた理由です。
HTTP/3自体HTTP over QUICとしてHTTP/2の機能からQUICと重複する部分を切り落として効率化したプロトコルなので、
今後HTTP/3の利用が本格化した際にもキャッチアップが楽になるだろうと。HTTP/2の概要は HTTP/2 の概要 (オライリーのHigh Performance Browser Networkingからの抜粋記事) 等がわかりやすいですが、
幾つか基本的な事を書いておきます。HTTP/2の概要の概要
基本的な構成要素はHTTP/1.1と同じ
HTTP/2であっても、HTTPを構成する
メソッド,ヘッダ,ステータス,ボディといった要素は変わりません。
というかこのあたりのシンタックスを維持したままHTTP/1.1で生じていた様々な課題を解決しようと生まれたのがHTTP/2です。なので、普通に使う分には今までと殆ど変わりはありません。(というか意識してないだけで多分使ってます。)
では何が違うのか。大きな変更点
HTTP/2での主な変更点は下記の通り。
- メッセージ構造がテキストベースからバイナリベースになった
- 単一のTCP接続で複数のストリームを持ち、多重に送受信が出来るようになった
- ストリーム内での優先順位設定や、サーバーサイドプッシュなどの新たな機能の実装
- ヘッダーが圧縮されるようになった
その他、仕様上は強制では無いものの多くのサーバーがTLS必須になっています。
HTTP/2はそれ以前のHTTP/1系と互換性が無い全く別のプロトコルになっているため、
通信経路上にあるプロキシが自分が解釈出来ないプロトコルとして遮断してしまう事があるようです。
TLSを使えば通信内部は完全に隠蔽されプロキシが通信内容を解釈する余地が挟まれないため、
安定した通信が出来るようになるというわけです。GoのHTTP/2対応
Goはバージョン1.6から標準でHTTP/2に対応しています。
HTTP/2の実装はgolang.org/x/net/http2に置かれていますが、直接呼び出して使う必要はありません。
殆どの場合は、HTTP/2だからと言って特別な事は何もなく利用できます。package main import ( "fmt" "log" "net/http" ) func main() { http.HandleFunc("/", func(w http.ResponseWriter, r *http.Request) { fmt.Fprint(w, "Hello world!!") }) err := http.ListenAndServeTLS(":3000", "server.crt", "server.key", nil) if err != nil { log.Fatal(err) } }*手元で確認する場合は適当にサーバー側の証明書とキーを生成して使ってください。
これだけで、HTTP/2サーバとして機能します。
ブラウザから呼び出してみましょう。ブラウザのデベロッパーツールで確認するとプロトコルにHTTP/2が使われているのがわかります。
ネゴシエーション時にお互いにHTTP/2に対応しているかを確認(
NPN/ALPN)しており、
可能であれば何もせずともHTTP/2が使用されています。バイナリフレーミングレイヤーを見る
普通に使う分にはそれほど意識する事はありませんが、実際ライブラリの中身ではHTTP/2対応で様々な事が行われています。
大きな変更点として挙げていた
バイナリベースの部分をもう少し掘り下げて見て行きます。JSON文字列をPOSTするクライアントと、それを受け画像データをチャンクで返すサーバを作り、
少し細かい動きを見て行きましょう。クライアントの実装
クライアント側は単にメッセージをPOSTして、受信した画像データを保存するだけです。
func main() { client := http.Client{ Transport: &http2.Transport{}, } resp, err := client.Post("https://localhost:3000", "application/json", bytes.NewReader([]byte("{\"message\":\"hello\"}"))) if err != nil { log.Fatal(err) } defer resp.Body.Close() file, err := os.Create("image.png") if err != nil { panic(err) } defer file.Close() io.Copy(file, resp.Body) log.Printf("Protocol Version: %s\n", resp.Proto) }実行時に
GODEBUG=http2debug=2を指定する事で詳細なデバッグログが得られ、
送受信しているフレームの詳細を見ることが出来ます。
以下ではこちらのログと合わせて動きを追って行きます。サーバーの実装
先ほどのように
ListenAndServeTLSを使ってしまうと中の動きが追い辛いため、
Lisnerを取得してcert, err := tls.LoadX509KeyPair("server.crt", "server.key") if err != nil { log.Fatal("load key pair error:", err) } tlsCfg := &tls.Config{ Certificates: []tls.Certificate{cert}, NextProtos: []string{"h2"}, } l, err := tls.Listen("tcp", ":3000", tlsCfg) if err != nil { log.Fatal("listen for tls over tcp error:", err) } defer l.Close()クライアントからのアクセスを待ち、生TCPコネクションを取得します。
conn, err := l.Accept() if err != nil { log.Fatal("accept connection error:", err) }HTTP/2ではプロトコル使用の確認のため、最初に
コネクションプリフェイスを送信します。
プリフェイスは"PRI * HTTP/2.0\r\n\r\nSM\r\n\r\n"と定義されており、
これが期待と異なる場合にはサーバーはコネクションエラーとして扱わなければなりません。
RFC7540 3.5const preface = "PRI * HTTP/2.0\r\n\r\nSM\r\n\r\n" b := make([]byte, len(preface)) if _, err := io.ReadFull(conn, b); err != nil { log.Fatal("read from conn error:", err) } if string(b) != preface { log.Fatal("invalid preface:", string(b)) }ここから先はHTTP/2の世界なので、バイナリフレームでのやりとりが行われます。
HTTPの基本要素となるメソッド,ヘッダ,ステータス,ボディも全てフレームに内包されます。
クライアント側のデバッグログを確認すると、
ヘッダーを圧縮(HPACK)しHADERフレームに、
ボディのデータをDATAフレームに書き込んでいます。http2: Transport creating client conn 0xc00040c000 to [::1]:3000 http2: Framer 0xc0003fa0e0: wrote SETTINGS len=18, settings: ENABLE_PUSH=0, INITIAL_WINDOW_SIZE=4194304, MAX_HEADER_LIST_SIZE=10485760 http2: Framer 0xc0003fa0e0: wrote WINDOW_UPDATE len=4 (conn) incr=1073741824 http2: Transport encoding header ":authority" = "localhost:3000" http2: Transport encoding header ":method" = "POST" http2: Transport encoding header ":path" = "/" http2: Transport encoding header ":scheme" = "https" http2: Transport encoding header "content-type" = "application/json" http2: Transport encoding header "content-length" = "19" http2: Transport encoding header "accept-encoding" = "gzip" http2: Transport encoding header "user-agent" = "Go-http-client/2.0" http2: Framer 0xc0003fa0e0: wrote HEADERS flags=END_HEADERS stream=1 len=52 http2: Framer 0xc0003fa0e0: wrote DATA flags=END_STREAM stream=1 len=19 data="{\"message\":\"hello\"}"GoではFramer構造体が用意されており、フレームデータの読み書きを担ってくれます。
framer := http2.NewFramer(conn, conn) frames, err := readFrames(framer) if err != nil { log.Fatal("read frames error:", err) }フレームの種類は下記の通り。詳しくはRFCを参照してください。
種類 データ HEADERS ヘッダー DATA ボディ PRIORITY 優先度 RST_STREAM エラーコード SETTINGS 各種設定値 PUSH_PROMISE プッシュ開始予約 PING PING GOAWAY コネクション終了通知 WINDOW_UPDATE ウインドウ値の更新 CONTINUATION HEADERS/PUSH_PROMISEの続きのデータ
Framerからフレームデータを読み出して行きます。
ストリームの最終フレームはEND_STREAMフラグを持っているので、そこまで読んでいきます。func readFrames(framer *http2.Framer) ([]http2.Frame, error) { frames := make([]http2.Frame, 0) for { frame, err := framer.ReadFrame() if err != nil { return frames, err } frames = append(frames, frame) if frame.Header().Flags.Has(http2.FlagDataEndStream) { return frames, nil } } }では早速フレームのデータを見てみましょう。
現在のストリームのStreamIDと受信したJSON文字列を確認します。var streamID uint32 var data []byte for _, frame := range frames { if headersframe, ok := frame.(*http2.HeadersFrame); ok { streamID = headersframe.StreamID } if headersframe, ok := frame.(*http2.DataFrame); ok { data = headersframe.Data() } } fmt.Printf("StreamID: %v, Message: %s\n", streamID, string(data))StreamID: 1, Message: {"message":"hello"}ストリームID=1 でPOSTしたJSONメッセージがデータフレームから取得出来ているのがわかります。
サーバーはプリフェイスが問題ない事を確認したら、まずは
SETTINGフレームを返します。
これは空でも良いとされているので、今回はとりあえず空で返します。framer.WriteRawFrame(http2.FrameSettings, 0, 0, []byte{})http2: Framer 0xc0003fa0e0: read SETTINGS len=0 http2: Transport received SETTINGS len=0 http2: Framer 0xc0003fa0e0: wrote SETTINGS flags=ACK len=0クライアントに送信する画像データを開いて、レスポンスヘッダ情報をHPACK圧縮します。
pic, err := ioutil.ReadFile("image.png") if err != nil { log.Fatal(err) } hbuf := bytes.NewBuffer([]byte{}) henc := hpack.NewEncoder(hbuf) henc.WriteField(hpack.HeaderField{Name: ":status", Value: "200"}) henc.WriteField(hpack.HeaderField{Name: "content-length", Value: strconv.Itoa(len(pic))}) henc.WriteField(hpack.HeaderField{Name: "content-type", Value: "image/png"}) fmt.Printf("Encoded Header: %d Byte\n", len(hbuf.Bytes()))ヘッダデータは16バイトに圧縮されています。
Encoded Header: 16 Byte圧縮したヘッダーデータをHEADERSフレームに書き込みます。
err = framer.WriteHeaders(http2.HeadersFrameParam{StreamID: streamID, BlockFragment: hbuf.Bytes(), EndHeaders: true}) if err != nil { log.Fatal("write headers error: ", err) }HTTP/1.1ではヘッダーに"Transfer-Encoding: chunked"を指定して転送エンコードを行っていましたが、
HTTP/2では単純にDATAフレームに分割して送信するだけで効率の良いデータストリーミングが行えます。
最後のDATAフレームにEND_STREAMフラグを立てて送れば、クライアント側はそれを検知して通信を終了します。for _, chunk := range chunkBy(pic, 1024) { framer.WriteData(streamID, false, chunk) } framer.WriteData(streamID, true, []byte{})func chunkBy(items []byte, chunkSize int) [][]byte { var chunks [][]byte for chunkSize < len(items) { items, chunks = items[chunkSize:], append(chunks, items[0:chunkSize:chunkSize]) } return append(chunks, items) }クライアント側のデバッグログではヘッダーデータ受信後、続けてチャンク化された画像データを受信しているのが確認できます。
(データ内容はあんまり長ったらしいので省略しています。)
クライアントは逐次受信したデータを処理し、途中何度かWINDOW_UPDATEフレームで空いたバッファサイズを
サーバーに通知してフロー制御を行っています。http2: Framer 0xc0003fa0e0: read HEADERS flags=END_HEADERS stream=1 len=16 http2: decoded hpack field header field ":status" = "200" http2: decoded hpack field header field "content-length" = "15229" http2: decoded hpack field header field "content-type" = "image/png" http2: Transport received HEADERS flags=END_HEADERS stream=1 len=16 http2: Framer 0xc0003fa0e0: read DATA stream=1 len=1024 data="\x89PNG\..." http2: Transport received DATA stream=1 len=1024 data="" (768 bytes omitted) http2: Framer 0xc0003fa0e0: read DATA stream=1 len=1024 data="<TS\xa3k\..." ... http2: Framer 0xc0003fa0e0: wrote WINDOW_UPDATE stream=1 len=4 incr=5120 ... http2: Framer 0xc0003fa0e0: wrote WINDOW_UPDATE stream=1 len=4 incr=5120 ... http2: Framer 0xc0003fa0e0: read DATA flags=END_STREAM stream=1 len=0 data="" http2: Transport received DATA flags=END_STREAM stream=1 len=0 data="" http2: Framer 0xc0003fa0e0: wrote WINDOW_UPDATE stream=1 len=4 incr=4989 Protocol Version: HTTP/2.0最後に
こうやって一連の流れを追ってみると、HTTP/2もやっている事自体はシンプルかつ、より効率的なプロトコルになっている事がわかります。
今回は触れていませんが、一本のTCPコネクションでストリームを多重化していたり、双方向通信も行えるので、
今後サーバの内側でもHTTP/2を使ってサービス同士の通信を行い効率化されていくんだろうなと思います。とはいえ今回の様な実装をプロジェクトの中でする機会はおそらくないと思いますが、
HTTP/2がどの様に動作しているのかをある程度把握しておけば、今後gRPCなどを扱う場面で
勘が利くようにもなるでしょうし、実装して動かして見る事で理解の助けにもなるものと思います。参考
- HTTP/2の概要：Google Developers Web Fundamentals
- Real World HTTP 第2版：渋川よしき(オライリー・ジャパン)
- Go言語とHTTP2：deeeet(SOTAブログエントリー)
- 投稿日：2021-03-22T12:06:38+09:00
今週のアルゴリズム：最短経路の計算！(Go2/Crystal/Kotlin/Nim/Juliaでpermutation iterator)
Permutation Iterator next_permutation URL C#/Go/Python/Ruby/VB まとめ含む http://qiita.com/cielavenir/items/ac96da5e3040c2edb78c Boo/C#/Nemerle/VB http://qiita.com/cielavenir/items/0e07a024049017f7dea2 Java/Groovy/Scala/Fortran/Pascal http://qiita.com/cielavenir/items/4347fd0c6c69fa60804a D/Go/JavaScript/Lua/R http://qiita.com/cielavenir/items/9e821d04f574a6623d03 Perl HSP/PHP/Python/Ruby http://qiita.com/cielavenir/items/006a878292c5be209231 Go2/Crystal/Kotlin/Nim/Julia http://qiita.com/cielavenir/items/74f8d547437154c14e72 V/Rust http://qiita.com/cielavenir/items/cec1812999547909a9e4 D/Nemerle/JavaScript/Perl6/PHP C/C++/Crystal/Go2/Julia
Kotlin/Nim/Perl/Perl6(github参照) Go2
ジェネリクスにより、sort.Interfaceを使って頑張る必要がなくなった。ありがたい。
というかこの記事の更新をしようと思ったのはジェネリクスのおかげ--;;;
tyama_codeiq608_iter.go2//usr/bin/env go run $0 $@;exit package main import "fmt" type ordered interface { type int, int8, int16, int32, int64, uint, uint8, uint16, uint32, uint64, uintptr, float32, float64, string } func reverse[T any](a []T,start int,size int){ for end:=start+size-1;start<end;start++ { z:=a[start] a[start]=a[end] a[end]=z end-- } } func permutation[T ordered](x []T, n int) <- chan []T{ ch := make(chan []T) go func(){ if 0<=n&&n<=len(x) { a:=make([]T,n) for i:=0;i<n;i++ {a[i]=x[i]} for { { b:=make([]T,n) for i:=0;i<n;i++ {b[i]=a[i]} ch <- b } reverse(a,n,len(a)-n) i:=0 for i=len(a)-2;i>=0;i-- {if a[i]<a[i+1] {break}} if i<0 { //reverse(a,0,len(a)) break } k:=i for i=len(a)-1;i>=k+1;i-- {if a[k]<a[i] {break}} l:=i z:=a[k] a[k]=a[l] a[l]=z reverse(a,k+1,len(a)-(k+1)) } } close(ch) }() return ch } func main(){ N:=6 e0:=make([]int,N*2) f0:=make([]int,N*2) i:=0 r:=0 for i=0;i<N;i++ {e0[N+i]=1;f0[N+i]=1} e:=make([]int,N*2+1); f:=make([]int,N*2+1); for _e:=range permutation[int](e0,len(e0)) { for i=0;i<N*2;i++ {e[i+1]=e[i]+_e[i]} for _f:=range permutation[int](f0,len(f0)) { for i=0;i<N*2;i++ { f[i+1]=f[i]+_f[i] if e[i]==f[i]&&e[i+1]==f[i+1] {break} } if i==N*2 {r++} } } fmt.Println(r) }Crystal
Rubyには
Enumerator.new{|y|}があるけどCrystalにはない。Channel(T)にinclude Iterator(T)させれば良いと思った。なんで標準でincludeされていないんだろう。。tyama_codeiq608_iter.cr#!/usr/bin/env crystal class Array(T) def unique_permutation(n=self.size) : Channel(Array(T)) nxt=Channel(Array(T)).new spawn{ if n<0||self.size<n nxt.close next end a=self.sort nxt.send a[0,n] loop{ a=a[0,n]+a[n..-1].reverse k=(a.size-2).downto(0).find{|i|a[i]<a[i+1]} if k.is_a?(Nil) nxt.close break end l=(a.size-1).downto(k+1).find{|i|a[k]<a[i]}.not_nil! a[k],a[l]=a[l],a[k] a=a[0,k+1]+a[k+1..-1].reverse nxt.send a[0,n] } } nxt end def partial_sum self.reduce([0]){|s,e|s << s.last+e} end end class Channel(T) include Iterator(T) def next begin receive rescue ClosedError stop end end end N=6 P=([0]*N+[1]*N).unique_permutation.to_a #各Pは経路を表す。1が縦、0が横を表す。 r=0 P.each{|e0| e = e0.partial_sum #数学の座標系のように左下をA、右上をBとすると、eの各インデックスiにおいて、x座標がi-e[i]、y座標がe[i]となる。 P.each{|f0| f = f0.partial_sum r+=1 if (N*2).times.none?{|i| #i番目の座標とi+1番目の座標が等しければ、「道に重複がある」とみなせる。 e[i]==f[i] && e[i+1]==f[i+1] } } } p r # 100360Kotlin
fun <T: Comparable<T>>を使う点以外は多段階選抜の答案を見ながらさくっと。
※いつものことながらkotlin-native対応していますtyama_codeiq608_iter.kt//usr/bin/env kscript $0 $@;exit fun <T>reverse(a: Array<T>,start: Int,size: Int){ val end=start+size-1 for(i in 0..size/2-1){ val z=a[start+i] a[start+i]=a[end-i] a[end-i]=z } } fun <T: Comparable<T>>unique_permutation(a0: Array<T>,n: Int):Sequence<Array<T>>{ return sequence seq@{ if(n<0||a0.size<n)return@seq var a=a0.copyOf() while(true){ yield(a.sliceArray(0..n-1)) reverse(a,n,a.size-n) var k = -1 for(i in (a.size-2) downTo 0 step 1)if(a[i]<a[i+1]){k=i;break} if(k<0){ //reverse(a,0,a.size) break } var l = -1 for(i in a.size-1 downTo k+1 step 1)if(a[k]<a[i]){l=i;break} val z=a[k];a[k]=a[l];a[l]=z reverse(a,k+1,a.size-(k+1)) } } } fun <T: Comparable<T>>unique_permutation(a: Array<T>):Sequence<Array<T>>{ return unique_permutation(a,a.size) } fun main(args: Array<String>){ val N=6 var r=0 val e0=Array<Int>(N*2){0} val f0=Array<Int>(N*2){0} for(i in 0..N-1){e0[N+i]=1;f0[N+i]=1} val e=Array<Int>(N*2+1){0} val f=Array<Int>(N*2+1){0} for(e_ in unique_permutation(e0)){ for(i in 0..N*2-1)e[i+1]=e[i]+e_[i] for(f_ in unique_permutation(f0)){ run outer@{ for(i in 0..N*2-1){ f[i+1]=f[i]+f_[i] if(e[i]==f[i]&&e[i+1]==f[i+1])return@outer } r++ } } } println(r) }Nim
tyama_codeiq608_iter.nim#[ /usr/bin/env nim c --nimcache:$HOME/.nimcache --opt:speed --run $0 $@;exit #]# import algorithm import sequtils proc unique_permutation[T](a0:seq[T],n0:ref int=nil):iterator:seq[T] = return iterator:seq[T] = var n=len(a0) if n0!=nil: n=n0[] if n<0 or len(a0)<n: return var a=a0.sorted yield a[0..n-1] while true: a=concat(a[0..n-1],a[n..len(a)-1].reversed) var k = -1 block blk: for i in countdown(len(a)-2,0): if a[i]<a[i+1]: k=i break blk #a.reverse return for l in countdown(len(a)-1,k): if a[k]<a[l]: let z=a[k] a[k]=a[l] a[l]=z break a=concat(a[0..k],a[k+1..len(a)-1].reversed) yield a[0..n-1] let N=6 var e0=concat(repeat(0,N),repeat(1,N)) var f0=concat(repeat(0,N),repeat(1,N)) #各Pは経路を表す。1が縦、0が横を表す。 var r=0 var e=repeat(0,N*2+1) var f=repeat(0,N*2+1) for e1 in unique_permutation(e0): for i in countup(0,N*2-1): e[i+1]=e[i]+e1[i] #数学の座標系のように左下をA、右上をBとすると、eの各インデックスiにおいて、x座標がi-e[i]、y座標がe[i]となる。 for f1 in unique_permutation(f0): for i in countup(0,N*2-1): f[i+1]=f[i]+f1[i] block blk: for i in countup(0,N*2-1): if e[i]==f[i] and e[i+1]==f[i+1]: break blk r+=1 #i番目の座標とi+1番目の座標が等しければ、「道に重複がある」とみなせる。 writeLine(stdout,r) # 100360Julia
tyama_codeiq608_iter.jl#!/usr/bin/env julia function reverse(a,start::Int,size::Int) local end_=start+size-1 while start<end_ local z=a[start] a[start]=a[end_] a[end_]=z end_-=1 start+=1 end end function next_permutation(a0,n::Int) local ch = Channel{typeof(a0)}(8) function _producer() if n<0||length(a0)<n close(ch) return end local a=a0[:] while true put!(ch,a[1:n]) reverse(a,n+1,length(a)-n) local i=length(a)-1 while i>0 if a[i]<a[i+1] break end i-=1 end if i<=0 #reverse(a,1,length(a)) break end local k=i i=length(a) while i>=k if a[k]<a[i] break end i-=1 end local l=i local z=a[k] a[k]=a[l] a[l]=z reverse(a,k+1,length(a)+1-(k+1)) end close(ch) end @async _producer() return ch end Base.@ccallable function julia_main(args::Vector{String})::Cint local N=6 local e0=Array{Int}(undef,N*2) local f0=Array{Int}(undef,N*2) local i=1 local r=0 while i<=N e0[N+i]=1 f0[N+i]=1 i+=1 end sort!(e0) sort!(f0) local e=Array{Int}(undef,N*2+1) local f=Array{Int}(undef,N*2+1) for e_ in next_permutation(e0,length(e0)) for i in 1:N*2 e[i+1]=e[i]+e_[i] end for f_ in next_permutation(f0,length(f0)) i=1 while i<=N*2 f[i+1]=f[i]+f_[i] if e[i]==f[i]&&e[i+1]==f[i+1] break end i+=1 end if i>N*2 r+=1 end end end println(r) return 0 end if get(ENV, "COMPILE_STATIC", "false") == "false" julia_main(ARGS) end