再帰を使わない順列生成 : 1から9の数字を1回ずつ使ってできる数を、小さい方から順に列挙する(アルゴリズム編)

1から9の数字を1回ずつ使ってできる数を、小さい方から順に列挙するアルゴリズムです。

次に小さい数を求めるアルゴリズム

ある数Nが与えられたとき、その数に使用されている数字を使用してできる数で、Nの次に大きい数を生成します。

N10^iの桁を、n[i]で表します

n[i]を桁小さい方からみていき、初めてn[i] < n[i-1]となるiを求めます

n[0]からn[i-1]まで順番に見ていき、n[i]より初めて大きくなるものを求めます。求めたものをn[j]とします。

n[i]n[j]を入れ替えます

n[0]からn[i-1]を逆順にします

この説明だとよくわからないと思うので、具体的な数字でアルゴリズムを確かめてみましょう。

アルゴリズムを適用した例

N=179836542 とします。

N10^iの桁を、n[i]で表します

以下のようになります。

n[0] = 2  // 一の位 (10^0)
n[1] = 4  // 十の位 (10^1)
n[2] = 5  // 百の位 (10^2)
n[3] = 6  // 千の位 (10^3)
n[4] = 3  // 万の位 (10^4)
n[5] = 8  // 十万の位 (10^5)
n[6] = 9  // 百万の位 (10^6)
n[7] = 7  // 千万の位 (10^7)
n[8] = 1  // 億の位 (10^8)

f:id:yucatio:20200326160139p:plain

n[i]を桁小さい方からみていき、初めてn[i] < n[i-1]となるiを求めます

小さい桁から見て行ったとき、3 < 6のとき初めて数が小さくなります。このときn[4] < n[3]なので、i = 4です。

f:id:yucatio:20200326160231p:plain

n[0]からn[i-1]まで順番に見ていき、n[i]より初めて大きくなるものを求めます。求めたものをn[j]とします。

10^4より下の桁で3より大きい数が初めて出てくるのは4です。n[1] = 4なので、j = 1です。

f:id:yucatio:20200326160423p:plain

n[i]n[j]を入れ替えます

34を入れ替えます。入れ替えた後も、n[0]からn[i-1]までは昇順に並んでいますね。

f:id:yucatio:20200326160434p:plain

n[0]からn[i-1]を逆順にします

入れ替えた結果です。

f:id:yucatio:20200326160448p:plain

以上で、179836542から、次に大きい数である、179842356を得ることができました。

小さい方から列挙するアルゴリズム

1から9の数字を1回ずつ使ってできる数の中で、一番小さい数は123456789です。 ここから、上記アルゴリズムを使用して、次に小さい数を求めます。 さらにそこから得られた数に対して上記アルゴリズムを適用します。

これを繰り返すことによって順列を取り出すことができます。

手順の、

n[i]を桁小さい方からみていき、初めてn[i] < n[i-1]となるiを求めます

ここで該当するiがなくなったら終了です。

数字が重複しているとき

数が重複しているとき、も上記アルゴリズムはうまく動作します。

例えばN=652331の場合を考えます。

N10^iの桁を、n[i]で表します

f:id:yucatio:20200330085020p:plain

n[i]を桁小さい方からみていき、初めてn[i] < n[i-1]となるiを求めます こちらは上記と同じで、

n[0] = 1  // 一の位 (10^0)
n[1] = 3  // 百の位 (10^2)
n[2] = 3  // 千の位 (10^3)
n[3] = 2  // 万の位 (10^4)
n[4] = 5  // 十万の位 (10^5)
n[5] = 6  // 百万の位 (10^6)

2 < 3のとき初めて数が小さくなります。このときn[3] < n[2]なので、i = 3です。

f:id:yucatio:20200330085047p:plain

n[0]からn[i-1]まで順番に見ていき、n[i]より初めて大きくなるものを求めます。求めたものをn[j]とします。

2より下の桁で2より大きい数で、その中で最小なのは3です。3は2つありますが、桁が小さい方を選択します。桁が小さい方は n[1] = 3なので、j = 1です。

f:id:yucatio:20200330085113p:plain

n[i]n[j]を入れ替えます 32を入れ替えます。

f:id:yucatio:20200330085150p:plain

n[0]からn[i-1]を逆順にします

f:id:yucatio:20200330085217p:plain

以上で、652331から、次に大きい数である、653123を得ることができました。

応用 : n個の数のうちk個を使用する組み合わせ

上記のアルゴリズムは、n個の数を全て使用する場合の順列を列挙しました。 n個の数のち、k個を使用する場合のアルゴリズムは以下をご覧ください。

★記事作成中

Groovyのクロージャ ④Groovyで独自のDSLの作成

背景

JenkinsというCIツールではGroovyのコードでCI挙動を記述できるJenkins pipelineがあります。 ここではGroovyのDSL(Domain-Specific Language:ドメイン固有言語)が使われています。 DSLにはクロージャが効果的に使用されています。

今回は独自のDSLの作成です。

前回の記事

前回の記事で、 クロージャの名前解決の方法の各挙動を確認しました。

yucatio.hatenablog.com

今回は、クロージャと名前解決方法を利用して、独自のDSLを定義します。

DSLとは

DSLとは特定のタスク向けに設計されたコンピュータ言語である。

ドメイン固有言語 - Wikipedia

例えば、文章の構造を表すDSL(XMLなど)やページの装飾に特化したDSL(CSSなど)、データの取得に特化したDSL(SQLなど)が挙げられます。

特定のタスクに向けて設計されるDSLは、プログラミング経験者以外が使用することを前提としたものもあります。また、人が自然に読めるように配慮されているものも多くあります。

記述には、宣言型のスタイルがよく用いられます。 宣言型のスタイル(宣言型プログラミング)とは、

対象の性質を宣言してプログラムを構成するプログラミングパラダイム、あるいはそのような性質をもったプログラミングパラダイムの総称である。

宣言型プログラミング - Wikipedia

宣言型プログラミングでは、どのように処理をするかは書かれておらず、何を処理するか(対象)を記述(宣言)します。

例: SQLの場合

SELECT id, name, price FROM item WHERE price >= 100
-- itemテーブルからpriceが100以上の行を見つけ、その行のidとnameとpriceを取得するという意味のSQL
-- 具体的にどのように取ってくるかは書かれていない

GroovyでのDSLの実現方法

Groovyでは以下のようなDSLを作成できます。何を表すか(するか)という短い説明の後に、内容を記載します。 子要素がある場合は{}で囲います。

report {
    title "DSLの説明"
    date "2020-02-03"
    body {
        section("クロージャとは") {
            paragraph  "クロージャとは生まれ故郷(クロージャ自身が定義された場所)を忘れない無名関数のことです。"
        }
        section("thisとownerとdelegate") {
            paragraph  "thisはクロージャを囲んでいるクラスです。"
            paragraph  "ownerはクロージャを囲んでいるオブジェクトです。クラスか、クロージャを囲んでいるクロージャです。"
            paragraph  "delegateは外部のオブジェクトです。メソッドやプロパティ名が元のオブジェクトで解決できないときに呼ばれます。"
        }
    }
}

この記法はプログラミング言語っぽくないですが、groovyの言語仕様に従って記載されています。{}で囲まれた部分はクロージャです。reporttitlesectionなどはメソッドです。

今回は以下のような簡単なDSLを作成します。

  • reportディレクティブはレポートを作成するためのトップ階層です
  • reportの下にはtitle、date、bodyのみ記載することができます
  • title、dateには文字列を続けて書きます
  • bodyの子要素はsectionのみです
  • sectionの子要素はparagraphのみです
  • paragraphには文字列を続けて書きます

reportメソッドの作成

reportメソッドは以下のようになります。クロージャdelegateReportSpecクラスのインスタンスを指定し、resolveStrategyClosure.DELEGATE_ONLYに設定します。

def report(Closure cl) {
    cl.delegate = new ReportSpec()
    cl.resolveStrategy = Closure.DELEGATE_ONLY
    cl()
}

移譲先のクラスの作成

ReportSpecクラスです。titleメソッドとdateメソッドは対応する文字列を表示します。bodyメソッドは、クロージャを引数にとり、BodySpecクラスのインスタンスdelegateに設定しています。

class ReportSpec {
    void title(String title) { println "<h1>${title}</h1>"}
    void date(String date) { println "<div>作成日 : ${date}</div>"}
    void body(Closure body) {
        body.delegate = new BodySpec()
        body.resolveStrategy = Closure.DELEGATE_ONLY
        body()
    }
}

同様に、BodySpecは、以下です。

class BodySpec {
    void section(String title, Closure section) {
        println "<h2>${title}</h2>"
        section.delegate = new SectionSpec()
        section.resolveStrategy = Closure.DELEGATE_ONLY
        section()
    }
}

同様に、SectionSpecは、以下です。

class SectionSpec {
    void paragraph(String paragraph) {println "<p>${paragraph}</p>"}
}

実行結果

以下のDSLを実行します。

report {
    title "DSLの説明"
    date "2020-02-03"
    body {
        section("クロージャとは") {
            paragraph  "クロージャとは生まれ故郷(クロージャ自身が定義された場所)を忘れない無名関数のことです。"
        }
        section("thisとownerとdelegate") {
            paragraph  "thisはクロージャを囲んでいるクラスです。"
            paragraph  "ownerはクロージャを囲んでいるオブジェクトです。クラスか、クロージャを囲んでいるクロージャです。"
            paragraph  "delegateは外部のオブジェクトです。メソッドやプロパティ名が元のオブジェクトで解決できないときに呼ばれます。"
        }
    }
}

実行結果です。

<h1>DSLの説明</h1>
<div>作成日 : 2020-02-03</div>
<h2>クロージャとは</h2>
<p>クロージャとは生まれ故郷(クロージャ自身が定義された場所)を忘れない無名関数のことです。</p>
<h2>thisとownerとdelegate</h2>
<p>thisはクロージャを囲んでいるクラスです。</p>
<p>ownerはクロージャを囲んでいるオブジェクトです。クラスか、クロージャを囲んでいるクロージャです。</p>
<p>delegateは外部のオブジェクトです。メソッドやプロパティ名が元のオブジェクトで解決できないときに呼ばれます。</p>

レポートが作成されました。

rehydrateメソッドの使用

今回、report, reportSpec, BodySpec内で、クロージャdelegateを以下のように指定しました。

def report(Closure cl) {
      cl.delegate = new ReportSpec()
      cl.resolveStrategy = Closure.DELEGATE_ONLY
      cl()
}

一般的に、引数として受け取った変数の内容は変更すべきではありません。 今回は引数として受け取ったクロージャdelegateフィールドを書き換えていたので、この制約を破っています。

この状態を避けるために、クロージャをコピーし、コピーしたものに対してdelegateを変更します。 幸いなことに、コピーとdelegateの変更を一度に行うrehydrateというメソッドが用意されています。 (hydrateは水分を補給するという意味) rehydrateではクロージャをコピーして、ownerthisdelegateを引数で与えられたオブジェクトに変更したものを返します。

reportメソッドをrehydrateで書き換えます。ownerthisObjの部分にthisを指定していますが、下で名前解決方法をClosure.DELEGATE_ONLYに指定しているので、ownerthisの部分は何でも構いません。

def report(Closure cl) {
  def reportSpec = new EmailSpec()
  def clCopy = cl.rehydrate(reportSpec, this, this)
  clCopy.resolveStrategy = Closure.DELEGATE_ONLY
  clCopy()
}

以上で独自のDSLの作成できました。

参考リンク

The Apache Groovy programming language - Domain-Specific Languages

Groovyのクロージャ ③名前解決方法(resolveStrategy)の挙動

背景

JenkinsというCIツールではGroovyのコードでCI挙動を記述できるJenkins pipelineがあります。 Jenkins pipelineではGroovyのDSL(Domain-Specific Language:ドメイン固有言語)が使われています。 DSLにはクロージャが効果的に使用されています。

今回はクロージャの名前解決方法(resolveStrategy)です。

前回の記事

前回の記事で、 クロージャは故郷を忘れないためにthisownerに生まれた場所の情報を格納していることが確認できました。また、クロージャで呼んでいるメソッドがownerで定義されていない場合にdelegateのメソッドを呼ぶことが分かりました。

yucatio.hatenablog.com

名前解決とは

名前解決とは、ここでは、「メソッドやプロパティ名が現れたとき、どこに定義されている名前を使用するか決めること」とします。

クロージャの名前解決 (resolveStrategy)

クロージャは、内部で呼んでいるメソッドがownerで定義されていない場合にdelegateのメソッドを呼びます。この挙動はクロージャオブジェクトのresolveStrategyプロパティに値をセットすることで変更できます。セットできるのは以下の5つです。

名前解決方法 説明
Closure.OWNER_FIRST デフォルト。プロパティ/メソッドがownerに存在するときは、ownerのものを使用し、なければdelegateのものを使用する
Closure.DELEGATE_FIRST OWNER_FIRSTの逆。プロパティ/メソッドがdelegateに存在するときは、delegateのものを使用し、なければownerのものを使用する
Closure.OWNER_ONLY プロパティ/メソッドの名前解決をownerのみで行う。delegateは無視される
Closure.DELEGATE_ONLY プロパティ/メソッドの名前解決をdelegateのみで行う。ownerは無視される
Closure.TO_SELF 名前解決はクロージャクラスで行われる。開発者がクロージャのサブクラスを作成して、クロージャの振る舞いをカスタマイズしたい場合にこの設定にする

名前解決方法の挙動の確認

OWNER_FIRSTDELEGATE_FIRSTOWNER_ONLYDELEGATE_ONLYの動作を確認するため、MainクラスとPipelineSpecクラスそれぞれに以下のようにメソッドを定義します。

a() b() c()
Main ×
PileineSpec ×
class PipelineSpec {
    def b() {
        println "I'm PipelineSpec.b"
    }
    def c() {
        println "I'm PipelineSpec.c"
    }
}

class Pipeline {
    def pipeline(Closure cl) {
      cl.delegate = new PipelineSpec()
      // ここを書き換えててテストする
      cl.resolveStrategy = Closure.OWNER_FIRST
      println "before closure"
      cl()
      println "after closure"
    }
}

class Main {
    // 普通のインスタンスメソッド
    def closureTest() {
        def pipeline = new Pipeline()
        pipeline.pipeline {
            a()
            b()
            c()
        }
    }
    
    def a() {
        println "I'm Main.a"
    }
    def b() {
        println "I'm Main.b"
    }
}

def main = new Main()
main.closureTest()

OWNER_FIRST

上記のコードを実行した結果です。

before closure
I'm Main.a
I'm Main.b
I'm PipelineSpec.c
after closure

a()メソッドとb()メソッドはMainクラスに定義したものが呼ばれ、c()メソッドはPipelineSpecのものが呼ばれました。

DELEGATE_FIRST

上記コードを下記のように書き換えて実行します。

      // ここを書き換えててテストする
      cl.resolveStrategy = Closure.DELEGATE_FIRST

実行結果です。

before closure
I'm Main.a
I'm PipelineSpec.b
I'm PipelineSpec.c
after closure

a()メソッドはMainクラスに定義したものが呼ばれ、b()メソッドとc()メソッドはPipelineSpecのものが呼ばれました。

OWNER_ONLY

上記コードを下記のように書き換えて実行します。

      // ここを書き換えててテストする
      cl.resolveStrategy = Closure.OWNER_ONLY

実行結果です。

before closure
I'm Main.a
I'm Main.b
Exception thrown

groovy.lang.MissingMethodException: No signature of method: Main.c() is applicable for argument types: () values: []
Possible solutions: a(), b(), is(java.lang.Object), any(), tap(groovy.lang.Closure), any(groovy.lang.Closure)
    at Main$_closureTest_closure1.doCall(closure_01.groovy:27)
    at Main$_closureTest_closure1.doCall(closure_01.groovy)
    // 以下略

Mainクラスに定義したa()メソッドとb()メソッドが呼ばれたあと、名前解決が失敗し、MissingMethodExceptionが発生しました。 PipelineSpecでの名前解決が行われなかったことがわかります。

DELEGATE_ONLY

上記コードを下記のように書き換えて実行します。

      // ここを書き換えててテストする
      cl.resolveStrategy = Closure.DELEGATE_ONLY

実行結果です。

before closure
Exception thrown

groovy.lang.MissingMethodException: No signature of method: PipelineSpec.a() is applicable for argument types: () values: []
Possible solutions: b(), c(), any(), tap(groovy.lang.Closure), any(groovy.lang.Closure), is(java.lang.Object)
    at Main$_closureTest_closure1.doCall(closure_01.groovy:25)
    at Main$_closureTest_closure1.doCall(closure_01.groovy)
    // 以下略

a()メソッドが見つからず、MissingMethodExceptionが発生しました。Mainメソッドでの名前解決が行われなかったことがわかります。

DELEGATE_FIRSTとDELEGATE_ONLYの使いどころ

DELEGATE_FIRSTDELEGATE_ONLYは、時に使用者の意図しない挙動を引き起こします。 例えば、以下のように、closureTestメソッド内でpipelineメソッドに渡しているクロージャa()を呼び出したとき、Mainクラスの実装者はMainクラスのa()を呼ぶことを意図していますが、実際にはPipelineSpecクラスのa()メソッドが呼ばれてしまいます。これはバグの温床になりそうです。

class PipelineSpec {
    def a() {
      println "I'm PipelineSpec.a"
    }
}

class Pipeline {
    def pipeline(Closure cl) {
      cl.delegate = new PipelineSpec()
     cl.resolveStrategy = Closure.DELEGATE_FIRST
      println "before closure"
      cl()
      println "after closure"
    }
}

class Main {
    def closureTest() {
        def pipeline = new Pipeline()
        pipeline.pipeline {
            // Main#a()を呼ぶ意図で書いているのに、実際にはPipelineSpec#a()が呼ばれる
            a()
        }
    }

    def a() {
      println "I'm Main.a"
    }
}

def main = new Main()
main.closureTest()

DELEGATE_ONLYの使い所は、DSL(Domain-Specific Language)です。 DELEGATE_ONLYでは、クロージャ内から呼び出せるメソッドを制限することができます。 次回の記事で詳しく解説します。

参考リンク

The Apache Groovy programming language - Closures

環境

次回に続く

yucatio.hatenablog.com

Groovyのクロージャ ②クロージャのthisとownerとdelegate

背景

JenkinsというCIツールではGroovyのコードでCI挙動を記述できるJenkins pipelineがあります。 Jenkins pipelineではGroovyのDSL(Domain-Specific Language:ドメイン固有言語)が使われています。 DSLにはクロージャが効果的に使用されています。

今回はクロージャのthisとownerとdelegateです。

前回の記事

前回の記事で、 クロージャとは生まれ故郷(クロージャ自身が定義された場所)を忘れない無名関数のこと、 クロージャは、クロージャが定義された場所で動く(ように見える)、ということが確認できました。

yucatio.hatenablog.com

クロージャが故郷を忘れないためにしていること

クロージャが実行されたときどのようなことが起こっているのでしょうか。どのようにして元のクラスのメソッドを呼ぶのでしょうか。

その答えは、クロージャが故郷(クロージャが定義された場所)の情報を持っているからです。

クロージャはオブジェクトなので、内部に情報を持てます。クロージャインスタンス変数にはthisownerdelegateの3つが定義されています。

それぞれ以下の情報が入っています。

フィールド 入ってる情報
this クロージャを囲んでいるクラス
owner クロージャを囲んでいるオブジェクト。クラスか、クロージャを囲んでいるクロージャ
delegate 外部のオブジェクト。メソッドやプロパティ名が元のオブジェクトで解決できないときに呼ばれる

確認してみましょう。

class Main {
    // 普通のインスタンスメソッド
    def closureTest() {
        Closure cl = {
          a()
        }
        println "this     : ${cl.thisObject}"
        println "owner    : ${cl.owner}"
        println "delegate : ${cl.delegate}"
    }
    
    def a() {
        println "I'm Main.a"
    }
}

def main = new Main()
main.closureTest()

実行結果です。

this     : Main@2e654c59
owner    : Main@2e654c59
delegate : Main@2e654c59

すべてMainクラスのインスタンスという結果でした。クロージャの中にさらにクロージャがある場合(クロージャがネストしている場合)にはownerとdelegateの値が、対象のクロージャを囲むクロージャになります。詳しくはこちらを参照してください。

qiita.com

ここまでで、クロージャは故郷を忘れないためにthisownerに生まれた場所の情報を格納していることが分かりました。 delegateは、デフォルトではownerと同じですが、クロージャが名前解決に使用するオブジェクトを格納するために使用されます。

delegateにクラスを指定する

delegateにクラスを指定します(正確にいうと、クラスのインスタンスを指定します)。Pipelineクラスのpipeline()メソッド内で、クロージャdelegateを変更します。 PipelineSpecクラスにa()メソッドを定義しました。Mainクラスにはa()メソッドはありません。

class PipelineSpec {
    def a() {
      println "I'm PipelineSpec.a"
    }
}

class Pipeline {
    def pipeline(Closure cl) {
      cl.delegate = new PipelineSpec()
      println "before closure"
      cl()
      println "after closure"
    }
}

class Main {
    def closureTest() {
        def pipeline = new Pipeline()
        pipeline.pipeline {
            a()
        }
    }
}

def main = new Main()
main.closureTest()

実行結果です。

before closure
I'm PipelineSpec.a
after closure

クロージャcl内のa()メソッドは、PipelineSpecのa()メソッドを呼んでいます。 このように、ownerのオブジェクトに該当するメソッドがない場合は、delegateに指定されたオブジェクトのメソッドを実行します。

環境

参考リンク

次回に続く

yucatio.hatenablog.com

Groovyのクロージャ ①クロージャ内のメソッド呼び出し基礎編

背景

JenkinsというCIツールではGroovyのコードでCI挙動を記述できるJenkins pipelineがあります。 Jenkins pipelineではGroovyのDSL(Domain-Specific Language:ドメイン固有言語)が使われています。 DSLにはクロージャが効果的に使用されています。

今回はクロージャの動作の基本編です。

クロージャとは

クロージャとは、生まれ故郷(クロージャ自身が定義された場所)を忘れない無名関数のことです。

こちらページが詳しいです。

koji-k.github.io

クロージャ内のメソッド呼び出し

生まれ故郷を忘れない無名関数とは何か、以下のプログラムで確認します。

MainクラスのclosureTest()内でPilpelineクラスのpipeline関数にクロージャ({}で囲んだ部分)を渡しています。 (クラス名と関数名はJenkins pipelineを意識しています)

クロージャの内部ではa()を呼び出しています。a()Mainクラス、Pipelineクラス両方で定義されています。

pipeline()メソッド内で、渡されたクロージャ(cl)を実行しています。

class Pipeline {
    def pipeline(Closure cl) {
      println "before closure"
      cl()
      println "after closure"
    }

    def a() {
        println "I'm Pipeline.a"
    }
}

class Main {
    def closureTest() {
        def pipeline = new Pipeline()
        pipeline.pipeline {
            a()
        }
    }
    
    def a() {
        println "I'm Main.a"
    }
}

def main = new Main()
main.closureTest()

このコードを実行します。出力は以下のようになりました。

before closure
I'm Main.a
after closure

クロージャが実行されたとき、Main.a()が呼ばれていることがわかります。

このように、クロージャは呼ばれた場所でなく、定義された(クロージャが書かれた)場所で実行されます。難しくいうと、クロージャは変数名やメソッドの名前解決を、(デフォルトでは)定義された場所で行う、ということです。クロージャを実行する側(今回はPipelineクラス)での名前解決は行われません。

呼び出し元のメソッドは呼ばれるか

確認として、Main.a()を削除してみましょう。それ以外は上記と同じコードです。

class Pipeline {
    def pipeline(Closure cl) {
      println "before closure"
      cl()
      println "after closure"
    }

    def a() {
        println "I'm Pipeline.a"
    }
}

class Main {
    def closureTest() {
        def pipeline = new Pipeline()
        pipeline.pipeline {
            a()
        }
    }
    
//    def a() {
//        println "I'm Main.a"
//    }
}

def main = new Main()
main.closureTest()

実行します。エラーになりました。

before closure
Exception thrown

groovy.lang.MissingMethodException: No signature of method: Main.a() is applicable for argument types: () values: []
Possible solutions: any(), tap(groovy.lang.Closure), any(groovy.lang.Closure), is(java.lang.Object), wait(), wait(long)
    at Main$_closureTest_closure1.doCall(closure_01.groovy:18)
    at Main$_closureTest_closure1.doCall(closure_01.groovy)
    at java.base/jdk.internal.reflect.NativeMethodAccessorImpl.invoke0(Native Method)
    at java.base/jdk.internal.reflect.NativeMethodAccessorImpl.invoke(NativeMethodAccessorImpl.java:62)
    at java.base/jdk.internal.reflect.DelegatingMethodAccessorImpl.invoke(DelegatingMethodAccessorImpl.java:43)
    at Pipeline.pipeline(closure_01.groovy:4)
    at Pipeline$pipeline.call(Unknown Source)
    at Main.closureTest(closure_01.groovy:17)
    at Main$closureTest.call(Unknown Source)
    at closure_01.run(closure_01.groovy:36)
    at jdk.internal.reflect.GeneratedMethodAccessor60.invoke(Unknown Source)
    at java.base/jdk.internal.reflect.DelegatingMethodAccessorImpl.invoke(DelegatingMethodAccessorImpl.java:43)

これにより、クロージャを実行したクラス/メソッド(今回はPipeline.pipeline())に定義されたメソッドはクロージャ内からは呼ばれないことが分かりました。

環境

次回に続く

yucatio.hatenablog.com

「ピーターからの問題」1から9までを使って分数の穴埋め算。解答のJavaScriptプログラム

Qiitaでこちらの問題をみたので、解いてみました。

アルゴリズム

考えることは大きく分けて以下の2つです。

  1. 1から9を1回ずつ使った組み合わせを列挙する
  2. 分数を計算して1かどうか確かめる

1から9を1回ずつ使った組み合わせを列挙する

こちらのアルゴリズムを利用して、1から9を1回ずつ使った組み合わせを列挙します。

yucatio.hatenablog.com

分数を計算して1かどうか確かめる

今回、分数の計算が必要に思えますが、式を以下のように変形すれば、分数を使わずとも解けることがわかります。

a/x + b/y + c/z = 1
// ↓
a*y*z + b*x*z + c*x*y = x*y*z

下準備

各マスに番号をふっておきます。配列のインデックスに対応します。

f:id:yucatio:20200214232720p:plain

1から9までの数字を格納している配列をnとすると、解く式は以下のように書けます。

n[0]/(n[1] * 10 + n[2]) + n[3]/(n[4] * 10 + n[5]) + n[6]/(n[7] * 10 + n[8]) = 1

コード

/**
 * 配列の順列を列挙するジェネレータ
 */
function* arrayEnumerator(numArr){
  yield [...numArr]
  while(true) {
    // numArr[i] < numArr[i-1] となるiを探す
    const changeIndex1 = numArr.findIndex((value, i , arr) => i >=1 && arr[i-1] > value)
    if (changeIndex1 < 0) {
      break
    }
    const changeNumber1 = numArr[changeIndex1]
    const newOrderArr = numArr.slice(0, changeIndex1)
    // changeNumber1 より下位の桁で、changeNumber1 より大きい数字のうち、最小のものを探す
    const changeNumber2 = Math.min(...newOrderArr.filter(value => value > changeNumber1))
    const changeIndex2 = newOrderArr.indexOf(changeNumber2)
    // changeNumber1とchangeNumber2入れ替える
    // 下位桁はreverseする
    newOrderArr[changeIndex2] = changeNumber1
    numArr = [...newOrderArr.reverse(), changeNumber2, ...numArr.slice(changeIndex1 + 1)]
    yield [...numArr]
  }
}


const enumerator = arrayEnumerator([9, 8, 7, 6, 5, 4, 3, 2, 1])

for(let n of enumerator){
  // denominators(分母)
  const denomi = [10 * n[1] + n[2], 10 * n[4] + n[5], 10 * n[7] + n[8]]
  // 左辺
  const left = n[0] * denomi[1] * denomi[2] + n[3] * denomi[0] * denomi[2] + n[6] * denomi[0] * denomi[1]
  // 右辺
  const right = denomi.reduce((acc, cur) => acc * cur , 1)
  if (left === right) {
    console.log(`${n[0]}/${n[1]}${n[2]} + ${n[3]}/${n[4]}${n[5]} + ${n[6]}/${n[7]}${n[8]} equals to 1`)
    break
  }
}

あとがき

急いで書いたので、変数名が微妙になってしまいました。

JavaScriptでPython風のzip_longest関数を実装する

こちらの記事でPython風のzip関数を実装しました。

yucatio.hatenablog.com

今回はzip_longest関数を作成します。以下のように、各配列の同じインデックスの要素をまとめます。

const a1 = [1, 2, 3]
const a2 = ["Jan", "Feb", "Mar"]
const a3 = ["Garnet", "Amethyst", "Aquamarine"]

zip_longest(a1, a2, a3)
#=> [[1, "Jan""Garnet"], [2, "Feb""Amethyst"],  [3, "Mar""Aquamarine"]]

各配列の長さが異なる場合には、一番長い配列の長さになります。未定義値はundefinedになります。

const a1 = [1, 2, 3, 4]
const a2 = ["Jan", "Feb", "Mar", "Apr", "May"]
const a3 = ["Garnet", "Amethyst", "Aquamarine"]

zip_longest(a1, a2, a3)
#=> [[1, "Jan""Garnet"], [2, "Feb""Amethyst"],  [3, "Mar""Aquamarine"], [4, "Apr", undefined], [undefined, "May", undefined]]

zip_longest関数本体

zip_longest関数の実装です。

const zip_longest = (...arrays) => {
  const length = Math.max(...(arrays.map(arr => arr.length)))
  return new Array(length).fill().map((_, i) => arrays.map(arr => arr[i]))
}

コードの解説

ほとんどzip関数の解説と同じです。

まず、関数の定義の部分を解説します。レスト構文を使用して、引数全てをarraysに格納します。

const zip_longest = (...arrays) => {

}

例えば、

const a1 = [1, 2, 3, 4]
const a2 = ["Jan", "Feb", "Mar", "Apr", "May"]
const a3 = ["Garnet", "Amethyst", "Aquamarine"]

zip_longest(a1, a2, a3)

と呼び出したとき、arrays

[
  [1, 2, 3, 4],
  ["Jan", "Feb", "Mar", "Apr", "May"],
  ["Garnet", "Amethyst", "Aquamarine"]
]

です。以下、引数にこの配列を渡したときの動作を説明します。

zip_longest関数では、一番長い配列の長さに合わせるので、まず一番長い配列の長さを求めます。

まず、各配列の長さを、求めます。

const zip_longest = (...arrays) => {
  arrays.map(arr => arr.length)
  #=> [4, 5, 3]
}

この中の最大値は、Math.maxとスプレッド演算子を使用して、以下のように書けます。

const zip_longest = (...arrays) => {
  const length = Math.max(...(arrays.map(arr => arr.length)))
  #=> const length = Math.max(...[4, 5, 3])
  #=> const length = Math.max(4, 5, 3)
  #=> const length = 5
}

5回繰り返すので、new Array(length).fill().map((_, i) => i)の構文を使用します。

const zip_longest = (...arrays) => {
  const length = Math.max(...(arrays.map(arr => arr.length)))
  new Array(length).fill().map((_, i) => i))
  #=> [0, 1, 2, 3, 4]
}

fillをはさむ理由については、こちらの記事をご覧ください。

yucatio.hatenablog.com

各配列のi番目の要素は、

arrays.map(arr => arr[i])

で取得することができます。よくわからない場合は、iではなく、012など具体的な数字で考えるとよいです。例えば、各配列の0番目の要素は、

arrays.map(arr => arr[0])
#=> [1, "Jan""Garnet"]

です。

これをmapに渡す関数の戻り値にします。

JavaScriptの場合、配列の長さより大きいインデックスを指定した場合はundefinedになります。

const zip_longest = (...arrays) => {
  const length = Math.max(...(arrays.map(arr => arr.length)))
  return new Array(length).fill().map((_, i) => arrays.map(arr => arr[i]))
  #=> [[1, "Jan""Garnet"], [2, "Feb""Amethyst"],  [3, "Mar""Aquamarine"], [4, "Apr", undefined], [undefined, "May", undefined]]
}

以上でzip_longest関数の完成です。

補足的な話題はzip関数の方の記事に記載していますので、あわせてご覧ください。

yucatio.hatenablog.com