Page 2 of 10 FirstFirst 1234 ... LastLast
Results 11 to 20 of 96

Thread: Beginner Programming Challenge #10

  1. #11
    Join Date
    Nov 2005
    Location
    Bordeaux, France
    Beans
    11,297
    Distro
    Ubuntu 12.04 Precise Pangolin

    Re: Beginner Programming Challenge #10

    Quote Originally Posted by howlingmadhowie View Post
    in case anybody's interested, it takes this much time:
    Code:
    howlingmadhowie% time guile lychrel.scm 1>/dev/null
    guile lychrel.scm > /dev/null  2,02s user 0,01s system 98% cpu 2,065 total
    Beat you

    Code:
    firas@momiji ~ % time ./lychrel > /dev/null
    ./lychrel > /dev/null  0.23s user 0.00s system 94% cpu 0.242 total
    「明後日の夕方には帰ってるからね。」


  2. #12
    Join Date
    Jul 2006
    Location
    somewhere :)
    Beans
    535
    Distro
    Ubuntu 10.04 Lucid Lynx

    Re: Beginner Programming Challenge #10

    Quote Originally Posted by Bachstelze View Post
    Beat you

    Code:
    firas@momiji ~ % time ./lychrel > /dev/null
    ./lychrel > /dev/null  0.23s user 0.00s system 94% cpu 0.242 total
    interesting. haskell must have some pretty good number/string conversion functions. i imagine my code is slow because of the huge amounts of quotient and remainder functions in it, but i can get around that by writing a function to add two chains. maybe i'll do that and see if it's faster ...
    there are 10 types of people in the world: those that understand binary and i don't know who the other F are.

  3. #13
    Join Date
    May 2008
    Beans
    Hidden!

    Re: Beginner Programming Challenge #10

    Quote Originally Posted by howlingmadhowie View Post
    interesting. haskell must have some pretty good number/string conversion functions. i imagine my code is slow because of the huge amounts of quotient and remainder functions in it, but i can get around that by writing a function to add two chains. maybe i'll do that and see if it's faster ...
    Python seems to be similar. This code:

    PHP Code:
    int(str(n)[::-1]) 
    will outperform this code:

    PHP Code:
    def reverse_digits(n):
        
    0
        
    while n:
            
    ndivmod(n10)
            
    10 t
        
    return 
    Though this isn't entirely surprising, as generally the more time Python code spends in C, the faster it runs.

  4. #14
    Join Date
    Apr 2007
    Location
    NorCal
    Beans
    1,149
    Distro
    Ubuntu 10.04 Lucid Lynx

    Re: Beginner Programming Challenge #10

    A fairly simple C implementation. It uses recursion, which may be a little tricky for beginners, but hopefully my comments explain it well enough. It's certainly not the most efficient method (converting to a string, reversing the string and atol()'ing it), but it gets the job done.

    I decided to do recursion because I'm not very good at it.

    Code:
    #include <stdio.h>
    #include <stdlib.h>
    #include <string.h>
    
    #define MAX_LYCHREL 10000
    #define DEPTH 30
    
    void reverse(char *str, char *rev_str) {
      // reverses str and stores it in rev_str
      
      long len = strlen(str); // get the length of the string
      long i;
      
      if (!len) // if the string is empty
        return;
      
      for (i = 0; i < len; i++) { // for each char in the string
        // put the i-th char from the back of str into the i-th position
        // of rev_str. For instance, put the second to last character of str
        // into the second position in rev_str.
        rev_str[i] = str[len - i - 1];
      } // for i
      
      // C ends all of its strings in '\0' characters, so we need to add one
      // to the end so that string functions know where the string is
      // supposed to end
      rev_str[len] = '\0';
      
    } // reverse()
    
    
    int islychrel(long n, long d) {
      // recursively decides if a number is a lychrel candidate after depth d
      
      // allocate strings for n and its reverse, and a long int for n's reverse
      char nStr[100], nRevStr[100];
      long nRev;
      
      // convert n to a string
      sprintf(nStr, "%ld", n);
      
      // reverse n and put it in a string
      reverse(nStr, nRevStr);
      
      // convert that string to a long int
      nRev = atol(nRevStr);
      
      // if we've reached the maximum recursion depth, we're done, so 
      // return true (ie, n is a lychrel candidate)
      if (d <= 0)
        return 1;
      
      // if the number is a palindrome, we're done and should return false
      // (n is NOT a lychrel candidate)   
      if (d != DEPTH && n == nRev)
        return 0;
      
      // now we go around again, this time checking if the number plus its reverse is
      // a palindrome. We decrement the depth so that once it gets to zero, we give up
      // and the recursion "unwinds"
      return islychrel(n + nRev, d - 1);
      
    } // islychrel()
    
    
    
    int main(int argc, char *argv[]) {
      long i;
      
      // iterate through 0 - MAX_LYCHREL (for this challenge, 10000)
      // and print it out if it's a lychrel candidate
      for (i = 0; i <= MAX_LYCHREL; i++)
        if (islychrel(i, DEPTH))
          printf("%ld\n", i);
      
      return 0;
      
    } // main()
    
    Code:
    real	0m0.039s
    user	0m0.023s
    sys	0m0.004s
    Last edited by schauerlich; March 8th, 2010 at 09:59 PM.
    Posting code? Use the [code] or [php] tags.
    I don't care, I'm still free. You can't take the sky from me.

  5. #15
    Join Date
    Apr 2007
    Location
    NorCal
    Beans
    1,149
    Distro
    Ubuntu 10.04 Lucid Lynx

    Re: Beginner Programming Challenge #10

    I decided to try it in python, a language I never really got into... wrote this in about 5 minutes. It's pretty much the same as my C entry, but python lists and easy casting between strings and ints made it much faster to write.

    Code:
    #!/usr/bin/env python
    
    DEPTH = 30
    MAX_LYCHREL = 10000
    
    def islychrel(n, d):
        # recursively decides if a number is a lychrel candidate,
        # giving up after d tries.
        
        # convert n to a string
        nStr = str(n)
        
        # reverse it. This uses a funky way of slicing nStr
        nRevStr = nStr[::-1]
        
        # make an int out of the reversed string
        nRev = int(nRevStr)
        
        # d will equal zero when we've hit our maximum recursion
        # depth - that is, when we've gone through a bunch of times
        # without finding a palindrome. This means the number IS a
        # lychrel candidate and we should return True
        if d <= 0:
            return True
        
        # if the number and its reverse are equal, then the
        # number is a palindrome. This means the number
        # is NOT a lychrel candidate and we should return False
        if d != DEPTH and n == nRev:
            return False
        
        # if neither of our base cases are met, then we should try
        # the same thing again, this time adding the number and its
        # reverse, and decrementing the depth.
        return islychrel(n + nRev, d - 1)
    
    def main():
        # for every number between 0 and 10000,
        # if the number is a lychrel candidate,
        # print it
        for i in range(0, MAX_LYCHREL):
            if islychrel(i, DEPTH):
                print i
    
    if __name__ == "__main__":
        main()
    Code:
    real	0m0.188s
    user	0m0.164s
    sys	0m0.016s
    Last edited by schauerlich; March 8th, 2010 at 09:59 PM.
    Posting code? Use the [code] or [php] tags.
    I don't care, I'm still free. You can't take the sky from me.

  6. #16
    Join Date
    Jul 2006
    Location
    somewhere :)
    Beans
    535
    Distro
    Ubuntu 10.04 Lucid Lynx

    Re: Beginner Programming Challenge #10

    okay. this one finds the seeds as well:

    Code:
    (use-modules (ice-9 format))
    
    (define reverse-chain
      (lambda (c)
        (define reverse-helper
          (lambda (l-in l-out)
    	(if (null? l-in)
    	    l-out
    	    (reverse-helper (cdr l-in) (cons (car l-in) l-out)))))
        (reverse-helper c '())))
    
    (define num->chain
      (lambda (num)
        (if (< num 10)
    	(list num)
    	(cons (remainder num 10) (num->chain (quotient num 10))))))
    
    
    (define empty-chain? null?)
    
    (define add-chains
      (lambda (c1 c2)
    
        (define add-links
          (lambda (l1 l2 carry)
    	(let ((num (+ l1 l2 carry)))
    	  (if (> num 9)
    	      (cons 1 (- num 10))
    	      (cons 0 num)))))
    
        (define loop
          (lambda (c1 c2 carry)
    	(cond ((and (null? c1) (null? c2))
    	       (if (> carry 0)
    		   (list carry)
    		   '()))
    	      ((null? c1)
    	       (let ((new-link (add-links 0 (car c2) carry)))
    		 (cons (cdr new-link) (loop '() (cdr c2) (car new-link)))))
    	      ((null? c2)
    	       (let ((new-link (add-links (car c1) 0 carry)))
    		 (cons (cdr new-link) (loop (cdr c1) '() (car new-link)))))
    	      (else
    	       (let ((new-link (add-links (car c1) (car c2) carry)))
    		 (cons (cdr new-link) (loop (cdr c1) (cdr c2) (car new-link))))))))
    
        (loop c1 c2 0)))
    
    (define chain->num
      (lambda (chain)
        (if (null? chain)
    	0
    	(+ (car chain) (* 10 (chain->num (cdr chain)))))))
    
    (define is-palindrome?
      (lambda (n)
    
        (define same-chain?
          (lambda (c1 c2)
    	(cond ((empty-chain? c1)
    	       (if (empty-chain? c2)
    		   #t
    		   #f))
    	      ((empty-chain? c2)
    	       (if (empty-chain? c1)
    		   #t
    		   #f))
    	      ((= (car c1) (car c2))
    	       (same-chain? (cdr c1) (cdr c2)))
    	      (else #f))))
    
        (same-chain? n (reverse-chain n))))
    
    (define find-lychrel-seeds
      (lambda (limit max-tries)
    
        (define iterate
          (lambda (chain)
    	(add-chains chain (reverse-chain chain))))
        
        (define is-lychrel-number?
          (lambda (chain try l return)
    	(cond ((> try max-tries)
    	       l)
    	      ((is-palindrome? chain)
    	       (return (chain->num chain)))
    	      (else
    	       (is-lychrel-number? (iterate chain) (+ try 1) (cons (chain->num chain) l) return)))))
    
        (define loop
          (lambda (number results)
    	(if (< number limit)
    	    (let ((result (call/cc (lambda (k) (is-lychrel-number? (num->chain number) 0 '() k)))))
    	      (if (list? result)
    		  (loop (+ 1 number) (cons result results))
    		  (loop (+ 1 number) results)))
    	    (reverse results))))
        
        (define get-last-elements
          (lambda (l)
    	(if (null? l)
    	    '()
    	    (cons (car (reverse (car l))) (get-last-elements (cdr l))))))
    
        (let ((lychrel-numbers (loop 1 '())))
    
          (define my-list-test?
    	(lambda (in1 in2 pred?)
    	  (let loop ((obj1 in1)
    		     (obj2 in2))
    	    (cond ((null? obj1) #f)
    		  ((pred? (car obj1) obj2) #t)
    		  (else (loop (cdr obj1) obj2))))))
    
          (define in-list?
    	(lambda (l elem)
    	  (my-list-test? l elem =)))
    
          (define seed-already-found?
    	(lambda (list-of-lists l2)
    	  (my-list-test? list-of-lists l2 same-seed?)))
    
          (define same-seed?
    	(lambda (l1 l2)
    	  (cond ((null? l1) #f)
    		((in-list? l2 (car l1)) #t)
    		(else
    		 (same-seed? (cdr l1) l2)))))
    
          (define inner-loop
    	(lambda (seed-list lychrel-list)
    	  (cond ((null? lychrel-list) seed-list)
    		((seed-already-found? seed-list (car lychrel-list))
    		 (inner-loop seed-list (cdr lychrel-list)))
    		(else (inner-loop (cons (car lychrel-list) seed-list) (cdr lychrel-list))))))
    
          (let ((lychrel-seed-lists (inner-loop '() lychrel-numbers)))
    
            (cons (get-last-elements lychrel-numbers) (list (reverse (get-last-elements lychrel-seed-lists))))))))
    
    (display (find-lychrel-seeds 10000 40))
    (newline)
    it's quite ugly code atm. i'll clean it up a bit later.

    it outputs two lists. the first one is the list of lychrel numbers, the second is the list of seeds:

    Code:
    howlingmadhowie% time guile lychrel.scm
    ((196 295 394 493 592 689 691 788 790 879 887 978 986 1495 1497 1585 1587 1675 1677 1765 1767 1855 1857 1945 1947 1997 2494 2496 2584 2586 2674 2676 2764 2766 2854 2856 2944 2946 2996 3493 3495 3583 3585 3673 3675 3763 3765 3853 3855 3943 3945 3995 4079 4169 4259 4349 4439 4492 4494 4529 4582 4584 4619 4672 4674 4709 4762 4764 4799 4852 4854 4889 4942 4944 4979 5078 5168 5258 5348 5438 5491 5493 5528 5581 5583 5618 5671 5673 5708 5761 5763 5798 5851 5853 5888 5941 5943 5978 5993 6077 6167 6257 6347 6437 6490 6492 6527 6580 6582 6617 6670 6672 6707 6760 6762 6797 6850 6852 6887 6940 6942 6977 6992 7059 7076 7149 7166 7239 7256 7329 7346 7419 7436 7491 7509 7526 7581 7599 7616 7671 7689 7706 7761 7779 7796 7851 7869 7886 7941 7959 7976 7991 8058 8075 8079 8089 8148 8165 8169 8179 8238 8255 8259 8269 8328 8345 8349 8359 8418 8435 8439 8449 8490 8508 8525 8529 8539 8580 8598 8615 8619 8629 8670 8688 8705 8709 8719 8760 8795 8799 8809 8850 8868 8885 8889 8899 8940 8958 8975 8979 8989 8990 9057 9074 9078 9088 9147 9164 9168 9178 9237 9254 9258 9268 9327 9344 9348 9358 9417 9434 9438 9448 9507 9524 9528 9538 9597 9614 9618 9628 9687 9704 9708 9718 9777 9794 9798 9808 9867 9884 9888 9898 9957 9974 9978 9988) (196 879 1997 7059))
    guile lychrel.scm  3,90s user 0,03s system 98% cpu 3,992 total
    maybe i'll tidy up the code a bit tomorrow
    there are 10 types of people in the world: those that understand binary and i don't know who the other F are.

  7. #17
    Join Date
    Nov 2005
    Location
    Bordeaux, France
    Beans
    11,297
    Distro
    Ubuntu 12.04 Precise Pangolin

    Re: Beginner Programming Challenge #10

    New version that tries to extract the seeds but still gives a few false positives... I also added a few comments to make things clearer.

    PHP Code:
    readInt             :: String -> Integer
    reverseInt          
    :: Integer -> Integer
    nextIt              
    :: Integer -> Integer
    isPalindrome        
    :: Integer -> Bool
    digitsSum           
    :: Integer -> Integer
    equalDigitsSum      
    :: Integer -> Integer -> Bool
    groupByDigitsSum    
    :: [Integer] -> [[Integer]]
    inSameThread        :: Integer -> Integer -> Bool
    isCandidate         
    :: (IntegerInteger) -> Bool
    extractSeeds        
    :: [Integer] -> [Integer]

    -- 
    readInt is just an instance of read.
    -- 
    Takes a string of digits as inputreturns the corresponding Integer
    readInt             
    read

    -- reverseInt takes an Integer as input and returns it with its digits
    -- in reverse order.
    reverseInt n        readInt (reverse (show n))

    -- 
    Self explanatory ;)
    nextIt n            + (reverseInt n)

    -- 
    Returns True iff the Integer passed as input is a palindrome.
    isPalindrome n      ns == reverse ns
                            where ns 
    show n

    -- Takes a 2-uple (np) as input.
    -- 
    nnumber we want to test
    -- pnumber of iterations so far (=for an initial call)
    -- 
    Returns True iff n is a Lychrel candidatei.eno palindrome has been
    -- found after 30-p iterations.
    isCandidate (_30) = True
    isCandidate 
    (n0)  = isCandidate (nextIt n1)
    isCandidate (np)  = if isPalindrome n
                            then False
                            
    else isCandidate (nextIt np+1)
                            
    -- 
    Takes an Integer as input and returns the sum of its digits.
    digitsSum n 10    n
                
    otherwise = (mod n 10) + digitsSum (quot n 10)

    -- 
    Self explanatory ;)
    equalDigitsSum n p  digitsSum n == digitsSum p

    -- Takes a list of Integers and returns a list of lists of Integers
    -- where the digits of all Integers in the same "sublist" have the same sum.
    -- 
    We do this because in each "sublist"there will be at most one seed,
    -- and if 
    there is oneit will be the first element of the list.
    groupByDigitsSum []     = []
    groupByDigitsSum (n:ns) = eqn:(groupByDigitsSum noteqn)
                                
    where   eqn n:[<- nsequalDigitsSum n p]
                                        
    noteqn = [<- ns`notElemeqn]

    -- 
    Returns True iff a and b are in the same threadi.ethey "meet" after
    -- a sufficient number of iterations.
    inSameThread a b
            
    -- We need this so we don't try indefinitely to make a and b "meet".
            | a > 100000000 = False
            | a > b         = inSameThread b a
            | a == b        = True
            | nextIt a == b = True
            | otherwise     = inSameThread (nextIt a) (nextIt b)

    -- Extract the seeds from a list of candidates
    extractSeeds []         = []
    extractSeeds (n:ns)     = n:(extractSeeds [p | p <- ns, not (inSameThread n p)])

    main = do
            -- List of all candidates < 10,000
            let candidates = [n | n <- [1..9999], isCandidate(n, 0)]

            putStrLn "Lychrel candidates < 10,000:"
            print candidates
            putStrLn ""
            putStrLn "Possible seeds < 10,000:"

            -- List of all possible seeds, i.e. the first element of each group of
            -- candidates whose digits have the same sum.
            let possibleSeeds = [head l | l <- groupByDigitsSum candidates]
            print possibleSeeds

            -- Bad news: we still have some non-seeds.
            -- Good news: inSameThread is going to help us!
            --
            -- if a is in possibleSeeds but it not actually a seed, it will be in
            -- the thread grown from a seed.
            putStrLn ""
            print (extractSeeds possibleSeeds) 
    Code:
    firas@momiji ~ % ./lychrel
    Lychrel candidates < 10,000:
    [196,295,394,493,592,689,691,788,790,879,887,978,986,1495,1497,1585,1587,1675,1677,1765,1767,1855,1857,1945,1947,1997,2494,2496,2584,2586,2674,2676,2764,2766,2854,2856,2944,2946,2996,3493,3495,3583,3585,3673,3675,3763,3765,3853,3855,3943,3945,3995,4079,4169,4259,4349,4439,4492,4494,4529,4582,4584,4619,4672,4674,4709,4762,4764,4799,4852,4854,4889,4942,4944,4979,4994,5078,5168,5258,5348,5438,5491,5493,5528,5581,5583,5618,5671,5673,5708,5761,5763,5798,5851,5853,5888,5941,5943,5978,5993,6077,6167,6257,6347,6437,6490,6492,6527,6580,6582,6617,6670,6672,6707,6760,6762,6797,6850,6852,6887,6940,6942,6977,6992,7059,7076,7149,7166,7239,7256,7329,7346,7419,7436,7491,7509,7526,7581,7599,7616,7671,7689,7706,7761,7779,7796,7851,7869,7886,7941,7959,7976,7991,8058,8075,8079,8089,8148,8165,8169,8179,8238,8255,8259,8269,8328,8345,8349,8359,8418,8435,8439,8449,8490,8508,8525,8529,8539,8580,8598,8615,8619,8629,8670,8688,8705,8709,8719,8760,8778,8795,8799,8809,8850,8868,8885,8889,8899,8940,8958,8975,8979,8989,8990,9057,9074,9078,9088,9147,9164,9168,9178,9237,9254,9258,9268,9327,9344,9348,9358,9417,9434,9438,9448,9507,9524,9528,9538,9597,9614,9618,9628,9687,9704,9708,9718,9777,9794,9798,9808,9867,9884,9888,9898,9957,9974,9978,9988,9999]
    
    Possible seeds < 10,000:
    [196,689,879,1495,1497,1997,4079,4799,7599,8089,8799,8899,9999]
    
    [196,879,1495,1997,7599,8799,9999]
    Last edited by Bachstelze; March 8th, 2010 at 05:05 AM.
    「明後日の夕方には帰ってるからね。」


  8. #18
    cprofitt's Avatar
    cprofitt is offline νόησις νοήσεως - nóesis noéseos
    Join Date
    Oct 2006
    Location
    平静
    Beans
    1,449
    Distro
    Ubuntu Development Release

    Re: Beginner Programming Challenge #10

    Most of the entries have a basic flaw in their design. Review what a Lychrel number is and check your code.

  9. #19
    Join Date
    Jul 2006
    Location
    somewhere :)
    Beans
    535
    Distro
    Ubuntu 10.04 Lucid Lynx

    Re: Beginner Programming Challenge #10

    Quote Originally Posted by cprofitt View Post
    Most of the entries have a basic flaw in their design. Review what a Lychrel number is and check your code.
    err, what's wrong? the entries i've looked at print a list of the candidate lychrel numbers under 10000. isn't that what you wanted?
    there are 10 types of people in the world: those that understand binary and i don't know who the other F are.

  10. #20
    Join Date
    Nov 2009
    Beans
    1,081

    Re: Beginner Programming Challenge #10

    The entries already posted tend to reject numbers that are palindromes.

Page 2 of 10 FirstFirst 1234 ... LastLast

Tags for this Thread

Bookmarks

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •