diff options
Diffstat (limited to 'haskell/wip')
| -rw-r--r-- | haskell/wip/145-how_many_reversible_numbers_are_there_below_onebillion.hs | 5 | ||||
| -rw-r--r-- | haskell/wip/345-matrix_sum.hs | 68 |
2 files changed, 70 insertions, 3 deletions
diff --git a/haskell/wip/145-how_many_reversible_numbers_are_there_below_onebillion.hs b/haskell/wip/145-how_many_reversible_numbers_are_there_below_onebillion.hs index e4fd400..77ef6fa 100644 --- a/haskell/wip/145-how_many_reversible_numbers_are_there_below_onebillion.hs +++ b/haskell/wip/145-how_many_reversible_numbers_are_there_below_onebillion.hs @@ -12,9 +12,8 @@ main = do - let notZeroEndedNums = filter (\x -> x `mod` 10 /= 0) [1..10 ^ 6] - revs = filter reversible notZeroEndedNums - -- print revs + let notZeroEndedNums = filter (\x -> x `mod` 2 /= 0) [1..10 ^ 7] + revs = filter reversible [1,3..10 ^ 6] --notZeroEndedNums print (length revs) -- print $ length $ filter id $ map reversible notZeroEndedNums -- print $ [r2 - r1 | (r1, r2) <- zip revs (tail revs)] diff --git a/haskell/wip/345-matrix_sum.hs b/haskell/wip/345-matrix_sum.hs new file mode 100644 index 0000000..77e46b5 --- /dev/null +++ b/haskell/wip/345-matrix_sum.hs @@ -0,0 +1,68 @@ +------ +-- Matrix Sum +-- Problem 345 +-- +-- We define the Matrix Sum of a matrix as the maximum sum of matrix elements with +-- each element being the only one in his row and column. For example, the Matrix Sum +-- of the matrix below equals 3315 ( = 863 + 383 + 343 + 959 + 767): +-- +-- 7 53 183 439 863 +-- 497 383 563 79 973 +-- 287 63 343 169 583 +-- 627 343 773 959 943 +-- 767 473 103 699 303 +-- +-- Find the Matrix Sum of: +-- +-- 7 53 183 439 863 497 383 563 79 973 287 63 343 169 583 +-- 627 343 773 959 943 767 473 103 699 303 957 703 583 639 913 +-- 447 283 463 29 23 487 463 993 119 883 327 493 423 159 743 +-- 217 623 3 399 853 407 103 983 89 463 290 516 212 462 350 +-- 960 376 682 962 300 780 486 502 912 800 250 346 172 812 350 +-- 870 456 192 162 593 473 915 45 989 873 823 965 425 329 803 +-- 973 965 905 919 133 673 665 235 509 613 673 815 165 992 326 +-- 322 148 972 962 286 255 941 541 265 323 925 281 601 95 973 +-- 445 721 11 525 473 65 511 164 138 672 18 428 154 448 848 +-- 414 456 310 312 798 104 566 520 302 248 694 976 430 392 198 +-- 184 829 373 181 631 101 969 613 840 740 778 458 284 760 390 +-- 821 461 843 513 17 901 711 993 293 157 274 94 192 156 574 +-- 34 124 4 878 450 476 712 914 838 669 875 299 823 329 699 +-- 815 559 813 459 522 788 168 586 966 232 308 833 251 631 107 +-- 813 883 451 509 615 77 281 613 459 205 380 274 302 35 805 +------ + + +main = do + print (testMatrix) + print (backtrack testMatrix 0 0 0 0) + +backtrack :: [[Int]] -> Int -> Int -> Int -> Int -> Int +backtrack mat col row maxsum prevSum + | col == 4 = backtrack mat col row (max currSum maxSum) 0 + | row == 4 = backtrack mat (succ col) 0 maxSum currSum + | otherwise = backtrack mat col (succ row) maxSum currSum + where currSum = prevSum + mat !! row !! col + +testMatrix = [ [ 7, 53, 183, 439, 863] + , [497, 383, 563, 79, 973] + , [287, 63, 343, 169, 583] + , [627, 343, 773, 959, 943] + , [767, 473, 103, 699, 303] + ] + +matrix = [ [ 7, 53, 183, 439, 863, 497, 383, 563, 79, 973, 287, 63, 343, 169, 583] + , [627, 343, 773, 959, 943, 767, 473, 103, 699, 303, 957, 703, 583, 639, 913] + , [447, 283, 463, 29, 23, 487, 463, 993, 119, 883, 327, 493, 423, 159, 743] + , [217, 623, 3, 399, 853, 407, 103, 983, 89, 463, 290, 516, 212, 462, 350] + , [960, 376, 682, 962, 300, 780, 486, 502, 912, 800, 250, 346, 172, 812, 350] + , [870, 456, 192, 162, 593, 473, 915, 45, 989, 873, 823, 965, 425, 329, 803] + , [973, 965, 905, 919, 133, 673, 665, 235, 509, 613, 673, 815, 165, 992, 326] + , [322, 148, 972, 962, 286, 255, 941, 541, 265, 323, 925, 281, 601, 95, 973] + , [445, 721, 11, 525, 473, 65, 511, 164, 138, 672, 18, 428, 154, 448, 848] + , [414, 456, 310, 312, 798, 104, 566, 520, 302, 248, 694, 976, 430, 392, 198] + , [184, 829, 373, 181, 631, 101, 969, 613, 840, 740, 778, 458, 284, 760, 390] + , [821, 461, 843, 513, 17, 901, 711, 993, 293, 157, 274, 94, 192, 156, 574] + , [ 34, 124, 4, 878, 450, 476, 712, 914, 838, 669, 875, 299, 823, 329, 699] + , [815, 559, 813, 459, 522, 788, 168, 586, 966, 232, 308, 833, 251, 631, 107] + , [813, 883, 451, 509, 615, 77, 281, 613, 459, 205, 380, 274, 302, 35, 805] + ] |