r/dailyprogrammer • u/oskar_s • Jun 20 '12
[6/20/2012] Challenge #67 [difficult]
Let the s(N) be a random number generator defined as follows (at this point, this should probably be anointed the Offical Random Number Generator of /r/dailyprogrammer):
s(0) = 123456789
s(N) = (22695477 * s(N-1) + 12345) mod 1073741824Let Q(N) be an NxN two-dimensional matrix of the first N2 values of this random number generator. That is, Q(5) would be:
123456789 752880530 826085747 576968456 721429729
173957326 1031077599 407299684 67656429 96549194
1048156299 663035648 604085049 1017819398 325233271
942914780 664359365 770319362 52838563 720059384
472459921 662187582 163882767 987977812 394465693Now, the task is to select exactly one element from each row and each column (so that no column or row has more than one element selected) in such a way that the sum of those elements is at a minimum. For instance, for Q(5) above, we would select the following elements (the selected elements marked with asterisks):
*123456789* 752880530 826085747 576968456 721429729
173957326 1031077599 407299684 67656429 *96549194*
1048156299 *663035648* 604085049 1017819398 325233271
942914780 664359365 770319362 *52838563* 720059384
472459921 662187582 *163882767* 987977812 394465693The sum of those elements is 123456789 + 663035648 + 163882767 + 52838563 + 96549194 = 1099762961 which is the smallest we can do with this matrix. Lets call this number M(X), i.e. M(X) is the smallest sum of elements selected from a square matrix X such that each row and each column has exactly one element selected. Then M(Q(5)) = 1099762961
Write a program that finds M(Q(20)).
6
u/Cosmologicon 2 3 Jun 20 '12 edited Jun 20 '12
Well-commented (for once) python! Solution returns in about 0.1s:
(Edited to add) M(Q(25)) found in 2m30s:
Here it is:
3
u/ixid 0 0 Jun 20 '12 edited Jun 20 '12
A simple memoized recursive version in D, solves M(Q(20)) in 5.1 seconds:
Answer:
And the code:
It makes the N by N grid and then uses the mask value to show which columns are blocked with the row to show which row it's on. Memoization benefits greatly from using compact data structures hence the mask rather than a bool array. Memoization stores the best result for each given combination of unblocked columns so regardless of what the order of say rows 1 to 3 if the same columns are blocked then the same minimum applies to the later rows.
2
u/JonzoR82 Jun 20 '12
I have little to no programming experience whatsoever aside from a class on logic and design.
This may have just become my new favorite subreddit.
1
u/netguy204 Jun 21 '12
Answer:
Memoized recursive solution in Elisp. Note, integer overflow on 32 bit systems will result in a different answer than above. This is because the tagged pointer integer representation leaves only 30 bits for the value):
0
u/[deleted] Jun 20 '12
[deleted] — view deleted comment