diff options
| author | Mohammad S Anwar <Mohammad.Anwar@yahoo.com> | 2021-03-03 12:24:48 +0000 |
|---|---|---|
| committer | GitHub <noreply@github.com> | 2021-03-03 12:24:48 +0000 |
| commit | 75de64a05d71b7f92b960579bf02a3d79d50f9b1 (patch) | |
| tree | 562215d4813dd37e53bbc4844599f2928e9aa55e | |
| parent | 86807642d4729d239f6b0e4d3d61787685dc4668 (diff) | |
| parent | 26ae49523623bfe48ad8ccfa78efbea4d1378133 (diff) | |
| download | perlweeklychallenge-club-75de64a05d71b7f92b960579bf02a3d79d50f9b1.tar.gz perlweeklychallenge-club-75de64a05d71b7f92b960579bf02a3d79d50f9b1.tar.bz2 perlweeklychallenge-club-75de64a05d71b7f92b960579bf02a3d79d50f9b1.zip | |
Merge pull request #3650 from Abigail/abigail/week-102
Abigail/week 102
36 files changed, 1906 insertions, 78 deletions
diff --git a/challenge-102/abigail/README.md b/challenge-102/abigail/README.md index caf1448381..687594c5f5 100644 --- a/challenge-102/abigail/README.md +++ b/challenge-102/abigail/README.md @@ -1,65 +1,52 @@ # Solution by Abigail -## [Pack a Spiral](https://perlweeklychallenge.org/blog/perl-weekly-challenge-101/#TASK1) +## [Rare Numbers](https://perlweeklychallenge.org/blog/perl-weekly-challenge-102/#TASK1) -You are given an array `@A` of items (integers say, but they can be anything). -Your task is to pack that array into an `MxN` matrix spirally -counterclockwise, as tightly as possible. +You are given a positive integer `$N`. -'Tightly' means the absolute value `|M-N|` of the difference has to be as -small as possible +Write a script to generate all Rare numbers of size `$N` if exists. +Please checkout [the page](http://www.shyamsundergupta.com/rare.htm) +for more information about it. ### Examples -#### Example 1 ~~~~ -Input: @A = (1,2,3,4) - -Output: - - 4 3 - 1 2 +(a) 2 digits: 65 +(b) 6 digits: 621770 +(c) 9 digits: 281089082 ~~~~ -Since the given array is already a `1x4` matrix on its own, but that's -not as tight as possible. Instead, you'd spiral it counterclockwise into +### Notes -~~~~ - 4 3 - 1 2 -~~~~ -#### Example 2 -~~~~ -Input: @A = (1..6) +There is no simple efficient algorithm for spitting out rare numbers; +at least not one which can be easily found online. -Output: +The code fragments in the OEIS only give code to check whether a +number is a rare number, and they don't suggest anything other +than "try all numbers" if you want to find all of the numbers of a +certain length. - 6 5 4 - 1 2 3 -~~~~ -or -~~~~ - 5 4 - 6 3 - 1 2 -~~~~ -Either will do as an answer, because they're equally tight. +Shyam writes: [*I have developed a computer program in Fortran to +calculate Rare numbers. In fact with refinement of the code over +the years, the program has been made so powerful that all numbers +up to 10^14 can be just checked for Rare numbers in less than a +minute on Pentium III PC. In few hours I have been able to check +up to 10^18.*](https://www.primepuzzles.net/conjectures/conj_023.htm) +but he does not publish his code. -#### Example 3 -~~~~ -Input: @A = (1..12) +Richard Guy writes [*Here are three problems that have come to light +recently, each of which can consume unlimited amounts of computer time, +perhaps without revealing anything +significant*.](https://www.jstor.org/stable/2325149?seq=1) +The rare numbers are one of the three problems. + +So, we just include a [list of all know rare numbers, +up to 10^22](https://oeis.org/A035519/b035519.txt) +and preprocess them so they're bucketed to length. Then it's just +a matter of reading the desired length, and printing the appropriate +entry (or the empty string if no rare numbers of that length exist). +There are only 124 known rare numbers, so preprocessing is very +feasible. -Output: - 9 8 7 6 - 10 11 12 5 - 1 2 3 4 -~~~~ -or -~~~~ - 8 7 6 - 9 12 5 - 10 11 4 - 1 2 3 -~~~~ ### Solutions * [AWK](awk/ch-1.awk) @@ -71,52 +58,38 @@ or * [Python](python/ch-1.py) * [Ruby](ruby/ch-1.rb) -### Blog -[Perl Weekly Challenge 101: Pack a Spiral](https://wp.me/pcxd30-r7) +## [Hash-counting String](https://perlweeklychallenge.org/blog/perl-weekly-challenge-102/#TASK2) -## [Origin-containing Triangle](https://perlweeklychallenge.org/blog/perl-weekly-challenge-101/#TASK2) +You are given a positive integer `$N`. -You are given three points in the plane, as a list of six co-ordinates: -`A=(x1,y1)`, `B=(x2,y2)` and `C=(x3,y3)`. +Write a script to produce Hash-counting string of that length. -Write a script to find out if the triangle formed by the given three -co-ordinates contain origin `(0,0)`. +The definition of a hash-counting string is as follows: +- the string consists only of digits 0-9 and hashes, `'#'`. +- there are no two consecutive hashes: `"##"z does not appear in your string +- the last character is a hash +- the number immediately preceding each hash (if it exists) is the position + of that hash in the string, with the position being counted up from 1 -Print `1` if found otherwise `0`. +It can be shown that for every positive integer `N` there is exactly one +such length-`N` string. ### Examples -#### Example 1 -~~~~ -Input: A=(0,1), B=(1,0) and C=(2,2) - -Output: 0 because that triangle does not contain (0,0). ~~~~ - -#### Example 2 -~~~~ -Input: A=(1,1), B=(-1,1) and C=(0,-3) - -Output: 1 because that triangle contains (0,0) in its interior. -~~~~ - -#### Example 3 -~~~~ -Input: A=(0,1), B=(2,0) and C=(-6,0) - -Output: 1 because (0,0) is on the edge connecting B and C. +(a) "#" is the counting string of length 1 +(b) "2#" is the counting string of length 2 +(c) "#3#" is the string of length 3 +(d) "#3#5#7#10#" is the string of length 10 +(e) "2#4#6#8#11#14#" is the string of length 14 ~~~~ ### Solutions * [AWK](awk/ch-2.awk) * [Bash](bash/ch-2.sh) -* [Befunge-93](befunge-93/ch-2.bf93) * [C](c/ch-2.c) * [Lua](lua/ch-2.lua) * [Node.js](node/ch-2.js) * [Perl](perl/ch-2.pl) * [Python](python/ch-2.py) * [Ruby](ruby/ch-2.rb) - -### Blog -[Perl Weekly Challenge 101: Origin-containing Triangle](https://wp.me/pcxd30-s8) diff --git a/challenge-102/abigail/awk/ch-1.awk b/challenge-102/abigail/awk/ch-1.awk new file mode 100644 index 0000000000..ccfb3cd023 --- /dev/null +++ b/challenge-102/abigail/awk/ch-1.awk @@ -0,0 +1,151 @@ +#!/usr/bin/awk + +# +# See ../README.md +# + +# +# Run as: awk -f ch-1.awk < input-file +# + +# +# Load the list of all known rare numbers. Note that we're using +# strings instead of numbers, since the largest number exceed +# the largest integer AWK stores losslessly. +# +BEGIN { + rare_numbers [ 2] = "65\n" + rare_numbers [ 6] = "621770\n" + rare_numbers [ 9] = "281089082\n" + rare_numbers [10] = "2022652202\n" \ + "2042832002\n" + rare_numbers [12] = "868591084757\n" \ + "872546974178\n" \ + "872568754178\n" + rare_numbers [13] = "6979302951885\n" + rare_numbers [14] = "20313693904202\n" \ + "20313839704202\n" \ + "20331657922202\n" \ + "20331875722202\n" \ + "20333875702202\n" \ + "40313893704200\n" \ + "40351893720200\n" + rare_numbers [15] = "200142385731002\n" \ + "204238494066002\n" \ + "221462345754122\n" \ + "244062891224042\n" \ + "245518996076442\n" \ + "248359494187442\n" \ + "403058392434500\n" \ + "441054594034340\n" \ + "816984566129618\n" + rare_numbers [16] = "2078311262161202\n" \ + "2133786945766212\n" \ + "2135568943984212\n" \ + "2135764587964212\n" \ + "2135786765764212\n" \ + "4135786945764210\n" \ + "6157577986646405\n" \ + "6889765708183410\n" \ + "8052956026592517\n" \ + "8052956206592517\n" \ + "8191154686620818\n" \ + "8191156864620818\n" \ + "8191376864400818\n" \ + "8650327689541457\n" \ + "8650349867341457\n" + rare_numbers [17] = "22542040692914522\n" \ + "67725910561765640\n" \ + "86965750494756968\n" + rare_numbers [18] = "225342456863243522\n" \ + "225342458663243522\n" \ + "225342478643243522\n" \ + "284684666566486482\n" \ + "284684868364486482\n" \ + "297128548234950692\n" \ + "297128722852950692\n" \ + "297148324656930692\n" \ + "297148546434930692\n" \ + "497168548234910690\n" \ + "619431353040136925\n" \ + "619631153042134925\n" \ + "631688638047992345\n" \ + "633288858025996145\n" \ + "633488632647994145\n" \ + "653488856225994125\n" \ + "811865096390477018\n" \ + "865721270017296468\n" \ + "871975098681469178\n" \ + "898907259301737498\n" + rare_numbers [19] = "2042401829204402402\n" \ + "2060303819041450202\n" \ + "2420424089100600242\n" \ + "2551755006254571552\n" \ + "2702373360882732072\n" \ + "2825378427312735282\n" \ + "6531727101458000045\n" \ + "6988066446726832640\n" \ + "8066308349502036608\n" \ + "8197906905009010818\n" \ + "8200756128308135597\n" \ + "8320411466598809138\n" + rare_numbers [20] = "22134434735752443122\n" \ + "22134434753752443122\n" \ + "22134436953532443122\n" \ + "22136414517954423122\n" \ + "22136414971554423122\n" \ + "22136456771730423122\n" \ + "61952807156239928885\n" \ + "61999171315484316965\n" \ + "65459144877856561700\n" + rare_numbers [21] = "208393425242000083802\n" \ + "219518549668074815912\n" \ + "257661195832219326752\n" \ + "286694688797362186682\n" \ + "837982875780054779738\n" + rare_numbers [22] = "2414924301133245383042\n" \ + "2414924323311045383042\n" \ + "2414946523311023183042\n" \ + "2576494891793995836752\n" \ + "2576494893971995836752\n" \ + "2620937863931054483162\n" \ + "2620937863931054483162\n" \ + "2620955641393276283162\n" \ + "2622935621573476481162\n" \ + "2622935643751276481162\n" \ + "2622937641933274481162\n" \ + "2622955841933256281162\n" \ + "2622957843751254281162\n" \ + "2727651947516658327272\n" \ + "2747736918335953517072\n" \ + "2788047668617596408872\n" \ + "2788047848617776408872\n" \ + "2788047868437576408872\n" \ + "2788047888617376408872\n" \ + "2939501759705522349392\n" \ + "2939503375709360349392\n" \ + "2939503537707740349392\n" \ + "2939521359525562149392\n" \ + "2939521557527542149392\n" \ + "2939523577527340149392\n" \ + "2939523779525320149392\n" \ + "2959503377707360349192\n" \ + "6344828989519887483525\n" \ + "8045841652464561594308\n" \ + "8045841654642561594308\n" \ + "8655059576513659814468\n" \ + "8655059772157639814468\n" \ + "8655079374155679614468\n" \ + "8655079574515659614468\n" \ + "8888070771864228883913\n" +} + + +# +# Print the numbers of the appropriate length. +# +{ + if ($1 in rare_numbers) { + printf "%s", rare_numbers [$1] + } +} diff --git a/challenge-102/abigail/awk/ch-2.awk b/challenge-102/abigail/awk/ch-2.awk new file mode 100644 index 0000000000..e673437860 --- /dev/null +++ b/challenge-102/abigail/awk/ch-2.awk @@ -0,0 +1,36 @@ +#!/usr/bin/awk + +# +# See ../README.md +# + +# +# Run as: awk -f ch-2.awk < input-file +# + +# +# Working from the end of the required string backwards, we alternate +# placing a hash, and placing a number. We place them in an array out, +# and at the end, print out said array in reverse order. +# + +{ + idx = $1 + hash = 0 + i = 0 + while (idx) { + i ++ + if (hash = !hash) { + out [i] = "#" + idx -- + } + else { + out [i] = idx + 1 + idx -= length (idx + 1) + } + } + for (; i; i --) { + printf "%s", out [i] + } + printf "\n" +} diff --git a/challenge-102/abigail/bash/ch-1.sh b/challenge-102/abigail/bash/ch-1.sh new file mode 100644 index 0000000000..874ae78998 --- /dev/null +++ b/challenge-102/abigail/bash/ch-1.sh @@ -0,0 +1,146 @@ +#!/bin/sh + +# +# See ../README.md +# + +# +# Run as: bash ch-1.sh < input-file +# + +# +# Put the known rare numbers into an array +# +declare -a rare_numbers + +rare_numbers[ 2]="65\n" +rare_numbers[ 6]="621770\n" +rare_numbers[ 9]="281089082\n" +rare_numbers[10]="2022652202\n"\ +"2042832002\n" +rare_numbers[12]="868591084757\n"\ +"872546974178\n"\ +"872568754178\n" +rare_numbers[13]="6979302951885\n" +rare_numbers[14]="20313693904202\n"\ +"20313839704202\n"\ +"20331657922202\n"\ +"20331875722202\n"\ +"20333875702202\n"\ +"40313893704200\n"\ +"40351893720200\n" +rare_numbers[15]="200142385731002\n"\ +"204238494066002\n"\ +"221462345754122\n"\ +"244062891224042\n"\ +"245518996076442\n"\ +"248359494187442\n"\ +"403058392434500\n"\ +"441054594034340\n"\ +"816984566129618\n" +rare_numbers[16]="2078311262161202\n"\ +"2133786945766212\n"\ +"2135568943984212\n"\ +"2135764587964212\n"\ +"2135786765764212\n"\ +"4135786945764210\n"\ +"6157577986646405\n"\ +"6889765708183410\n"\ +"8052956026592517\n"\ +"8052956206592517\n"\ +"8191154686620818\n"\ +"8191156864620818\n"\ +"8191376864400818\n"\ +"8650327689541457\n"\ +"8650349867341457\n" +rare_numbers[17]="22542040692914522\n"\ +"67725910561765640\n"\ +"86965750494756968\n" +rare_numbers[18]="225342456863243522\n"\ +"225342458663243522\n"\ +"225342478643243522\n"\ +"284684666566486482\n"\ +"284684868364486482\n"\ +"297128548234950692\n"\ +"297128722852950692\n"\ +"297148324656930692\n"\ +"297148546434930692\n"\ +"497168548234910690\n"\ +"619431353040136925\n"\ +"619631153042134925\n"\ +"631688638047992345\n"\ +"633288858025996145\n"\ +"633488632647994145\n"\ +"653488856225994125\n"\ +"811865096390477018\n"\ +"865721270017296468\n"\ +"871975098681469178\n"\ +"898907259301737498\n" +rare_numbers[19]="2042401829204402402\n"\ +"2060303819041450202\n"\ +"2420424089100600242\n"\ +"2551755006254571552\n"\ +"2702373360882732072\n"\ +"2825378427312735282\n"\ +"6531727101458000045\n"\ +"6988066446726832640\n"\ +"8066308349502036608\n"\ +"8197906905009010818\n"\ +"8200756128308135597\n"\ +"8320411466598809138\n" +rare_numbers[20]="22134434735752443122\n"\ +"22134434753752443122\n"\ +"22134436953532443122\n"\ +"22136414517954423122\n"\ +"22136414971554423122\n"\ +"22136456771730423122\n"\ +"61952807156239928885\n"\ +"61999171315484316965\n"\ +"65459144877856561700\n" +rare_numbers[21]="208393425242000083802\n"\ +"219518549668074815912\n"\ +"257661195832219326752\n"\ +"286694688797362186682\n"\ +"837982875780054779738\n" +rare_numbers[22]="2414924301133245383042\n"\ +"2414924323311045383042\n"\ +"2414946523311023183042\n"\ +"2576494891793995836752\n"\ +"2576494893971995836752\n"\ +"2620937863931054483162\n"\ +"2620937863931054483162\n"\ +"2620955641393276283162\n"\ +"2622935621573476481162\n"\ +"2622935643751276481162\n"\ +"2622937641933274481162\n"\ +"2622955841933256281162\n"\ +"2622957843751254281162\n"\ +"2727651947516658327272\n"\ +"2747736918335953517072\n"\ +"2788047668617596408872\n"\ +"2788047848617776408872\n"\ +"2788047868437576408872\n"\ +"2788047888617376408872\n"\ +"2939501759705522349392\n"\ +"2939503375709360349392\n"\ +"2939503537707740349392\n"\ +"2939521359525562149392\n"\ +"2939521557527542149392\n"\ +"2939523577527340149392\n"\ +"2939523779525320149392\n"\ +"2959503377707360349192\n"\ +"6344828989519887483525\n"\ +"8045841652464561594308\n"\ +"8045841654642561594308\n"\ +"8655059576513659814468\n"\ +"8655059772157639814468\n"\ +"8655079374155679614468\n"\ +"8655079574515659614468\n"\ +"8888070771864228883913\n" + +# +# Read a length, and print the rare numbers of that length +# +while read length +do printf "${rare_numbers[$length]}" +done diff --git a/challenge-102/abigail/bash/ch-2.sh b/challenge-102/abigail/bash/ch-2.sh new file mode 100644 index 0000000000..9a9072a56c --- /dev/null +++ b/challenge-102/abigail/bash/ch-2.sh @@ -0,0 +1,37 @@ +#!/bin/sh + +# +# See ../README.md +# + +# +# Run as: bash ch-2.sh < input-file +# + + +# +# Working from the end of the required string backwards, we alternate +# placing a hash, and placing a number. We place them in an array out, +# and at the end, print out said array in reverse order. +# + +while read index +do declare -a out + hash=0 + i=0 + while ((index > 0)) + do ((i ++)) + if ((hash = !hash)) + then out[$i]="#" + ((index --)) + else number=$((index + 1)) + out[$i]=$number + ((index -= ${#number})) + fi + done + for ((; i; i --)) + do printf "%s" ${out[$i]} + done + echo +done + diff --git a/challenge-102/abigail/c/ch-1.c b/challenge-102/abigail/c/ch-1.c new file mode 100644 index 0000000000..564ffc732a --- /dev/null +++ b/challenge-102/abigail/c/ch-1.c @@ -0,0 +1,164 @@ +# include <stdlib.h> +# include <stdio.h> +# include <string.h> + +/* + * See ../README.md + */ + +/* + * Run as: cc -o ch-1.o ch-1.c; ./ch-1.o < input-file + */ + +# define NR_OF_KNOWN_RARE_NUMBERS 124 +# define MAX_RARE_NUMBER_LENGTH 22 + +/* + * Create a list of all known rare numbers. + */ +char * rare_numbers [23]; + +int main () { + rare_numbers [ 0] = NULL; + rare_numbers [ 1] = NULL; + rare_numbers [ 2] = "65\n"; + rare_numbers [ 3] = NULL; + rare_numbers [ 4] = NULL; + rare_numbers [ 5] = NULL; + rare_numbers [ 6] = "621770\n"; + rare_numbers [ 7] = NULL; + rare_numbers [ 8] = NULL; + rare_numbers [ 9] = "281089082\n"; + rare_numbers [10] = "2022652202\n" \ + "2042832002\n"; + rare_numbers [11] = NULL; + rare_numbers [12] = "868591084757\n" \ + "872546974178\n" \ + "872568754178\n"; + rare_numbers [13] = "6979302951885\n"; + rare_numbers [14] = "20313693904202\n" \ + "20313839704202\n" \ + "20331657922202\n" \ + "20331875722202\n" \ + "20333875702202\n" \ + "40313893704200\n" \ + "40351893720200\n"; + rare_numbers [15] = "200142385731002\n" \ + "204238494066002\n" \ + "221462345754122\n" \ + "244062891224042\n" \ + "245518996076442\n" \ + "248359494187442\n" \ + "403058392434500\n" \ + "441054594034340\n" \ + "816984566129618\n"; + rare_numbers [16] = "2078311262161202\n" \ + "2133786945766212\n" \ + "2135568943984212\n" \ + "2135764587964212\n" \ + "2135786765764212\n" \ + "4135786945764210\n" \ + "6157577986646405\n" \ + "6889765708183410\n" \ + "8052956026592517\n" \ + "8052956206592517\n" \ + "8191154686620818\n" \ + "8191156864620818\n" \ + "8191376864400818\n" \ + "8650327689541457\n" \ + "8650349867341457\n"; + rare_numbers [17] = "22542040692914522\n" \ + "67725910561765640\n" \ + "86965750494756968\n"; + rare_numbers [18] = "225342456863243522\n" \ + "225342458663243522\n" \ + "225342478643243522\n" \ + "284684666566486482\n" \ + "284684868364486482\n" \ + "297128548234950692\n" \ + "297128722852950692\n" \ + "297148324656930692\n" \ + "297148546434930692\n" \ + "497168548234910690\n" \ + "619431353040136925\n" \ + "619631153042134925\n" \ + "631688638047992345\n" \ + "633288858025996145\n" \ + "633488632647994145\n" \ + "653488856225994125\n" \ + "811865096390477018\n" \ + "865721270017296468\n" \ + "871975098681469178\n" \ + "898907259301737498\n"; + rare_numbers [19] = "2042401829204402402\n" \ + "2060303819041450202\n" \ + "2420424089100600242\n" \ + "2551755006254571552\n" \ + "2702373360882732072\n" \ + "2825378427312735282\n" \ + "6531727101458000045\n" \ + "6988066446726832640\n" \ + "8066308349502036608\n" \ + "8197906905009010818\n" \ + "8200756128308135597\n" \ + "8320411466598809138\n"; + rare_numbers [20] = "22134434735752443122\n" \ + "22134434753752443122\n" \ + "22134436953532443122\n" \ + "22136414517954423122\n" \ + "22136414971554423122\n" \ + "22136456771730423122\n" \ + "61952807156239928885\n" \ + "61999171315484316965\n" \ + "65459144877856561700\n"; + rare_numbers [21] = "208393425242000083802\n" \ + "219518549668074815912\n" \ + "257661195832219326752\n" \ + "286694688797362186682\n" \ + "837982875780054779738\n"; + rare_numbers [22] = "2414924301133245383042\n" \ + "2414924323311045383042\n" \ + "2414946523311023183042\n" \ + "2576494891793995836752\n" \ + "2576494893971995836752\n" \ + "2620937863931054483162\n" \ + "2620937863931054483162\n" \ + "2620955641393276283162\n" \ + "2622935621573476481162\n" \ + "2622935643751276481162\n" \ + "2622937641933274481162\n" \ + "2622955841933256281162\n" \ + "2622957843751254281162\n" \ + "2727651947516658327272\n" \ + "2747736918335953517072\n" \ + "2788047668617596408872\n" \ + "2788047848617776408872\n" \ + "2788047868437576408872\n" \ + "2788047888617376408872\n" \ + "2939501759705522349392\n" \ + "2939503375709360349392\n" \ + "2939503537707740349392\n" \ + "2939521359525562149392\n" \ + "2939521557527542149392\n" \ + "2939523577527340149392\n" \ + "2939523779525320149392\n" \ + "2959503377707360349192\n" \ + "6344828989519887483525\n" \ + "8045841652464561594308\n" \ + "8045841654642561594308\n" \ + "8655059576513659814468\n" \ + "8655059772157639814468\n" \ + |
