スポンサーサイト

上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。

『プログラマ脳を鍛える数学パズル』キャンペーンクイズに挑戦したお

20個のカラーボックスで作る本棚は何通り?『プログラマ脳を鍛える数学パズル』キャンペーンクイズの解答 codezine
http://codezine.jp/article/detail/9005


問題の内容についてはリンク先を参照。


ここでは「俺なんでこんな糞コードになったの?」について考えます。愚痴と反省です



僕の結果は606通りで、正解は610通りでした。
点対称な1通りor線対称な2通りを見逃したのが原因かと思われます。先生怒らないから出てこなかった子は手を挙げなさい

何で見逃したの?

プログラムのオーダーがデカすぎて至る所に高速化の記述をしたから。
「こうやってこう進むと、こっちからこう進むのと重複するから、切り捨ててもいいよね!」

countPut.CountBox関数のwhileループとかまさにこれです。
元はforで辿っていたのですが、removeJointでぶった切ってます。この辺でしょう。


でも解答例のRubyには条件を付けて中断させたりするような記述は無いです。しかもめっっっっっちゃ早い。何で?
次の文を引用。

この配列に対して、「縦に置いた場合(2×3)、横に置いた場合(3×2)の位置に「1」をセットして、次の位置に置けるかを調べる」ということを繰り返します。
(ページ中央、ソースコード上)


一緒じゃん。

でも「次の位置」の定義が違いました。

解答例のRubyの「次の位置」とは、面積ブロックの「隣のセル」を指します。

自分が作成したプログラムの「次の位置」とは、既に置かれたブロックに隣接するセル(+ごみ)を指します。


つまり、解答例では右方向にしか再帰が伸びませんが、自分が作成したプログラムは右下へ再帰が伸びます。
やった!オーダー爆上がりだぜ!!解空間の重複もするぜ!!!

重複が絶対に起きないのでCountBoxのanswerリストのような解の重複調べも不要。



僕の脆くて硬い頭を何とかしたいものです。

で、見つからなかった4パターンって何ですか…





参考用に不正解なソースを載せておきます。
CountBox.countPut関数のbf.print()のコメントアウトを外すと、多少の暇は潰せます。

import java.util.*;
/* 考え方:
* 箱を置けるスペースを考え、左上から右下方向へ箱を積み上げていく。(解答例に併せて表現を修正)
* RESULT =>606 (ANSWER-4)
*/

// メインクラス
public class hako{
static public void main(String args[]){
CountBox cb = new CountBox(2,3);
System.out.println("answer is:"+cb.count(20));
}
}

// 数えるクラス
class CountBox{
private int width; // 置く箱の大きさ
private int height;
private int cubew; // widthとheightのうち長い方

private LinkedList<LinkedList<int[]>> answer;

public CountBox(int w,int h){
width =w;
height=h;
cubew =w>h?w:h;
answer = new LinkedList<LinkedList<int[]>>();
}

public int count(int num){
int result,len;
if (num<=0) return 0;
len = cubew*(num+1);
answer.clear();
result =countPut(num,num-1,0,width,height,new BoxField(len,len));
result+=countPut(num,num-1,0,height,width,new BoxField(len,len));
return result;
}

// 再帰用
// メモリにやや厳しい
private int countPut(int num,int left,int jointidx,int w,int h,BoxField bf){
int c=0;
// 箱を置く。置けなかったら無効
if (!bf.putBox(jointidx,w,h))return 0;

// 最小の長方形の面積が理論値(個数*1箱の面積)を超える場合、絶対に長方形にならない
if (num*w*h<bf.calcMaxarea()) return 0;

if (left<=0){ // 全て配置した
// 長方形に埋まってなかったら無効
if (!bf.isFillRect())return 0;
// 過去に決めたブロック
for (LinkedList<int[]> list:answer)
if (bf.isEqualBoxPos(list))return 0;
answer.add(bf.getBoxPos());
//bf.print();
return 1;
}

// 接続点にすべて置いてみる
while(0<bf.getJointNum()){
c+=countPut(num,left-1,0,w,h,bf.clone());
c+=countPut(num,left-1,0,h,w,bf.clone());
bf.removeJoint();
}

return c;
}
}

// 箱置場クラス
class BoxField implements Cloneable{
private boolean[][] data; // 左下を0,0、右上方向ににインデックスは増えると考える。
private int datawidth; // 十分な広さの部屋
private int dataheight;
private int maxwidth; // 置かれた箱をすべて含むことができる最小の長方形
private int maxheight;
private LinkedList<int[]> joint; // 次の箱が設置可能な点
private LinkedList<int[]> boxpos; // 箱が置かれた場所。

// note:joint,boxposに格納するint[]は弄らないのでコピー時参照可能

public BoxField(int w,int h){
datawidth = w;
dataheight= h;
maxwidth =0;
maxheight=0;
data = new boolean[w][h];
clear();
}

// フィールドに値をセットして初期化
public BoxField(int w,int h,boolean[][] d,int mw,int mh,LinkedList<int[]> jl,LinkedList<int[]> bpl){
int i;
datawidth = w;
dataheight= h;
data = new boolean[w][h];
for (i=0;i<d.length;i++)
data[i] = d[i].clone();
maxwidth =mw;
maxheight=mh;
joint = new LinkedList<int[]>();
joint.addAll(jl);
boxpos = new LinkedList<int[]>();
boxpos.addAll(bpl);
}

// 初期化(コンストラクタからも呼ばれる)
public void clear(){
int x,y;
for (y=0;y<dataheight;y++)
for (x=0;x<datawidth;x++)
data[x][y] = false;
maxwidth =0;
maxheight=0;

joint = new LinkedList<int[]>();
joint.add(new int[]{0,0}); // 初めは左上一点に置ける
boxpos = new LinkedList<int[]>();
}

// jointのサイズを返す
public int getJointNum(){
return joint.size();
}

// 箱を置く
public boolean putBox(int idx,int bw,int bh){
int x,y,bx,by;
int[] ac;

// 範囲外のidx
if (idx<0 || joint.size() <= idx) return false;

// jointの座標を取り出す
ac = joint.remove(idx);
bx=ac[0]; by=ac[1];
boxpos.add(new int[]{bx,by});

// 左・上にスペースがあるのはダメ。
// 例え置けるだけのスペースがあったとしても、別の順序で置けばその置き方ができる
if (0<bx)
for (y=by;y<bh+by;y++)
if (!data[bx-1][y]) return false;
if (0<by)
for (x=bx;x<bw+bx;x++)
if (!data[x][by-1]) return false;

// 置こうとしている場所に既にブロックがあるか
for (y=by;y<bh+by;y++)
for (x=bx;x<bw+bx;x++)
if (data[x][y]) return false;

// 空間を占領する
for (y=by;y<bh+by;y++)
for (x=bx;x<bw+bx;x++){
data[x][y] = true;
}


// 最小の長方形を再計算
if (maxwidth <bx+bw) maxwidth =bx+bw;
if (maxheight<by+bh) maxheight=by+bh;

// ブロックに接することができるjointを追加する
// 長い辺から順に追加する
if (bw<bh){
for (y=0;y<bh;y++){
joint.add(new int[]{bx+bw,by+y});
}
for (x=0;x<bw;x++){
joint.add(new int[]{bx+x,by+bh});
}
}else{
for (x=0;x<bw;x++){
joint.add(new int[]{bx+x,by+bh});
}
for (y=0;y<bh;y++){
joint.add(new int[]{bx+bw,by+y});
}
}

return true;
}
public void removeJoint(){
joint.remove(0);
}

public int calcMaxarea(){
return maxwidth*maxheight;
}

// 長方形状に密に埋まっているか
public boolean isFillRect(){
int x,y;
for (y=maxheight-1;0<=y;y--)
for (x=maxwidth-1;0<=x;x--)
if (!data[x][y]) return false;
return true;
}

// boxposが引数と順不同で一致するか
// 引数のint[]の中身は重複しないはず
public boolean isEqualBoxPos(LinkedList<int[]> target){
Iterator<int[]> i1,i2;
int[] a1,a2;
boolean f;
// サイズ違ってたら絶対に一致しない(起きないはず)
if (target.size() != boxpos.size()) return false;

// 走査
i1 = boxpos.iterator();
while (i1.hasNext()){
a1 = i1.next();
i2 = target.iterator();
f=false;
while(i2.hasNext()){
a2 = i2.next();
if (a1[0] == a2[0] && a1[1] == a2[1]) {f=true;break;}
}
if (!f) return false;
}
return true;
}

// boxposの参照を返す
public LinkedList<int[]> getBoxPos(){
return boxpos;
}

// 追記:表示は反転しますよー
public void print(){

int x,y;
for (y=maxheight-1;0<=y;y--){
for (x=maxwidth-1;0<=x;x--){
System.out.print(data[x][y]?"■":"□");
}
System.out.println("");
}
}

@Override
public BoxField clone(){
// お手軽実装
return new BoxField(datawidth,dataheight,data,maxwidth,maxheight,joint,boxpos);
}

}
スポンサーサイト

テーマ : プログラミング
ジャンル : コンピュータ

tag : Java アルゴリズムとデータ構造

コメントの投稿

非公開コメント

承認待ちコメント

このコメントは管理者の承認待ちです
ブログ移転のお知らせ
ブログをshonen.hateblo.jpに移転します. 新規の記事はこちらに投稿します.
プロフィール

舞葉(ぶよう)

Author:舞葉(ぶよう)
github.io
はてなブログ(競プロ)

古い記事のソースコードは色分けしていないので、高機能テキストエディタに貼り付けたほうが見やすいかも。

検索フォーム
このブログについて
自分がつまづいた話題、なんとなく書きたいと思ったこと、ググったけど殆ど資料なかったぞオイ な話等をアップする予定。通りすがりでも、参考になっていただければと。プログラムの例外入力、メモリリークは責任負いません。投稿された記事は修正・削除する場合があります。
カテゴリ
タグ

HSP3アルゴリズムとデータ構造c++RubyJavaUnity画像解析C機械学習C#LinuxcodeIQKinectMinecraftTonyuSystemraspberrypiPythonHTML5音声制御Simulinkruby俺ルール通信制御Javascriptシミュレーション

counter-shinobi
固定記事
最新記事
最新コメント
月別アーカイブ
ブロとも申請フォーム

この人とブロともになる

アクセスランキング
[ジャンルランキング]
コンピュータ
995位
アクセスランキングを見る>>

[サブジャンルランキング]
プログラミング
199位
アクセスランキングを見る>>
上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。