[Haskell-cafe] How to dynamic plan in Haskell?

[Thomas DuBuisson]

On Sat, May 18, 2019 at 2:56 AM Magicloud Magiclouds
<magicloud.magiclouds at gmail.com> wrote:
>
> Thanks. Just to make it clear, the code is for generating candidates,
> not the answer, right? From first glance, the code shows a lot
> solutions that do not sum to 10. Have not check if it contains all
> answers.

They were the right answers for each index.  N.B. the comment
-- A list of all sets of numbers, no duplicates and ignoring order,
-- that sum to the value @index + 1 at .

I'm glad to hear you only want the answer for 10 and the DP aspect
isn't supposed to re-use sum sets for values 1..9 to construct sums
for 10 (which is what I did, it was ugly and slow).  In that case you
can use Ariis's awesome solution with very minor modification:

```
import Data.List

main = print answer

type Solution = [Integer]

answer = sums 10

sums :: Integer -> [Solution]
sums n = do
  x <- [1..n]         -- Pick a largest number in the same
  go x [x] (n - x)  -- recursively pass the smallest value, the
current solution, and remainder
 where
    go x xs r
      | r > 0 && x == 1 = fail ""            -- If there is a
remainder and we've already used 1 this isn't a soluton
      | r > 0 = do x <- [1..min (x-1) r]  -- The next value must be
between 1 and the min of remainder and one-less than the last pick
                   go x (x:xs) (r - x)
      | otherwise = return xs
```

-Thomas

>
> On Sat, May 18, 2019 at 3:03 PM Thomas DuBuisson
> <thomas.dubuisson at gmail.com> wrote:
> >
> > As an aside: I feel certain I saw a beautiful solution presented as
> > lecture notes and referencing a game show (around 2007).  Maybe it was
> > in Hudak's book?
> >
> >
> > Perhaps I missed something, but the answer's I've seen posted thus far
> > are not dynamic programming.  Certainly in the powerset case you'll
> > experience exponential costs.  Benchmarks are good - try to solve with
> > numbers [1..64] in low numbers of seconds.
> >
> > An explicit 98-ish solution is to have a generator that will refer to
> > the prior indexes in the list when computing the current index.
> >
> >
> > First the boiler plate:
> >
> > ```
> > {-# LANGUAGE OverloadedLists #-}
> > module Main where
> >
> > import qualified Data.Set as Set
> > import Control.Monad  (guard)
> >
> > type Solution = Set.Set Int
> >
> > -- A list of all sets of numbers, no duplicates and ignoring order,
> > -- that sum to the value @index + 1 at .
> > answer :: [[Solution]]
> > answer =  fmap op [1..10]
> >  where
> > ```
> >
> > Now for the interesting part.  The recursive definition of a solution
> > for value `target` is `[target]` and the solutions for `x` added with
> > the solution for `target - x` where `x <- [0..target/2].  Some care
> > must be taken because solutions will overlap.
> >
> > With that in mind:
> >
> > ```
> >  -- Generate the entry for value @target@ (list index @target - 1@)
> >  op :: Int -> [Solution]
> >  op target =
> >     ([target] :: Solution)              -- The target itself is an answer
> >         : snub                          -- Ignore duplicate results
> >                                             -- Better idea: don't
> > generate dups if you can...
> >             (do let half = target `div` 2
> >                     halfRDown = (target-1) `div` 2
> >                 (ls,hs) <- zip (slice 0 half answer) -- Pair  0     .. t/2
> >                                                      -- with t-1, t-2 .. t/2+1
> >                                (reverse $ slice half halfRDown answer)
> >                 l <- ls  -- For each solution to the lower number
> >                 h <- hs  -- and the matching solution to the larger number
> >                 guard (Set.intersection l h == []) -- No repeat values! (?)
> >                 pure (l <> h) -- target = l + h
> >                 )
> >
> > -- | List slice from a base and of given length
> > slice :: Int -> Int -> [a] -> [a]
> > slice base len = take len . drop base
> >
> > -- | Efficient combined sort and nub
> > snub :: (Eq a, Ord a) => [a] -> [a]
> > snub = Set.toList . Set.fromList
> >
> > main :: IO ()
> > main = print answers
> > ```
> >
> > -Thomas
> >
> >
> > On Fri, May 17, 2019 at 9:35 PM Magicloud Magiclouds
> > <magicloud.magiclouds at gmail.com> wrote:
> > >
> > > Hi,
> > >
> > > I solved the question. But I could not figure out a FP style solution.
> > >
> > > Question:
> > >
> > > 1 - 9, nine numbers. Show all the possible combinations that sum up to
> > > 10. Different orders are counted as the same.
> > >
> > > For example, [1, 4, 5].
> > > _______________________________________________
> > > Haskell-Cafe mailing list
> > > To (un)subscribe, modify options or view archives go to:
> > > http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe
> > > Only members subscribed via the mailman list are allowed to post.