Using Monads in C++ to Solve Constraints: 1. The List Monad

Post by bpicolo » Tue, May 12, 2015, 3:41 AM UTC

TheLoneWolfling wrote: post #11

beambot wrote: post #6

Earlier quoted context omitted.

Here's one possible implementation of valueOf: import numpy as np def valueOf(*v): return sum( v * np.power(10,range(len(v)))[::-1] ) > valueOf( 2,3,4 ) # => 234 Also, in python 2.7, I don't think you can put a named variable proceeding a wildcard? At least, that doesn't work for me, so I left it out.

That is a) hauling in an awfully big external library for something that should be relatively trivial, b) inefficient (you're replacing a single multiplication by 10 and addition per digit with O(log x) multiplications and an addition per digit, assuming np.power uses a decent exponentiation algorithm), and c) if anything, less readable than my version. To put it simply, I don't see an improvement with that version.…

Post by im3w1l » Tue, May 12, 2015, 4:14 AM UTC

TheLoneWolfling wrote: post #2

This method is really inefficient. There are b! / (b - n)! ways to choose n of b unique numbers, whereas this solution is O(b^n). That being said, it's still fast enough for this example. Also, Python solution along the same lines: import itertoolsdef def valueOf(*values, base=10): v = 0 for v in itertools.accumulate(values, lambda a,b: a*base+b): pass return v def solve(): for s,e,n,d,m,o,r,y in itertools.permutatio…

    from functools import reduce
    def valueOf(*values, base=10):
        return reduce(lambda x,y: x*base+y, values)

Post by mafribe » Tue, May 12, 2015, 9:59 AM UTC

jordigh wrote: post #17

acconsta wrote: post #16

Earlier quoted context omitted.

The Haskell Wiki has what seems like a clean and efficient implementation: https://wiki.haskell.org/Edit_distance

Yeah, it's got a completely different algorithm along the diagonal of the matrix. That's the O(m+n) algorithm. I still haven't been able to understand it. But that's not the point. The point is that Haskellers have a hard time translating an algorithm that's right in front of them and instead of writing down an O(m*n) algorithm they instinctively do O(m^n). This whole "many-worlds" approach of the original article is…

    Haskellers have a hard time translating an algorithm that's right in front of them 

Post by TheLoneWolfling » Tue, May 12, 2015, 1:38 PM UTC

codygman wrote: post #26

bitL wrote: post #24

Earlier quoted context omitted.

There is a set of simple patterns/recipes most people use in Haskell that corresponds to their kind of math intuition Haskell seems to support. It doesn't have anything to do with efficiency though, for that you need to be an expert and you still won't be 100% sure the compiler really optimizes the execution the way you intended.

> you still won't be 100% sure the compiler really optimizes the execution the way you intended. You can be sure if you read the generated Core and/or assembly code.

Post by codygman » Tue, May 12, 2015, 3:17 PM UTC

TheLoneWolfling wrote: post #27

codygman wrote: post #26

Earlier quoted context omitted.

> you still won't be 100% sure the compiler really optimizes the execution the way you intended. You can be sure if you read the generated Core and/or assembly code.

And if you're willing to do that on every upgrade of the compiler or anything that may affect the compiler's exact execution path.