The technology that you do not master, will master you.

Using Bash To Solve A Brain Teaser

Date/Time Permalink: 02/21/12 11:01:57 am
Category: HOWTOs and Guides

So we have this puzzle, expressed as:

RUT * RUT = CAREER

...where each letter stands for a digit. So in other words, "RUT" is the square root of "CAREER". But what are the digits?

Obviously, we need a three-digit number whose square is a six-digit number. "317" is the lowest number that is the square root of a six-digit number, and the three-digit number can go as high as 999. So far our Bash line looks like this:

for N in $(echo {317..999}); do S=$(($N*$N)) && echo $N, $S; done

Our answer is somewhere in that column. Now we see another clue, that the first digit of the multiplier is the same as the third and sixth digits of the product. We know we can take an index slice from a variable, such as getting the first digit with ${N:0:1} (remembering that variable indexing in Bash starts at zero). So now we can create a conditional filter which only prints the numbers if the first digit of the multiplier is the same as the third and sixth digits of the product. We'll have to break that down into two separate tests.

First let's filter it down to products whose third and sixth digit are the same:

for N in $(echo {317..999}); do S=$(($N*$N)) && if [ ${S:2:1} = ${S:5:1} ]; then echo $N, $S; fi; done

Piping that into wc -l says that only 94 lines printed, so we know we're narrowing it down. Now test if the first digit of the multiplier is the same as the third digit of the product:

for N in $(echo {317..999}); do S=$(($N*$N)) && if [ ${S:2:1} = ${S:5:1} ]; then if [ ${N:0:1} = ${S:2:1} ]; then echo $N, $S; fi; fi; done

So we had nested conditionals there. Don't pass out on me, we're almost there. The above command line pumps out this column:

.
418, 174724
452, 204304
505, 255025
515, 265225
525, 275625
614, 376996
676, 456976
927, 859329
943, 889249

From here, we can get it by eyeball. We also know from "RUT" and "CAREER" that the fourth and fifth digits of the product have to be the same digit. We could include a third nested test like so:

for N in $(echo {317..999}); do S=$(($N*$N)) && if [ ${S:2:1} = ${S:5:1} ]; then if [ ${N:0:1} = ${S:2:1} ]; then if [ ${S:3:1} = ${S:4:1} ]; then echo $N, $S; fi; fi; fi; done

Great Scott! We're down to two possible numbers:

.
515, 265225
614, 376996

We have one more clue, that the first and third digits of the multiplier must be different from each other. We can clearly see that that disqualifies 515, leaving "RUT" = 614 and CAREER = 376966, but we're here to do it in Bash:

for N in $(echo {317..999}); do S=$(($N*$N)) && if [ ${S:2:1} = ${S:5:1} ]; then if [ ${N:0:1} = ${S:2:1} ]; then if [ ${S:3:1} = ${S:4:1} ]; then if [ ${N:0:1} != ${N:2:1} ]; then echo $N, $S; fi; fi; fi; fi; done

That gave us the correct answer.

So, what have we learned in this example?

  • How to list a sequence of numbers. (echo {X..Y})
  • Shell math. (X=$(($Y*$Z)))
  • How to do a one-liner loop. (for X in $(command); do thing; done)
  • How to take a piece of a variable (${X:0:1})
  • How to do a one-liner conditional test. (if [ $X = $Y ]; then do thing; done)
  • How to do a negated one-liner conditional test. (if [ $X != $Y ]; then do thing; done)
  • That we can nest this all together!

Good thing this problem comes up all the time, isn't it?

Follow me on Twitter for an update every time this blog gets a post.
Stumble it Reddit this share on Facebook

suddenly the moon