leet4_median.adb 7.3 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245
  1. with ada.text_io; use ada.text_io;
  2. with ada.float_text_io;
  3. use ada.float_text_io;
  4. with ada.numerics.generic_elementary_functions;
  5. with ada.containers.indefinite_vectors;
  6. procedure leet4_median is
  7. type sequence is array (positive range<>) of integer;
  8. package foo is new
  9. ada.numerics.generic_elementary_functions(float);
  10. package asdf is new ada.containers.indefinite_vectors
  11. (index_type => positive, element_type => sequence);
  12. use asdf;
  13. procedure print(v: in sequence) is
  14. begin
  15. for element of v loop
  16. put(element'image);
  17. end loop;
  18. new_line;
  19. end;
  20. function partial_merge
  21. (a: in sequence; b: in sequence; limit: in integer)
  22. return sequence is
  23. n : integer := a'length + b'length;
  24. merged :sequence(1 .. limit);
  25. i : integer := 1;
  26. ca : integer := 1;
  27. cb : integer := 1;
  28. ae : integer;
  29. be : integer;
  30. begin
  31. for i in 1 .. limit loop
  32. if ca <= a'length then
  33. ae := a(ca);
  34. else
  35. ae := integer'last;
  36. end if;
  37. if cb <= b'length then
  38. be := b(cb);
  39. else
  40. be := integer'last;
  41. end if;
  42. if ae < be then
  43. merged(i) := ae;
  44. ca := ca + 1;
  45. else
  46. merged(i) := be;
  47. cb := cb + 1;
  48. end if;
  49. end loop;
  50. return merged;
  51. end;
  52. function get_median_even
  53. (a: in sequence; b: in sequence) return float is
  54. n : integer := a'length + b'length;
  55. m1 : integer := n/2;
  56. m2 : integer := (n/2)+1;
  57. c : sequence := partial_merge(a, b, m2);
  58. begin
  59. put("merged: ");
  60. print(c);
  61. return float(c(m1)+c(m2))/2.0;
  62. end;
  63. function get_median_odd
  64. (a: in sequence; b: in sequence) return float is
  65. n : integer := a'length + b'length;
  66. m : integer := (n/2)+1; -- index of median
  67. c : sequence := partial_merge(a, b, m);
  68. begin
  69. put("merged: ");
  70. print(c);
  71. return float(c(m));
  72. end;
  73. -- first solution
  74. function get_median
  75. (a: in sequence; b: in sequence) return float is
  76. n : integer := a'length + b'length;
  77. begin
  78. if n mod 2 = 1 then
  79. -- if my length is 7, then i need the 4th index
  80. return get_median_odd(a,b);
  81. else
  82. -- if my length is 4 then i need 2+2+1/2
  83. -- if my length is 6 then i need 3+3+1/2
  84. return get_median_even(a,b);
  85. end if;
  86. end;
  87. function get_median_optimal
  88. (a : in sequence; b : in sequence) return float is
  89. n : integer := a'length;
  90. m : integer := b'length;
  91. low : integer := 1;
  92. high : integer := a'length;
  93. mid_a : integer;
  94. mid_b : integer;
  95. left_a : integer;
  96. right_a : integer;
  97. left_b : integer;
  98. right_b : integer;
  99. answer : float;
  100. iterations : integer := 0;
  101. target : float := foo.log(float(m+n));
  102. begin
  103. if n < m then
  104. return get_median_optimal(b, a);
  105. end if;
  106. while low <= high loop
  107. mid_a := (low+high)/2; -- 6/2 = 3
  108. mid_b := ((1+m+n)/2) - mid_a; -- 10/2 - 3 = 2
  109. --put_line("mid (a,b): " & mid_a'image & mid_b'image);
  110. if mid_a <= 0 then
  111. left_a := integer'first;
  112. else -- mid_a < a'length then
  113. left_a := a(mid_a);
  114. end if;
  115. if mid_a < a'length then
  116. right_a := a(mid_a+1);
  117. else
  118. right_a := integer'last;
  119. end if;
  120. -- b is the shorter array - avoid out of bounds
  121. if mid_b <= 0 then
  122. left_b := integer'first;
  123. elsif mid_b < b'length then
  124. left_b := b(mid_b);
  125. elsif mid_b >= b'length then
  126. left_b := b(b'last);
  127. end if;
  128. if mid_b < 0 then
  129. right_b := b(b'first);
  130. elsif mid_b < b'length then
  131. right_b := b(mid_b+1);
  132. else
  133. --right_b := b(b'last);
  134. right_b := integer'last;
  135. end if;
  136. --put_line("left (a,b): " & left_a'image & left_b'image);
  137. --put_line("right (a,b): " & right_a'image & right_b'image);
  138. -- both left values are less than both right values
  139. if (left_a <= right_b)
  140. and (left_b <= right_a) then
  141. if ((n + m) mod 2) = 0 then
  142. answer := float(
  143. integer'max(left_a, left_b)
  144. + integer'min(right_a, right_b)
  145. ) / 2.0;
  146. exit;
  147. else
  148. answer := float(integer'max(left_a, left_b));
  149. exit;
  150. end if;
  151. elsif (left_a > right_b) then
  152. high := mid_a - 1;
  153. elsif (left_b > right_a) then
  154. low := mid_a + 1;
  155. end if;
  156. iterations := iterations +1;
  157. end loop;
  158. put("iterations: " & iterations'image);
  159. put("; target: O(ln(m+n)) = " & target'image);
  160. if float(iterations) <= target then
  161. put(" ✓");
  162. end if;
  163. new_line;
  164. return answer;
  165. end;
  166. function test
  167. (x : in sequence; y : in sequence) return boolean is
  168. s : float := get_median(x,y);
  169. t : float := get_median_optimal(x,y);
  170. begin
  171. put("median =");
  172. put(s, 4, 1, 0); -- fore, aft, exp
  173. new_line;
  174. if s = t then
  175. return true;
  176. else
  177. put_line("result 1: " & float'image(s));
  178. put_line("result 2: " & float'image(t));
  179. end if;
  180. return false;
  181. end;
  182. procedure main is
  183. tests_a : asdf.vector;
  184. tests_b : asdf.vector;
  185. pass : integer := 0;
  186. begin
  187. tests_a.append((1,3));
  188. tests_a.append((1,2));
  189. tests_a.append((1,2,3,4,10));
  190. tests_a.append((1, 2, 3, 4, 10, 12,13,14,15,16,20,27,30));
  191. tests_a.append((1,2,3,4,5,6,7,8,9,10,11,12,13,14,15));
  192. tests_a.append((1,2,3,4));
  193. tests_a.append(((1,2,3,4,5,6)));
  194. tests_a.append((2,3,5,7,9));
  195. tests_b.append((1 => 2));
  196. tests_b.append((3,4));
  197. tests_b.append((5, 6, 11));
  198. tests_b.append((5, 6, 11));
  199. tests_b.append((1 => 17));
  200. tests_b.append((1 => 1));
  201. tests_b.append((1 => 0));
  202. tests_b.append((1,4,6,8,10));
  203. tests_a.append((1,1,1,1,22,40));
  204. tests_b.append((1,36,44,62,77,77,77,77));
  205. for i in 1..integer(tests_a.length) loop
  206. put_line("----------------------");
  207. put("a = ");
  208. print(tests_a(i));
  209. put("b = ");
  210. print(tests_b(i));
  211. if test(tests_a(i), tests_b(i)) then
  212. put_line("test case #" & i'image & " passed");
  213. pass := pass +1;
  214. end if;
  215. end loop;
  216. new_line;
  217. put_line(pass'image
  218. & " out of"
  219. & tests_a.length'image
  220. & " tests pass" );
  221. end;
  222. begin
  223. put_line("This is leetcode challenge #4");
  224. put_line("https://leetcode.com/problems/median-of-two-sorted-arrays/");
  225. main;
  226. end;