How to sum match numbers

Question

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

Answer 1

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

Answer 2

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 greplines 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

• The conditional expression - Bash

Answer 3

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.