Colorful numbers: Difference between revisions
Added Easylang
(Created Nim solution.) |
(Added Easylang) |
||
| (8 intermediate revisions by 5 users not shown) | |||
Line 515:
Elapsed time: 0.031256 seconds</pre>
=={{header|C++}}==
<syntaxhighlight lang="c++">
#include <cstdint>
#include <iomanip>
#include <iostream>
#include <vector>
std::vector<uint32_t> count(8, 0);
std::vector<bool> used(10, false);
uint32_t largest = 0;
bool is_colorful(const uint32_t& number) {
if ( number > 98'765'432 ) {
return false;
}
std::vector<uint32_t> digit_count(10, 0);
std::vector<uint32_t> digits(8, 0);
uint32_t number_digits = 0;
for ( uint32_t i = number; i > 0; i /= 10 ) {
uint32_t digit = i % 10;
if ( number > 9 && ( digit == 0 || digit == 1 ) ) {
return false;
}
if ( ++digit_count[digit] > 1 ) {
return false;
}
digits[number_digits++] = digit;
}
std::vector<uint32_t> products(36, 0);
for ( uint32_t i = 0, product_count = 0; i < number_digits; ++i ) {
for ( uint32_t j = i, product = 1; j < number_digits; ++j ) {
product *= digits[j];
for ( uint32_t k = 0; k < product_count; ++k ) {
if ( products[k] == product ) {
return false;
}
}
products[product_count++] = product;
}
}
return true;
}
void count_colorful(const uint32_t& taken, const uint32_t& number, const uint32_t& digits) {
if ( taken == 0 ) {
for ( uint32_t digit = 0; digit < 10; ++digit ) {
used[digit] = true;
count_colorful(digit < 2 ? 9 : 1, digit, 1);
used[digit] = false;
}
} else {
if ( is_colorful(number) ) {
++count[digits - 1];
if ( number > largest ) {
largest = number;
}
}
if ( taken < 9 ) {
for ( uint32_t digit = 2; digit < 10; ++digit ) {
if ( ! used[digit] ) {
used[digit] = true;
count_colorful(taken + 1, number * 10 + digit, digits + 1);
used[digit] = false;
}
}
}
}
}
int main() {
std::cout << "Colorful numbers less than 100:" << std::endl;
for ( uint32_t number = 0, count = 0; number < 100; ++number ) {
if ( is_colorful(number) ) {
std::cout << std::setw(2) << number << ( ++count % 10 == 0 ? "\n" : " ");
}
}
std::cout << "\n" << std::endl;
count_colorful(0, 0, 0);
std::cout << "Count of colorful numbers by number of digits:" << std::endl;
uint32_t total = 0;
for ( uint32_t digit = 0; digit < 8; ++digit ) {
std::cout << digit + 1 << ": " << count[digit] << std::endl;
total += count[digit];
}
std::cout << std::endl;
std::cout << "The largest possible colorful number is: " << largest << "\n" << std::endl;
std::cout << "The total number of colorful numbers is: " << total << std::endl;
}
</syntaxhighlight>
{{ out }}
<pre>
Colorful numbers less than 100:
0 1 2 3 4 5 6 7 8 9
23 24 25 26 27 28 29 32 34 35
36 37 38 39 42 43 45 46 47 48
49 52 53 54 56 57 58 59 62 63
64 65 67 68 69 72 73 74 75 76
78 79 82 83 84 85 86 87 89 92
93 94 95 96 97 98
Count of colorful numbers by number of digits:
1: 10
2: 56
3: 328
4: 1540
5: 5514
6: 13956
7: 21596
8: 14256
The largest possible colorful number is: 98746253
The total number of colorful numbers is: 57256
</pre>
=={{header|Delphi}}==
{{works with|Delphi|6.0}}
{{libheader|SysUtils,StdCtrls}}
<syntaxhighlight lang="Delphi">
procedure ShowColorfulNumbers(Memo: TMemo);
var I,P,Cnt,OldCnt,Start,Stop: integer;
var S: string;
var Largest: integer;
function IsColorful(N: integer): boolean;
var IA: TIntegerDynArray;
var PList: TList;
var I,J,D,P: integer;
begin
PList:=TList.Create;
try
Result:=False;
GetDigits(N,IA);
{Number of digits at a time}
for D:=1 to Length(IA) do
{For all digits in number}
for I:=High(IA) downto D-1 do
begin
P:=1;
{Product of digits in a group}
for J:=0 to D-1 do P:=P * IA[I-J];
{Has it already been used}
if PList.IndexOf(Pointer(P))>=0 then exit;
{Store in list}
PList.Add(Pointer(P));
end;
Result:=True;
finally PList.Free; end;
end;
begin
Cnt:=0; S:='';
Memo.Line.Add('Colorful Number less than 100');
for I:=0 to 100-1 do
if IsColorful(I) then
begin
Inc(Cnt);
S:=S+Format('%7D',[I]);
If (Cnt mod 5)=0 then S:=S+CRLF;
end;
Memo.Lines.Add(S);
Memo.Lines.Add('Count = '+IntToStr(Cnt));
for Largest:=98765432 downto 1 do
if IsColorful(Largest) then break;
Memo.Lines.Add('Largest Colorful Number = '+IntToStr(Largest));
Start:=0; Stop:=9;
Cnt:=0; OldCnt:=0;
for P:=1 to 8 do
begin
for I:=Start to Stop do
if IsColorful(I) then Inc(Cnt);
Memo.Lines.Add(Format('Colorful Numbers from %10.0n to %10.0n: %5D', [Start+0.0,Stop+0.0,Cnt-OldCnt]));
Start:=Stop+1;
Stop:=(Start*10)-1;
OldCnt:=Cnt;
end;
for I:=Stop+1 to Largest do
if IsColorful(I) then Inc(Cnt);
Memo.Lines.Add('Total All Colorful = '+IntToStr(Cnt));
end;
</syntaxhighlight>
{{out}}
<pre>
Colorful Numbers less than 100
0 1 2 3 4
5 6 7 8 9
23 24 25 26 27
28 29 32 34 35
36 37 38 39 42
43 45 46 47 48
49 52 53 54 56
57 58 59 62 63
64 65 67 68 69
72 73 74 75 76
78 79 82 83 84
85 86 87 89 92
93 94 95 96 97
98
Count = 66
Largest Colorful Number = 98746253
Colorful Numbers from 0 to 9: 10
Colorful Numbers from 10 to 99: 56
Colorful Numbers from 100 to 999: 328
Colorful Numbers from 1,000 to 9,999: 1540
Colorful Numbers from 10,000 to 99,999: 5514
Colorful Numbers from 100,000 to 999,999: 13956
Colorful Numbers from 1,000,000 to 9,999,999: 21596
Colorful Numbers from 10,000,000 to 99,999,999: 14256
Total All Colorful = 57256
Elapsed Time: 01:36.252 min
</pre>
=={{header|EasyLang}}==
{{trans|C}}
<syntaxhighlight>
func colorful n .
len digcnt[] 10
arrbase digcnt[] 0
len digits[] 8
m = n
while m > 0
d = m mod 10
if n > 9 and d <= 1
return 0
.
digcnt[d] += 1
if digcnt[d] > 1
return 0
.
ndigs += 1
digits[ndigs] = d
m = m div 10
.
len products[] 36
for i to ndigs
p = 1
for j = i to ndigs
p *= digits[j]
for k to prodcnt
if products[k] = p
return 0
.
.
prodcnt += 1
products[prodcnt] = p
.
.
return 1
.
len cnt[] 8
len used[] 10
arrbase used[] 0
largest = 0
proc cnt_colorful taken n digits . .
if taken = 0
for d = 0 to 9
used[d] = 1
h = 1
if d < 2
h = 9
.
cnt_colorful h d 1
used[d] = 0
.
return
.
if colorful n = 1
cnt[digits] += 1
largest = higher largest n
.
if taken < 9
for d = 2 to 9
if used[d] = 0
used[d] = 1
cnt_colorful (taken + 1) (n * 10 + d) (digits + 1)
used[d] = 0
.
.
.
.
print "Colorful numbers less than 100:"
for n = 0 to 99
if colorful n = 1
write n & " "
.
.
cnt_colorful 0 0 0
print "\n\nLargest colorful number:" & largest
#
print "\nCount of colorful numbers by number of digits:\n"
for d to 8
print d & " " & cnt[d]
total += cnt[d]
.
print "\nTotal: " & total
</syntaxhighlight>
{{out}}
<pre>
Colorful numbers less than 100:
0 1 2 3 4 5 6 7 8 9 23 24 25 26 27 28 29 32 34 35 36 37 38 39 42 43 45 46 47 48 49 52 53 54 56 57 58 59 62 63 64 65 67 68 69 72 73 74 75 76 78 79 82 83 84 85 86 87 89 92 93 94 95 96 97 98
Largest colorful number:98746253
Count of colorful numbers by number of digits:
1 10
2 56
3 328
4 1540
5 5514
6 13956
7 21596
8 14256
Total: 57256
</pre>
=={{header|Factor}}==
Line 1,834 ⟶ 2,168:
Total colorful numbers: 57256</pre>
=={{header|RPL}}==
We have assumed that the largest colored number has 8 digits. This means we only need to check the permutations of 98765432. Brute force is here used, generating these permutations - and many other numbers - through decrementation by 9. Before testing the colorfulness, the sum of the digits of the generated number is compared to that of 98765432. This improves execution time a little bit.
If the search had been unsuccessful, we would have tested the different possibilities of 7-digit pandigital numbers - but luckily it was not necessary.
{{works with|HP|48G}}
{| class="wikitable" ≪
! RPL code
! Comment
|-
|
≪ →STR DUP SIZE → num dig
≪ '''CASE'''
dig 1 == '''THEN''' 1 '''END'''
num "0" POS num "1" POS OR '''THEN''' 0 '''END'''
1 SF
{ } 1 dig '''FOR''' j num j DUP SUB STR→ + '''NEXT'''
DUP SORT ΔLIST 1 + ΠLIST NOT '''THEN''' DROP 0 '''END'''
DUP
1 dig 1 - '''FOR''' k
1 dig k - '''FOR''' c
OVER c DUP k + SUB ΠLIST
'''IF''' DUP2 POS
'''THEN''' DROP 1 CF dig DUP 'c' STO 'k' STO
'''ELSE''' + '''END'''
'''NEXT NEXT'''
DROP2 1 FS? '''END'''
≫ ≫ '<span style="color:blue">COLOR?</span>' STO
|
<span style="color:blue">COLOR?</span> ( num → boolean )
if num has only 1 digit then return true
if num contains 0 or 1 then return false
color = true
convert n into a list of digits
if 2 digits are identical then return false
list of products = list of digits
for k = 1 to ndig-1
for c = 1 to ndig-k
p = digit[c]*..*digit[c+k]
if p in list of products
then color = false, exit loops
else append p to list of products
end loops
clean stack, return color
|}
≪ →STR 0
1 3 PICK SIZE '''FOR''' j
OVER j DUP SUB NUM +
'''NEXT''' SWAP DROP
≫ '<span style="color:blue">DSTAMP</span>' STO
≪ { }
1 100 '''FOR''' j IF j <span style="color:blue">COLOR?</span> '''THEN''' + '''END NEXT'''
98765432 DUP <span style="color:blue">DSTAMP</span> SWAP
'''WHILE''' DUP <span style="color:blue">COLOR?</span> NOT '''REPEAT'''
'''DO''' 9 - '''UNTIL''' DUP2 <span style="color:blue">DSTAMP</span> == '''END'''
'''END''' SWAP DROP
≫ '<span style="color:blue">TASK</span>' STO
{{out}}
<pre>
2: { 1 2 3 4 5 6 7 8 9 23 24 25 26 27 28 29 32 34 35 36 37 38 39 42 43 45 46 47 48 49 52 53 54 56 57 58 59 62 63 64 65 67 68 69 72 73 74 75 76 78 79 82 83 84 85 86 87 89 92 93 94 95 96 97 98 }
1: 98746253
</pre>
Largest colorful number found in 10 minutes 22 seconds on a HP-48G.
=={{header|Ruby}}==
Line 1,879 ⟶ 2,280:
Total colorful numbers: 57256
</pre>
=={{header|Rust}}==
<syntaxhighlight lang="rust">use core::cmp::max;
use std::collections::HashSet;
fn to_digits(mut n: u64, base: u64) -> Vec<u64> {
if n == 0 {
return [0].to_vec();
}
let mut v: Vec<u64> = Vec::new();
while n > 0 {
let d = n % base;
n /= base;
v.push(d);
}
return v;
}
fn is_colorful(n: u64) -> bool {
if &n > &9 {
let dig: Vec<u64> = to_digits(n, 10);
if dig.contains(&1) || dig.contains(&0) {
return false;
}
let mut products: HashSet<u64> = HashSet::new();
for i in 0..dig.len() {
if products.contains(&dig[i]) {
return false;
}
products.insert(dig[i]);
}
for i in 0..dig.len() {
for j in i+2..dig.len()+1 {
let p: u64 = (dig[i..j]).iter().product();
if products.contains(&p) {
return false;
}
products.insert(p);
}
}
}
return true;
}
fn main() {
println!("Colorful numbers for 1:25, 26:50, 51:75, and 76:100:");
for i in (1..101).step_by(25) {
for j in 0..25 {
if is_colorful(i + j) {
print!("{:5}", i + j);
}
}
println!();
}
println!();
let mut csum: u64 = 0;
let mut largest: u64 = 0;
let mut n: u64;
for i in 0..8 {
let j: u64 = { if i == 0 { 0 } else { 10_u64.pow(i) } };
let k: u64 = 10_u64.pow(i + 1) - 1;
n = 0;
for x in j..k+1 {
if is_colorful(x) {
largest = max(largest, x);
n += 1;
}
}
println!("The count of colorful numbers within the interval [{j}, {k}] is {n}.");
csum += n;
}
println!("The largest possible colorful number is {largest}.");
println!("The total number of colorful numbers is {csum}.")
}
</syntaxhighlight>{{out}}
<pre>
Colorful numbers for 1:25, 26:50, 51:75, and 76:100:
1 2 3 4 5 6 7 8 9 23 24 25
26 27 28 29 32 34 35 36 37 38 39 42 43 45 46 47 48 49
52 53 54 56 57 58 59 62 63 64 65 67 68 69 72 73 74 75
76 78 79 82 83 84 85 86 87 89 92 93 94 95 96 97 98
The count of colorful numbers within the interval [0, 9] is 10.
The count of colorful numbers within the interval [10, 99] is 56.
The count of colorful numbers within the interval [100, 999] is 328.
The count of colorful numbers within the interval [1000, 9999] is 1540.
The count of colorful numbers within the interval [10000, 99999] is 5514.
The count of colorful numbers within the interval [100000, 999999] is 13956.
The count of colorful numbers within the interval [1000000, 9999999] is 21596.
The largest possible colorful number is 98746253.
The total number of colorful numbers is 57256.
</pre>
Line 1,885 ⟶ 2,379:
{{libheader|Wren-math}}
{{libheader|Wren-set}}
{{libheader|Wren-fmt}}
<syntaxhighlight lang="
import "./set" for Set
import "./fmt" for Fmt
Line 1,946 ⟶ 2,438:
var cn = (0..99).where { |i| isColorful.call(i) }.toList
System.print("The %(cn.count) colorful numbers less than 100 are:")
countColorful.call(0, "")
| |||