Upside Up

May 27, 2011

This is an easy exercise for a lazy late-spring Friday afternoon. We take 0, 1, 6, 8 and 9 as the possible upside up digits:

(define (upside-up d)
  (case d ((0) 0) ((1) 1) ((6) 9) ((8) 8) ((9) 6) (else #f)))

Then we map over the digits of the input, report #f if any have no upside, then recombine and check if the number is the same as its upside up reversal:

(define (upside-up? n)
  (let ((ds (map upside-up (digits n))))
    (if (member #f ds) #f
      (= (undigits (reverse ds)) n))))

The next upside up number after 1961 is 6009, and there are 39 upside up numbers less than ten thousand:

> (let loop ((n 1962))
    (if (upside-up? n) n
      (loop (+ n 1))))
6009
> (length (filter upside-up? (range 10000)))
39

We used range, filter, digits, and undigits from the Standard Prelude. You can run the program at http://programmingpraxis.codepad.org/VYkXm2GM.

About these ads

Pages: 1 2

21 Responses to “Upside Up”

  1. [...] today’s Programming Praxis exercise, our task is to write a function to determine if a number remains the [...]

  2. My Haskell solution (see http://bonsaicode.wordpress.com/2011/05/27/programming-praxis-upside-up/ for a version with comments):

    upsideUp :: Show a => a -> Bool
    upsideUp n = and . zipWith isRot (show n) . reverse $ show n where
        isRot a b = maybe False (== b) . lookup a $ zip "01689" "01986"
    
    main :: IO ()
    main = do print $ head (filter upsideUp [1962..]) == 6009
              print $ length (filter upsideUp [0..9999]) == 39
    
  3. Graham said

    My Python solution:

    #!/usr/bin/env python
    from itertools import count, ifilter
    
    UPSIDE_DICT = dict(zip("01689", "01986"))   # matches digit to rotated version
    
    def is_upside_up(n):
        """Determines whether reads the same after being rotated 180 degrees"""
        digit_pairs = zip(str(n), str(n)[::-1])
        return all(UPSIDE_DICT.get(x, False) == y for (x, y) in digit_pairs)
    
    def next_upside_up(n):
        """Next upside up number after n"""
        return next(ifilter(is_upside_up, count(n + 1)))
    
    if __name__ == "__main__":
        print next_upside_up(1961)
        print sum(1 for n in xrange(10000) if is_upside_up(n))
    

    I went through at least 3 different versions of is_upside_up, making my solution less complicated each time; the first version was an imperative-style mess!

  4. Rainer said

    My Try in REXX

    count = 0                                                          
    first = 1                                                          
    do x = 1 to 10000                                                  
        /* valid: only digits 1,6,8,9         */                       
        /*        6 and 9 only in combination */                       
        if verify(x,'1689','N') > 0 then iterate                       
        if (verify(x,'18','N') == 0) &,                                
           ((pos('6',x) > 0 & pos('9',x) > 0) |,                       
            (pos('6',x) == 0 & pos('9',x) == 0)) then do               
            y = swap69(x)                                              
            if x == reverse(y) then do                                 
                count = count + 1                                      
                if x > 1691 & first == 1 then do                       
                    say 'First No. > 1691 =' x                         
                    first = 0                                          
                end                                                    
            end                                                        
        end                                                            
    end                                                                
    say 'there are' count 'upside up numbers between 1 and 10000'        
    exit                                                                 
    

    /*
    First No. > 1691 = 1881
    there are 12 upside up numbers between 1 and 10000
    */

  5. Rainer said

    and the Swap-Routine

     swap69: procedure                                   
         parse arg in                                    
         out = translate(in,'s',6)  /* 6 -> s */         
         out = translate(in,'n',9)  /* 9 -> n */         
         out = translate(in,9,'s')  /* s -> 9 */         
         out = translate(in,6,'n')  /* n -> 6 */         
         return out  
    
  6. Rainer said

    Sorry, copied confusing tries, this should be it:

    count = 0                                                    
    first = 1                                                    
    do x = 1 to 10000                                            
        /* valid: only digits 1,6,8,9         */                 
        /*        6 and 9 only in combination */                 
        if verify(x,'1689','N') > 0 then iterate                 
        if (verify(x,'18','N') == 0) &,                          
           ((pos('6',x) > 0 & pos('9',x) > 0) |,                 
            (pos('6',x) == 0 & pos('9',x) == 0)) then do         
            y = swap69(x)                                        
            if x == reverse(y) then do                           
                count = count + 1                                
                if x > 1691 & first == 1 then do                 
                    say 'First No. > 1691 =' x                   
                    first = 0                                    
                end                                              
            end                                                  
        end                                                      
    end                                                          
    say 'there are' count 'upside up numbers between 1 and 10000'  
    exit                                                           
                                                                   
    swap69: procedure                                              
        parse arg in                                               
        out = translate(in,'s',6)  /* 6 -> s */                    
        out = translate(out,'n',9)  /* 9 -> n */                   
        out = translate(out,9,'s')  /* s -> 9 */                   
        out = translate(out,6,'n')  /* n -> 6 */                   
        return out                                                 
    
  7. Bogdan Popa said

    My solution is pretty similar to Graham’s:

    from itertools import count, ifilter
    
    UPTABLE = dict(zip('01689', '01986'))
    valid = lambda n: all(UPTABLE.get(x, None) == y
                          for (x, y) in zip(str(n), reversed(str(n))))
    
    print next(ifilter(valid, count(1962)))
    print len(filter(valid, range(int(1e4))))
    
  8. Kanon said

    An inelegant solution to show them all for validation:

    print [i for i in range(10000) if set(str(i)).issubset(‘01689′) and str(i)[::-1].replace(‘6′,’x’).replace(‘9′,’6′).replace(‘x’,’9′)==str(i)]

  9. Pascal Bourguignon said

    ;;; Common Lisp:

    ;; 5 and 2 are clearly symetrical, as any 2¢ pocket calculator will
    ;; show you:
    ;;
    ;;  _     _
    ;; |_     _|
    ;;  _|   |_
    ;;

    ;; But since the concensus seems to be to ignore them:

    (defparameter *symetric-digits*
      #((#\0) (#\1) () () () () (#\9) () (#\8) (#\6))
      “A vector indexed by digits, containing lists of symetrical digits.”)

    (defun upside-down-digit-p (a b)
      (member a (aref *symetric-digits* (digit-char-p b))))

    (defun upside-down-number-p (n &optional (base 10.))
      (loop
         :with digits = (format nil “~VR” base n)
         :with last-index = (1- (length digits))
         :for i :from 0 :to (truncate (length digits) 2)
         :always (upside-down-digit-p (aref digits i) (aref digits (- last-index i)))))

    (defun programming-praxis-2011-05-27 ()
      (loop
         :with first-upside-down = nil
         :with count = 0
         :for n :from 1962 :below 10000
         :do (when (upside-down-number-p n)
               (unless first-upside-down
                 (setf first-upside-down n))
               (incf count))
         :finally (return (values first-upside-down count))))

    (programming-praxis-2011-05-27)
    –> 6009
        15

  10. slabounty said

    Cheating a bit by looking at the Python programs, but here’s one in Ruby …

    UPSIDE_DICT = %w[0 1 6 8 9].zip(%w[0 1 9 8 6])
    
    class Integer
        def upside?
            self.to_s.split(//).zip(self.to_s.split(//).reverse).inject(true) { |r,v| r && UPSIDE_DICT.include?(v) }
        end
    end
    
    (1..10000).each do |v|
        puts "#{v} is an upside number" if v.upside?
    end
    
  11. Mike said

    Another variant using python:

    from itertools import ifilter, imap, islice
    from operator import eq, methodcaller, Counter
    from string import maketrans
    
    # create a function that strips non-flipable digits (2,3,4,5,7) and flips the
    # flipable ones (e.g., 6 and 9).
    flipped = methodcaller('translate', maketrans('69','96'), '23457')
    
    def is_upside_up(n):
        s = str(n)
        return all(islice(imap(eq, s, flipped(s[::-1])), (len(s)+1)/2))
    
    
    next(ifilter(is_upside_up, count(1692)))
    
    Counter(imap(is_upside_up, xrange(10000)))
    
  12. David said

    Factor Programming language

    CONSTANT: upside-up-xform H{ { 0 0 }  { 1 1 }  { 6 9 }  { 8 8 }  { 9 6 } }
    
    : reversed-digits ( n -- list )
        { } swap
        [ dup 0 > ]
            [ 10 /mod  swapd suffix  swap ]
        while drop ;
    
    : list>number ( list -- n )
        0 [ swap 10 * + ] reduce ;
    
    : upside-up?  ( n -- ? )
        dup reversed-digits [ upside-up-xform at ] map
        [ ] filter list>number = ;
    

    ( scratchpad ) 10000 iota [ upside-up? ] filter length .
    39

  13. Mike said

    For grins, here’s a Erlang implementation. I’m new to Erlang, so I’m sure there are other, better, ways to do it.

    -module(upside).
    -export([is_upside_up/1, test/0]).
    
    is_upside_up(N) ->
            NL = integer_to_list(N),
    	NL == flipped(NL,[]).
    
    flipped([$0| T], L) -> flipped(T,[$0|L]);
    flipped([$1| T], L) -> flipped(T,[$1|L]);
    flipped([$2| _], _) -> false;
    flipped([$3| _], _) -> false;
    flipped([$4| _], _) -> false;
    flipped([$5| _], _) -> false;
    flipped([$6| T], L) -> flipped(T,[$9|L]);
    flipped([$7| _], _) -> false;
    flipped([$8| T], L) -> flipped(T,[$8|L]);
    flipped([$9| T], L) -> flipped(T,[$6|L]);
    flipped([],L)     -> L.
    
    test() ->
    	UL = [X || X <- lists:seq(0,10000), is_upside_up(X)],
    	{lists:nth(1, [N || N <- UL, N > 1961]), length(UL)}.
    
  14. Axio said

    I don’t understand why, sometimes, even though submission went good, the comment won’t show up…

    ;; Scheme
    (define (upside-char=? x y)
      (let ((yy (assoc x
                       '((#\0 #\0) (#\1 #\1) (#\2 #\5) (#\5 #\2) (#\6 #\9)
                                   (#\8 #\8) (#\2 #\5)))))
        (and yy (char=? y (cadr yy)))))
    ;
    (define (upside-down? n)
      (let* ((s (number->string n))
             (l (string-length s)))
        (let loop ((i 0) (j (1- l)))
          (if (< i j)
            (and
              (upside-char=? (string-ref s i)
                             (string-ref s j))
              (loop (1+ i) (1- j)))
            (or (and (member (string-ref s i) '(#\0 #\1 #\8)) #t)
                (> i j))))))

  15. Hunter said

    I went with building upside up numbers instead of looping 10,000 times and checking each one

    def build(string, flips):
      if len(string) == 2:
        return [string + flips[string[1]] + flips[string[0]]]
      else:
        upsideUps = []
        for key in flips.keys():
          upsideUps += build(string + flips[key], flips)
        return upsideUps
    
    def main():
      flips = {"0": "0", "1": "1", "6": "9", "8": "8", "9": "6"}
      upsideUps = build("", flips)
      upsideUps = sorted(upsideUps)
      for num in upsideUps:
        print num
    
  16. Dennis Decker Jensen said
    #include <stdio.h>
    
    // Upside up map of digits
    static char map[] = "01xxxx9x86";
    
    int
    main(void)
    {
    	int i, j;
    	char s[5], r[5];
    	int n = 0;
    
    	s[4] = r[4] = '\0';
    	for (i=1962; i<=9999; ++i)
    	{
    		sprintf(s, "%04d", i);
    		for (j=0; j<4; ++j)
    			r[j] = map[s[3-j] - '0'];
    		if (strcmp(s, r) == 0)
    			if (++n == 1)
    				printf("First upside up number: %d\n", i);
    	}
    	printf("There are %d upside up numbers between 1962 and 9999\n", n);
    }
    
  17. ardnew said
    function UpsideUp(N : Integer) : Boolean;
    const
      Map : array[0 .. 9] of Char =
        ('0', '1', '.', '.', '.', '.', '9', '.', '8', '6');
    
    var
      sN : String;
      sR : String;
      C  : PChar;
    
    begin
      sN := IntToStr(N);
      sR := '';
      C  := PChar(sN);
    
      while C^ <> #0 do
      begin
        sR := Map[StrToInt(C^)] + sR;
        Inc(C);
      end;
    
      Result := sN = sR;
    end;
    
  18. Atul Patel said

    //C# Solution.
    for (int i = 1961; i x == ‘1’ ||x == ‘6’ || x == ‘8’ ||x == ‘9’ ||x == ‘0’);
    foreach (var item in j)
    {
    topupNo += item;
    }
    if (topupNo == i.ToString())
    {
    Console.WriteLine(i.ToString());
    }
    }

  19. Atul Patel said

    //C# Solution

    . for (int i = 1961; i <= 10000; i++) {

     string topupNo = string.Empty; var j = i.ToString().Replace("6", "T").Replace("9",
    "6").Replace("T", "9").Reverse().Where(x => x == '1' ||x == '6' || x == '8' ||x
    == '9' ||x == '0');

    foreach (var item in j) { topupNo += item; }

    if (topupNo == i.ToString()) { Console.WriteLine(i.ToString()); } }

  20. DGel said

    Just cause there isn’t a version in Go yet.. It’s simple, but gets the job done:


    package main
    
    import (
    	"fmt"
    	"strconv"
    )
    
    func Is_upside_up(test int) bool {
    	transl := map[byte]byte{}
    	in := "01689"
    	out := "01986"
    	for i := 0; i < len(in); i++ {
    		transl[in[i]] = out[i]
    	}
    	
    	teststr := strconv.Itoa(test)
    	begin := 0
    	end := len(teststr) - 1
    	
    	for begin <= end {
    		if transl[teststr[begin]] != teststr[end] {
    			return false
    		}
    		begin++; end--
    	}
    	return true
    }
    
    func Next_upside_up(test int) int {
    	test += 1
    	for !Is_upside_up(test) { test += 1 }
    	return test
    }
    
    func main() {
    	fmt.Println(Next_upside_up(1961))
    	var sum int
    	for a := 0; a < 10000; a++ {
    		if Is_upside_up(a) {sum += 1}
    	}
    	fmt.Println(sum)
    }
    

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Follow

Get every new post delivered to your Inbox.

Join 630 other followers

%d bloggers like this: