Page 1 of 10 123 ... LastLast
Results 1 to 10 of 96

Thread: Beginner Programming Challenge #10

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

    Beginner Programming Challenge #10

    Welcome to the 10th programming challenge, sponsored by The Ubuntu Beginners Team Development Focus Group. I have been tasked with coming up with this challenge by virtue of 'winning' programming challenge #9.

    background
    :
    -----
    I have a connection with Lychrel numbers so I wanted to make this challenge something in relation to those.

    lychrel numbers:
    -----
    A Lychrel number is a natural number which cannot form a palindrome through the iterative process of repeatedly reversing its digits and adding the resulting numbers. The name "Lychrel" was coined by Wade VanLandingham; a rough anagram of his girlfriend's name Cheryl.

    example: The reverse and add process produces the sum of a number and the number formed by reversing the order of its digits.eg. 56 + 65 = 121, 125 + 521 = 646, 9999 + 9999 = 19998


    task:
    -----
    Find all the Lychrel candidate numbers below 10,000


    bonus points
    :
    -----
    Find all the Lychrel seed numbers below 10,000


    Disqualified Entries:
    -----
    Any overly obfuscated code will be immediately disqualified without account for programmers skill. Please remember that these challenges are for beginners and therefore the code should be easily readable and well commented.

    Any non-beginner entries will not be judged. Please use common sense when posting code examples. Please do not give beginners a copy paste solution before they have had a chance to try this for themselves.


    Assistance:
    -----
    If you require any help with this challenge please do not hesitate to come and chat to the development focus group. We have a channel on irc.freenode.net #ubuntu-beginners-dev

    ----------
    OK -- time for you all to be rockstars!

  2. #2
    Join Date
    Feb 2008
    Location
    Boston, MA
    Beans
    Hidden!
    Distro
    Ubuntu

    Re: Beginner Programming Challenge #10

    Looks great! Let's see some entries, people!

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

    Re: Beginner Programming Challenge #10

    I'm not sure I'd call this a "beginner" challenge...
    Posting code? Use the [code] or [php] tags.
    I don't care, I'm still free. You can't take the sky from me.

  4. #4
    Join Date
    Apr 2007
    Location
    Germany
    Beans
    239
    Distro
    Ubuntu 10.04 Lucid Lynx

    Re: Beginner Programming Challenge #10

    Quote Originally Posted by schauerlich View Post
    I'm not sure I'd call this a "beginner" challenge...
    +1

    Is 196 a Lychrel number? Nobody knows, it hasn't been proven yet. So 196 would be a Lychrel candidate number? But how many iterations should be made before calling a number a Lychrel candidate? And what is a Lychrel seed number?
    NEVER use a command given to you before asking and knowing exactly what it does. Make sure you know what it is that you're telling your system to do before doing it; some commands can be very harmful to your system or leave you vulnerable to attack.

  5. #5

    Re: Beginner Programming Challenge #10

    I think its a good challenge.

    I am going to do it in a language I am still a bit green with: Python

    -Silver Fox

  6. #6

    Re: Beginner Programming Challenge #10

    Quote Originally Posted by conehead77 View Post
    What is a Lychrel seed number?
    From Wikipedia:
    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.
    -Silver Fox

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

    Re: Beginner Programming Challenge #10

    Quote Originally Posted by conehead77 View Post
    +1

    Is 196 a Lychrel number? Nobody knows, it hasn't been proven yet. So 196 would be a Lychrel candidate number? But how many iterations should be made before calling a number a Lychrel candidate? And what is a Lychrel seed number?
    Wikipedia says that the largest number of iterations for a number under 10,000 to resolve to a palindrome is 24. So I'd say go for 30 iterations before calling it a lychrel candidate.
    Posting code? Use the [code] or [php] tags.
    I don't care, I'm still free. You can't take the sky from me.

  8. #8
    Join Date
    Nov 2005
    Location
    Sendai, Japan
    Beans
    11,296
    Distro
    Kubuntu

    Re: Beginner Programming Challenge #10

    Obligatory Haskell.

    PHP Code:
    readInt             :: String -> Int
    reverseInt          
    :: Int -> Int
    isPalindrome        
    :: Int -> Bool
    isCandidate         
    :: (IntInt) -> Bool

    readInt             
    read

    reverseInt n        
    = if 10
                            then n
                            
    else readInt (reverse (show n))

    isPalindrome n      = if 10
                            then True
                            
    else ns == reverse ns
                                where ns 
    show n

    isCandidate 
    (30_) = True
    isCandidate 
    (np)  = if isPalindrome p
                            then False
                            
    else isCandidate (1reverseInt p)

    main = print [<- [1..9999], isCandidate (0n)] 
    I'll do the seed-hunting later. I don't think it really needs commenting, but someone correct me if I'm wrong.
    Last edited by Bachstelze; March 7th, 2010 at 10:45 PM.
    「明後日の夕方には帰ってるからね。」


  9. #9
    Join Date
    Nov 2005
    Location
    Sendai, Japan
    Beans
    11,296
    Distro
    Kubuntu

    Re: Beginner Programming Challenge #10

    Quote Originally Posted by schauerlich View Post
    Wikipedia says that the largest number of iterations for a number under 10,000 to resolve to a palindrome is 24. So I'd say go for 30 iterations before calling it a lychrel candidate.
    Yup. I went up to 10,000 iterations, and it gave me the same results as 30.
    「明後日の夕方には帰ってるからね。」


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

    Re: Beginner Programming Challenge #10

    here's my first scheme implementation.
    Code:
    (use-modules (ice-9 format))
    
    (define num->chain
      (lambda (num)
        (if (< num 10)
            (list num)
            (cons (remainder num 10) (num->chain (quotient num 10))))))
    
    (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 empty-chain? null?)
    
    (define chain->num
      (lambda (chain)
        (if (empty-chain? 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-numbers
      (lambda (limit max-tries)
    
        (define iterate
          (lambda (chain)
            (num->chain (+ (chain->num chain) (chain->num (reverse-chain chain))))))
    
        (define is-lychrel-number?
          (lambda (chain try)
            (cond ((> try max-tries)
                   #f)
                  ((is-palindrome? chain)
                   (chain->num chain))
                  (else
                   (is-lychrel-number? (iterate chain) (+ try 1))))))
    
        (define loop
          (lambda (number)
            (if (< number limit)
                (let ((result (is-lychrel-number? (num->chain number) 0)))
                  (if (not result)
                      (format #t "~d is a candidate\n" number))
                  (loop (+ 1 number))))))
    
        (loop 1)))
    
    (find-lychrel-numbers 10000 40)
    it works by storing the numbers in chains of digits and then reversing these chains and adding them. this saves the overhead of using int->string and string->int conversion.

    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
    there are 10 types of people in the world: those that understand binary and i don't know who the other F are.

Page 1 of 10 123 ... 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
  •