9
\$\begingroup\$

This was inspired by part of the 2016 ARML competition Team Problem #6.

Here's the challenge:

You're given a "wildcard sequence", which is a sequence of digits and another character. A string matches this wildcard sequence by the following pseudocode:

w = wildcard
s = string
# s matches w iff
for all 0 >= i > wildcard.length, w[i] == '?' or s[i] == w[i]

Where '?' is a character of your choice.

In terms of regex, just imagine the '?' to be '.'.

The challenge is to find all square numbers (the requirement is up to 1 million) whose decimal string representations match this wildcard sequence. The "wildcard character" can be any ASCII character of your choice, as long as it isn't a digit, obviously.

For example, 4096 matches 4**6 and 4*9* but 4114 does not match either.

Input

Input will be given as a sequence matching the regex [0-9?]+. This can be a string, a character array, or a byte array of the characters in ASCII.

Output

Output will be a whatever-you-want-delimited list/set/array of numbers which are perfect squares and match the wildcard sequence.

Examples of valid inputs:

1234567*90
1234567?90
1234567u90
['1', '2', '3', '4', '5', '6', '7', '*', '9', '0']
[49, 50, 51, 52, 53, 54, 55, 42, 57, 48]
[1, 2, 3, 4, 5, 6, 7, '*', 9, 0]

Examples of valid outputs:

[1, 4, 9]
1 4 9
1, 4, 9
1-4-9

etc.

Specifications

  • You may not use builtins for finding a list of squares in a certain range
  • Standard Loopholes Apply
  • You must be able to handle up to 1 000 000 (1 million)
  • If provided with the input 1******, it is correct to print [1000000]. It is also correct to print [1000000, 1002001, 1004004, 1006009, 1008016, 1010025, ...]
  • Wildcard sequences will never start with the wildcard character; that is, they will always match strings of the same length.

Test Cases

4**6  ->  [4096, 4356]
1**1  ->  [1521, 1681]
1**  ->  [100, 121, 144, 169, 196]
9****9  ->  [908209, 915849, 927369, 935089, 946729, 954529, 966289, 974169, 986049, 994009]
9*9***  ->  [919681, 929296]
1**0*  ->  [10000, 10201, 10404, 10609, 12100, 14400, 16900, 19600]
9***4  ->  [91204, 94864, 97344]

Winning

Shortest (valid) (working) submission by February 14th, tie-break by earliest submission winning.

\$\endgroup\$
  • 1
    \$\begingroup\$ I think a good start to making this clearer would be to specify that ? is to be chosen by the answerer. \$\endgroup\$ – FryAmTheEggman Jan 13 '17 at 0:49
  • 2
    \$\begingroup\$ Why is 25 a valid answer for *** but not for *2*? \$\endgroup\$ – Neil Jan 13 '17 at 0:54
  • 3
    \$\begingroup\$ I think this would be cleaner if the numbers never had leading zeroes, so only matched sequences of their length. \$\endgroup\$ – xnor Jan 13 '17 at 1:07
  • \$\begingroup\$ @Neil That would be a problem with my own solution. I'll take xnor's suggestion. \$\endgroup\$ – HyperNeutrino Jan 13 '17 at 1:11
  • \$\begingroup\$ Can the input be an array of one-digit integers and the special character, such as {4, "w", "w", 6} (or better yet, {4, w, w, 6}), rather than an array of characters, such as {"4", "w", "w", "6"}? \$\endgroup\$ – Greg Martin Jan 13 '17 at 1:24

11 Answers 11

0
\$\begingroup\$

05AB1E, 22 bytes

Probably plenty of room for improvement here.
Any non-digit is okay as wildcard.

3°LnvyS¹)ø€Æ0QPyg¹gQ&—

Try it online!

Explanation to come after further golfing.

|improve this answer|||||
\$\endgroup\$
  • \$\begingroup\$ This appears to work for all inputs. Good job. \$\endgroup\$ – HyperNeutrino Jan 13 '17 at 14:35
1
\$\begingroup\$

Mathematica, 44 bytes

Print@@@IntegerDigits[Range@1*^3^2]~Cases~#&

The input is a list of digits with a _ (no quotes) as a wildcard. e.g. {4, _, _, 6}

Explanation

Range@1*^3

Generate list {1, 2, 3, ... , 1000}

... ^2

Square it. (list of all squares from 1 to 1,000,000)

IntegerDigits[ ... ]

Split each square into a list of digits.

... ~Cases~#

Find the ones that match the pattern specified by the input.

Print@@@ ...

Print them.

|improve this answer|||||
\$\endgroup\$
  • \$\begingroup\$ This appears to work for all test cases. Good job. \$\endgroup\$ – HyperNeutrino Jan 13 '17 at 2:37
1
\$\begingroup\$

Brachylog, 23 bytes

@e:{@$|,}a#0:{c.~^#I,}f

Try it online!

Explanation

@e                        Split into a list of characters
  :{@$|,}a                Replace each digit char by the corresponding digit, and each things
                            that are ot digits into variables
          #0              All elements of the resulting list must be digits
            :{       }f   Output is the result of finding all...
              c.            ...concatenations of those digits which...
               .~^#I,       ...result in a number which is the square of an integer #I

Different input format, 13 bytes

Depending on what your consider valid as input, you could do this:

#0:{c.~^#I,}f

Try it online!

which is basically the second part of the answer above, with a list as input containing digits and variables where the wildcards are.

I don't consider this valid though because there are only 26 variable names in Brachylog (the uppercase letters), so this would not work if you had more than 26 wilcards.

|improve this answer|||||
\$\endgroup\$
  • \$\begingroup\$ This appears to work for all inputs. Good job. However, I would consider this to be 24 bytes because a 1-byte argument is required. I'm not sure how scoring for this would work though. \$\endgroup\$ – HyperNeutrino Jan 13 '17 at 14:47
  • 1
    \$\begingroup\$ @AlexL. The argument is only there to tell the name of the output variable (you can use another uppercase letter if you want). This is similar to answers in Prolog/languages with functions where the predicate/function is named but you don't actually count the bytes you use when you call it. \$\endgroup\$ – Fatalize Jan 13 '17 at 14:53
  • \$\begingroup\$ Okay. I'm not sure if one should score it as 24 since the argument is necessary (otherwise it just returns true.), but I haven't used languages that require this before. I'll try to find some reference to determine how I should score this, but it would make sense to score it as 23, so I'll keep it at that. \$\endgroup\$ – HyperNeutrino Jan 13 '17 at 15:07
1
\$\begingroup\$

Perl 6, 30 26 bytes

Thanks to @b2gills for -4 bytes!

{grep /^<$_>$/,map * **2,^1e4}

{grep /^<$_>$/,(^1e4)»²}

Uses the dot as wildcard character, so that the input can be used as a regex:

{                            }   # a lambda
                         ^1e4    # range from 0 to 9999
               map * **2,        # square each value
 grep /      /,                  # filter numbers that match this regex:
        <$_>                     #   lambda argument eval'ed as sub-regex
       ^    $                    #   anchor to beginning and end

Try it online.

A variant that accepts the asterisk as wildcard (as suggested by a previous revision of the task description) would be 42 bytes:

{grep /^<{.trans("*"=>".")}>$/,(^1e4)»²}
|improve this answer|||||
\$\endgroup\$
  • \$\begingroup\$ I've restated the rules, and you can choose any wildcard character. I'm scoring this as 38 bytes. \$\endgroup\$ – HyperNeutrino Jan 13 '17 at 14:57
  • \$\begingroup\$ Um, how do you use this? I don't know anything about Perl. \$\endgroup\$ – HyperNeutrino Jan 13 '17 at 15:05
  • \$\begingroup\$ @AlexL.: Thanks, I've updated the answer (and added an explanation too). It's a lambda; you could call it directly (e.g. { ... }("9*9***")), or assign it to a variable/symbol for later use. Note that Perl 6 is a separate language from Perl, so it won't work with a Perl interpreter. \$\endgroup\$ – smls Jan 13 '17 at 15:17
  • \$\begingroup\$ I used sudo apt-get install rakudo to get a supposed Perl6 interpreter... When I put perl6 as a command into my terminal, it starts what seems to be a Perl6 interpreter, but I don't know how to use it. I know it's a lambda, but I don't know how to call it. \$\endgroup\$ – HyperNeutrino Jan 13 '17 at 15:18
  • \$\begingroup\$ @AlexL.: I added a "Try it online" link which shows it as a full script that you can run as perl6 foo.p6. You can also test it in a shell oneliner, like perl6 -e 'say {grep /^<$_>$/,map * **2,^1e4}( "9.9..." )' \$\endgroup\$ – smls Jan 13 '17 at 15:27
1
\$\begingroup\$

Ruby, 54 bytes

Function that takes a string argument. Try it online.

->s{(0..1e3).map{|i|"#{i**2}"[/^#{s.tr ?*,?.}$/]}-[p]}
|improve this answer|||||
\$\endgroup\$
  • \$\begingroup\$ You could save a byte by using i*i instead of i**2 \$\endgroup\$ – G B Jan 13 '17 at 11:40
  • \$\begingroup\$ This doesn't appear to work because the second # is making the rest of the line a comment. \$\endgroup\$ – HyperNeutrino Jan 13 '17 at 14:54
  • \$\begingroup\$ @AlexL Oh, it works all right. repl.it/FJCV \$\endgroup\$ – Value Ink Jan 13 '17 at 20:16
  • \$\begingroup\$ ohhhh okay I just didn't know how to test Ruby. My apologies. This appears to work for all input. Good job! \$\endgroup\$ – HyperNeutrino Jan 14 '17 at 3:43
0
\$\begingroup\$

Batch, 109 bytes

@for /l %%i in (0,1,999)do @set/aj=%%i*%%i&call copy nul %%j%%.%%j%%$>nul
@for %%s in (%1.%1$)do @echo %%~ns

Uses ? as the wildcard. Works by creating 1000 files. The name of the file is the square number, and the extension of the file is the square number with a $ suffixed. This is because Batch's pattern matching counts trailing ?s as optional, so 1? will match both 1 and 16; the $ therefore forces the match to be exact. However, we don't want to output the $, so we just output the file name only without extension.

|improve this answer|||||
\$\endgroup\$
0
\$\begingroup\$

JavaScript (ES6), 68 66 bytes

EDIT: Updated my solution below after being inspired by JungHwan Min's answer. It is now ES6 compliant.

Takes input in the format '1..4' where . is the wildcard.

Instead of iterating to 1e6 and square rooting this one iterates to 1e3 and squares.

p=>[...Array(1e3)].map((_,n)=>''+n*n).filter(n=>n.match(`^${p}$`))

F=p=>[...Array(1e3)].map((_,n)=>''+n*n).filter(n=>n.match(`^${p}$`))

const update = () => {
  console.clear();
  console.log(F(input.value));
}

submit.onclick = update;
update();
<input id="input" type="text" value="9....9" style="width: 100%; box-sizing: border-box" /><button id="submit">submit</button>

JavaScript (ES7), 71 69 bytes

p=>[...Array(1e6).keys()].filter(n=>n**.5%1?0:(''+n).match(`^${p}$`))

Creates an array of numbers from 0 to 1e6 then filters it by numbers that are square and match the pattern.

It is horrendously slow because it always iterates to 1e6.

F=p=>[...Array(1e6).keys()].filter(n=>n**.5%1?0:(''+n).match(`^${p}$`))

const update = () => {
  console.clear();
  console.log(F(input.value));
}

submit.onclick = update;
update();
<input id="input" type="text" value="9....9" style="width: 100%; box-sizing: border-box" /><button id="submit">submit</button>

|improve this answer|||||
\$\endgroup\$
  • \$\begingroup\$ I don't think ** is working, because it's giving me a "SyntaxError: expected expression, got '*'". \$\endgroup\$ – HyperNeutrino Jan 13 '17 at 1:35
  • \$\begingroup\$ @AlexL. The rules seem to have changed. The previous rules suggested I could choose the wildcard character. \$\endgroup\$ – George Reith Jan 13 '17 at 1:42
  • \$\begingroup\$ You only need to support up to 1e6... \$\endgroup\$ – HyperNeutrino Jan 13 '17 at 1:42
  • \$\begingroup\$ Additionally, I changed the rules back; the issue isn't with the rules, it's because the ** operator doesn't exist, at least not with my system. \$\endgroup\$ – HyperNeutrino Jan 13 '17 at 1:43
  • \$\begingroup\$ @AlexL. Ah sorry I thought you meant the input **. Yes it is ES7 I will update title here is a list of currently supported browsers developer.mozilla.org/en/docs/Web/JavaScript/Reference/… \$\endgroup\$ – George Reith Jan 13 '17 at 1:44
0
\$\begingroup\$

Perl, 42 45 38 bytes

EDIT: clarification by Alex, we can use the period as wildcard character which shaves off the y// operation.

perl -pe 's|.*|@{[grep/^$&$/,map$_*$_,1..1e3]}|'

EDIT: solution that uses the asterisk as wildcard character and expects the wildcard sequence on STDIN

perl -pe 'y/*/./;s|.*|@{[grep/^$&$/,map$_*$_,1..1e3]}|'

This one leaves undoubtedly a lot of room for improvement, it's pretty straightforward. The wildcard expression is expected as command line argument, with the period wildcard character (what else?).

say"@{[grep/^$ARGV[0]$/,map$_*$_,1..1e3]}"
|improve this answer|||||
\$\endgroup\$
  • \$\begingroup\$ The question specifies that wildcards are given as asterisks. Did an earlier revision of the question allow choosing your own wildcard character? \$\endgroup\$ – smls Jan 13 '17 at 11:55
  • 1
    \$\begingroup\$ @smls: The question still specifies choose your own wildcard although it is not in the rule section: The character used as the wildcard doesn't necessarily need to be an asterisk, it can be any ASCII character of your choice, as long as it isn't a digit, obviously. \$\endgroup\$ – Emigna Jan 13 '17 at 12:33
  • \$\begingroup\$ Yes, I got confused by that. Later on, it clearly says the wildcard character needs to be an asterisk. I guess the definition with the regex is leading. I'll revise my solution. \$\endgroup\$ – daniel Jan 13 '17 at 12:39
  • 1
    \$\begingroup\$ Hm actually, the sentence quoted by @Emigna is pretty clear that we can choose our own wildcard character, isn't it? \$\endgroup\$ – smls Jan 13 '17 at 12:51
  • \$\begingroup\$ To clarify, the wildcard character can be whatever you want. I accidentally messed up the rules when restating the explanation. \$\endgroup\$ – HyperNeutrino Jan 13 '17 at 13:17
0
\$\begingroup\$

Python 3 - 98 97 bytes

import re;print(re.findall(r"\b"+input()+r"\b",("\n".join([str(x*x) for x in range(1,1001)]))))

Requires input like '4..6'.

|improve this answer|||||
\$\endgroup\$
  • \$\begingroup\$ You can save 3 bytes by using import re and re.findall; the optimization with the from...import * doesn't actually optimize it in this case. \$\endgroup\$ – HyperNeutrino Jan 13 '17 at 15:09
  • \$\begingroup\$ Provided input 1...., it gives 1 4 9 and 16 25 as valid answers, which is not correct. Please correct your program. \$\endgroup\$ – HyperNeutrino Jan 13 '17 at 15:11
  • \$\begingroup\$ Fixet the case by joining on "\n". \$\endgroup\$ – Carra Jan 13 '17 at 15:43
  • \$\begingroup\$ This doesn't work for 1....... It returns [], but it should give [1000000]. This can be fixed at a cost of 0 bytes by using range(0, 1001) rather than range(0, 1000). \$\endgroup\$ – HyperNeutrino Jan 13 '17 at 15:53
  • \$\begingroup\$ Good point, I just checked all the test cases from the description :) \$\endgroup\$ – Carra Jan 13 '17 at 16:03
0
\$\begingroup\$

k - 28 characters

{s(&:)($:s:s*s:!1001)like x}

Uses ? as the wildcard character. The like function uses ? as a wildcard, and this function makes a list of the first 1001 squares (to be inclusive to 1M), casts them all to strings, and then checks where they match the pattern.

    {s(&:)($:s:s*s:!1001)like x} "1??"
100 121 144 169 196
|improve this answer|||||
\$\endgroup\$
  • \$\begingroup\$ I'm getting this error for it: type error {s(&:)($:s:s*s:!1001)like x} "1" at execution instance 2 of ":". Could you provide a link to a working test suite or see if there's a problem? \$\endgroup\$ – HyperNeutrino Jan 13 '17 at 18:34
  • \$\begingroup\$ @AlexL. It works for me in kdb+'s k mode \$\endgroup\$ – C. Quilley Jan 16 '17 at 10:34
  • \$\begingroup\$ Hmm. I'll try testing it with different interpreters. \$\endgroup\$ – HyperNeutrino Jan 16 '17 at 13:12
0
\$\begingroup\$

bash + Unix utilities, 33 bytes

dc<<<'0[2^pv1+lax]dsax'|grep ^$1$

This uses '.' as the wildcard character.

The dc program prints the square numbers in an infinite loop:

0     Push 0 on the stack.

[     Start a macro (called a).

2^    Square the number at the top of the stack.

p     Print the number at the top of the stack, followed by a newline.

v     Replace the number at the top of the stack (a square number) with its square root.

1+    Increment the number at the top of the stack.

lax   Run the macro again (looping).

]     End of the macro.

dsax  Store the macro in register a and run it.

The dc output is piped to grep, which prints just the squares that match the required pattern.

This works when I run it on an actual Linux or OS X system (but it doesn't work at TIO, probably because the dc program tries to recurse forever, and I suspect TIO runs out of stack space for the recursion and/or has a problem with the never-ending pipe).

|improve this answer|||||
\$\endgroup\$
  • \$\begingroup\$ I'm running this with Linux Mint 17.3 Rosa, and it's not terminating. I think the problem is with the never-ending dc command. \$\endgroup\$ – HyperNeutrino Jan 14 '17 at 21:58
  • \$\begingroup\$ I suspect it's actually the buffering that's causing the issue. I don't have that version of Linux, but you could try replacing the grep with grep --line-buffered (to cause each line to be printed as it's grepped). [Of course, that adds a number of bytes.] \$\endgroup\$ – Mitchell Spector Jan 14 '17 at 22:27
  • \$\begingroup\$ I added the grep argument, but it doesn't make a difference. I tried putting the --line-buffered on either side of the ^$1$, but it doesn't work either way. \$\endgroup\$ – HyperNeutrino Jan 14 '17 at 23:07
  • \$\begingroup\$ @AlexL.Thank you for trying. I don't know if the difference is in the kernel or in the bash version I'm running. I got it to work in TIO by forcing an end to grep's input using head, as follows: dc<<<'0[2^pv1+lax]dsax'|head -1sed s/./0/g<<<$1|grep ^$1$ This uses the length of the pattern to limit the numbers being tested (4-character patterns check only up to 9999, etc.). Here's a TIO link: tio.run/nexus/… \$\endgroup\$ – Mitchell Spector Jan 15 '17 at 0:32
  • \$\begingroup\$ Thank you for the fix. I don't think the current solution would actually work (though I don't have much knowledge of bash), because it appears that it needs to calculate all values before feeding that into grep. However, as it is currently not the shortest solution, I will keep it at 33 bytes for scoring. It appears to work for all inputs, so good job! \$\endgroup\$ – HyperNeutrino Jan 15 '17 at 2:34

Not the answer you're looking for? Browse other questions tagged or ask your own question.