動機
研究室内の課題で水汲み問題を解く問題が出たので始めにPyhtonで書き、Javascriptの勉強中だったのでJavascriptでも書いてWebサイト風にアレンジしてみました。これをサーバーで公開するのもなぁと思ったのでコピペしてブラウザで開いてみてください。
Pythonのコード
water_jug.py
import queue
class Bottle:
def __init__(self,one,two):
self.one = 0 #一個目のボトル
self.two = 0 #二個目のボトル
self.one_max = one
self.two_max = two
def put(self,now_one,now_two,num,past_list): #oneのボトルを水で満たす
copy = past_list.copy()
if num ==1:
now_one = self.one_max
elif num ==2:
now_two = self.two_max
for i in range(len(copy)):
if copy[i] != [now_one,now_two]:
if (i== len(copy)-1):
copy.append([now_one,now_two])
queue.put(copy)
break
else:
break
def pour(self,now_one,now_two,num,past_list): #numから一方のボトルに水を移す
copy = past_list.copy()
if num==1: #oneからtwo
now_two += now_one
if now_two >= self.two_max: #あふれる場合,全部は入れない場合
now_one = now_two - self.two_max
now_two = self.two_max
else:
now_one = 0
elif num ==2: #twoからone
now_one += now_two
if now_one >= self.one_max: #あふれる場合,全部は入れない場合
now_two = now_one - self.one_max
now_one = self.one_max
else:
now_two = 0
for i in range(len(copy)):
if copy[i] != [now_one,now_two]:
if (i== len(copy)-1):
copy.append([now_one,now_two])
queue.put(copy)
break
else:
break
def away(self,now_one,now_two,num,past_list): #水を捨てる
copy = past_list.copy()
if num==1:
now_one = 0
elif num==2:
now_two = 0
for i in range(len(copy)):
if copy[i] != [now_one,now_two]:
if (i== len(copy)-1):
copy.append([now_one,now_two])
queue.put(copy)
break
else:
break
past_op = []
queue = queue.Queue()
num_one = int(input("Bottle1? "))
num_two = int(input("Bottle2? "))
num_Want = int(input("How much do you want? "))
bottle = Bottle(num_one,num_two)
bottle.one = bottle.one_max
past_op.append([bottle.one,bottle.two])
queue.put(past_op)
while (True):
get_queue = queue.get()
now = get_queue[-1]
bottle.one,bottle.two = now[0],now[1]
if (bottle.one == num_Want or bottle.two == num_Want):
for i in get_queue:
print(i)
break
if bottle.one > 0 and num_one > bottle.one:
bottle.put(bottle.one,bottle.two,1,get_queue)
bottle.pour(bottle.one,bottle.two,1,get_queue) #oneからtwo
bottle.away(bottle.one,bottle.two,1,get_queue) #oneを捨てる
if bottle.one == 0:
bottle.put(bottle.one,bottle.two,1,get_queue)
if bottle.one == num_one:
bottle.pour(bottle.one,bottle.two,1,get_queue) #oneからtwo
bottle.away(bottle.one,bottle.two,1,get_queue)
if bottle.two > 0 and num_two > bottle.two:
bottle.put(bottle.one,bottle.two,2,get_queue)
bottle.pour(bottle.one,bottle.two,2,get_queue) #oneからtwo
bottle.away(bottle.one,bottle.two,2,get_queue) #oneを捨てる
if bottle.two == 0:
bottle.put(bottle.one,bottle.two,2,get_queue)
if bottle.two == num_two:
bottle.pour(bottle.one,bottle.two,2,get_queue) #oneからtwo
bottle.away(bottle.one,bottle.two,2,get_queue)
if(queue.empty()):
print("無理です")
break
はい、めちゃくちゃ長いです。頑張ればもうちょい短くなると思います。
やってることはBottleクラスでボトル１と２の入っている水量とサイズを定義し、水を入れる関数と水を移す関数、水を捨てる関数を定義します。
あとはキューに今までの水の推移を表したリストを入れていき、ボトル１か２が目的の水量になったらその推移を表したリストを表示して終了です。
もし不可能な組み合わせ(例:6Lと3Lの容器で4Lを測るなど)をしたらいずれキューが空になるのでそうなったら無理と表示して終わりです。
Javascript(+HTML+CSS)のコード
water_jug.html
<!DOCTYPE html>
<html lang="ja">
<head>
<meta charset="utf-8">
<title>水量を測る</title>
<h1>水を測ってみよう！</h1>
<style type="text/css">
body{
text-align: center;
}
#table{
position: relative;
}
#table table{
position:absolute;
left: 50%;
}
</style>
<script>
var queue = [];
var past_op = [];
function Bottle(one,two){
this.one = 0;
this.two = 0;
this.one_max = one;
this.two_max = two;
}
function show(list_water){
var table = document.getElementById("table");
var string = "<table><tr><th>ボトル１</th><th>ボトル２</th></tr><br>";
for(var i = 0; i<= list_water.length-1; i++){
string += "<tr><td>"+list_water[i][0]+"</td><td>"+list_water[i][1]+"</td></tr><br>";
}
string +="</table><br>";
table.innertHTML = string;
}
function calc_water(myForm) {
var bottle = new Bottle(Number(myform.Bottle1.value),Number(myform.Bottle2.value));
bottle.one = bottle.one_max;
past_op.push([bottle.one,bottle.two])
queue.push(past_op)
while (1){
var get_queue = queue.shift()
var now = get_queue[get_queue.length -1]
bottle.one = now[0];
bottle.two = now[1];
if (bottle.one == Number(myform.Want_Water.value) || bottle.two == Number(myform.Want_Water.value)){
for (var i=0; i < get_queue.length; i++){
console.log(get_queue[i]);
}
show(get_queue);
break;
}
if (bottle.one > 0 && bottle.one_max > bottle.one){
bottle.put(bottle.one,bottle.two,1,get_queue);
bottle.pour(bottle.one,bottle.two,1,get_queue); //oneからtwo
bottle.away(bottle.one,bottle.two,1,get_queue); //oneを捨てる
}
if (bottle.one == 0){
bottle.put(bottle.one,bottle.two,1,get_queue);
}
if (bottle.one == bottle.one_max){
bottle.pour(bottle.one,bottle.two,1,get_queue); //oneからtwo
bottle.away(bottle.one,bottle.two,1,get_queue);
}
if (bottle.two > 0 && bottle.two_max > bottle.two){
bottle.put(bottle.one,bottle.two,2,get_queue);
bottle.pour(bottle.one,bottle.two,2,get_queue); //oneからtwo
bottle.away(bottle.one,bottle.two,2,get_queue); //oneを捨てる
}
if (bottle.two == 0){
bottle.put(bottle.one,bottle.two,2,get_queue);
}
if (bottle.two == bottle.two_max){
bottle.pour(bottle.one,bottle.two,2,get_queue); //oneからtwo
bottle.away(bottle.one,bottle.two,2,get_queue);
}
if (queue.length == 0){
cant();
break;
}
}
}
Bottle.prototype.put = function(now_one,now_two,num,past_list){
var copy = Array.from(past_list);
if (num ==1){
now_one = this.one_max;
}
else if (num ==2){
now_two = this.two_max;
}
for (var i=0;i< copy.length;i++){
if (past_list[i].toString() != [now_one,now_two].toString()){
if (i==copy.length-1){
copy.push([now_one,now_two]);
queue.push(copy);
break;
}
}
else{
break;
}
}
}
Bottle.prototype.pour = function(now_one,now_two,num,past_list){
var copy = Array.from(past_list)
if (num==1) {
now_two += now_one;
if (now_two >= this.two_max){ //あふれる場合,全部は入れない場合
now_one = now_two - this.two_max;
now_two = this.two_max;
}
else {
now_one = 0;
}
}
else if (num ==2){ //twoからone
now_one += now_two;
if (now_one >= this.one_max){//あふれる場合,全部は入れない場合
now_two = now_one - this.one_max;
now_one = this.one_max;
}
else{
now_two = 0;
}
}
for (var i=0;i< copy.length;i++){
if (past_list[i].toString() != [now_one,now_two].toString()){
if (i==copy.length-1){
copy.push([now_one,now_two]);
queue.push(copy);
break;
}
}
else{
break;
}
}
}
Bottle.prototype.away = function(now_one,now_two,num,past_list){ //水を捨てる
var copy = Array.from(past_list)
if (num==1){
now_one = 0;
}
else if (num==2){
now_two = 0;
}
for (var i=0;i< copy.length;i++){
if (past_list[i].toString() != [now_one,now_two].toString()){
if (i==copy.length-1){
copy.push([now_one,now_two]);
queue.push(copy);
break;
}
}
else{
break;
}
}
}
</script>
</head>
<body>
<form id="myform" name="myform"><p>
Bottle1の大きさ:<input type="text" name="Bottle1"><br>
Bottle2の大きさ:<input type="text" name="Bottle2"><br>
欲しい水の量:<input type="text" name="Want_Water"><br>
<input type="button" value="計算"
name="calc" onclick="calc_water(this.form)"><br>
</p></form>
<div id = "table">
</div>
</body>
</html>
javascriptは勉強して１週間でクソザコナメクジなのでもっといいコードが書けるかもしれません
やってることはpythonとほとんど同じです。解が見つかったら表を作成するHTMLコードを作成し表示するって感じです。
質問またはこうした方がいいってのがあったら気軽にコメントしてください