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.
Programming Praxis 
[…] today’s Programming Praxis exercise, our task is to write a function to determine if a number remains the […]
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]) == 39My 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!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
*/
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 outSorry, 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 outMy 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))))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)]
;;; 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
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? endAnother 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)))[…] 출처: https://programmingpraxis.com/2011/05/27/upside-up/ […]
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
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)}.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))))))
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#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); }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;//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());
}
}
//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()); } }
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) }