As was foretold, we've added advertisements to the forums! If you have questions, or if you encounter any bugs, please visit this thread: https://forums.penny-arcade.com/discussion/240191/forum-advertisement-faq-and-reports-thread/
Options

Project Euler - Let's do Math/Programming Challenges

MonoxideMonoxide Registered User, ClubPA regular
Project Euler
click it, it's an url dummy
What is Project Euler?

Project Euler is a series of challenging mathematical/computer programming problems that will require more than just mathematical insights to solve. Although mathematics will help you arrive at elegant and efficient methods, the use of a computer and programming skills will be required to solve most problems.

I've started looking through these after reading the thread about it on Something Awful and they seem pretty neat. It's a great way to get some programming practice in or get some practice in while learning a new language. Since I've decided to toy with Python, I'll be trying to do these with that, but you can use any language you like.

Monoxide on
«1

Posts

  • Options
    VeegeezeeVeegeezee Registered User regular
    edited November 2007
    Holy crap, these look fun.

    Veegeezee on
  • Options
    0blique0blique Registered User regular
    edited November 2007
    Hmmm, looks pretty interesting. I'll have a look at solving some of these when I get some time.

    0blique on
  • Options
    SmasherSmasher Starting to get dizzy Registered User regular
    edited November 2007
    I did the first 63 or so a while back, but I think I was at the point where my math skills were having trouble keeping up with the later problems. Good mix of math and programming though; I may have to pick this up again.

    Smasher on
  • Options
    JasconiusJasconius sword criminal mad onlineRegistered User regular
    edited November 2007
    How are we comparing our answers, by execution time? Fewest lines?

    Oh, maybe it's not a contest. D'oh.

    These are pretty cool, but shit, I have a too much real programming to do already.

    I'm dreaming about calling methods and objects every now and then.

    Sheesh.

    Jasconius on
  • Options
    Cold KoalaCold Koala Registered User regular
    edited November 2007
    The way me and my roommate handle it is this: Execution time is paramount. Elegance and shortness of code do count for style points sometimes. If you do it with pencil and paper, you are a hardass, but if it takes you longer to do than the other guy takes to write, compile, and run his code, then you lose.

    Cold Koala on
  • Options
    JragghenJragghen Registered User regular
    edited November 2007
    Hmm. This looks interesting. Will have to investigate further tomorrow.

    Edit: This finally prompted me to download an environment at home, because while it'd be easier (and I'd be more in the mindset) to do it at work, I really shouldn't.

    Cranked out the first few. I'm being nowhere near the most efficient manner possible, but it's more an effort to make sure I remember how to do some of this stuff (both math and programming-wise).

    Jragghen on
  • Options
    LewishamLewisham Registered User regular
    edited November 2007
    Can we do these in Haskell? Haskell seems like the perfect thing for these.
    The first one needs modulus stuff! Yay!

    Lewisham on
  • Options
    SmasherSmasher Starting to get dizzy Registered User regular
    edited November 2007
    You can use whatever language(s) you want. I used c++ for most of them, but ended up going with python for a few where I had to deal with really large numbers and didn't want to write my own integer class.

    Smasher on
  • Options
    LewishamLewisham Registered User regular
    edited November 2007
    OK, so I went ahead and did some of these in Haskell.

    Problem 3 was a cheat, because I didn't know how to specify whether a number was prime. Now I do! I'm using these to learn maths and Haskell at the same time. I did problem 1 all by myself, found out it was horribly slow, then used the clever Haskell way on the Internet. Again, learning is fun! Problem 1 and 7 I did all by myself. I like Problem 7 a LOT, as it really illustrates how much power Haskell's infinite lists can buy you. It's basically a one-liner, albeit with an expensive boolean test.
    module Euler
        where
    
    -- Support functions
    sqrtFloor :: Integer -> Integer
    sqrtFloor n = floor $ sqrt $ fromIntegral n
    
    fib n = fibs !! n
    fibs = 0 : 1 : zipWith (+) fibs (tail fibs)
    
    _isPrime n x y | x > y = True
                   | n `mod` x == 0 = False
                   | otherwise  = _isPrime n (x + 1) y
                   
    isPrime n | n < 2 = False
              | otherwise  = _isPrime n 2 (sqrtFloor n)
    
    primeFactors n = [x | x <- [1..(sqrtFloor n)], n `mod` x == 0, isPrime x]
    primeNumbers = [x | x <- [1..], isPrime x]
    
    -- Answers
    p1 [] = 0
    p1 (x:xs) | (x `mod` 3 == 0) || (x `mod` 5 == 0) = x + p1 xs
              | otherwise = x + p2 xs
    
    p2 [] = 0
    p2 (x:xs) | x > 1000000 = 0
              | (x `mod` 2 /= 0) = p2 xs
              | otherwise = x + p2 xs
              
    p3 n = last (primeFactors n)
    
    -- Take one off the value to get the index
    p7 n = primeNumbers !! (n - 1)
    

    Haskell gurus: I require your help!
    primeNumbers = [x | x <- [1..], isPrime x]
    primesUpto n = [x | x <- [1..n], isPrime x]
    

    Is there a way I can merge these into one function so that it runs infinitely if not passed n, or up to the sequence if passed a limit?

    EDIT: Answer - primesUpto n = takeWhile (< n) primeNumbers

    Yayyyy.

    Lewisham on
  • Options
    LewishamLewisham Registered User regular
    edited November 2007
    I've become addicted to this shit.

    Problem 6 was so easy in Haskell.
    square n = n * n
    p6 x = abs (sum (map square x) - square (sum x))

    Lewisham on
  • Options
    Mr_AnonymousMr_Anonymous Registered User regular
    edited November 2007
    I hope I can java these with only two months of java under my belt, because this crap looks fun...

    Mr_Anonymous on
  • Options
    LewishamLewisham Registered User regular
    edited November 2007
    Expressing the solutions in Java isn't hard, but you'd need the math skills to understand what you're doing.

    I have to sit and think about pretty much every line of Haskell I write, but it means that the code is cleaner, and better for it. You can't half ass a Haskell implementation of anything.

    Lewisham on
  • Options
    Randall_FlaggRandall_Flagg Registered User regular
    edited November 2007
    I like doing these in scheme, mainly because scheme requires basically no knowledge of programming at all

    I guess I'll probably switch to C for some of the later ones, especially the ones that require you to read ridiculous long .txt files

    Randall_Flagg on
  • Options
    NibbleNibble Registered User regular
    edited November 2007
    Lewisham wrote: »
    OK, so I went ahead and did some of these in Haskell.

    Problem 3 was a cheat, because I didn't know how to specify whether a number was prime. Now I do! I'm using these to learn maths and Haskell at the same time. I did problem 1 all by myself, found out it was horribly slow, then used the clever Haskell way on the Internet. Again, learning is fun! Problem 1 and 7 I did all by myself. I like Problem 7 a LOT, as it really illustrates how much power Haskell's infinite lists can buy you. It's basically a one-liner, albeit with an expensive boolean test.
    module Euler
        where
    
    -- Support functions
    sqrtFloor :: Integer -> Integer
    sqrtFloor n = floor $ sqrt $ fromIntegral n
    
    fib n = fibs !! n
    fibs = 0 : 1 : zipWith (+) fibs (tail fibs)
    
    _isPrime n x y | x > y = True
                   | n `mod` x == 0 = False
                   | otherwise  = _isPrime n (x + 1) y
                   
    isPrime n | n < 2 = False
              | otherwise  = _isPrime n 2 (sqrtFloor n)
    
    primeFactors n = [x | x <- [1..(sqrtFloor n)], n `mod` x == 0, isPrime x]
    primeNumbers = [x | x <- [1..], isPrime x]
    
    -- Answers
    p1 [] = 0
    p1 (x:xs) | (x `mod` 3 == 0) || (x `mod` 5 == 0) = x + p1 xs
              | otherwise = x + p2 xs
    
    p2 [] = 0
    p2 (x:xs) | x > 1000000 = 0
              | (x `mod` 2 /= 0) = p2 xs
              | otherwise = x + p2 xs
              
    p3 n = last (primeFactors n)
    
    -- Take one off the value to get the index
    p7 n = primeNumbers !! (n - 1)
    

    Maybe I just don't get Haskell, but I count 22 lines.

    Nibble on
    sig.php?id=178
  • Options
    LewishamLewisham Registered User regular
    edited November 2007
    Nibble wrote: »
    Maybe I just don't get Haskell, but I count 22 lines.

    That code has the answers to 4-5 questions. Admittedly, problem 7 builds on things from the other problems, but my point was that you can take things and adapt them very quickly. I did actually solve a problem in one line (the one about finding the difference between the sum of squares of all numbers in a sequence and the square of the sum of the numbers in the sequence), but I left it at work :/

    Lewisham on
  • Options
    LindenLinden Registered User regular
    edited November 2007
    God, I spent far too long on problem 5 (I've done these in Haskell also – 1 through 7 at present, and I have some more time soonish)

    I ended up doing it by hand, then realised that there's an lcm function in the Prelude. At that point, of course, it was just a fold away.

    Your solution to 7 is much briefer than mine, although that's probably because I just grabbed a prime list I already had that was designed for efficiency as much as readability (there are two lists building on each other, and two helper functions that might well exist elsewhere)

    If you just want clarity (execution speed is abysmal) then this isn't bad.
    primes :: [Integer]
    primes = sieve [2..]
    	where
    		sieve (p:xs) = p : sieve [ x | x <- xs, x `mod` p > 0 ]
    

    Linden on
  • Options
    TechnicalityTechnicality Registered User regular
    edited November 2007
    I cheated on number 3. Didn't particularly want to muck about with primes so just calculated the big factors and looked a few of them up. Looking at number 7 though, it might have helped to have done a bit of groundwork :|

    These are good stuff though, great find!

    Technicality on
    handt.jpg tor.jpg

  • Options
    LewishamLewisham Registered User regular
    edited November 2007
    Linden wrote: »

    If you just want clarity (execution speed is abysmal) then this isn't bad.
    primes :: [Integer]
    primes = sieve [2..]
    	where
    		sieve (p:xs) = p : sieve [ x | x <- xs, x `mod` p > 0 ]
    

    I did that for the question about the sum of the primes less than a million (question 10?).

    It took 2 hours on an Intel Mac :/ But my Math is not good enough to do it more efficently.

    Lewisham on
  • Options
    jackaljackal Fuck Yes. That is an orderly anal warehouse. Registered User regular
    edited November 2007
    I should probably be using C# 3.0 for this, but problem 10 in VB.Net 2005:

    I could have written this faster if I just used a list instead of an IEnumerable. Execution time is around 3 seconds. This is obviously not optimal at all.

    I know it seems like a lot of code, but most of it will be reused a lot.
    Private Sub uxProblem10_Click(ByVal sender As System.Object, ByVal e As System.EventArgs) Handles uxProblem10.Click
        Dim test As New NaturalNumbersCollection
        Dim primes As New PredicatedCollection(Of Integer)(test, AddressOf Factor.IsPrime)
        Dim sum As Long
    
        For Each tempInteger As Integer In primes
            If tempInteger >= 1000000 Then
                Exit For
            End If
            sum = sum + tempInteger
        Next
        uxOutput.Text = sum.ToString
    End Sub
    
    Public Class Factor
        'Snip
    
        Public Shared Function IsPrime(ByVal value As Integer) As Boolean
            Dim factorList As New Collections.Generic.List(Of Long)
            Dim square As Long
    
            If value < 2 Then
                Return False
            End If
            If value = 2 Then
                Return True
            End If
    
            square = CInt(Math.Ceiling(Math.Sqrt(value)))
            For tempNumber As Long = 2 To square
                If value Mod tempNumber = 0 Then
                    Return False
                End If
            Next
    
            Return True
        End Function
    End Class
    
    'I could avoid this trouble by using lists for everything instead of
    'Enumerables, or I could just use Orcas.
    Public Class PredicatedCollection(Of T)
        Implements IEnumerable
        Implements IEnumerator
    
        Private _predicate As Predicate(Of T)
        Private _internalCollection As IEnumerator
    
        Public Sub New(ByVal internalCollection As IEnumerator, ByVal predicate As Predicate(Of T))
            _internalCollection = internalCollection
            _predicate = predicate
        End Sub
    
        Public Function GetEnumerator() As System.Collections.IEnumerator Implements System.Collections.IEnumerable.GetEnumerator
            Return Me
        End Function
    
        Public ReadOnly Property Current() As Object Implements System.Collections.IEnumerator.Current
            Get
                Return _internalCollection.Current
            End Get
        End Property
    
        Public Function MoveNext() As Boolean Implements System.Collections.IEnumerator.MoveNext
            _internalCollection.MoveNext()
            Do While _predicate(DirectCast(_internalCollection.Current, T)) = False
                If Not _internalCollection.MoveNext Then Return False
            Loop
            Return True
        End Function
    
        Public Sub Reset() Implements System.Collections.IEnumerator.Reset
            Throw New NotSupportedException
        End Sub
    End Class
    
    Public Class NaturalNumbersCollection
        Implements IEnumerable
        Implements IEnumerator
    
        Private _current As Integer = 0
    
        Public Function GetEnumerator() As System.Collections.IEnumerator Implements System.Collections.IEnumerable.GetEnumerator
            Return Me
        End Function
    
        Public ReadOnly Property Current() As Object Implements System.Collections.IEnumerator.Current
            Get
                Return _current
            End Get
        End Property
    
        Public Function MoveNext() As Boolean Implements System.Collections.IEnumerator.MoveNext
            _current += 1
            Return True
        End Function
    
        Public Sub Reset() Implements System.Collections.IEnumerator.Reset
            Throw New NotSupportedException
        End Sub
    End Class
    

    Problem 1:
        Private Sub uxProblem1_Click(ByVal sender As System.Object, ByVal e As System.EventArgs) Handles uxProblem1.Click
            Dim naturals As New NaturalNumbersCollection
            Dim modThreeFive As New PredicatedCollection(Of Integer)(naturals, AddressOf modulusThreeFive)
            Dim sum As Integer
    
            For Each tempNumber As Integer In modThreeFive
                If tempNumber >= 1000 Then
                    Exit For
                End If
                sum = sum + tempNumber
            Next
            uxOutput.Text = sum.ToString
        End Sub
    
        Public Function modulusThreeFive(ByVal value As Integer) As Boolean
            Return (value Mod 3 = 0) Or (value Mod 5 = 0)
        End Function
    

    Problem 2:
    Private Sub uxProblem2_Click(ByVal sender As System.Object, ByVal e As System.EventArgs) Handles uxProblem2.Click
            Dim fibs As New FibonacciNumbersCollection
            Dim evenFibs As New PredicatedCollection(Of Integer)(fibs, AddressOf isEven)
            Dim sum As Integer
    
            For Each tempInteger As Integer In evenFibs
                If tempInteger > 1000000 Then
                    Exit For
                End If
                sum = sum + tempInteger
            Next
            uxOutput.Text = sum.ToString
        End Sub
    
    'This is all types of inelegant.
    Public Class FibonacciNumbersCollection
        Implements IEnumerable
        Implements IEnumerator
    
        Dim _beforeLast As Integer
        Dim _last As Integer
        Dim _currentIndex As Integer = 0
    
        Public ReadOnly Property Current() As Object Implements System.Collections.IEnumerator.Current
            Get
                Return _last + _beforeLast
            End Get
        End Property
    
        Public Function MoveNext() As Boolean Implements System.Collections.IEnumerator.MoveNext
            Dim tempNumber As Integer
            If _currentIndex = 0 Then
                _beforeLast = 0
                _last = 1
                _currentIndex += 1
            ElseIf _currentIndex = 1 Then
                _beforeLast = 1
                _last = 1
                _currentIndex += 1
            Else
                tempNumber = _beforeLast
                _beforeLast = _last
                _last = tempNumber + _last
            End If
            Return True
        End Function
    
        Public Sub Reset() Implements System.Collections.IEnumerator.Reset
            Throw New NotSupportedException
        End Sub
    
        Public Function GetEnumerator() As System.Collections.IEnumerator Implements System.Collections.IEnumerable.GetEnumerator
            Return Me
        End Function
    End Class
    
    

    Problem 3:
        Private Sub uxProblem3_Click(ByVal sender As System.Object, ByVal e As System.EventArgs) Handles uxProblem3.Click
            Dim factors As List(Of Long) = Factor.FactorNumber(317584931803)
            'The sort isn't actually necessary, but if FactorNumber was implemented differently
            'it would be.
            factors.Sort()
            uxOutput.Text = factors(factors.Count - 1).ToString
        End Sub
    
    Public Class Factor
        Public Shared Function FactorNumber(ByVal value As Long) As Collections.Generic.List(Of Long)
            Dim factorList As New Collections.Generic.List(Of Long)
            Dim toFactor As Long
            Dim square As Long
            toFactor = value
    
            Do While True
                square = CInt(Math.Ceiling(Math.Sqrt(toFactor)))
                For tempNumber As Long = 2 To square
                    If toFactor Mod tempNumber = 0 Then
                        factorList.Add(tempNumber)
                        toFactor = toFactor \ tempNumber
                        Continue Do
                    End If
                Next
                factorList.Add(toFactor)
                Exit Do
            Loop
    
            Return factorList
        End Function
    
    'snip
    End Class
    

    Problem 4:
    'cheesy, but fast to write.
        Private Sub uxProblem4_Click(ByVal sender As System.Object, ByVal e As System.EventArgs) Handles uxProblem4.Click
            Dim products As New ProductOfThreeDigitNumbersCollection
            Dim palindromes As New PredicatedCollection(Of Integer)(products, AddressOf isPalindrome)
            Dim palindromeList As New Collections.Generic.List(Of Integer)
            Dim largest As Long = 0
    
            For Each tempInteger As Integer In palindromes
                palindromeList.Add(tempInteger)
            Next
            palindromeList.Sort()
            uxOutput.Text = palindromeList.Item(palindromeList.Count - 1).ToString
        End Sub
    
        Public Function isPalindrome(ByVal value As Integer) As Boolean
            Dim valueText As String = value.ToString
            For counter As Integer = 0 To valueText.Length - 1
                If valueText.Substring(counter, 1) <> valueText.Substring(valueText.Length - counter - 1, 1) Then
                    Return False
                End If
            Next
            Return True
        End Function
    
    Public Class ProductOfThreeDigitNumbersCollection
        Implements IEnumerable
        Implements IEnumerator
    
        Dim _x As Integer = 99
        Dim _y As Integer = 100
    
        Public ReadOnly Property Current() As Object Implements System.Collections.IEnumerator.Current
            Get
                Return _x * _y
            End Get
        End Property
    
        Public Function MoveNext() As Boolean Implements System.Collections.IEnumerator.MoveNext
            _x = _x + 1
            If _x = 1000 Then
                _x = 100
                _y = _y + 1
                If _y = 1000 Then
                    Return False
                End If
            End If
            Return True
        End Function
    
        Public Sub Reset() Implements System.Collections.IEnumerator.Reset
            Throw New NotSupportedException
        End Sub
    
        Public Function GetEnumerator() As System.Collections.IEnumerator Implements System.Collections.IEnumerable.GetEnumerator
            Return Me
        End Function
    End Class
    

    Problem 7: (uses stuff from problem 10)
        Private Sub uxProblem7_Click(ByVal sender As System.Object, ByVal e As System.EventArgs) Handles uxProblem7.Click
            Dim naturals As New NaturalNumbersCollection
            Dim primes As New PredicatedCollection(Of Integer)(naturals, AddressOf Factor.IsPrime)
            Dim primeCount As Integer = 0
    
            For Each tempInteger As Integer In primes
                primeCount += 1
                If primeCount = 10001 Then
                    uxOutput.Text = tempInteger.ToString
                    Return
                End If
            Next
        End Sub
    

    I just got 11, but the code is too ugly to post. I need to clean it up.

    jackal on
  • Options
    LindenLinden Registered User regular
    edited November 2007
    Lewisham wrote: »
    Linden wrote: »

    If you just want clarity (execution speed is abysmal) then this isn't bad.
    primes :: [Integer]
    primes = sieve [2..]
    	where
    		sieve (p:xs) = p : sieve [ x | x <- xs, x `mod` p > 0 ]
    

    I did that for the question about the sum of the primes less than a million (question 10?).

    It took 2 hours on an Intel Mac :/ But my Math is not good enough to do it more efficently.

    I did say that performance was bad!

    My current code for that particular problem (using a generalised version of your primesUpto function) gives pretty reasonable timing.
    primes, nonprimes :: [Integer] -- These are circularly defined.
    primes    = [2, 3, 5] ++ (diff [7, 9 ..] nonprimes) 
    nonprimes = foldr1 f $ map g $ tail primes
    	where 
    		f (x:xt) ys = x : (merge xt ys)
    		g p         = [ n * p | n <- [p, p + 2 ..]]
    
    merge :: (Ord a) => [a] -> [a] -> [a]
    merge [] y                = y
    merge x []                = x
    merge xs@(x:xt) ys@(y:yt) = 
    	case compare x y of
    		LT -> x : (merge xt ys)
    		EQ -> x : (merge xt yt)
    		GT -> y : (merge xs yt)
    
    diff :: (Ord a) => [a] -> [a] -> [a]
    diff xs@(x:xt) ys@(y:yt) = 
    	case compare x y of
    		LT -> x : (diff xt ys)
    		EQ -> diff xt yt
    		GT -> diff xs yt
    
    upTo n list = takeWhile (< n) list
    
    p10 = sum $ upTo 1000000 primes
    

    The lists and first two helper functions are from literateprograms.org (was looking at these during my earlier explorations), and both functions work only with infinite sorted lists.

    Linden on
  • Options
    jackaljackal Fuck Yes. That is an orderly anal warehouse. Registered User regular
    edited November 2007
    Eh, this isn't a beauty contest. Forgive the ugliness of this code. Integers are initialized to 0, so everything that is not assigned to is a sentinel value. It makes everything that goes outside of the 20 x 20 grid show up as 0.

    Problem 11:
    Private Sub uxProject11_Click(ByVal sender As System.Object, ByVal e As System.EventArgs) Handles uxProject11.Click
    
            Dim grid(22, 25) As Integer
            Dim inputText As String
            Dim currentRow As Integer
            Dim currentColumn As Integer
            Dim max As Integer
            Dim temp As Integer
            inputText = uxInput.Text
            For Each tempLine As String In inputText.Split(New String() {ControlChars.NewLine}, StringSplitOptions.RemoveEmptyEntries)
                currentColumn = 3
                For Each tempNumberText As String In tempLine.Split(" "c)
                    grid(currentRow, currentColumn) = Integer.Parse(tempNumberText)
                    currentColumn += 1
                Next
                currentRow += 1
            Next
            For rowIndex As Integer = 0 To 19
                For columnIndex As Integer = 3 To 22
                    'across
                    temp = grid(rowIndex, columnIndex) * grid(rowIndex, columnIndex + 1) * grid(rowIndex, columnIndex + 2) * grid(rowIndex, columnIndex + 3)
                    If max < temp Then
                        max = temp
                    End If
                    'down
                    temp = grid(rowIndex, columnIndex) * grid(rowIndex + 1, columnIndex) * grid(rowIndex + 2, columnIndex) * grid(rowIndex + 3, columnIndex)
                    If max < temp Then
                        max = temp
                    End If
                    'down left
                    temp = grid(rowIndex, columnIndex) * grid(rowIndex + 1, columnIndex + 1) * grid(rowIndex + 2, columnIndex + 2) * grid(rowIndex + 3, columnIndex + 3)
                    If max < temp Then
                        max = temp
                    End If
                    'down right
                    temp = grid(rowIndex, columnIndex) * grid(rowIndex + 1, columnIndex - 1) * grid(rowIndex + 2, columnIndex - 2) * grid(rowIndex + 3, columnIndex - 3)
                    If max < temp Then
                        max = temp
                    End If
                Next
            Next
            uxOutput.Text = max.ToString
        End Sub
    

    I feel dirty because I looked up an algorithm for problem 12.

    jackal on
  • Options
    LewishamLewisham Registered User regular
    edited November 2007
    Linden wrote: »
    p10 = sum $ upTo 1000000 primes
    

    A little OT: but how do you feel about $ notation? I just read what it meant, which is to say it essentially wraps up the next thing in parathenses, so your code goes to:
    p10 = sum (upTo 1000000 primes)
    

    Maybe I'm just stuck in my ways, but I find parens more obvious as to what is binding to what.

    Lewisham on
  • Options
    LindenLinden Registered User regular
    edited November 2007
    Lewisham wrote: »
    A little OT: but how do you feel about $ notation? I just read what it meant, which is to say it essentially wraps up the next thing in parathenses, so your code goes to:
    <-->

    Maybe I'm just stuck in my ways, but I find parens more obvious as to what is binding to what.

    I find it helpful, but mostly for obvious examples with several nested functions. That example is probably the result of me changing the code – I'm pretty sure there was more there initially. As an example, I had a main function in Problem 4 which contained
    print $ show $ last $ palindromes [100..999] [100..999]
    (or)
    print (show (last (palindromes [100..999] [100..999] )))
    

    In this situation, I find the $ clearer than the parentheses, but there are certainly circumstances where the reverse would be true.

    Incidentally, those functions are equivalent to
    print . show . last $ palindromes [100..999] [100..999]
    
    but replacing the $ with parens causes a typing error. If we also surround the three functions with parens, it works as expected.

    Clearly someone really wanted a variety of options. There's $!, as well, which causes strict evaluation.

    Edit: This is also posted here, for any interested parties and to avoid cluttering this thread.

    Linden on
  • Options
    jackaljackal Fuck Yes. That is an orderly anal warehouse. Registered User regular
    edited November 2007
    Problem 15:
        'This one could really use some comments.
        Private Sub uxProblem15_Click(ByVal sender As System.Object, ByVal e As System.EventArgs) Handles uxProblem15.Click
            uxOutput.Text = (2L * 2L * 7L * 5L * 23L * 29L * 31L * 33L * 37L * 39L).ToString
        End Sub
    
        'Here is the brute force. It only takes a small fraction of a millisecond.
        Private Sub uxProblem15_Click(ByVal sender As System.Object, ByVal e As System.EventArgs) Handles uxProblem15.Click
            Dim grid(20, 20) As Long
            For rowIndex As Integer = 0 To 20
                grid(rowIndex, 0) = 1
            Next
            For columnIndex As Integer = 0 To 20
                grid(0, columnIndex) = 1
            Next
            For rowIndex As Integer = 1 To 20
                For columnIndex As Integer = 1 To 20
                    grid(rowIndex, columnIndex) = grid(rowIndex - 1, columnIndex) + grid(rowIndex, columnIndex - 1)
                Next
            Next
            uxOutput.Text = grid(20, 20).ToString
        End Sub
    

    Woo! Finished the first 15.

    jackal on
  • Options
    jackaljackal Fuck Yes. That is an orderly anal warehouse. Registered User regular
    edited November 2007
    Problem 18 and 67:
        'It mentions you can brute force 18, but it seems like that would be harder.
        Private Sub uxProblem18_Click(ByVal sender As System.Object, ByVal e As System.EventArgs) Handles uxProblem18.Click
            Dim rows()() As Integer
            Dim rowText() As String
            Dim currentRowLength As Integer
            Dim lastRow() As Integer
            rowText = uxInput.Text.Split(New String() {ControlChars.NewLine}, StringSplitOptions.RemoveEmptyEntries)
            ReDim rows(rowText.Length - 1)
            For counterX As Integer = 0 To rowText.Length - 1
                rows(counterX) = Array.ConvertAll(rowText(counterX).Split(" "c), New Converter(Of String, Integer)(AddressOf Integer.Parse))
            Next
            For counterX As Integer = 1 To rows.Length - 1
                currentRowLength = rows(counterX).Length
                rows(counterX)(0) += rows(counterX - 1)(0)
                For counterY As Integer = 1 To currentRowLength - 2
                    rows(counterX)(counterY) += Math.Max(rows(counterX - 1)(counterY), rows(counterX - 1)(counterY - 1))
                Next
                rows(counterX)(currentRowLength - 1) += rows(counterX - 1)(currentRowLength - 2)
            Next
            lastRow = rows(rows.Length - 1)
            Array.Sort(lastRow)
            uxOutput.Text = lastRow(lastRow.Length - 1).ToString
        End Sub
    

    jackal on
  • Options
    jackaljackal Fuck Yes. That is an orderly anal warehouse. Registered User regular
    edited November 2007
    Problem 16 and 20
    Private Sub uxProblem16_Click(ByVal sender As System.Object, ByVal e As System.EventArgs) Handles uxProblem16.Click
        Dim bigNumber As java.math.BigInteger = java.math.BigInteger.valueOf(2)
        bigNumber = bigNumber.pow(1000)
        uxOutput.Text = SumDigitsInBigInteger(bigNumber).ToString
    End Sub
    
    Private Sub uxProblem20_Click(ByVal sender As System.Object, ByVal e As System.EventArgs) Handles uxProblem20.Click
        Dim bigNumber As java.math.BigInteger = java.math.BigInteger.valueOf(2)
        bigNumber = Factorial(100)
        uxOutput.Text = SumDigitsInBigInteger(bigNumber).ToString
    End Sub
    
    Private Function SumDigitsInBigInteger(ByVal value As java.math.BigInteger) As Integer
        Dim total As Integer
        Dim temp As java.math.BigInteger
        Dim zero As java.math.BigInteger = java.math.BigInteger.valueOf(0)
        Dim ten As java.math.BigInteger = java.math.BigInteger.valueOf(10)
        temp = value
        Do
            total += temp.mod(ten).ToInt32(Nothing)
            temp = temp.divide(ten)
        Loop Until temp.Equals(zero)
        Return total
    End Function
    
    Private Function Factorial(ByVal value As Integer) As java.math.BigInteger
        Dim fact As java.math.BigInteger = java.math.BigInteger.valueOf(1)
        For counter As Integer = 1 To value
            fact = fact.multiply(java.math.BigInteger.valueOf(counter))
        Next
        Return fact
    End Function
    

    I needed to speed up the function I used to sum the digits of BigIntegers:

    The original:
        Private Function SumDigitsInBigInteger(ByVal value As java.math.BigInteger) As Integer
            Dim total As Integer
            Dim temp As java.math.BigInteger
            Dim zero As java.math.BigInteger = java.math.BigInteger.valueOf(0)
            Dim ten As java.math.BigInteger = java.math.BigInteger.valueOf(10)
            temp = value
            Do
                total += temp.mod(ten).ToInt32(Nothing)
                temp = temp.divide(ten)
            Loop Until temp.Equals(zero)
            Return total
        End Function
    

    Used DivideAndRemainder function instead of seperate function (twice the speed of original):
        Private Function SumDigitsInBigInteger2(ByVal value As java.math.BigInteger) As Integer
            Dim total As Integer
            Dim temp As java.math.BigInteger
            Dim zero As java.math.BigInteger = java.math.BigInteger.valueOf(0)
            Dim ten As java.math.BigInteger = java.math.BigInteger.valueOf(10)
            Dim quotientAndRemainder As java.math.BigInteger()
            temp = value
            Do
                quotientAndRemainder = temp.divideAndRemainder(ten)
                total += quotientAndRemainder(1).ToInt32(Nothing) ' temp.mod(ten).ToInt32(Nothing)
                temp = quotientAndRemainder(0)
            Loop Until temp.Equals(zero)
            Return total
        End Function
    

    Broke number up into Integer sized chunks and then summed their digits (ten times the speed of the original):
        Private Function SumDigitsInBigInteger3(ByVal value As java.math.BigInteger) As Integer
            Dim total As Integer
            Dim currentInInteger As Integer
            Dim temp As java.math.BigInteger
            Dim zero As java.math.BigInteger = java.math.BigInteger.valueOf(0)
            Dim billion As java.math.BigInteger = java.math.BigInteger.valueOf(1000000000)
            Dim quotientAndRemainder As java.math.BigInteger()
            temp = value
            Do
                quotientAndRemainder = temp.divideAndRemainder(billion)
    
                currentInInteger = quotientAndRemainder(1).ToInt32(Nothing)
                Do
                    total += currentInInteger Mod 10
                    currentInInteger = currentInInteger \ 10
                Loop Until currentInInteger = 0
    
                temp = quotientAndRemainder(0)
            Loop Until temp.Equals(zero)
            Return total
        End Function
    

    I tried one that breaks the number up into long sized chunks, but it didn't run any faster. I tried a function that would split up the number into half on a power of 10 border and then subdivide that until it is down to integer size, but it ran slow. I think I did something wrong.

    jackal on
  • Options
    JaninJanin Registered User regular
    edited December 2007
    Bumping this, because it's great fun. Just solved #5, which was much more trouble than it first seemed.
    to_check = (20, 19, 18, 17, 16, 15, 14, 13, 12, 11)
    factors = (1, 2, 3, 5, 7)
    
    divisible = lambda num: all ((num &#37; ii == 0) for ii in to_check)
    increment = reduce (lambda a, b: a * b, factors)
    num = increment
    while not divisible (num):
    	num += increment
    	
    print num
    

    Janin on
    [SIGPIC][/SIGPIC]
  • Options
    Cold KoalaCold Koala Registered User regular
    edited December 2007
    @Jackal: How is it that you used java.math.BigInteger but I don't recognize your code as Java at all?

    Also, how many has everyone solved so far? I'm on 25. (I took a long hiatus.)

    Cold Koala on
  • Options
    MonoxideMonoxide Registered User, ClubPA regular
    edited December 2007
    Cold Koala wrote: »
    @Jackal: How is it that you used java.math.BigInteger but I don't recognize your code as Java at all?

    Also, how many has everyone solved so far? I'm on 25. (I took a long hiatus.)

    It looks like Visual Basic. I think you can call Java classes in VB .NET to some extent, though I don't know the details.

    Monoxide on
  • Options
    jackaljackal Fuck Yes. That is an orderly anal warehouse. Registered User regular
    edited December 2007
    Monoxide wrote: »
    Cold Koala wrote: »
    @Jackal: How is it that you used java.math.BigInteger but I don't recognize your code as Java at all?

    Also, how many has everyone solved so far? I'm on 25. (I took a long hiatus.)

    It looks like Visual Basic. I think you can call Java classes in VB .NET to some extent, though I don't know the details.

    Several Java classes can be used if you reference vjslib. I think most versions of Visual Studios should come with it. If not just install Visual J# 2005 Express Edition. It seems like a lot of trouble, but it is easier than implementing your own bigint library.

    I have solved 36 problems so far, but I haven't touched any in at least a month. I'm glad this got resurrected. After a while it was just me talking to myself. I need to get back to work on 76.

    jackal on
  • Options
    jackaljackal Fuck Yes. That is an orderly anal warehouse. Registered User regular
    edited January 2008
    I've decided to redo some of these in C# 3.0. I am loving me some C# 3.0.

    Problem 1
            public static void Problem1()
            {
                var oneTo999 = Enumerable.Range(1, 999);
                Console.WriteLine(oneTo999.Where(x => x &#37; 5 ==0 || x % 3 == 0).Sum());
            }
    

    Problem 2
           public static void Problem2()
            {
                var fibs = NumberSequences.Fibonacci();
                Console.WriteLine(fibs.TakeWhile( x => x <= 1000000 ).Where(x => x % 2 == 0).Sum());
            }
    

    It seems like I should be able to do this more easily. I actually had to use a control structure! D:
    If you let it run long enough it will throw an overflow exception. That actually seems more correct than if it stopping, because the Fibonacci numbers don't stop.
        static class NumberSequences
        {
            public static IEnumerable<int> Fibonacci()
            {
                int secondToLastTerm = 1;
                int lastTerm = 2;
                int current;
                yield return secondToLastTerm;
                yield return lastTerm;
                while (true)
                {
                    current = secondToLastTerm + lastTerm;
                    yield return current;
                    secondToLastTerm = lastTerm;
                    lastTerm = current;
                }
            }
        }
    

    Problem 3
    I didn't bother creating a functional style prime factor function. Making it an extension method is a little silly.
            public static void Problem3()
            {
                Console.WriteLine(317584931803.PrimeFactors().Max());
            }
    

    Avert your eyes. There is imperative code ahead!
            public static IEnumerable<long> PrimeFactors(this long value)
            {   bool foundFlag;
                do
                {
                    foundFlag = false;
                    long square = (long)Math.Ceiling(Math.Sqrt(value));
                    for (int counterX = 2; counterX <= square; counterX++)
                    {
                        if (value % counterX == 0)
                        {
                            yield return counterX;
                            value = value / counterX;
                            foundFlag = true;
                            break;
                        }
                    }
                } while (foundFlag == true);
                yield return value;
            }
    

    Problem 4
    This one is a little slow because I reversed the string instead of the integer.
    I could also speed it up if I could manage to only join when the value from the second range is greater than or equal to the value from the first range.
            public static void Problem4()
            {
                
                var range = Enumerable.Range(100, 900);
                var products = range.Join(range, x => 1, x => 1, (x, y) => x * y);
                var palindromes = products.Where(x => x.ToString() == x.ToString().Reverse());
                Console.WriteLine(palindromes.Max());
            }
    
            public static string Reverse(this string value)
            {
                return value.ToCharArray().Reverse().Aggregate(new StringBuilder(), (x, y) => x.Append(y), x => x.ToString());
            }
    

    Problem 6
            public static void Problem6()
            {
                var oneToTen = Enumerable.Range(1, 100).ToList();
                Console.WriteLine(oneToTen.Sum().Square() - oneToTen.ConvertAll(x => x.Square()).Sum());
            }
    
    
            public static int Square(this int value)
            {
                return value * value;
            }
    

    Problem 7 and 10
            public static void Problem7and10()
            {
                var range = Enumerable.Range(1 , 999999 ).Cast<long>();
                var primes = range.Where(x => x.IsPrime()).ToList();
                if (primes.Count >= 10001)
                {
                    Console.WriteLine(string.Format("Problem  7: {0}", primes[10000]));
                }
                Console.WriteLine(string.Format("Problem 10: {0}", primes.Sum()));
            }
    
            public static bool IsPrime(this long value)
            {
                if (value <= 1) return false;
                int square = Convert.ToInt32((Math.Sqrt(value)));
                return !Enumerable.Range(2, square - 1).Any(x => value % x == 0);
            }
    

    jackal on
  • Options
    jackaljackal Fuck Yes. That is an orderly anal warehouse. Registered User regular
    edited January 2008
    For 9 the functional style solution was not very good compared to the imperative solution. Either I am doing something wrong or this doesn't lend itself to this type of solution. The one positive point about the first example is that it more naturally emerges from the problem definition.
            public static void Problem9()
            {
                var range = Enumerable.Range( 1, 999);
                var duplets = range.Join( range,  x => 1 , x => 1, (x, y) => new { a = x, b = y });
                var filteredDuplets = duplets.Where(x => x.a < x.b && x.a + x.b <= 999);
                var triplets = filteredDuplets.ToList().ConvertAll(x => new { a = x.a, b = x.b, c = 1000 - x.a - x.b });
                var filteredTriplets = triplets.Where(x => x.b < x.c);
                var pythagoreanTriplet = filteredTriplets.First(x => x.a * x.a + x.b * x.b == x.c * x.c);
                Console.WriteLine(pythagoreanTriplet.a * pythagoreanTriplet.b * pythagoreanTriplet.c);
            }
    
        Private Sub uxProblem9_Click(ByVal sender As System.Object, ByVal e As System.EventArgs) Handles uxProblem9.Click
            For a As Integer = 1 To 998
                For b As Integer = 1 To 999 - a
                    Dim c As Integer = 1000 - b - a
                    If (a * a + b * b) = (c * c) Then
                        uxOutput.Text = (a * b * c).ToString
                        Return
                    End If
                Next
            Next
        End Sub
    
    EDIT:
    Yeah, I was doing something wrong. This is much better.
            public static void Problem9b()
            {
                var range = Enumerable.Range(1, 999);
                var triplets = range.Join(range, x => 1, x => 1, (x, y) => new { a = x, b = y, c = 1000 - x - y });
                var filteredTriplets = triplets.Where(x => x.a < x.b && x.b < x.c);
                var pythagoreanTriplet = filteredTriplets.First(x => x.a * x.a + x.b * x.b == x.c * x.c);
                Console.WriteLine(pythagoreanTriplet.a * pythagoreanTriplet.b * pythagoreanTriplet.c);
            }
    

    jackal on
  • Options
    JaninJanin Registered User regular
    edited January 2008
    This is my solution to #9. Also, please use spoilers.
    is_trip = lambda a, b, c: (a < b) and (b < c) and ((a**2) + (b**2) == (c**2))
    for a, b in ((a, b) for a in xrange (1001) for b in xrange (1001)):
    	c = 1000 - (a + b)
    	if is_trip (a, b, c):
    		print a*b*c
    		break
    

    Janin on
    [SIGPIC][/SIGPIC]
  • Options
    jackaljackal Fuck Yes. That is an orderly anal warehouse. Registered User regular
    edited January 2008
    What language is that?

    Anyway 9 using LINQ:
            public static void Problem9c()
            {
                var range = Enumerable.Range(1, 999);
                var triplets =
                   from x in range
                   join y in range on 1 equals 1
                   where x < y && y < (1000 - x - y)
                   select new { a = x, b = y, c = 1000 - x - y };
    
                var pythagoreanTriplet = (from x in triplets
                         where x.a * x.a + x.b * x.b == x.c * x.c
                         select x).FirstOrDefault();
    
                Console.WriteLine(pythagoreanTriplet.a * pythagoreanTriplet.b * pythagoreanTriplet.c);
            }
    
    

    EDIT:
    Using nested froms seems to be appropriate than the explicit join. It looks like it could be more optimizable this way.
            public static void Problem9c2()
            {
                var range = Enumerable.Range(1, 999);
                var triplets =
                   from x in range
                       from y in range
                   where x < y && y < (1000 - x - y)
                   select new { a = x, b = y, c = 1000 - x - y };
    
                var pythagoreanTriplet = (from x in triplets
                                          where x.a * x.a + x.b * x.b == x.c * x.c
                                          select x).FirstOrDefault();
    
                Console.WriteLine(pythagoreanTriplet.a * pythagoreanTriplet.b * pythagoreanTriplet.c);
            }
    

    Here it is in a single LINQ query. It is getting ugly or beautiful. I'm not sure which.
            public static void Problem9d()
            {
                var range = Enumerable.Range(1, 999);
                var pythagoreanTriplet =
                    (from z in
                       from x in range
                            from y in range
                       where x < y && y < (1000 - x - y)
                       select new { a = x, b = y, c = 1000 - x - y }
                            where z.a * z.a + z.b * z.b == z.c * z.c
                            select z).FirstOrDefault();
    
                Console.WriteLine(pythagoreanTriplet.a * pythagoreanTriplet.b * pythagoreanTriplet.c);
            }
    

    I am digging the anonymous data types.

    jackal on
  • Options
    JaninJanin Registered User regular
    edited January 2008
    jackal wrote: »
    What language is that?

    Python

    Janin on
    [SIGPIC][/SIGPIC]
  • Options
    jackaljackal Fuck Yes. That is an orderly anal warehouse. Registered User regular
    edited January 2008
    Oh man, I really need to figure out how to make this stuff readable.

    Problem 5 (this is a lot of code for something that takes about a minute to solve on paper):
    I'm casting the ints to longs because the PrimeFactors extension method I wrote works with longs.
            public static void Problem5()
            {
                var range = Enumerable.Range(2, 19).Cast<long>();
                var factors = range.SelectMany(x => x.PrimeFactors().GroupBy(y => y).Select(z => new {factor = z.Key, count = z.Count()}));
                var groupedFactors = factors.GroupBy(y => y.factor);
                var factorsAndExponents = groupedFactors.Select(x => new { Factor = x.Key, Exponent = x.Max(z => z.count) });
                Console.WriteLine(factorsAndExponents.Aggregate(1d, (x, y) => x * Math.Pow(y.Factor, y.Exponent), x => x.ToString("0")));
            }
    

    The disturbing thing is that it can all be smashed into one line of code.
            public static void Problem5ForTheLoveOfGodDontDoThis()
            {
                Console.WriteLine(Enumerable.Range(2, 19).Cast<long>().SelectMany(x => x.PrimeFactors().GroupBy(y => y).Select(z => new { factor = z.Key, count = z.Count() })).GroupBy(y => y.factor).Select(x => new { Factor = x.Key, Exponent = x.Max(z => z.count) }).Aggregate(1d, (x, y) => x * Math.Pow(y.Factor, y.Exponent), x => x.ToString("0")));
            }
    

    Problem 12:
            public static void Problem12()
            {
                var primeFactorsOfTriangleNumbers = NumberSequences.TriangleNumbers().Cast<long>().Select(x => new { number = x, primeFactors = x.PrimeFactors().GroupBy(y => y)});
                var numberOfDivisorsOfTriangleNumbers = primeFactorsOfTriangleNumbers.Select(x => new {number = x.number, divisorCount = x.primeFactors.Aggregate(1, (y, z) => y * (z.Count() + 1))});
                Console.WriteLine(numberOfDivisorsOfTriangleNumbers.First(x => x.divisorCount > 500).number);
            }
    

    Problem 29:
    This one turned out really well.
            public static void Problem29()
            {
                var range = Enumerable.Range(2, 99);
                var answer = (from x in range
                                from y in range
                                    select java.math.BigInteger.valueOf(x).pow(y))
                                        .Distinct().Count();
                Console.WriteLine(answer);
            }
    

    Problem 30:
    This is the first one I tried from scratch with C# 3.0
            public static void Problem30()
            {
                var numbersAndDigits = Enumerable.Range(10, 360000).Select(x => new {number = x, digits = NumberSequences.Digits(x)});
                var numbersAndTransforms = numbersAndDigits.Select(x => new {x.number, transform = x.digits.Aggregate(0d, (y, z) => y + Math.Pow(z, 5), y => (int)y)});
                var targetNumbers = numbersAndTransforms.Where(x => x.number == x.transform);
                Console.WriteLine(targetNumbers.Sum(x => x.transform));
            }
    
            public static IEnumerable<int> Digits(int value)
            {
                do
                {
                    yield return value &#37; 10;
                    value /= 10;
                } 
                while (value != 0);
            }
    

    jackal on
  • Options
    JaninJanin Registered User regular
    edited January 2008
    jackal wrote: »
    Oh man, I really need to figure out how to make this stuff readable.

    Problem 5 (this is a lot of code for something that takes about a minute to solve on paper):
    I'm casting the ints to longs because the PrimeFactors extension method I wrote works with longs.
            public static void Problem5()
            {
                var range = Enumerable.Range(2, 19).Cast<long>();
                var factors = range.SelectMany(x => x.PrimeFactors().GroupBy(y => y).Select(z => new {factor = z.Key, count = z.Count()}));
                var groupedFactors = factors.GroupBy(y => y.factor);
                var factorsAndExponents = groupedFactors.Select(x => new { Factor = x.Key, Exponent = x.Max(z => z.count) });
                Console.WriteLine(factorsAndExponents.Aggregate(1d, (x, y) => x * Math.Pow(y.Factor, y.Exponent), x => x.ToString("0")));
            }
    

    The disturbing thing is that it can all be smashed into one line of code.
            public static void Problem5ForTheLoveOfGodDontDoThis()
            {
                Console.WriteLine(Enumerable.Range(2, 19).Cast<long>().SelectMany(x => x.PrimeFactors().GroupBy(y => y).Select(z => new { factor = z.Key, count = z.Count() })).GroupBy(y => y.factor).Select(x => new { Factor = x.Key, Exponent = x.Max(z => z.count) }).Aggregate(1d, (x, y) => x * Math.Pow(y.Factor, y.Exponent), x => x.ToString("0")));
            }
    

    Good lord. Mine might have a few more lines, but I think it's much more readable:
    to_check = range (20, 10, -1)
    factors = (1, 2, 3, 5, 7)
    
    divisible = lambda num: all ((num &#37; ii == 0) for ii in to_check)
    increment = reduce (lambda a, b: a * b, factors)
    
    num = increment
    while not divisible (num):
    	num += increment
    	
    print num
    

    Janin on
    [SIGPIC][/SIGPIC]
  • Options
    jackaljackal Fuck Yes. That is an orderly anal warehouse. Registered User regular
    edited January 2008
    Janin wrote: »
    jackal wrote: »
    Oh man, I really need to figure out how to make this stuff readable.

    Problem 5 (this is a lot of code for something that takes about a minute to solve on paper):
    I'm casting the ints to longs because the PrimeFactors extension method I wrote works with longs.
            public static void Problem5()
            {
                var range = Enumerable.Range(2, 19).Cast<long>();
                var factors = range.SelectMany(x => x.PrimeFactors().GroupBy(y => y).Select(z => new {factor = z.Key, count = z.Count()}));
                var groupedFactors = factors.GroupBy(y => y.factor);
                var factorsAndExponents = groupedFactors.Select(x => new { Factor = x.Key, Exponent = x.Max(z => z.count) });
                Console.WriteLine(factorsAndExponents.Aggregate(1d, (x, y) => x * Math.Pow(y.Factor, y.Exponent), x => x.ToString("0")));
            }
    

    The disturbing thing is that it can all be smashed into one line of code.
            public static void Problem5ForTheLoveOfGodDontDoThis()
            {
                Console.WriteLine(Enumerable.Range(2, 19).Cast<long>().SelectMany(x => x.PrimeFactors().GroupBy(y => y).Select(z => new { factor = z.Key, count = z.Count() })).GroupBy(y => y.factor).Select(x => new { Factor = x.Key, Exponent = x.Max(z => z.count) }).Aggregate(1d, (x, y) => x * Math.Pow(y.Factor, y.Exponent), x => x.ToString("0")));
            }
    

    Good lord. Mine might have a few more lines, but I think it's much more readable:
    to_check = range (20, 10, -1)
    factors = (1, 2, 3, 5, 7)
    
    divisible = lambda num: all ((num % ii == 0) for ii in to_check)
    increment = reduce (lambda a, b: a * b, factors)
    
    num = increment
    while not divisible (num):
    	num += increment
    	
    print num
    

    Well, the techniques are very different. I basically translated how the problem would be solved on paper. Yours looks like a good middle ground between simplicity and speed. If I am understanding your code correctly couldn't you include 11, 13, 17 and 19 in factors and get a pretty significant speed improvement?

    jackal on
  • Options
    JaninJanin Registered User regular
    edited January 2008
    I have no idea how any of these problems would be solved on paper, so all my solutions are wild guesses. Didn't notice any difference in speed including 11, 13, 17, and 19, but it still came up with the correct solution vOv.

    Janin on
    [SIGPIC][/SIGPIC]
  • Options
    jackaljackal Fuck Yes. That is an orderly anal warehouse. Registered User regular
    edited January 2008
    Janin wrote: »
    I have no idea how any of these problems would be solved on paper, so all my solutions are wild guesses. Didn't notice any difference in speed including 11, 13, 17, and 19, but it still came up with the correct solution vOv.

    I think this is how your code could be implemented in C#. How long does your code take to run? This takes a little over a minute and a half on an Athlon XP 1900+.
            public static void Problem5Janin()
            {
                var toCheck = Enumerable.Range(10, 10);
                int[] factors = { 2, 3, 5, 7, 11, 13, 17, 19 };
                Func<int, bool> divisible = x => toCheck.All(y => x % y == 0);
                var increment = factors.Aggregate(1, (x,y) => x * y);
                var incrementMultiples = Enumerable.Range(1, int.MaxValue);
                Console.WriteLine(incrementMultiples.First(x => divisible(x)));     
            }
    

    jackal on
Sign In or Register to comment.