質問をすることでしか得られない、回答やアドバイスがある。

15分調べてもわからないことは、質問しよう!

ただいまの
回答率

90.52%

  • JavaScript

    16376questions

    JavaScriptは、プログラミング言語のひとつです。ネットスケープコミュニケーションズで開発されました。 開発当初はLiveScriptと呼ばれていましたが、業務提携していたサン・マイクロシステムズが開発したJavaが脚光を浴びていたことから、JavaScriptと改名されました。 動きのあるWebページを作ることを目的に開発されたもので、主要なWebブラウザのほとんどに搭載されています。

  • アルゴリズム

    408questions

    アルゴリズムとは、定められた目的を達成するために、プログラムの理論的な動作を定義するものです。

8パズルをハッシュ表を使って最適なルートを見つける

受付中

回答 0

投稿 編集

  • 評価
  • クリップ 2
  • VIEW 726

kt3302y

score 19

javascriptのプログラムについて質問なんですが、下記のコードを参考にしてroot(hash_table,pat)関数を作成し、最適なルートを文字列で表示するプログラムを作成したいのですが、どのようにしたらよいのでしょうか。patは最適なルートを表す文字配列です。
/*                                                                              
 * A hash function which outputs values
 * less than 20,011                        
 */
function h(pat){
    var s = 0
    for (var i = 0; i < 9; i++){
        s = (s  * 3444 + pat[i]) % 20011
    }
    return s
}
function eq_pat(pat1, pat2){
    for (var i = 0; i < 9; i++){
        if (pat1[i] != pat2[i])
            return false
    }
    return true
}
var pat_table = []
function add_pat(pat, dist){
    var v = h(pat)
    if (pat_table[v] === undefined){
        pat_table[v] = [[pat, dist]]
        return 1
    } else{
        lst = pat_table[v]
        for (var i = 0; i < lst.length; i++)
            if (eq_pat(lst[i][0], pat)) return 0
        pat_table[v].push([pat, dist])
        return 1
    }
}
function find_pat(pat){
    var v = h(pat)
    if (pat_table[v] === undefined) return -1
    else {
        var lst = pat_table[v]
        for (var i = 0; i < lst.length; i++)
            if (eq_pat(lst[i][0], pat)) return 
lst[i][1]
        return -1
    }
}
function find_zero(pat){
    for (var i = 0; i < 9; i++){
        if (pat[i] == 0) return i
    }
    return -1
}
function work(){
    var init_pat = [0, 1, 2, 3, 4, 5, 6, 7, 8]
    var queue = [[init_pat, 0]]
    var counter = 0
    while (queue.length > 0){
        var [pat, dist] = queue.shift()
        var ddist = find_pat(pat)
        if (ddist < 0){
            add_pat(pat, dist)
            counter += 1
            var p = find_zero(pat)
            var px = p % 3
            var py = Math.floor(p / 3)
            if (px > 0){
                ppat = pat.slice(0)
                ppat[p] = ppat[p - 1]
                ppat[p - 1] = 0
                queue.push([ppat, dist + 1])
            }
            if (px < 2){
                ppat = pat.slice(0)
                ppat[p] = ppat[p + 1]
                ppat[p + 1] = 0
                queue.push([ppat, dist + 1])
            }
            if (py > 0){
                ppat = pat.slice(0)
                ppat[p] = ppat[p - 3]
                ppat[p - 3] = 0
                queue.push([ppat, dist + 1])
            }
            if (py < 2){
                ppat = pat.slice(0)
                ppat[p] = ppat[p + 3]
                ppat[p + 3] = 0
                queue.push([ppat, dist + 1])
            }
        }
    }
    puts(counter)
}
  • 気になる質問をクリップする

    クリップした質問は、後からいつでもマイページで確認できます。

    またクリップした質問に回答があった際、通知やメールを受け取ることができます。

    クリップを取り消します

  • 良い質問の評価を上げる

    以下のような質問は評価を上げましょう

    • 質問内容が明確
    • 自分も答えを知りたい
    • 質問者以外のユーザにも役立つ

    評価が高い質問は、TOPページの「注目」タブのフィードに表示されやすくなります。

    質問の評価を上げたことを取り消します

  • 評価を下げられる数の上限に達しました

    評価を下げることができません

    • 1日5回まで評価を下げられます
    • 1日に1ユーザに対して2回まで評価を下げられます

    質問の評価を下げる

    teratailでは下記のような質問を「具体的に困っていることがない質問」、「サイトポリシーに違反する質問」と定義し、推奨していません。

    • プログラミングに関係のない質問
    • やってほしいことだけを記載した丸投げの質問
    • 問題・課題が含まれていない質問
    • 意図的に内容が抹消された質問
    • 広告と受け取られるような投稿

    評価が下がると、TOPページの「アクティブ」「注目」タブのフィードに表示されにくくなります。

    質問の評価を下げたことを取り消します

    この機能は開放されていません

    評価を下げる条件を満たしてません

    評価を下げる理由を選択してください

    詳細な説明はこちら

    上記に当てはまらず、質問内容が明確になっていない質問には「情報の追加・修正依頼」機能からコメントをしてください。

    質問の評価を下げる機能の利用条件

    この機能を利用するためには、以下の事項を行う必要があります。

まだ回答がついていません

15分調べてもわからないことは、teratailで質問しよう!

  • ただいまの回答率 90.52%
  • 質問をまとめることで、思考を整理して素早く解決
  • テンプレート機能で、簡単に質問をまとめられる

関連した質問

同じタグがついた質問を見る

  • JavaScript

    16376questions

    JavaScriptは、プログラミング言語のひとつです。ネットスケープコミュニケーションズで開発されました。 開発当初はLiveScriptと呼ばれていましたが、業務提携していたサン・マイクロシステムズが開発したJavaが脚光を浴びていたことから、JavaScriptと改名されました。 動きのあるWebページを作ることを目的に開発されたもので、主要なWebブラウザのほとんどに搭載されています。

  • アルゴリズム

    408questions

    アルゴリズムとは、定められた目的を達成するために、プログラムの理論的な動作を定義するものです。