Upside Up

May 27, 2011

An “upside up” number is a number that reads the same when it is rotated 180°. For instance, 689 and 1961 are upside up numbers.

Your task is to find the next upside up number greater than 1961, and to count the number of upside up numbers less than ten thousand. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

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 635 other followers

%d bloggers like this: