How to resolve the algorithm Colorful numbers step by step in the jq programming language

Published on 12 May 2024 09:40 PM
#Jq

How to resolve the algorithm Colorful numbers step by step in the jq programming language

Table of Contents

Problem Statement

A colorful number is a non-negative base 10 integer where the product of every sub group of consecutive digits is unique.

24753 is a colorful number. 2, 4, 7, 5, 3, (2×4)8, (4×7)28, (7×5)35, (5×3)15, (2×4×7)56, (4×7×5)140, (7×5×3)105, (2×4×7×5)280, (4×7×5×3)420, (2×4×7×5×3)840 Every product is unique.

2346 is not a colorful number. 2, 3, 4, 6, (2×3)6, (3×4)12, (4×6)24, (2×3×4)48, (3×4×6)72, (2×3×4×6)144 The product 6 is repeated.

Single digit numbers are considered to be colorful. A colorful number larger than 9 cannot contain a repeated digit, the digit 0 or the digit 1. As a consequence, there is a firm upper limit for colorful numbers; no colorful number can have more than 8 digits.

Colorful numbers have no real number theory application. They are more a recreational math puzzle than a useful tool.

Let's start with the solution:

Step by Step solution about How to resolve the algorithm Colorful numbers step by step in the jq programming language

Source code in the jq programming language

# Uncomment for gojq
# def _nwise($n):
#   def n: if length <= $n then . else .[0:$n] , (.[$n:] | n) end;
#   n;

def lpad($len): tostring | ($len - length) as $l | (" " * $l)[:$l] + .;

# Generate a stream of the permutations of the input array.
def permutations:
  if length == 0 then []
  else
    range(0;length) as $i
    | [.[$i]] + (del(.[$i])|permutations) 
  end ;

def isColorful:
  def digits: [tostring | explode[] | [.] | implode | tonumber];

  if . < 0 then false
  elif . < 10 then true
  else . as $n
  | digits as $digits
  | if any($digits[]; . == 0 or . == 1) then false
    else ($digits|unique) as $set
    | ($digits|length) as $dc
    | if ($set|length) < $dc then false
      else label $out
      | foreach range(2; $dc) as $k ({$set}; 
          foreach range(0; $dc-$k+1) as $i (.;
            (reduce range($i; $i+$k) as $j (1; . *  $digits[$j])) as $prod
            | if .set|index($prod) then .return = 0, break $out   
              else .set += [$prod]
	      end ;
	    . );
	  select(.return) ) // null
      | if .return == 0 then false else true end
      end
    end
  end;

# Emit a stream of colorfuls in range(a;b)
def colorfuls(a;b):
  range(a;b) | select(isColorful);

def task($n):
  [colorfuls(0; $n)]
  | "The \(length) colorful numbers less than \($n) are:",
    (_nwise($10) | map(lpad(4)) | join(" ")) ;

def largestColorful:
  [[range(2;10)] | permutations | join("") | tonumber | select(isColorful)] | max;

# Emit a JSON object giving the counts by number of digits
def classifyColorful:
  def nonTrivialCandidates:
    [range(2; 10)]
    | range(1; 9) as $length
    | combinations($length) 
    | join("")
    | tonumber;
  reduce (0,1,nonTrivialCandidates) as $i ({};
     if $i|isColorful
     then .[$i|tostring|length|tostring] += 1
     else .
     end);
     
task(100),
"",
"The largest possible colorful number is \(largestColorful)."
"",
"The counts of colorful numbers by number of digits are:",
(classifyColorful
 | (., "\nTotal: \([.[]]|add)"))

  

You may also check:How to resolve the algorithm Sorting algorithms/Bogosort step by step in the VBA programming language
You may also check:How to resolve the algorithm Cistercian numerals step by step in the AWK programming language
You may also check:How to resolve the algorithm Kolakoski sequence step by step in the Haskell programming language
You may also check:How to resolve the algorithm Day of the week step by step in the AWK programming language
You may also check:How to resolve the algorithm Floyd's triangle step by step in the Python programming language