# How to sum match numbers

I'm new at scripting, and need some help. Will appreciate your answers.

I got this assignment, which is to find the sum of all five-digit numbers (in the range 10000 - 99999) containing exactly two out of the following set of digits: { 4, 5, 6 }. These may repeat within the same number, and if so, they count once for each occurrence.

Some examples of matching numbers are 42057, 74638, and 89515. I only have this little piece of code.

``````#! /bin/bash
for (( CON1=10000; CON1<=99999; CON1++ )) ;
do
## UNKNOWN COMMANDS
done
``````
• Do you want to compare? do you want to sum? What do want to do? Oct 20, 2014 at 0:05
• I think he means that the number X has to contain exactly 2 digits from the set, {4,5,6}, has to be in the range 10000 - 99999, and contain any other digits. The numbers from the set can repeat. So the you could have a 5 digit number w/ 2 fives, or 2 sixes.
– slm
Oct 20, 2014 at 0:28

Here is one way of counting how many 4, 5, or 6 appear in your number and having `bash` execute a statement based on whether the result is two or not:

``````\$ con1=1457
\$ a=\${con1//[^456]/}; [ \${#a} -eq 2 ] && echo Yes
Yes
``````

### Getting started

Whenever I have a project like this I like to approach it in stages. The first thing I like to do is add an `echo` to the inside the loop and then run it, to make sure that the loop is giving me what I want.

``````#! /bin/bash
for (( CON1=10000; CON1<=99999; CON1++ )) ;
do
echo \$CON1
done
``````

Now when I run it I'll use `head -5` to just show the first 5 lines it outputs.

``````\$ ./cmd.bash | head -5
10000
10001
10002
10003
10004
``````

OK, so that looks good, check the end like this:

``````\$ ./cmd.bash | tail -5
99995
99996
99997
99998
99999
``````

That looks good too. So now let's figure out some ways we could approach the next step of identifying numbers with 2 digits from the set {4,5,6}. My first instinct here is to go for `grep`. There are also methods for doing this purely in Bash, but I like to use the various tools, `grep`, `awk`, and `sed` for doing these types of things, mainly because that's how my mind works.

### An approach

So how can we `grep`lines that contain 2 digits from the set, {4,5,6}? For this you can use a set notation, that's written like this in regex, `[456]`. You can also specify how many digits you want to match from this set. That's written like this:

``````[456]{#}
``````

Where `#` is a number or range of numbers. If we wanted 3, we'd write `[456]{3}`. If we wanted 2-5 digits, we'd write `[456]{2,5}`. If you wanted 3 or more, [456]{3,}`.

So for your scenario it's `[456]{2}`. To use a regex in `grep`, your particular version of `grep` needs to support the `-E` swtich. This is typically available in most standard `grep`'s.

``````\$ echo "45123" | grep -E "[456]{2}"
45123
``````

Seems to work but if we give it numbers with 3, we start to see an issue:

``````\$ echo "45423" | grep -E "[456]{2}"
45423
``````

That's matching too. This is because `grep` has not concept of the fact that these are digits in a string. It's dumb. We told it to tell us if the series of characters in our string are from a set and that there are 2 of them and there are 2 digits in the string `45423`.

It also fails for these strings:

``````\$ echo "41412" | grep -E "[456]{2}"
\$
``````

So is this method usable? It is if we change tactics a bit, but we'll have to rejigger the regex.

### Example

``````\$ echo -e "41123\n44123\n44423\n41423" | grep -E "[^456]*([456][^456]*){2}"
44123
44423
41423
``````

The above is presenting 4 types of the strings. The `echo -e "41123\n44123\n44423\n41423"` just prints 4 of the numbers from our range.

``````\$ echo -e "41123\n44123\n44423\n41423"
41123
44123
44423
41423
``````

How does this regex work? It sets up a regex pattern of zero or more "not [456]" followed by either 1 or more [456] or zero or more "not [456]" characters, looking for 2 occurrences of the latter.

So now we do a little assembly in your script.

``````for (( CON1=10000; CON1<=99999; CON1++ )) ;
do
if echo \$CON1 | grep -q -E "[^456]*([456][^456]*){2}"; then
echo \$CON1
fi
done
``````

Using our `head` & `tail` trick from above we can see that it's working:

``````\$ ./cmd.bash | head -5
10044
10045
10046
10054
10055

\$ ./cmd.bash | tail -5
99955
99956
99964
99965
99966
``````

But this method proves to be dog slow. The problem is that `grep`. It's expensive, and we're running `grep 1 time, per iteration through the loop, so that's ~80k times!

To improve that we could move our `grep` command outside the loop and run it 1 time, after the list's been generated, like so, using our original version of the script that just echoed the numbers out:

``````\$ ./cmd.bash | grep -E "[^456]*([456][^456]*){2}"
``````

NOTE: We could drop the for loop entirely and use the command line tool, `seq`. This will generate the same sequence of numbers, `seq 10000 99999`.

### One liner?

A fancy way to do this would be to use the sequence of numbers from the above command, and then pipe it to the `paste` command which would insert a `+` between each number, and then run that output into the command line calculator, `bc`.

``````\$ ./cmd.bash | grep -E "[^456]*([456][^456]*){2}" | paste -s -d"+"
10044+10045+10046+10054+10055+10056+10064+10065+10066+10144+10145+...

\$ ./cmd.bash | grep -E "[^456]*([456][^456]*){2}" | paste -s -d"+" | bc
2409327540
``````

But that's a completely different way to solve this problem, so lets get back to the `for` loop.

### Using pure Bash

So we need some method for testing if a digit has exactly 2 digits within Bash, but isn't as expensive as calling `grep` 80k times. Modern versions of Bash include the ability to match using the `=~` operator, which can do similar matching as `grep`. Let's take a look at that next.

``````#!/bin/bash
for (( CON1=10000; CON1<=99999; CON1++ )) ;
if [[ \$CON1 =~ [^456]*([456][^456]*){2} ]]; then
echo \$CON1
fi
done
``````

Running this looks to do exactly what we want.

``````\$ ./cmd1.bash  | head -5
10044
10045
10046
10054
10055

\$ ./cmd1.bash  | tail -5
99955
99956
99964
99965
99966
``````

Checking it shows that it works with 41511 now:

``````\$ ./cmd1.bash | grep 41511
41511
``````

### References

• This is fast, but your regexes don't catch strings where the target digits aren't adjacent. You could use `^[^456]*([456][^456]*){2}\$` but it takes twice as long as John1024's algorithm. Oct 20, 2014 at 3:18
• @PM2Ring - thanks for the catch, fixed.
– slm
Oct 20, 2014 at 3:39

I suppose you have to do this in pure Bash script, but translating John1024's algorithm to awk gives a considerable speed-up:

``````awk 'BEGIN{k=0;for(i=10000;i<100000;i++){j=i;if(gsub(/[456]/,"",j)==2)k+=i};print k}'
``````

This runs in less than 1/20 of the time that the bash version takes; it's also a little faster than a Python version that uses Python's built-in `str.count()` method.