CODEWITHSUNDEEP
recursionlispschemesicp
Bob Parker
Bob Parker

Reputation: 41

Count amount of odd numbers in a sentence

I am fairly new to lisp and this is one of the practice problems.

First of all, this problem is from simply scheme. I am not sure how to answer this.
The purpose of this question is to write the function, count-odd that takes a sentence as its input and count how many odd digits are contained in it as shown below:

(count-odd'(234 556 4 10 97)) 6

or

(count-odd '(24680 42 88)) 0

If possible, how would you be able to do it, using higher order functions, or recursion or both - whatever gets the job done.

Upvotes: 4

Views: 1051

Answers (5)

user1001237
user1001237

Reputation:

I think this is a good way, too.

(define (count-odd sequence)
  (length (filter odd? sequence)))

(define (odd? num)
  (= (remainder num 2) 1))

(count-odd '(234 556 4 10 97))

Hope this will help~

The (length sequence) will return the sequence's length,
(filter proc sequence) will return a sequence that contains all the elements satisfy the proc.
And you can define a function called (odd? num)

Upvotes: 0

soegaard
soegaard

Reputation: 31145

Don't be confused if some of the other solutions look strange. Simply Scheme uses non-standard definitions for first and butfirst. Here is a solution, that I hope follows Simply Scheme friendly.

Here is one strategy to solve the problem:

  • turn the number into a list of digits
  • transform into a list of zero and ones (zero=even, one=odd)
  • add the numbers in the list

Example: 123 -> '(1 2 3) -> '(1 0 1) -> 2

(define (digit? x)
  (<= 0 x 9))

(define (number->digits x)
  (if (digit? x)
      (list x)
      (cons (remainder x 10)
            (number->digits (quotient x 10)))))

(define (digit->zero/one d)
  (if (even? d) 0 1))

(define (digits->zero/ones ds)
  (map digit->zero/one ds))

(define (add-numbers xs)
  (if (null? xs)
      0
      (+ (first xs)
         (add-numbers (butfirst xs)))))

(define (count-odds x)
  (add-numbers 
     (digits->zero/ones 
        (number->digits x))))

The above is untested, so you might need to fix a few typos.

Upvotes: 0

&#211;scar L&#243;pez
&#211;scar L&#243;pez

Reputation: 236122

Try to solve the problem by hand using only recursion before jumping to a higher-order solution; for that, I'd suggest to take a look at the other answers. After you have done that, aim for a practical solution using the tools at your disposal - I would divide the problem in two parts.

First, how to split a positive integer in a list of its digits; this is a recursive procedure over the input number. There are several ways to do this - by first converting the number to a string, or by using arithmetic operations to extract the digits, to name a few. I'll use the later, with a tail-recursive implementation:

(define (split-digits n)
  (let loop ((n n)
             (acc '()))
    (if (< n 10)
        (cons n acc)
        (loop (quotient n 10)
              (cons (remainder n 10) acc)))))

With this, we can solve the problem in terms of higher-order functions, the structure of the solution mirrors the mental process used to solve the problem by hand:

  1. First, we iterate over all the numbers in the input list (using map)
  2. Split each number in the digits that compose it (using split-digits)
  3. Count how many of those digits are odd, this gives a partial solution for just one number (using count)
  4. Add all the partial solutions in the list returned by map (using apply)

This is how it looks:

(define (count-odd lst)
  (apply +
         (map (lambda (x)
                (count odd? (split-digits x)))
              lst)))

Upvotes: 0

PALEN
PALEN

Reputation: 2876

Please take first into consideration the other answer guide so that you try to do it by yourself. The following is a different way of solving it. Here is a tested full solution:

(define (count-odd num_list)
    (if (null? num_list)
        0
        (+ (num_odds (car num_list)) (count-odd (cdr num_list)))))

(define (num_odds number)
    (if (zero? number)
        0
        (+ (if (odd? number) 1 0) (num_odds (quotient number 10)))))

Both procedures are recursive.

  • count-odd keeps getting the first element of a list and passing it to num_odds until there is no element left in the list (that is the base case, a null list).

  • num_odds gets the amount of odd digits of a number. To do so, always asks if the number is odd in which case it will add 1, otherwise 0. Then the number is divided by 10 to remove the least significant digit (which determines if the number is odd or even) and is passed as argument to a new call. The process repeats until the number is zero (base case).

Upvotes: 1

daniel gratzer
daniel gratzer

Reputation: 53901

I'll give you a few pointers, not a full solution:

First of all, I see 2 distinct ways of doing this, recursion or higher order functions + recursion. For this case, I think straight recursion is easier to grok.

So we'll want a function which takes in a list and does stuff, so

(define count-odd
  (lambda (ls) SOMETHING))

So this is recursive, so we'd want to split the list

(define count-odd
  (lambda (ls)
    (let ((head (car ls)) (rest (cdr ls)))
      SOMETHING)))

Now this has a problem, it's an error for an empty list (eg (count-odd '())), but I'll let you figure out how to fix that. Hint, check out scheme's case expression, it makes it easy to check and deal with an empty list

Now something is our recursion so for something something like:

(+ (if (is-odd head) 1 0) (Figure out how many odds are in rest))

That should give you something to start on. If you have any specific questions later, feel free to post more questions.

Upvotes: 4

Related Questions