# All squares that match a wildcard sequence [closed]

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.

• I think a good start to making this clearer would be to specify that ? is to be chosen by the answerer. Jan 13, 2017 at 0:49
• Why is 25 a valid answer for *** but not for *2*?
– Neil
Jan 13, 2017 at 0:54
• I think this would be cleaner if the numbers never had leading zeroes, so only matched sequences of their length.
– xnor
Jan 13, 2017 at 1:07
• @Neil That would be a problem with my own solution. I'll take xnor's suggestion. Jan 13, 2017 at 1:11
• 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"}? Jan 13, 2017 at 1:24

# 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.

• This appears to work for all test cases. Good job. Jan 13, 2017 at 2:37

# 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.

• 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. Jan 13, 2017 at 14:47
• @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. Jan 13, 2017 at 14:53
• 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. Jan 13, 2017 at 15:07

# 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


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)»²}  • I've restated the rules, and you can choose any wildcard character. I'm scoring this as 38 bytes. Jan 13, 2017 at 14:57 • Um, how do you use this? I don't know anything about Perl. Jan 13, 2017 at 15:05 • @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. – smls Jan 13, 2017 at 15:17 • 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. Jan 13, 2017 at 15:18 • @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..." )' – smls Jan 13, 2017 at 15:27 # Ruby, 54 bytes Function that takes a string argument. Try it online. ->s{(0..1e3).map{|i|"#{i**2}"[/^#{s.tr ?*,?.}$/]}-[p]}

• You could save a byte by using i*i instead of i**2
– G B
Jan 13, 2017 at 11:40
• This doesn't appear to work because the second # is making the rest of the line a comment. Jan 13, 2017 at 14:54
• @AlexL Oh, it works all right. repl.it/FJCV Jan 13, 2017 at 20:16
• ohhhh okay I just didn't know how to test Ruby. My apologies. This appears to work for all input. Good job! Jan 14, 2017 at 3:43

# 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.

• This appears to work for all inputs. Good job. Jan 13, 2017 at 14:35

## 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. # 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> • I don't think ** is working, because it's giving me a "SyntaxError: expected expression, got '*'". Jan 13, 2017 at 1:35 • @AlexL. The rules seem to have changed. The previous rules suggested I could choose the wildcard character. Jan 13, 2017 at 1:42 • You only need to support up to 1e6... Jan 13, 2017 at 1:42 • 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. Jan 13, 2017 at 1:43 • @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/… Jan 13, 2017 at 1:44 # Perl, 4245 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]}"  • The question specifies that wildcards are given as asterisks. Did an earlier revision of the question allow choosing your own wildcard character? – smls Jan 13, 2017 at 11:55 • @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. Jan 13, 2017 at 12:33 • 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. Jan 13, 2017 at 12:39 • Hm actually, the sentence quoted by @Emigna is pretty clear that we can choose our own wildcard character, isn't it? – smls Jan 13, 2017 at 12:51 • To clarify, the wildcard character can be whatever you want. I accidentally messed up the rules when restating the explanation. Jan 13, 2017 at 13:17 # 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'. • 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. Jan 13, 2017 at 15:09 • Provided input 1...., it gives 1 4 9 and 16 25 as valid answers, which is not correct. Please correct your program. Jan 13, 2017 at 15:11 • Fixet the case by joining on "\n". Jan 13, 2017 at 15:43 • 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). Jan 13, 2017 at 15:53 • Good point, I just checked all the test cases from the description :) Jan 13, 2017 at 16:03 # 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  • 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? Jan 13, 2017 at 18:34
• @AlexL. It works for me in kdb+'s k mode Jan 16, 2017 at 10:34
• Hmm. I'll try testing it with different interpreters. Jan 16, 2017 at 13:12

# 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).

• 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. Jan 14, 2017 at 21:58
• 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.] Jan 14, 2017 at 22:27
• 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. Jan 14, 2017 at 23:07
• @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/… Jan 15, 2017 at 0:32
• 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! Jan 15, 2017 at 2:34