独学道場で、アルゴリズムの勉強を再開しています。
僕らが主催するプログラミング独学道場で、帰国後遠ざかっていた アルゴリズムの勉強を再開。 Manberという人が書いた「Introduction to Algorithms」の第1章の末尾、エクササイズの1.3をやった。
独学道場とは www.dokugaku.io
エクササイズ 1.3 は、訳すとこんな感じ。
「9, 44, 32, 12, 7, 42」のような順番で並ぶ数字のリストを考えてください。 このリストから、できるだけ少ない回数 数字を取り除いて、数字が大きくなる順で並ぶようなリストにしてください。
自分が唸って書いたRubyスクリプトは下記。もっと良いやり方あるよ! って方は、ぜひぜひ!コメントください。
require 'pp' def make_ol(list) possible_arr = [] list.each do |n| possible_arr.each do |arr| i = (arr.length - 1) while i >= 0 if arr[i] < n arr.delete_if{ |m| m > n } arr << n break end i -= 1 end end possible_arr << [n] pp possible_arr end possible_arr.max{ |a,b| a.length <=> b.length } end pp make_ol([9, 44, 32, 12, 7, 42])