Page 3 of 10 FirstFirst 12345 ... LastLast
Results 21 to 30 of 96

Thread: Beginner Programming Challenge #10

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

    Re: Beginner Programming Challenge #10

    Quote Originally Posted by Some Penguin View Post
    The entries already posted tend to reject numbers that are palindromes.
    from wikipedia:
    A Lychrel number is a natural number which cannot form a palindrome through the iterative process of repeatedly reversing its base 10 digits and adding the resulting numbers.
    the way i read that is that the entries already posted are doing the right thing.
    there are 10 types of people in the world: those that understand binary and i don't know who the other F are.

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

    Re: Beginner Programming Challenge #10

    i modified the code to use some of the in-built scheme functions, like reverse and equal?. this shortens the code considerably but also introduces an element of cargo-cult programming.

    Code:
    (define reverse-chain reverse)
    
    (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)
        (num->chain (+ (chain->num c1) (chain->num c2)))))
    
    (define chain->num
      (lambda (chain)
        (if (null? chain)
    	0
    	(+ (car chain) (* 10 (chain->num (cdr chain)))))))
    
    (define same-chain? equal?)
    
    (define is-palindrome?
      (lambda (n)
        (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 return)
    	(cond ((> try max-tries)
    	       '())
    	      ((and (> try 0) (is-palindrome? chain))
    	       (return (chain->num chain)))
    	      (else
    	       (cons (chain->num chain) (is-lychrel-number? (iterate chain) (+ try 1) 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-first-elements
          (lambda (ll)
    	(if (null? ll)
    	    '()
    	    (cons (car (car ll)) (get-first-elements (cdr ll))))))
    
        (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-first-elements lychrel-numbers) (list (reverse (get-first-elements lychrel-seed-lists))))))))
    
    (display (find-lychrel-seeds 10000 40))
    (newline)
    --edit--
    okay, i've modified the code to also return palindromes which are lychrel candidates.
    Last edited by howlingmadhowie; March 8th, 2010 at 11:02 AM. Reason: modified the code
    there are 10 types of people in the world: those that understand binary and i don't know who the other F are.

  3. #23

    Re: Beginner Programming Challenge #10

    Quote Originally Posted by howlingmadhowie View Post
    the way i read that is that the entries already posted are doing the right thing.
    I thought so too. Can clarification be added please if we are wrong?

    -Silver Fox
    Me on the web:

  4. #24
    Join Date
    Nov 2009
    Beans
    1,081

    Re: Beginner Programming Challenge #10

    http://www.p196.org/lychrel%20records.html

    Well, if you go by that -- 9999 is a suspected Lychrel number, tested to over 60M iterations. The question is whether it can form a palindrome by that process -- going zero iterations does not appear to be permitted.

  5. #25
    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
    from wikipedia:


    the way i read that is that the entries already posted are doing the right thing.
    Seed numbers are a subset of Lychrel numbers, that is the smallest number of each non palindrome producing thread. A seed number may be a palindrome itself. The first three examples are shown in bold in the list above.
    Since a seed is necessarily a Lychrel number and may be a palindrome itself, a palindrome seed would be a palindrome Lychrel number.
    「明後日の夕方には帰ってるからね。」


  6. #26
    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
    Since a seed is necessarily a Lychrel number and may be a palindrome itself, a palindrome seed would be a palindrome Lychrel number.
    i think op means that we should take something like 9999 to be a lychrel candidate, so we have to change our code to start checking after one iteration.
    there are 10 types of people in the world: those that understand binary and i don't know who the other F are.

  7. #27
    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
    i think op means that we should take something like 9999 to be a lychrel candidate, so we have to change our code to start checking after one iteration.
    You have to change your code. I already have.
    「明後日の夕方には帰ってるからね。」


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

    Re: Beginner Programming Challenge #10

    Quote Originally Posted by howlingmadhowie View Post
    i think op means that we should take something like 9999 to be a lychrel candidate, so we have to change our code to start checking after one iteration.
    That is accurate if you are saying one iteration of the 196-algorithm.
    Last edited by cprofitt; March 8th, 2010 at 01:41 PM.

  9. #29
    Join Date
    Mar 2009
    Location
    Brazil
    Beans
    475
    Distro
    Ubuntu 12.04 Precise Pangolin

    Re: Beginner Programming Challenge #10

    I'm working on mine.
    It's in python and I'm not sure on how accurate is it yet.
    It's a quite difficult challenge.

    It's taking about 6 seconds to run up to 10000 and it finds lots of numbers, I'm not sure if they are all Lychrel candidates.
    I'll try again latter.
    Ubuntu User #27453 | Linux User #490358
    "Don't preach Linux, mention it"
    "Linux is not Windows"
    73% of statistics in forums are made up on the spot

  10. #30
    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 Marlonsm View Post
    I'm working on mine.
    It's in python and I'm not sure on how accurate is it yet.
    It's a quite difficult challenge.

    It's taking about 6 seconds to run up to 10000 and it finds lots of numbers, I'm not sure if they are all Lychrel candidates.
    I'll try again latter.
    You can look at howlingmadhowie's and my entries to check your results.
    「明後日の夕方には帰ってるからね。」


Page 3 of 10 FirstFirst 12345 ... 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
  •