StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<p>The best solution is not a greedy algorithm from the top down, but rather an approach that starts with the last row and works up:</p> <pre><code>import Data.Function import Data.List -- All elements of Board are lists of equal lengths -- valid b = 1 == length (group (map length b)) type Value = Int type Board = [[Value]] type Index = Int type Result = ([Index], Value) p :: Board p = [[5,4,3,1],[10,2,1,0],[0,1,2,0],[2,3,4,20]] best_from :: Board -> Result best_from [] = undefined best_from xs | any null xs = undefined best_from b = best_of . best_list $ b best_list :: Board -> [Result] best_list b = foldr1 layer (map label b) where label = zipWith (\index value -> ([index],value)) [1..] layer new rest = zipWith (\(i1,v1) (i2,v2) -> (i1++i2, v1+v2)) new best where temp = head rest : map best_pair (zip rest (tail rest)) best = map best_pair (zip temp (tail rest)) ++ [last temp] best_pair :: (Result,Result) -> Result best_pair (a@(_,a1), b@(_,b1)) | a1 >=b1 = a | otherwise = b best_of :: [Result] -> Result best_of = maximumBy (compare `on` snd) main = do print (best_from p) </code></pre> <p>It is easy to solve if there is one row. So this converts each row into a list of Result with a simple [#] solution path.</p> <p>Given the <code>rest</code> for the puzzel below a <code>new</code> row then adding the <code>new</code> row is a matter of finding the <code>best</code> solution from <code>rest</code> (by checking down, down left, down right) and combining with the <code>new</code> row.</p> <p>This makes <code>foldr</code>, or here <code>foldr1</code> the natural structure.</p>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload