peterdk · December 11, 2015 21:48 · Jan 29, 2013 · Jan 29, 2013 · Jan 29, 2013 · Jan 29, 2013
diff --git a/3 - find the min.rb b/3 - find the min.rb
@@ -111,7 +111,7 @@ def generate_k_row(m,k,negative_index)
 
 
 input = data.lines.to_a
-cases = ((input.size - 1) /2)
+cases = ((input.size - 1) / 2)
 results = []
 cases.times do |case_index|
 line1 = input[(case_index * 2) + 1].chomp

diff --git a/3 - find the min.rb b/3 - find the min.rb
@@ -1,3 +1,4 @@
+require 'set'
 
 def find_min_better3(a,b,c,r,k,n)
 

diff --git a/3 - find the min.rb b/3 - find the min.rb
@@ -1,52 +1,143 @@
-def find_min(a,b,c,r,k,n)
 
-#Generate initial numbers with the given generator
+def find_min_better3(a,b,c,r,k,n)
+
 m = []
 m << a
 (k - 1).times do |k|
   m << ((b * m[k] + c) % r)
 end
-last_k_items = m[-k..-1]
 
-#Calculate what the negative index is (backwards index from end) for the required item on position n.
+puts "M items generated by pseudo generator: #{m.size}"
+last_k_items = m[-k..-1]
+#puts last_k_items.inspect
 item_index = (n % k) - (n/k)
 negative_index = item_index < 0
 item_index = item_index.abs % last_k_items.size
 item_index = 0 - item_index if negative_index
 if (!negative_index)
+  puts "index: #{item_index}"
+  puts "k == #{k}"  
   item_index = item_index - (k+1)
 end
-
-#Generate the cyclic row of K items
+puts "index = #{item_index}"
 k_row = generate_k_row(last_k_items, k, item_index)
+puts k_row.size
 
-#RESULT
 return k_row[item_index]
 
 end
 
 def generate_k_row(m,k,negative_index)
-#Initial row. Just 0,1,2,3...K
 k_row = (0..k).to_a
 
 deleted = Set.new
-
-#Traverse the k_row from end until required index is in the list. 
+puts "calculating down to: #{k + negative_index}"
 start = k-1
-ending = k + negative_index #Very important: otherwise you use 0 and generate all the items. (much!)
+ending = k + negative_index
 (start.downto ending).each do |i|
+  #100 - 90
+
+  if (i % 250 == 0)
+    max = start - ending
+    current = i - ending
+    puts "#{(((start-current-ending)/max.to_f) * 100).to_i}%"
+
+  end
+  #puts "#{m[i]} #{k_row[i+1]}"
   m_i = m[i]
   if (m_i > k_row[i+1])
-    #Do nothing
+    #let it stay
+  #  puts "stay"
   else
+   # puts "delete #{m[i]} and insert #{m[i]} at #{i+1}"
     if (!deleted.include?(m_i))
       k_row.delete(m_i)
       deleted << m_i
       k_row.insert(i+1,m_i)
   end
+    # puts k_row.inspect
   end
 end
 
+#puts k_row.inspect
 return k_row
 
-end
+end
+
+data = <<EOF
+20
+73 26
+5 8 4 54214
+1000000000 100000
+999999999 1 999999999 1000000000
+59 26
+14 19 681 59
+28 21
+6 5 1 85919
+1000000000 1
+12 7 74 12
+1000000000 100000
+1 1 0 2
+640834505 28785
+3 9 1 999946125
+46 18
+7 11 9 46
+186 75
+68 16 539 186
+98 59
+6 30 524 98
+840698758 13331
+8 7 10 999955808
+45068754 29153
+2 9 5 999904402
+232959116 56689
+4 9 1 999903057
+22 21
+1 4 869 22
+249718282 93729
+1 5 6 999917908
+177 73
+7 7 5 56401
+218492221 46085
+3 7 1 999969453
+66 39
+35 2 589 66
+254 99
+1 8 9 74990
+78 51
+3 5 5 51230
+EOF
+
+
+input = data.lines.to_a
+cases = ((input.size - 1) /2)
+results = []
+cases.times do |case_index|
+line1 = input[(case_index * 2) + 1].chomp
+line2 = input[(case_index * 2) + 2].chomp
+n,k = line1.match(/(\d+) (\d+)/).captures.map{|s|s.to_i}
+a,b,c,r = line2.match(/(\d+) (\d+) (\d+) (\d+)/).captures.map{|s|s.to_i}
+puts "Case #{case_index + 1}"
+puts "a:#{a} b:#{b} c:#{c} r:#{r}"
+puts "n:#{n} k:#{k}"
+#result = find_min(a,b,c,r,k,n)#WATCH IT: K BEFORE N
+#result_2 = find_min_better(a,b,c,r,k,n)
+#result_3 = find_min_better2(a,b,c,r,k,n)
+result_4 = find_min_better3(a,b,c,r,k,n)
+#puts "m[0] = #{a}"
+#puts "m[i] = (#{b} * m[i-1] + #{c}) % #{r}"
+#puts "(((#{a} * #{b}) + #{c}) % #{r})/#{a} = #{(((a * b) + c)%r).to_f / a}"
+#puts "Case \##{case_index + 1}: #{result}"
+#puts "Case \##{case_index + 1}: #{result_2}"
+#results << "Case \##{case_index + 1}: #{result_3}"
+results << "Case \##{case_index + 1}: #{result_4}"
+
+
+
+end
+puts
+puts
+puts results.join("\n")
+# file = File.new("3-output.txt", "w")
+# file << results.join("\n")
+# file.close
diff --git a/3 - find the min.rb b/3 - find the min.rb
@@ -0,0 +1,52 @@
+def find_min(a,b,c,r,k,n)
+
+#Generate initial numbers with the given generator
+m = []
+m << a
+(k - 1).times do |k|
+  m << ((b * m[k] + c) % r)
+end
+last_k_items = m[-k..-1]
+
+#Calculate what the negative index is (backwards index from end) for the required item on position n.
+item_index = (n % k) - (n/k)
+negative_index = item_index < 0
+item_index = item_index.abs % last_k_items.size
+item_index = 0 - item_index if negative_index
+if (!negative_index)
+  item_index = item_index - (k+1)
+end
+
+#Generate the cyclic row of K items
+k_row = generate_k_row(last_k_items, k, item_index)
+
+#RESULT
+return k_row[item_index]
+
+end
+
+def generate_k_row(m,k,negative_index)
+#Initial row. Just 0,1,2,3...K
+k_row = (0..k).to_a
+
+deleted = Set.new
+
+#Traverse the k_row from end until required index is in the list. 
+start = k-1
+ending = k + negative_index #Very important: otherwise you use 0 and generate all the items. (much!)
+(start.downto ending).each do |i|
+  m_i = m[i]
+  if (m_i > k_row[i+1])
+    #Do nothing
+  else
+    if (!deleted.include?(m_i))
+      k_row.delete(m_i)
+      deleted << m_i
+      k_row.insert(i+1,m_i)
+  end
+  end
+end
+
+return k_row
+
+end
Original file line number	Diff line number	Diff line change
		@@ -1,3 +1,4 @@
		require 'set'

		def find_min_better3(a,b,c,r,k,n)