ロボット救出作戦

最近は災害現場でロボットの活躍が期待されている。というかもう活躍し始めているらしい。それを聞いて考えたのが、ロボットが途中で故障したらやっぱりロボットが救出に行くのだろうか、ということ。過酷な状況下では救出に行くロボットも故障するだろうから、一回の出動で救出出来ない場合もあるだろう。そんなことをあれこれ考えていたらちょっとしたパズルを思いついた。

(問題)
ある災害現場で、出動したロボット(No.0)が故障して止まってしまった。場所は出発点から距離Lの地点。ロボットには貴重な情報が入っているので別のロボットでけん引して回収したい。しかし、救出用ロボットもNo.0の所まで行って戻ってくるだけの堅牢さはなく、途中で故障してしまう。そこで、次々と救出用ロボットを繰り出して戻って来れるところまでけん引しては次のロボットに引き継ぐことにした(図1)。

図1 ロボットの救出方法

救出用ロボットNo.1は距離a(<2L)しか走れないが、幸いなことに途中で技術が向上し、No.2はNo.1のb倍、No.3はNo.2のさらにb倍…というように、走行距離を増やしていける。さて、No.0をけん引して出発点まで戻って来れるのは何台めのロボットか。

（答え)
ロボットNo.kの最終位置をx(k)とする。x(k)は漸化式で表すことができる。

x(k)=2・x(k-1)-a・b^(k-1)
x(0)=L

なんか面倒な形になったが、ちょっと書き下してみるとこの漸化式は簡単に解くことができることがわかる。(面倒な人はWolfram先生に聞いてね！）

x(0)=L
x(1)=2・L-a
x(2)=2・(2・L-a)-a・b
x(3)=2・(2・(2・L-a)-a・b)-a・b^2
…
x(k)=2^k・L-a・(2^(k-1)+b・2^(k-2)+…b^(k-1))

よって、等比級数の公式を使って、

x(k)=L・2^k-a・(2^k - b^k)/(2-b)

となることがわかる。ここで、x(n)=0となるようなnを求めると、

n=log((a+(b-2)・L)/a)/log(b/2)

を得る。(ただしnは整数だから小数部分を切り上げた値が答えになる)
なお、図2はL=1の時のnのグラフをWolfram先生に描いてもらったもの。

n=log((a+(b-2)・L)/a)/log(b/2)のグラフ。(ただしL=1)

…とまぁこんな感じ。別に意外な結果が出るわけではない。しいて言えば漸化式が簡単に解けるところが面白い。

覆面算を計算するプログラムを作ってみた(CodeIQ)

CodeIQ 増井技術士事務所さんの問題(https://codeiq.jp/ace/thisweek_masuipeo/q860)に解答するため覆面算のプログラムを作った。Fortranで。

バッジ貰えたのでソースコード公開します:D

    program Console1
    implicit none
 
    integer, parameter :: lm = 9
    integer :: a(0:lm), l
    integer :: i
 
    write(*, 1000)
    1000 format('  a  d  e  i  k  l  r  s  t  w')
 
    l = 0
    do i = 0, lm
        a(l) = i
        call sub(lm, l, a)
    enddo
    end program Console1

    recursive subroutine sub(lm, l, a)
    implicit none
    integer, parameter :: nstde = 0
    integer, intent(in) :: lm, l, a(0:lm)
    integer :: l1, a1(0:lm)
    integer :: i, ii, p, q, r, s
 
    if(l == lm)then
        if(a(6) /= 0 .and. a(9) /= 0 .and. a(8) /= 0 .and. a(7) /= 0)then
            p =                     a(6) * 1000 + a(2) * 100 + a(0) * 10 + a(1)
            q = a(9) * 10000 + a(6) * 1000 + a(3) * 100 + a(8) * 10 + a(2)
            r =                      a(8) * 1000 + a(0) * 100 + a(5) * 10 + a(4)
            s = a(7) * 10000 + a(4) * 1000 + a(3) * 100 + a(5) * 10 + a(5)
            if(s == p + q + r)then
                write(nstde, 1000)(a(i), i = 0, lm)
                1000 format(10(1x,i2))
            endif
        endif
    else
        l1 = l + 1
        a1 = a
        loop1: do i = 0, lm
            a1(l1) = i
            do ii = 0, l
                if(a1(l1) == a1(ii))cycle loop1
            enddo
            call sub(lm, l1, a1)
        enddo loop1
    endif
 
    end subroutine sub

問題ごとにプログラムを書き換える必要はあるけれど、再帰を使って割とシンプルにかけたと思う:)

《チケットゴブル問題》をPerlで解いてみた(CodeIQ)

結城浩先生のチケットゴブル問題(https://codeiq.jp/ace/yuki_hiroshi/q863)を解いてみた。よく知られたアルゴリズム（貪欲法）に従えばもっと簡単に解けるとのことだけど、一応バッジ貰えたんでここに記録しておく。

1. アイディア

（証明に一部誤植がありました。すみません＞結城先生）

複数存在する解のうちの一つを求める手順として以下を考えた。

1) 出発日の早い順にチケットを並べなおす。
2) 二枚のチケットの日程が包含関係にあるとき、日程の長い方の航空券を取り除く（全く同じ日程の場合は一方を取り除く)。
3) こうして得られたチケットの組を{(L1,R1),(L2,R2),...,(LN,RN)}と表すことにする。
Lk, Rkはそれぞれk番目のチケットの出発日、帰還日である。
4) (l1,r1)=(L1,R1)とする。
5) (lk,rk)=(LK,RK)とする。ただしKは、LK-1<=rk-1<LKを満たすように選ぶ。
5.の手順を繰り返すことにより得られたチケットの組{(l1,r1),...,(ln,rn)}は解の一つである。

上の手順で解の一つが求められるためには、
a){(L1,R1),...,(LN,RN)}の要素のみからなる解が存在する。
b)(L1,R1)を要素とする解が存在する。
c)ある解{(l1,r1),...,(ln,rn)}に対して、{(l1,r1),...,(lk-1,rk-1)}を含み、かつLK-1<=rk-1<LKを満たすような(LK,RK)を要素とするような解が存在する。
を証明すればよい。

a)の証明
ある解{(l1,r1),...,(ln,rn)}のk枚目のチケット(lk,rk)に対し、lk<l,r<rkとなるようなチケット(r,k)が存在するとする。{(l1,r1),..,(lk-1,rk-1),(l,r),(lk+1,rk+1),...,(ln,rn)}は日程が重複しないn枚のチケットからなるのでこれも解である。日程が包含関係にあるすべてのチケットに対しこの置き換えを行って得られる解は{(L1,R1),...,(LN,RN)}の要素のみからなる。//
以下、b)c)の証明ではa)の条件を満たす解のみについて考える。

b)の証明
(L1,R1)を含まないある解{(l1,r1),...,(ln,rn)}が存在するとする。1)2)より、L1<l1かつR1<r1である。解に含まれるチケット同士では日程は重複しないのでr1<l2,したがってR1<l2。
{(L1,R1),(l2,r2),...,(ln,rn)}は日程が重複しないn枚のチケットからなるのでこれも解である。//

c)の証明
(lk,rk)=(LK,RK)ならば証明終了。そうでない場合1)2)およびLK-1<=rk-1<LKより、LK<lkかつRK<rkである。解に含まれるチケット同士では日程は重複しないのでrk<lk+1,従ってRK<lk+1である。
{(l1,r1),...,(lk-1,rk-1),(LK,RK),(lk+1,rk+1),...,(ln,rn)}は日程が重複しないn枚のチケットからなるのでこれも解である。//

2. コード

#!/usr/bin/perl -w
$infile = 'tickets.txt';
$ofilecsv = 'answer.csv';
$ofiletxt = 'answer.txt';

# $tk[$i][0] : 元データ
# $tk[$i][1] : 行先
# $tk[$i][2] : 出発日(Julian)
# $tk[$i][3] : 帰還日(Julian)
# $tk[$i][4] : 他の日程を包含する場合1, そうでない場合は0

open(INFILE, $infile) || die("# can not open $infile");
$i=0;
while(<INFILE>){
$tk[$i][0] = $_;
chomp($tk[$i][0]);
($tk[$i][1], $schedule) = split(/ /,$tk[$i][0]);
($date1, $date2) = split(/-/,$schedule);
($mm1, $dd1) = split(/\//, $date1);
($mm2, $dd2) = split(/\//, $date2);
$tk[$i][2]=jd($mm1, $dd1);
$tk[$i][3]=jd($mm2, $dd2);
$i++;
}
$nd = $i;
close(INFILE);

for ($i = 0; $i < $nd; $i++) {
$tk[$i][4] = 0;
for($j = 0; $j < $nd; $j++){
if($tk[$i][2] <= $tk[$j][2] &&
  $tk[$i][3] >= $tk[$j][3]){
if($tk[$i][2] != $tk[$j][2] ||
  $tk[$i][3] != $tk[$j][3] ||
  $i > $j){
$tk[$i][4] = 1;
}
}
}
}

@tk2 = sort {$a->[4]<=>$b->[4] or $a->[2] <=> $b->[2]} @tk;

$tk3[0] = $tk2[0];
for($i = 1; $i < $nd; $i++){
if($tk2[$i][4] == 0){
if($tk2[$i][2] > $tk3[$#tk3][3]){
$tk3[$#tk3 + 1] = $tk2[$i];
}
}
}

open(OFILECSV, ">$ofilecsv") || die("# can not open $ofilecsv\n");
printf(OFILECSV "dest,jd1,jd2, flag, str\n");
for($i = 0; $i <= $#tk3; $i++){
printf(OFILECSV "%s, %d, %d, %d, %s\n",
$tk3[$i][1], $tk3[$i][2], $tk3[$i][3], $tk3[$i][4], $tk3[$i][0]);
}

@tk4 = sort {$a->[1] cmp $b->[1]} @tk3;

open(OFILETXT, ">$ofiletxt") || die("# can not open $ofiletxt\n");
printf(OFILETXT "%d", $#tk4 + 1);
for($i = 0; $i <= $#tk4; $i++){
printf(OFILETXT " %s", $tk4[$i][1]);
}

sub jd {
my (@dm, $jd, $mm, $dd, $i);
@dm = (31, 29, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31);
$jd = 0;
($mm, $dd) = @_;
for ($i = 1; $i < $mm; $i ++){
$jd = $jd + $dm[$i-1];
}
$jd = $jd + $dd;
return $jd;
}