Upside-down numbers: Difference between revisions
another Ada solution, based on Phix
m (→{{header|Quackery}}: tweaked layout) |
(another Ada solution, based on Phix) |
||
| (10 intermediate revisions by 5 users not shown) | |||
Line 29:
;* [[oeis:A299539|OEIS:A299539 - Upside-down numbers]]
=={{header|Ada}}==
===Version 1 (slower, direct from definition)===
<syntaxhighlight lang="ada">
pragma Ada_2022;
with Ada.Text_IO;
with Ada.Containers.Indefinite_Vectors;
with Ada.Containers.Indefinite_Ordered_Sets;
procedure Upside_Down_Numbers is
-- a rather slow algorithm that proceeds by recursive expansion; i.e.,
-- a straightforward implementation via the definition
package IO renames Ada.Text_IO;
subtype Digit is Integer range 1 .. 9;
Mirror : constant array (Digit) of Digit :=
[for Ith in Digit => 10 - Ith];
type Upside_Down_Number is array (Positive range <>) of Digit;
procedure Put (Number : Upside_Down_Number) is
package Digit_IO is new IO.Integer_IO (Num => Digit);
begin
for N of Number loop
Digit_IO.Put (N, 0);
end loop;
end Put;
package Upside_Down_Vecs is new Ada.Containers.Indefinite_Vectors
(Index_Type => Positive, Element_Type => Upside_Down_Number);
subtype Upside_Down_Vec is Upside_Down_Vecs.Vector;
package Upside_Down_Sets is new Ada.Containers.Indefinite_Ordered_Sets
(Element_Type => Upside_Down_Number);
subtype Upside_Down_Set is Upside_Down_Sets.Set;
function Expand_Even (Numbers : Upside_Down_Set) return Upside_Down_Set is
-- if Numbers holds even-length upside-down numbers,
-- this expands them to corresponding odd-length upside-down numbers
Result : Upside_Down_Set;
Length : constant Positive := Numbers.First_Element'Length;
Half_Length : constant Positive := Length / 2;
New_Number : Upside_Down_Number (1 .. Length + 1);
begin
for Old_Number of Numbers loop
for Ith in 1 .. Half_Length loop
New_Number (Ith) := Old_Number (Ith);
New_Number (Length + 1 - Ith + 1) := Old_Number (Length - Ith + 1);
end loop;
New_Number (Half_Length + 1) := 5;
if not Result.Contains (New_Number) then
Result.Insert (New_Number);
end if;
end loop;
return Result;
end Expand_Even;
function Expand_Odd (Numbers : Upside_Down_Set) return Upside_Down_Set is
-- if Numbers holds odd-length upside-down numbers,
-- this expands them to corresponding even-length upside-down numbers
--
-- alas, this is inefficient not only by exhaustive enumeration,
-- but by generating several numbers more than once
Result : Upside_Down_Set;
Length : constant Positive := Numbers.First_Element'Length;
Half_Length : constant Positive := (Length + 1) / 2;
New_Number : Upside_Down_Number (1 .. Length + 1);
begin
for Old_Number of Numbers loop
for Breakpoint in 1 .. Half_Length loop
for Ith in 1 .. Half_Length loop
if Ith < Breakpoint then
New_Number (Ith) := Old_Number (Ith);
New_Number (Length + 1 - Ith + 1) :=
Old_Number (Length - Ith + 1);
elsif Ith >= Breakpoint then
New_Number (Ith + 1) := Old_Number (Ith);
New_Number (Length + 1 - Ith) :=
Old_Number (Length - Ith + 1);
end if;
end loop;
for D in Digit loop
New_Number (Breakpoint) := D;
New_Number (Length + 1 - Breakpoint + 1) := Mirror (D);
if not Result.Contains (New_Number) then
Result.Insert (New_Number);
end if;
end loop;
end loop;
end loop;
return Result;
end Expand_Odd;
function Expand (Number : Upside_Down_Set) return Upside_Down_Set is
(if Number.First_Element'Length mod 2 = 0 then Expand_Even (Number)
else Expand_Odd (Number));
Iterations : array (1 .. 100) of Upside_Down_Set;
Result : Upside_Down_Vec;
Number_Computed : Positive := 1;
Ith : Positive := 1;
begin
IO.Put_Line ("Slow Formula");
IO.Put_Line ("==== =======");
Iterations (1).Insert (Upside_Down_Number'[5]);
Result.Append (Upside_Down_Number'[5]);
while Number_Computed < 5_000_000 loop
Iterations (Ith + 1) := Expand (Iterations (Ith));
Number_Computed := @ + Positive (Iterations (Ith + 1).Length);
for Each of Iterations (Ith + 1) loop
Result.Append (Each);
end loop;
Ith := @ + 1;
end loop;
IO.Put_Line ("Computed" & Number_Computed'Image & " upside-down numbers");
IO.Put ("The first 50: ");
for Ith in 1 .. 50 loop
Put (Result (Ith));
IO.Put (", ");
end loop;
IO.New_Line;
IO.Put ("The 500th: ");
Put (Result (500));
IO.New_Line;
IO.Put ("The 5_000th: ");
Put (Result (5_000));
IO.New_Line;
IO.Put ("The 500_000th: ");
Put (Result (500_000));
IO.New_Line;
IO.Put ("The 5_000_000th: ");
Put (Result (5_000_000));
IO.New_Line;
end Upside_Down_Numbers;
</syntaxhighlight>
{{out}}
<pre>
Slow Formula
==== =======
Computed 5978710 upside-down numbers
The first 50: 5, 19, 28, 37, 46, 55, 64, 73, 82, 91, 159, 258, 357, 456, 555, 654, 753, 852, 951, 1199, 1289, 1379, 1469, 1559, 1649, 1739, 1829, 1919, 2198, 2288, 2378, 2468, 2558, 2648, 2738, 2828, 2918, 3197, 3287, 3377, 3467, 3557, 3647, 3737, 3827, 3917, 4196, 4286, 4376, 4466,
The 500th: 494616
The 5_000th: 56546545
The 500_000th: 729664644183
The 5_000_000th: 82485246852682
</pre>
===Version 2===
{{Trans|Phix}}
<syntaxhighlight lang="ada">
pragma Ada_2022;
with Ada.Text_IO;
with Ada.Containers.Indefinite_Vectors;
with Ada.Containers.Indefinite_Ordered_Sets;
procedure Upside_Down_Numbers is
-- This translates the Phix solution, which essentially puts in a formula
-- the roughly quadratic growth of the upside-down numbers.
-- The essential insight is that every even digit increases
-- the number of new numbers generated by a factor of 10.
-- So, there are only 1 upside-down number of length 1,
-- 9 of length 2, 9 of length 3, 81 of length 4, and so forth.
-- From this fact you can navigate your way relatively quickly
-- to the desired number.
package IO renames Ada.Text_IO;
subtype Digit is Integer range 1 .. 9;
Mirror : constant array (Digit) of Digit :=
[for Ith in Digit => 10 - Ith];
type Upside_Down_Number is array (Positive range <>) of Digit;
procedure Put (Number : Upside_Down_Number) is
package Digit_IO is new IO.Integer_IO (Num => Digit);
begin
for N of Number loop
Digit_IO.Put (N, 0);
end loop;
end Put;
function Kth_Of_N (Kth, Digit, Count : Natural) return Upside_Down_Number is
-- we want the Kth integer of Digit length,
-- when we know it is Count from the first of this length
New_Count : Natural := Count;
New_Kth : Natural := Kth;
This_Digit : Natural;
begin
if Digit = 0 then
return Upside_Down_Number'[];
elsif Digit = 1 then
return Upside_Down_Number'[5];
else
New_Count := @ / 9;
This_Digit := (New_Kth - 1) / New_Count + 1;
New_Kth := @ - (This_Digit - 1) * New_Count;
declare
Temp : Upside_Down_Number :=
Kth_Of_N (New_Kth, Digit - 2, New_Count);
Result : Upside_Down_Number (1 .. Temp'Length + 2) :=
[1 => This_Digit, others => 1];
begin
Result (Temp'Last + 2) := Mirror (This_Digit);
for Ith in Temp'Range loop
Result (Ith + 1) := Temp (Ith);
end loop;
return Result;
end;
end if;
end Kth_Of_N;
function Phormula (Nth : Positive) return Upside_Down_Number is
-- Find the setup for Nth so that the Kth_Of_N formula works out.
-- This implements the insight mentioned above, that
-- the number of upside-down numbers increases by a factor of 9
-- for every even digit.
Digit : Positive := 1; -- number of digits needed
Count : Positive := 1; -- how many we've skipped so far
First : Positive := 1; -- the first u-d number for the current #digits
Last : Positive := 1; -- the last u-d number for the current #digits
begin
while Nth > Last loop
First := Last + 1;
Digit := @ + 1;
if Digit mod 2 = 0 then
Count := @ * 9;
end if;
Last := First + Count - 1;
end loop;
return Kth_Of_N (Nth - First + 1, Digit, Count);
end Phormula;
begin
IO.Put_Line ("Phast Phormula:");
IO.Put_Line ("===== ========");
IO.Put ("The first 50: ");
for Ith in 1 .. 50 loop
Put (Phormula (Ith));
IO.Put (", ");
end loop;
IO.New_Line;
IO.Put ("The 500th: ");
Put (Phormula (500));
IO.New_Line;
IO.Put ("The 5_000th: ");
Put (Phormula (5_000));
IO.New_Line;
IO.Put ("The 500_000th: ");
Put (Phormula (500_000));
IO.New_Line;
IO.Put ("The 5_000_000th: ");
Put (Phormula (5_000_000));
IO.New_Line;
end Upside_Down_Numbers;
</syntaxhighlight>
{{out}}
<pre>
Phast Phormula:
===== ========
The first 50: 5, 19, 28, 37, 46, 55, 64, 73, 82, 91, 159, 258, 357, 456, 555, 654, 753, 852, 951, 1199, 1289, 1379, 1469, 1559, 1649, 1739, 1829, 1919, 2198, 2288, 2378, 2468, 2558, 2648, 2738, 2828, 2918, 3197, 3287, 3377, 3467, 3557, 3647, 3737, 3827, 3917, 4196, 4286, 4376, 4466,
The 500th: 494616
The 5_000th: 56546545
The 500_000th: 729664644183
The 5_000_000th: 82485246852682
</pre>
=={{header|ALGOL 68}}==
Line 155 ⟶ 471:
=={{header|Basic}}==
==={{header|Applesoft BASIC}}===
Beyond 9 digits, rounding errors occur.
<syntaxhighlight lang="basic"> 1 PRINT "THE FIRST 50 UPSIDE DOWN NUMBERS:": FOR I = 1 TO 50: GOSUB 4: NEXT I: PRINT
2 FOR J = 2 TO 10::I = INT (5 * 10 ^ J): PRINT CHR$ (13)I"TH: ";: GOSUB 4: NEXT J
3 END
4 GOSUB 5: PRINT O$;: RETURN
5 IF I > = 1E9 THEN PRINT "?OVERFLOW" + CHR$ (7): END
6 L$ = "":R$ = "":S = I - 1:F = 1:I$(1) = "5": FOR E = 0 TO 1E38: FOR O = F TO 1:R = S:S = S - INT (9 ^ E):F = 0: IF S > = 0 THEN NEXT O,E
7 IF E THEN R = R + .5: FOR D = E - 1 TO 0 STEP - 1:N = INT (R / 9 ^ D):L$ = L$ + STR$ (N + 1):R$ = STR$ (9 - N) + R$:R = R - N * INT (9 ^ D): NEXT D
8 O$ = L$ + I$(O) + R$ + " "
9 RETURN
</syntaxhighlight>
{{out}}
<pre>THE FIRST 50 UPSIDE DOWN NUMBERS:
5 19 28 37 46 55 64 73 82 91 159 258 357 456 555 654 753 852 951 1199 1289 1379 1469 1559 1649 1739 1829 1919
500TH: 494616
Line 176 ⟶ 494:
50000000TH: 9285587463255281
500000000TH: 1436368345672474769
5E+09TH: ?OVERFLOW
</pre>
==={{header|FreeBASIC}}===
Line 218 ⟶ 537:
494616
56546545
</pre>
=={{header|C++}}==
<syntaxhighlight lang="C++">#include <iostream>
#include <vector>
#include <algorithm>
bool isUpsideDown( int n ) {
std::vector<int> digits ;
while ( n != 0 ) {
digits.push_back( n % 10 ) ;
n /= 10 ;
}
if ( std::find ( digits.begin( ) , digits.end( ) , 0 ) != digits.end( ) )
return false ;
int forward = 0 ;
int backward = digits.size( ) - 1 ;
while ( forward <= backward ) {
if ( digits[forward] + digits[backward] != 10 )
return false ;
forward++ ;
if ( backward > 0 ) {
backward-- ;
}
}
return true ;
}
int main( ) {
int current = 0 ;
int sum = 0 ;
std::vector<int> solution ;
while ( sum != 5000 ) {
current++ ;
if ( isUpsideDown( current ) ) {
solution.push_back( current ) ;
sum++ ;
}
}
std::cout << "The first 50 upside-down numbers:\n" ;
std::cout << "(" ;
for ( int i = 0 ; i < 50 ; i++ )
std::cout << solution[ i ] << ' ' ;
std::cout << ")\n" ;
std::cout << "The five hundredth such number: " << solution[499] << '\n' ;
std::cout << "The five thousandth such number: " << solution[4999] << '\n' ;
return 0 ;
}</syntaxhighlight>
{{out}}
<pre>
The first 50 upside-down numbers:
(5 19 28 37 46 55 64 73 82 91 159 258 357 456 555 654 753 852 951 1199 1289 1379 1469 1559 1649 1739 1829 1919 2198 2288 2378 2468 2558 2648 2738 2828 2918 3197 3287 3377 3467 3557 3647 3737 3827 3917 4196 4286 4376 4466 )
The five hundredth such number: 494616
The five thousandth such number: 56546545
</pre>
Line 405 ⟶ 778:
</pre>
=={{header|Haskell}}==
<syntaxhighlight lang="Haskell">import Data.Char ( digitToInt )
import Data.List ( unfoldr , (!!) )
findLimits :: (Int , Int) -> [(Int , Int)]
findLimits (st , end ) = unfoldr(\(x , y ) -> if x > y then Nothing else
Just ((x , y ) , (x + 1 , y - 1 ))) (st , end )
isUpsideDown :: Int -> Bool
isUpsideDown n
|elem '0' str = False
|otherwise = all (\(a , b ) -> digitToInt( str !! a ) + digitToInt ( str !!
b ) == 10 ) $ findLimits ( 0 , length str - 1 )
where
str = show n
main :: IO ( )
main = do
let upsideDowns = take 5000 $ filter isUpsideDown [1..]
putStrLn "The first fifty upside-down numbers!"
print $ take 50 upsideDowns
putStr "The five hundredth such number : "
print $ upsideDowns !! 499
putStr "The five thousandth such number : "
print $ last upsideDowns</syntaxhighlight>
{{out}}
<pre>
The first fifty upside-down numbers!
[5,19,28,37,46,55,64,73,82,91,159,258,357,456,555,654,753,852,951,1199,1289,1379,1469,1559,1649,1739,1829,1919,2198,2288,2378,2468,2558,2648,2738,2828,2918,3197,3287,3377,3467,3557,3647,3737,3827,3917,4196,4286,4376,4466]
The five hundredth such number : 494616
The five thousandth such number : 56546545
</pre>
=={{header|jq}}==
Line 1,078 ⟶ 1,483:
=={{header|Quackery}}==
(Load extensions for the faster merge sort.)
'''Method'''
Start with generation zero as the empty string and "5". Make the next generation by expanding the previous generation (<code>expand</code>) i.e. wrapping each of the strings in "1" and "9", "2" and "8" … "8" and "2", "9" and "1". Accumulate the generations. The accumulator starts with "5", after one iteration it has "5", "19", "28" … "82", "91", "159", "258" … "852", "951".
Note that this does not produce the numbers in numerical order. It's close to numerical order but not quite there.
So once sufficient numbers have been produced to guarantee that all the numbers in the required range have been calculated, convert them from string format to numerical format and sort, then truncate the list of upside down numbers to the required length.
<code>necessary</code> computes a safe number of items to include in the list to guarantee that none are missing from the truncated list - i.e. the length of the list after each iteration of <code>expand</code>. It is <code>(9^n - 5) / 4</code>, where <code>n</code> is the number of iterations. ([https://oeis.org/A211866 OEIS A211866])
<code>^</code> in <code>necessary</code> is bitwise XOR, not exponentiation.
<syntaxhighlight lang="Quackery"> [ 0
Line 1,281 ⟶ 1,699:
5000000th : 82485246852682
</pre>
=={{header|Rust}}==
<syntaxhighlight lang="Rust">fn is_upside_down( num : u32 ) -> bool {
let numberstring : String = num.to_string( ) ;
let len = numberstring.len( ) ;
let numberstr = numberstring.as_str( ) ;
if numberstr.contains( "0" ) {
return false ;
}
if len % 2 == 1 && numberstr.chars( ).nth( len / 2 ).unwrap( ) != '5' {
return false ;
}
let mut forward : usize = 0 ;
let mut backward : usize = len - 1 ;
while forward <= backward {
let first = numberstr.chars( ).nth( forward ).expect("No digit!").
to_digit( 10 ).unwrap( ) ;
let second = numberstr.chars( ).nth( backward ).expect("No digit!").
to_digit( 10 ).unwrap( ) ;
if first + second != 10 {
return false ;
}
forward += 1 ;
if backward != 0 {
backward -= 1 ;
}
}
true
}
fn main() {
let mut solution : Vec<u32> = Vec::new( ) ;
let mut sum : u32 = 0 ;
let mut current : u32 = 0 ;
while sum < 50 {
current += 1 ;
if is_upside_down( current ) {
solution.push( current ) ;
sum += 1 ;
}
}
let five_hundr : u32 ;
while sum != 500 {
current += 1 ;
if is_upside_down( current ) {
sum += 1 ;
}
}
five_hundr = current ;
let five_thous : u32 ;
while sum != 5000 {
current += 1 ;
if is_upside_down( current ) {
sum += 1 ;
}
}
five_thous = current ;
println!("The first 50 upside-down numbers:") ;
println!("{:?}" , solution ) ;
println!("The five hundredth such number : {}" , five_hundr) ;
println!("The five thousandth such number : {}" , five_thous ) ;
}</syntaxhighlight>
{{out}}
<pre>
The first 50 upside-down numbers:
[5, 19, 28, 37, 46, 55, 64, 73, 82, 91, 159, 258, 357, 456, 555, 654, 753, 852, 951, 1199, 1289, 1379, 1469, 1559, 1649, 1739, 1829, 1919, 2198, 2288, 2378, 2468, 2558, 2648, 2738, 2828, 2918, 3197, 3287, 3377, 3467, 3557, 3647, 3737, 3827, 3917, 4196, 4286, 4376, 4466]
The five hundredth such number : 494616
The five thousandth such number : 56546545
</pre>
=={{header|Wren}}==
{{trans|Python}}
{{libheader|Wren-fmt}}
<syntaxhighlight lang="
var genUpsideDown = Fiber.new {
| |||