プログラマ脳を鍛える数学パズル
- Q25:オシャレな靴ひもの結び方｜プログラマ脳を鍛える数学パズル (13 Jul 2016 | Tags:
Q25:オシャレな靴ひもの結び方｜プログラマ脳を鍛える数学パズル )Q25:オシャレな靴ひもの結び方｜プログラマ脳を鍛える数学パズル
プログラマ脳を鍛える数学パズル シンプルで高速なコードが書けるようになる70問をやる。今回は、Q25:オシャレな靴ひもの結び方。
Q: スニーカーの合計12カ所の穴にひもを通すとき、交差する点が最も多くなるときの交点の数を求める。ただし、ひもを結ぶ位置は一番上とし、左右交互に使用する。
for { l <- (1 to n-1).permutations r <- (1 to n-1).permutations } yield { val path = (0+:l.init).zip(r).zip(l.zip(r)).foldLeft(Seq.empty[(Int,Int)]){(z,n)=>z:+n._1:+n._2}:+(l.last,0) (0 to path.length).foldLeft(0){(z,i) => z + (i+1 until path.length).count{ j => (path(i)._1 - path(j)._1) * (path(i)._2 - path(j)._2) < 0 } } }5行目のひもの通す順番を生成する部分がかなりカオスになってしまった。。
LinkLatest post:
- OpenWhiskのScala sbtプロジェクトのgiter8テンプレートを作った
- OpenWhisk+Scalaで作るServerless Architectureとっかかり
- BluemixにPlayframeworkアプリケーションをデプロイする
- sbt、Giter8を統合するってよ
- Scala 2.12.0でSAM型
Recent Books:
- Q24:完璧に撃ち抜くストラックアウト｜プログラマ脳を鍛える数学パズル (10 Jul 2016 | Tags:
Q24:完璧に撃ち抜くストラックアウト｜プログラマ脳を鍛える数学パズル )Q24:完璧に撃ち抜くストラックアウト｜プログラマ脳を鍛える数学パズル
プログラマ脳を鍛える数学パズル シンプルで高速なコードが書けるようになる70問をやる。今回は、Q24:完璧に撃ち抜くストラックアウト。
Q: 9枚の的を打ち抜く順番を考える。周囲にフレームのある5番の的以外は、隣り合う的を2枚抜きできる。この時、9枚の的を打ち抜く順番が何通りあるか求める。
val single = (1 to 9).map(Seq(_)) val double = Seq((1,2),(2,3),(1,4),(3,6),(4,7),(6,9),(7,8),(8,9)).map{i => Seq(i._1,i._2)} val memo = scala.collection.mutable.Map(Seq.empty[Seq[Int]]-> 1) def count(remain:Seq[Seq[Int]]):Int = { memo.getOrElse(remain, { val result = remain.foldLeft(0){(z,t) => z + count(remain.filterNot(_.exists(t.contains))) } memo + (remain -> result) result }) } count(single ++ double)Latest post:
- OpenWhiskのScala sbtプロジェクトのgiter8テンプレートを作った
- OpenWhisk+Scalaで作るServerless Architectureとっかかり
- BluemixにPlayframeworkアプリケーションをデプロイする
- sbt、Giter8を統合するってよ
- Scala 2.12.0でSAM型
Recent Books:
- Q23:ブラックジャックで大もうけ!?|プログラマ脳を鍛える数学パズル (09 Jul 2016 | Tags:
Q23:ブラックジャックで大もうけ!?|プログラマ脳を鍛える数学パズル )Q23:ブラックジャックで大もうけ!?|プログラマ脳を鍛える数学パズル
プログラマ脳を鍛える数学パズル シンプルで高速なコードが書けるようになる70問をやる。今回は、Q23:ブラックジャックで大もうけ!?。
Q: コインを1枚ずつ賭けていったとき、最初に10枚のコインを持ち、ゲームを24回行った時、手元にコインが残るよパターンが何通りか求める。
val memo = scala.collection.mutable.Map.empty[(Int,Int),Int] def bet(game:Int, coin:Int):Int = { if(game == 0) 1 else if(coin == 0) 0 else { memo.getOrElse(game->coin, { val result = bet(game-1, coin+1) + bet(game-1, coin-1) memo + ((game -> coin)->result) result }) } } bet(24,10)Latest post:
- OpenWhiskのScala sbtプロジェクトのgiter8テンプレートを作った
- OpenWhisk+Scalaで作るServerless Architectureとっかかり
- BluemixにPlayframeworkアプリケーションをデプロイする
- sbt、Giter8を統合するってよ
- Scala 2.12.0でSAM型
Recent Books:
- Q22:絡まない糸電話|プログラマ脳を鍛える数学パズル (08 Jul 2016 | Tags:
Q22:絡まない糸電話|プログラマ脳を鍛える数学パズル )Q22:絡まない糸電話|プログラマ脳を鍛える数学パズル
プログラマ脳を鍛える数学パズル シンプルで高速なコードが書けるようになる70問をやる。今回は、Q22:絡まない糸電話。
Q: 同一円周上に等間隔に並んだ子供が、ペアを組んで糸電話する。この時、意図が交差しないようペアを組む必要がある。16人の子供がいた場合、作ることができるペアが何通りあるかを求める。
val memo = scala.collection.mutable.Map(0->1) def count(num:Int):Int = { memo.getOrElse(num, { val result = (0 until num).fold(0){(z,a) => z + count(a)*count(num-a-1)} memo + (num -> result) result }) } count(16/2)Latest post:
- OpenWhiskのScala sbtプロジェクトのgiter8テンプレートを作った
- OpenWhisk+Scalaで作るServerless Architectureとっかかり
- BluemixにPlayframeworkアプリケーションをデプロイする
- sbt、Giter8を統合するってよ
- Scala 2.12.0でSAM型
Recent Books:
- Q21:排他的論理和で作る三角形|プログラマ脳を鍛える数学パズル (04 Jul 2016 | Tags:
Q21:排他的論理和で作る三角形|プログラマ脳を鍛える数学パズル )Q21:排他的論理和で作る三角形|プログラマ脳を鍛える数学パズル
プログラマ脳を鍛える数学パズル シンプルで高速なコードが書けるようになる70問をやる。今回は、Q21:排他的論理和で作る三角形。
Q: 「パスカルの三角形」を「右上の数と左上の数の和」ではなく「排他的論理和」で配置した時、2014番目の0が出力される段数を求める。
def makeCol(before:Seq[Int])(n:Int) = (before(n-1) + before(n))%2 def count(n:Int, before:Seq[Int], zero:Int=0):Int = { if(zero >= 2014) n-1 else { val next = 1+:(1 until n-1).map(makeCol(before)):+1 count(n+1, next, zero+next.count(_ == 0)) } } count(3,Seq(1,1))Latest post:
- OpenWhiskのScala sbtプロジェクトのgiter8テンプレートを作った
- OpenWhisk+Scalaで作るServerless Architectureとっかかり
- BluemixにPlayframeworkアプリケーションをデプロイする
- sbt、Giter8を統合するってよ
- Scala 2.12.0でSAM型
Recent Books:
- Q20:受難のファサードの魔法陣|プログラマ脳を鍛える数学パズル (03 Jul 2016 | Tags:
Q20:受難のファサードの魔法陣|プログラマ脳を鍛える数学パズル )Q20:受難のファサードの魔法陣|プログラマ脳を鍛える数学パズル
プログラマ脳を鍛える数学パズル シンプルで高速なコードが書けるようになる70問をやる。今回は、Q20:受難のファサードの魔法陣。
1 14 14 4 11 7 6 9 8 10 10 5 13 2 3 15 Q: 上の魔法陣を使い、以下の条件で足し算をした結果、その和が同じになる組み合わせが最もおおくなる値(和)を求める。
- 足し合わせるのは、縦・横・斜めに限らない
- 足し合わせる数字の個数は4つに限らない
(1 to numbers.length).foldLeft(Map.empty[Int,Int]){(y,num) => numbers.zipWithIndex.combinations(num).foldLeft(y){(z,n) => val v = n.foldLeft(0){(x,s) => x+s._1} z.updated(v,z.getOrElse(v,0)+1) } }.maxBy(_._2)Scalaの
combinationsは、Rubyのcombinationと異なり、同じ値を区別しないので、zipWithIndexを使って区別するようにしている。すごい無駄感。 区別しなかったとしても、66になるしね。。Latest post:
- OpenWhiskのScala sbtプロジェクトのgiter8テンプレートを作った
- OpenWhisk+Scalaで作るServerless Architectureとっかかり
- BluemixにPlayframeworkアプリケーションをデプロイする
- sbt、Giter8を統合するってよ
- Scala 2.12.0でSAM型
Recent Books:
- Q19:友達の友達は友達？|プログラマ脳を鍛える数学パズル (02 Jul 2016 | Tags:
Q19:友達の友達は友達？|プログラマ脳を鍛える数学パズル )Q19:友達の友達は友達？|プログラマ脳を鍛える数学パズル
プログラマ脳を鍛える数学パズル シンプルで高速なコードが書けるようになる70問をやる。今回は、Q19:友達の友達は友達？。
Q: 2つの数の最大公約数が1でない場合、それを友達とする。ある数から他のすべての数にたどり着くには、何段階の友達をたどれば良いか数える。1~Nまでの合成から7個を選んだ時、最大で6段階たどることになる最小のNを求める。
val primes: Stream[Int] = 2 #:: Stream.from(3).filter{n => !primes.takeWhile(_ <= math.sqrt(n)).exists(n % _ == 0)} primes.take(6).permutations.foldLeft(Int.MaxValue){(z,per) => Seq(z,((per.head * per.head)+:(0 to 4).map{i => per.slice(i,i+2).product}:+(per.last*per.last)).max).min }横に長くなってしまった。。
Latest post:
- OpenWhiskのScala sbtプロジェクトのgiter8テンプレートを作った
- OpenWhisk+Scalaで作るServerless Architectureとっかかり
- BluemixにPlayframeworkアプリケーションをデプロイする
- sbt、Giter8を統合するってよ
- Scala 2.12.0でSAM型
Recent Books:
- Q18:ショートケーキの日|プログラマ脳を鍛える数学パズル (01 Jul 2016 | Tags:
Q18:ショートケーキの日|プログラマ脳を鍛える数学パズル )Q18:ショートケーキの日|プログラマ脳を鍛える数学パズル
プログラマ脳を鍛える数学パズル シンプルで高速なコードが書けるようになる70問をやる。今回は、Q18:ショートケーキの日。
Q: ホールケーキを切り分けるとき、ケーキに乗っているイチゴの数がすべて異なるような切り方を考える(N個に切り分けるとき、1~N個のイチゴがそれぞれ乗っている)。ただし、隣り合う２つのケーキに乗っているイチゴの数の和がいずれも平方数にならなければならない。これらの条件を満たす最小のNを求める。
def num(n:Int):Stream[Int] = n #:: num(n+1) def check(n:Int, sqr:Seq[Int], before:Int = 1, acc:Set[Int] = Set(1)):Boolean = { if(acc.size == n) sqr.contains(1+before) else { (1 to n).diff(acc.toSeq).find{ next => sqr.contains(before+next) && check(n, sqr, next, acc + before) }.isDefined } } num(2).find{n => check(n, (2 to scala.math.sqrt(2*n).toInt).map(a => a*a))}.getLatest post:
- OpenWhiskのScala sbtプロジェクトのgiter8テンプレートを作った
- OpenWhisk+Scalaで作るServerless Architectureとっかかり
- BluemixにPlayframeworkアプリケーションをデプロイする
- sbt、Giter8を統合するってよ
- Scala 2.12.0でSAM型
Recent Books:
- Q17:30人31脚に挑戦！|プログラマ脳を鍛える数学パズル (30 Jun 2016 | Tags:
Q17:30人31脚に挑戦！|プログラマ脳を鍛える数学パズル )Q17:30人31脚に挑戦！|プログラマ脳を鍛える数学パズル
プログラマ脳を鍛える数学パズル シンプルで高速なコードが書けるようになる70問をやる。今回は、Q17:30人31脚に挑戦！。
Q: 30人31脚をするときの男女の並び方が何通りあるか求める。ただし、女子が隣り合わないようにする。
def pattern(num:Int):Int = { def stack(n:Int, last:Char):Int = { if(n == 0) 1 else if(last == 'b') stack(n-1,'b')+stack(n-1,'g') else stack(n-1,'b') } stack(num-1,'b')+stack(num-1,'g') } pattern(30)Latest post:
- OpenWhiskのScala sbtプロジェクトのgiter8テンプレートを作った
- OpenWhisk+Scalaで作るServerless Architectureとっかかり
- BluemixにPlayframeworkアプリケーションをデプロイする
- sbt、Giter8を統合するってよ
- Scala 2.12.0でSAM型
Recent Books:
- Q16:３本のひもで作る四角形|プログラマ脳を鍛える数学パズル (29 Jun 2016 | Tags:
Q16:３本のひもで作る四角形|プログラマ脳を鍛える数学パズル )Q16:３本のひもで作る四角形|プログラマ脳を鍛える数学パズル
プログラマ脳を鍛える数学パズル シンプルで高速なコードが書けるようになる70問をやる。今回は、Q16:３本のひもで作る四角形。
Q: 長さが1から500まで変化する同じ長さのひも３本で、正方形を１つ、長方形を２つ作った時、正方形の面積と２つの長方形の面積の和が等しくなる組をカウントする。ただし、同じ比で整数倍のものは１つとしてカウントする。
def count(max:Int) = { (for { len <- 1 to max/4 Seq(a,b) <- (1 until len).combinations(2) if a*a + b*b == len*len } yield { (a/len.toFloat, b/len.toFloat) }).toSet.size } count(500)Latest post:
- OpenWhiskのScala sbtプロジェクトのgiter8テンプレートを作った
- OpenWhisk+Scalaで作るServerless Architectureとっかかり
- BluemixにPlayframeworkアプリケーションをデプロイする
- sbt、Giter8を統合するってよ
- Scala 2.12.0でSAM型
Recent Books:
- Q15:階段で立ち話|プログラマ脳を鍛える数学パズル (28 Jun 2016 | Tags:
Q15:階段で立ち話|プログラマ脳を鍛える数学パズル )Q15:階段で立ち話|プログラマ脳を鍛える数学パズル
プログラマ脳を鍛える数学パズル シンプルで高速なコードが書けるようになる70問をやる。今回は、Q15:階段で立ち話。
Q: 10段の階段の上下にそれぞれ人がいて、最大3段飛ばしで移動したとき、2人が同じ段に止まる移動方法は何通りか求める。
メモ化してるから結構早い
val range = 1 to 4 val memo = scala.collection.mutable.Map.empty[(Int,Int),Int] def move(a:Int, b:Int):Int = { if(a > b) 0 else if(a == b) 1 else if(memo.isDefinedAt((a,b))) memo((a,b)) else { val res = range.fold(0){(z,up) => range.fold(z){(zz,down) => zz + move(a+up, b-down)}} memo += ((a,b) -> res) res } } move(0,10)Latest post:
- OpenWhiskのScala sbtプロジェクトのgiter8テンプレートを作った
- OpenWhisk+Scalaで作るServerless Architectureとっかかり
- BluemixにPlayframeworkアプリケーションをデプロイする
- sbt、Giter8を統合するってよ
- Scala 2.12.0でSAM型
Recent Books:
- Q14:W杯出場国しりとり|プログラマ脳を鍛える数学パズル (27 Jun 2016 | Tags:
Q14:W杯出場国しりとり|プログラマ脳を鍛える数学パズル )Q14:W杯出場国しりとり|プログラマ脳を鍛える数学パズル
プログラマ脳を鍛える数学パズル シンプルで高速なコードが書けるようになる70問をやる。今回は、Q14:W杯出場国しりとり。
Q: どの国名も１度しか使うことができないとき、最も長く続けられる順を求め、長さを応える。
foldLeftはmapしてmaxで置き換えられるし、その方が見た目シュッとするけど、こっちの方が性能は良いはず。val countries = Set("Brazil","Croatia","Mexico","Cameroon","Spain","Netherlands","Chile","Australia","Colombia","Greece","Cote d'lvoire","Japan","Uruguay","Costa Rica","England","Italy","Switzerland","Ecuador","France","Honduras","Argentina","Bosnia and Herzegovina","Iran","Nigeria","Germany","Portugal","Ghana","USA","Belgium","Algeria","Russia","Korea Republic") def count(last:Char, group:Set[String], acc:Int):Int = { val matching = group.filter(_.head == last) if(matching.size == 0) acc else { matching.foldLeft(acc){ (z,country) => val length = count(country.last.toUpper, group - country, acc + 1) if(length > z) counted else z } } } upperCase.foldLeft(1){(z,country) => val length = count(country.last.toUpper, countries - country, 1) if(length > z) length else z }Latest post:
- OpenWhiskのScala sbtプロジェクトのgiter8テンプレートを作った
- OpenWhisk+Scalaで作るServerless Architectureとっかかり
- BluemixにPlayframeworkアプリケーションをデプロイする
- sbt、Giter8を統合するってよ
- Scala 2.12.0でSAM型
Recent Books:
- Q13:覆面算を満たすのは何通り？|プログラマ脳を鍛える数学パズル (26 Jun 2016 | Tags:
Q13:覆面算を満たすのは何通り？|プログラマ脳を鍛える数学パズル )Q13:覆面算を満たすのは何通り？|プログラマ脳を鍛える数学パズル
プログラマ脳を鍛える数学パズル シンプルで高速なコードが書けるようになる70問をやる。今回は、Q13:覆面算を満たすのは何通り？。
Q: “READ+WRITE+TALK=SKILL”という文字列が与えられた時、式を満たす文字と数の組み合わせは何通りあるか？ただし、項の最上位に0は入らず、同じ文字には同じ数、異なる文字には異なる数が入る。
性能は良くない。 けど、左辺が単項 or 複数項の足し算、右辺の単項であれば、他の文字列でも可。
def count(str:String) = { val Array(left, right) = str.split("=",2) val expressions = left.split("[+]") val characters = (expressions.flatten ++ right).distinct val initials = right.head +: expressions.map(_.head) (0 to 9).permutations.count{ com => val mapping = characters.zip(com).toMap mapping.forall { case (char, num) => if(num == 0 && initials.contains(char)) false else true } && expressions.foldLeft(0){ (z, expr) => z + expr.reverse.zipWithIndex.foldLeft(0){ (zz, n) => zz + (mapping(n._1) * scala.math.pow(10, n._2).toInt) } } == right.reverse.zipWithIndex.foldLeft(0){(zzz, n) => zzz + mapping(n._1) * scala.math.pow(10, n._2).toInt } } } count("READ+WRITE+TALK=SKILL")Latest post:
- OpenWhiskのScala sbtプロジェクトのgiter8テンプレートを作った
- OpenWhisk+Scalaで作るServerless Architectureとっかかり
- BluemixにPlayframeworkアプリケーションをデプロイする
- sbt、Giter8を統合するってよ
- Scala 2.12.0でSAM型
Recent Books:
- Q12:平方根の数字|プログラマ脳を鍛える数学パズル (25 Jun 2016 | Tags:
Q12:平方根の数字|プログラマ脳を鍛える数学パズル )Q12:平方根の数字|プログラマ脳を鍛える数学パズル
プログラマ脳を鍛える数学パズル シンプルで高速なコードが書けるようになる70問をやる。今回は、Q12:平方根の数字。
Q: 平方根を少数で表したとき、0~9までの数字がすべて現れる最小の整数を求める。正の平方根のみを対象とし、整数部分を含む場合と、少数部分のみの場合を求める。
def num(n:Int):Stream[Int] = n#::num(n+1) 1 + num(1).indexWhere{ scala.math.sqrt(_).toString.take(11).distinct.length == 11 } 1 + num(1).indexWhere{ n => val s = scala.math.sqrt(n) (s - s.toInt).toString.take(12).tail.distinct.length == 11 }Latest post:
- OpenWhiskのScala sbtプロジェクトのgiter8テンプレートを作った
- OpenWhisk+Scalaで作るServerless Architectureとっかかり
- BluemixにPlayframeworkアプリケーションをデプロイする
- sbt、Giter8を統合するってよ
- Scala 2.12.0でSAM型
Recent Books:
- Q11:フィボナッチ数列|プログラマ脳を鍛える数学パズル (24 Jun 2016 | Tags:
Q11:フィボナッチ数列|プログラマ脳を鍛える数学パズル )Q11:フィボナッチ数列|プログラマ脳を鍛える数学パズル
プログラマ脳を鍛える数学パズル シンプルで高速なコードが書けるようになる70問をやる。前回で第１章が終わって、第2章に突入。今回は、Q11:フィボナッチ数列。
Q: フィボナッチ数列のうち、各桁の数字を足した数で割り切れ、144より大きなものを小さい順に5つ求める。
def fibStream(a:BigInt, b:BigInt):Stream[BigInt] = a #:: fibStream(b, a+b) def digits(num:BigInt, acc:Seq[BigInt] = Nil):Seq[BigInt] = { if(num/10 == 0) num+:acc else digits(num/10, num%10+:acc) } fibStream(0,1).filter{ fib => fib > 144 && fib % digits(fib).sum == 0 }.take(5).mkString("\n")Latest post:
- OpenWhiskのScala sbtプロジェクトのgiter8テンプレートを作った
- OpenWhisk+Scalaで作るServerless Architectureとっかかり
- BluemixにPlayframeworkアプリケーションをデプロイする
- sbt、Giter8を統合するってよ
- Scala 2.12.0でSAM型
Recent Books:
- Q10:ルーレットの最大値|プログラマ脳を鍛える数学パズル (23 Jun 2016 | Tags:
Q10:ルーレットの最大値|プログラマ脳を鍛える数学パズル )Q10:ルーレットの最大値|プログラマ脳を鍛える数学パズル
プログラマ脳を鍛える数学パズル シンプルで高速なコードが書けるようになる70問をやる。今回は、Q10:ルーレットの最大値。
Q: ヨーロピアンスタイルとアメリカンスタイルのルーレットで、2<=n<=36のnについて、連続するn個の数の和が最大になる場合において、ヨーロピアンスタイルがアメリカンスタイルよりも小さくなるnの個数を求める。
val euro = Seq(0,32,15,19,4,21,2,25,17,34,6,27,13,36,11,30,8,23,10,5,24,16,33,1,20,14,31,9,22,18,29,7,28,12,35,3,26) val usa = Seq(0,28,9,26,30,11,7,20,32,17,5,22,34,15,3,24,36,13,1,0,27,10,25,29,12,8,19,31,18,6,21,33,16,4,23,35,14,2) def max(target:Seq[Int], n:Int):Int = { val length = target.length (0 until length).fold(0){(z,start) => Seq(z,(0 until n).fold(0){(zz,n) => zz+target((start+n)%length)}).max } } (2 to 36).count{ n => max(euro, n) < max(usa, n) }この問題のなにがだるいって、ヨーロピアンとアメリカンの数の並びを入力しないといけないっていうのがだるい。kindleなのに、図の文字はコピーできないだなんて。。
Latest post:
- OpenWhiskのScala sbtプロジェクトのgiter8テンプレートを作った
- OpenWhisk+Scalaで作るServerless Architectureとっかかり
- BluemixにPlayframeworkアプリケーションをデプロイする
- sbt、Giter8を統合するってよ
- Scala 2.12.0でSAM型
Recent Books:
- Q09:つりあわない男女|プログラマ脳を鍛える数学パズル (22 Jun 2016 | Tags:
Q09:つりあわない男女|プログラマ脳を鍛える数学パズル )Q09:つりあわない男女|プログラマ脳を鍛える数学パズル
プログラマ脳を鍛える数学パズル シンプルで高速なコードが書けるようになる70問をやる。今回は、Q09:つりあわない男女。
タイトルが日経ほげほげの婚活イジリねたコラムっぽい。
Q: 男性20人、女性10人が到着順に並んだ場合、どこで区切っても２つのグループの男女の人数が同じにならないような到着順は何通りあるか。
val man = 20 val woman = 10 val end = Seq((19,10),(20,9)) def count(x:Int, y:Int):Int = { if(x < 0 || y < 0) 0 else if(x == 0 && y == 0) 1 else if(x != y && man - x != woman - y) count(x-1,y) + count(x,y-1) else 0 } end.foldLeft(0){(z,n) => z + count(n._1, n._2)}基本的な考え方は本の解説と同じだけど、到着順の組み合わせの求め方が違う。
Latest post:
- OpenWhiskのScala sbtプロジェクトのgiter8テンプレートを作った
- OpenWhisk+Scalaで作るServerless Architectureとっかかり
- BluemixにPlayframeworkアプリケーションをデプロイする
- sbt、Giter8を統合するってよ
- Scala 2.12.0でSAM型
Recent Books:
- Q08:優秀な掃除ロボット|プログラマ脳を鍛える数学パズル (21 Jun 2016 | Tags:
Q08:優秀な掃除ロボット|プログラマ脳を鍛える数学パズル )Q08:優秀な掃除ロボット|プログラマ脳を鍛える数学パズル
プログラマ脳を鍛える数学パズル シンプルで高速なコードが書けるようになる70問をやる。今回は、Q08:優秀な掃除ロボット。
Q: 同じ場所を通らない前後左右にのみ移動できる掃除ロボットを考える。このロボットが12回移動するときに考えられる経路のパターンは何通りあるか。
val RLUD = Seq((1,0),(-1,0),(0,1),(0,-1)) def move(count:Int, history:(Int, Int)*):Int = { if(history.length > count) 1 else { RLUD.foldLeft(0){(sum, to) => val next = (history.head._1 + to._1, history.head._2 + to._2) if(history.exists(_ == next)) sum else move(count, next+:history:_*) + sum } } } move(12,(0,0))畳み込みって和な響きするよね。 コンボリューションっていうとトランスフォーマーな響きだなぁ。
Latest post:
- OpenWhiskのScala sbtプロジェクトのgiter8テンプレートを作った
- OpenWhisk+Scalaで作るServerless Architectureとっかかり
- BluemixにPlayframeworkアプリケーションをデプロイする
- sbt、Giter8を統合するってよ
- Scala 2.12.0でSAM型
Recent Books:
- Q07:日付の2進数変換|プログラマ脳を鍛える数学パズル (18 Jun 2016 | Tags:
Q07:日付の2進数変換|プログラマ脳を鍛える数学パズル )Q07:日付の2進数変換|プログラマ脳を鍛える数学パズル
プログラマ脳を鍛える数学パズル シンプルで高速なコードが書けるようになる70問をやる。今回は、Q07:日付の2進数変換。
Q: 1964年10月10日から2020年7月24日の間で、YYYYMMDDの10進数を2進数に変換し、逆向きに並べ替えて10進数に戻した時、元の日付と同じになる日付を求める。
日付の操作が面倒なので、nscala-timeとJoda-Timeを使う。
import com.github.nscala_time.time.Imports._ import org.joda.time.Days val start = new DateTime("1964-10-10") val diff = Days.daysBetween(start, new DateTime("2020-07-24")).getDays (0 to diff).map(d => (start + d.days).toString("YYYYMMdd").toInt).filter{ date => val bin = date.toBinaryString bin.takeRight(4) == "1001" && java.lang.Integer.parseInt(bin.reverse, 2) == date }Latest post:
- OpenWhiskのScala sbtプロジェクトのgiter8テンプレートを作った
- OpenWhisk+Scalaで作るServerless Architectureとっかかり
- BluemixにPlayframeworkアプリケーションをデプロイする
- sbt、Giter8を統合するってよ
- Scala 2.12.0でSAM型
Recent Books:
- Q06:（改造版）コラッツの予想|プログラマ脳を鍛える数学パズル (17 Jun 2016 | Tags:
Q06:（改造版）コラッツの予想|プログラマ脳を鍛える数学パズル )Q06:（改造版）コラッツの予想|プログラマ脳を鍛える数学パズル
プログラマ脳を鍛える数学パズル シンプルで高速なコードが書けるようになる70問をやる。今回は、Q06:（改造版）コラッツの予想。
コラッツの予測
自然数nについて、
- nが偶数の場合、nを2で割る
- nが奇数の場合、nに3をかけて1を足す
という操作を繰り返す時、初期値がどんな数値であっても必ず1に到達する。
Q: 初回のみnに3をかけて1を足すことから始めた場合、「最初の数に戻る数」が10000以下の偶数のうち何個か求める。
def collatz(num:Int, target:Int):Boolean = { if(num == target) true else if(num == 1) false else if(num%2 == 0) collatz(num/2, target) else collatz(num*3+1, target) } (2 to 10000 by 2).count(num => collatz(num*3+1, num))Latest post:
- OpenWhiskのScala sbtプロジェクトのgiter8テンプレートを作った
- OpenWhisk+Scalaで作るServerless Architectureとっかかり
- BluemixにPlayframeworkアプリケーションをデプロイする
- sbt、Giter8を統合するってよ
- Scala 2.12.0でSAM型
Recent Books:
- Q05:いまだに現金払い？|プログラマ脳を鍛える数学パズル (15 Jun 2016 | Tags:
Q05:いまだに現金払い？|プログラマ脳を鍛える数学パズル )Q05:いまだに現金払い？|プログラマ脳を鍛える数学パズル
プログラマ脳を鍛える数学パズル シンプルで高速なコードが書けるようになる70問をやる。今回は、Q05:いまだに現金払い？。しかし、無駄に煽りを効かせたタイトルだなぁ
Q: 1000札を両替したときにでてくる硬貨の組み合わせは何通りあるか？ただし、取り扱う硬貨は500円、100円、50円、10円のみとし、硬貨の枚数は最大で15枚とする。
def count(price:Int, coins:Seq[Int], max:Int):Int = { coins.sortWith((a,b) => a > b) match { case coin::Nil => if(price/coin <= max) 1 else 0 case coin::t => (0 to price/coin).fold(0){ (sum:Int, num:Int) => count(price - num*coin, t, max - num) + sum } } } count(1000, Seq(500, 100, 50, 10), 15)Latest post:
- OpenWhiskのScala sbtプロジェクトのgiter8テンプレートを作った
- OpenWhisk+Scalaで作るServerless Architectureとっかかり
- BluemixにPlayframeworkアプリケーションをデプロイする
- sbt、Giter8を統合するってよ
- Scala 2.12.0でSAM型
Recent Books:
- Q04:棒の切り分け|プログラマ脳を鍛える数学パズル (14 Jun 2016 | Tags:
Q04:棒の切り分け|プログラマ脳を鍛える数学パズル )Q04:棒の切り分け|プログラマ脳を鍛える数学パズル
プログラマ脳を鍛える数学パズル シンプルで高速なコードが書けるようになる70問をやる。今回は、Q04:棒の切り分け。
Q: 長さ
n[cm]の1本の棒を1[cm]単位に切り分ける。ただし、1本の棒を一度に切ることが出来るのは1人だけ(ex. 棒が3本あれば同時に3人で切ることができる)。最大m人いるとき、最短何回で切り分けられるか。20cmを3人の場合と、100cmを5人の場合と、それぞれ求めろ。
def divide(m:Int, n:Int, num:Int = 1, acc:Int = 0):Int = { if(num >= n) acc else if(num < m) divide(m, n, num*2, acc + 1) else divide(m, n, num + m, acc + 1) } divide(3, 20) divide(5, 100)Latest post:
- OpenWhiskのScala sbtプロジェクトのgiter8テンプレートを作った
- OpenWhisk+Scalaで作るServerless Architectureとっかかり
- BluemixにPlayframeworkアプリケーションをデプロイする
- sbt、Giter8を統合するってよ
- Scala 2.12.0でSAM型
Recent Books:
- Q03:カードを裏返せ|プログラマ脳を鍛える数学パズル (12 Jun 2016 | Tags:
Q03:カードを裏返せ|プログラマ脳を鍛える数学パズル )Q03:カードを裏返せ|プログラマ脳を鍛える数学パズル
プログラマ脳を鍛える数学パズル シンプルで高速なコードが書けるようになる70問をやる。今回は、Q03:カードを裏返せ。 だいぶ間が空いてしまった。。
Q: 順番に並んだ1~100までの番号が書かれた100枚のカードが裏返しに置かれている。n番目のカードからn-1枚おきにカードを裏返すのを、2から100までやったとき、最後に裏向きになっているカードの番号を求めろ。
var cards = (1 to 100).map((_, false)) (2 to 100).foreach{ n => cards = cards.map{case(num, side) => (num, if(num%n == 0) !side else side)} } cards.flatMap{case(num, side) => if(side) None else Some(num)}だいぶやっつけな感じになってしまった。
Latest post:
- OpenWhiskのScala sbtプロジェクトのgiter8テンプレートを作った
- OpenWhisk+Scalaで作るServerless Architectureとっかかり
- BluemixにPlayframeworkアプリケーションをデプロイする
- sbt、Giter8を統合するってよ
- Scala 2.12.0でSAM型
Recent Books:
- Q02:数列の四則演算|プログラマ脳を鍛える数学パズル (23 Mar 2016 | Tags:
Q02:数列の四則演算|プログラマ脳を鍛える数学パズル )Q02:数列の四則演算|プログラマ脳を鍛える数学パズル
プログラマ脳を鍛える数学パズル シンプルで高速なコードが書けるようになる70問をやる。今回は、Q02:数列の四則演算。
Q: 1000~9999で、数字の各桁の間に四則演算の演算子を最低１つは入れて計算し、元の数の桁を逆から並べた数字と同じになるものを求める。
def calc(expr:List[Either[Char, Int]]):Int = { def recur(expr:List[Either[Char, Int]], acc:List[Int]):Int = { expr match { case Nil => acc.sum case Right(x)::xs => recur(xs, x::acc) case Left('+')::(Right(xs)::xss) => recur(xss, xs::acc) case Left('-')::(Right(xs)::xss) => recur(xss, (-xs)::acc) case Left('*')::(Right(xs)::xss) => recur(xss, (xs*acc.head)::acc.tail) case _ => throw new Exception() } } recur(expr, Nil) } def gen(num:Int):List[List[Either[Char, Int]]] = { val parsed = num.toString.map(_.asDigit) var comb:List[List[Either[Char, Int]]] = List(List(Right(parsed.head))) def left(c:Char):Either[Char, Int] = Left(c) def right(n:Int):Either[Char, Int] = Right(n) for(n <- parsed.tail) { comb = comb.flatMap{ c => List(c.init++(right(c.last.right.get*10 + n)::Nil), c++(left('+')::right(n)::Nil), c++(left('-')::right(n)::Nil), c++(left('*')::right(n)::Nil)) } } comb } (1000 to 9999).flatMap { num => val reverse = num.toString.reverse if(gen(num).withFilter(_.exists(_.isLeft)).map(calc).exists(_.toString == reverse)) Option(num) else None }#calcは引数に数値もしくは演算子のリストを受け取り、計算結果を返す。ex.)
calc(List(Right(1), Left(+), Right(2))) > 3#genは引数に数値を受け取り、その数値の各桁と演算子のバリエーションの配列を返す。ex.)
gen(12) > List(List(Right(12)), List(Right(1), Left(+), Right(2)), List(Right(1), Left(-), Right(2)), List(Right(1), Left(*), Right(2)))Latest post:
- OpenWhiskのScala sbtプロジェクトのgiter8テンプレートを作った
- OpenWhisk+Scalaで作るServerless Architectureとっかかり
- BluemixにPlayframeworkアプリケーションをデプロイする
- sbt、Giter8を統合するってよ
- Scala 2.12.0でSAM型
Recent Books:
- Q01:10進数で回文|プログラマ脳を鍛える数学パズル (22 Mar 2016 | Tags:
Q01:10進数で回文|プログラマ脳を鍛える数学パズル )Q01:10進数で回文|プログラマ脳を鍛える数学パズル
Kindleのセールでプログラマ脳を鍛える数学パズル シンプルで高速なコードが書けるようになる70問を買ったから、ぼちぼちやってく。Q01:10進数で回文。
Q: 10進数、2進数、8進数のいずれで表現しても回文数となる数のうち、10進数の10以上で最小の値を求める。
def nextNum(n:Int):Stream[Int] = n #:: nextNum(n+2) nextNum(11).find{ decimal => decimal.toString == decimal.toString.reverse && decimal.toBinaryString == decimal.toBinaryString.reverse && decimal.toOctalString == decimal.toOctalString.reverse }.foreach(println)Latest post:
- OpenWhiskのScala sbtプロジェクトのgiter8テンプレートを作った
- OpenWhisk+Scalaで作るServerless Architectureとっかかり
- BluemixにPlayframeworkアプリケーションをデプロイする
- sbt、Giter8を統合するってよ
- Scala 2.12.0でSAM型
Recent Books:
