Pattern problem. 4

[mmerlinn]

[tt]I notice that this forum has been dead for almost a year.

Today I was thinking (yeah, I know, DANGEROUS) about a simple test that could be given to prospective coders to determine how well they can visualize and code on the fly. The following is what I think would separate real coders from the rest of the pack.

Let's see some code for the following problem:

0123456789
9876543210
1234567890

Using the above three lines as a pattern, write code that will output the above lines and all following lines until the pattern repeats. Hint: This pattern will repeat starting with the 21st line.​

Everything you need to know is posted above. There should be no reason for me to answer any questions. And, yes, this is deliberately minimal to test two things. First, how well a coder can recognize patterns. And, second, how well a coder can write code to output those patterns.

I spent about 10 minutes before I could visualize how to code this. Then I spent 20 more minutes writing/debugging C++ code to solve this problem. I am a FoxPro programmer, but chose C++ because I have about 3 HOURS total experience in C++ coding. I did not try FoxPro, but I assume that the time would be comparable.

Later I will post my C++ code for comparison purposes. I may even give stars to code that I think is exceptional (assuming that I understand your coding language).[/tt]

mmerlinn

http://mmerlinn.com

Poor people do not hire employees. If you soak the rich, who are you going to work for?

"We've found by experience that people who are careless and sloppy writers are usually also careless and sloppy at thinking and coding. Answering questions for careless and sloppy thinkers is not rewarding." - Eric Raymond

 

[strongm]

Um - about 2 seconds to see the pattern, and about 1 minute to write the code ...

[hide]Public Sub main()
Dim strDigits As String

strDigits = "0123456789"
Do
Debug.Print strDigits
strDigits = StrReverse(strDigits)
Debug.Print strDigits
strDigits = StrReverse(Left(strDigits, 9)) & Right(strDigits, 1)
Loop Until strDigits = "0123456789"
End Sub[/hide]

Note that the HIDE tag rather spoils the layout of the code ...

 

[strongm]

And upon reflection, I can simplify it slightly:
[hide]Public Sub main2()
Dim strDigits As String

strDigits = "0123456789"
Do
Debug.Print strDigits & vbCrLf & StrReverse(strDigits)
strDigits = Right(strDigits, 9) & Left(strDigits, 1)
Loop Until strDigits = "0123456789"
End Sub[/hide]

 

[mmerlinn]

[tt]Dang, not exactly the way I had envisioned it.

I never thought of assigning the "0123456789" to a variable. So, my instructions were not clear.

My intent was that the pattern would be generated one digit at a time entirely by the code without assigning any part of the pattern to a string variable.

So, let me try again.

0123456789
9876543210
1234567890

Using the above three lines as a pattern, write code that will output the above lines and all following lines until the pattern repeats.

Rules: The results must be generated by your code one digit at a time. String variables, if needed, are only permitted to build and output the results. No part of the input pattern may be assigned to a variable, although it is obvious that the intermediary and output results must be assigned to one or more variables. In other words, the results must be entirely generated by the code, one digit at a time, without starting with any fixed variable(s). Note that string variables are not even needed in some languages like C++.

Hint: This pattern will repeat starting with the 21st line.​

Also, an explanation of how the code works might help. It took me a bit to figure out how the code submitted by strongm above works since I am not familiar with his language.

Now let's see whether my revised instructions are still as clear as mud.[/tt]

mmerlinn

http://mmerlinn.com

Poor people do not hire employees. If you soak the rich, who are you going to work for?

"We've found by experience that people who are careless and sloppy writers are usually also careless and sloppy at thinking and coding. Answering questions for careless and sloppy thinkers is not rewarding." - Eric Raymond

 

[strongm]

Ok
(language is VBA, by the way)

[hide]Public Sub Main3()
Dim lp1 As Long
Dim lp2 As Long
Dim lp3 As Long

For lp3 = 0 To 9
For lp1 = 0 To 9
Debug.Print Trim((lp1 + lp3) Mod 10);
Next
Debug.Print
For lp2 = 9 To 0 Step -1
Debug.Print Trim((lp2 + lp3) Mod 10);
Next
Debug.Print
Next
End Sub[/hide]

 

[kwbMitel]

@mmerlinn

In my opinion, you have not provided enough information to establish a reasonable pattern.

Based on assumptions any of the following would be valid for the next value.

9876543210
8765432109
0987654321

If it is pattern recognition you are looking for, then you would have to accept any of those as valid (and others IMO less valid)

The clue of repeating at line 21 is valid for all of those.

For the record, I would have chose 876543210

**********************************************
What's most important is that you realise ... There is no spoon.

 

[strongm]

Fair point (and I can make miniscule modifications of my code to deal with all of those ). But as a test, the whole premise now seems flawed to me anyway. The OP stated that it was to "determine how well they can visualize and code on the fly", but by then changing the parameters of the question because the first solution didn't fit the OPs idea of how it should be solved, this goal is immediately undermined since we are no longer allowed to solve it any way we like.

 

[kwbMitel]

It struck me as odd that the method mattered at all.

I would see more value in seeing various methods as this would give insights into a persons thought processes. If this is a programming hiring test then how people think is as important as how they perform a given task.

**********************************************
What's most important is that you realise ... There is no spoon.

 

[PHV]

Spoiler

#!/usr/bin/awk -f
BEGIN{for(i=0;i<=9;++i){
 for(j=0;j<=9;++j)printf "%i",(i+j)%10;printf "\n"
 for(j=9;j>=0;--j)printf "%i",(i+j)%10;printf "\n"
}}

Hope This Helps, PH.
FAQ219-2884
FAQ181-2886

 

[mmerlinn]

[tt]It is obvious that I did not think this all the way through as well as not being clear in the presentation.

As for the other possible patterns, I fail to see how two of the three given are possible.

9876543210 >> is already used so how could it be next?
8765432109 >> when I look at this one, it seems to break the pattern, but then I may be missing something obvious
0987654321 >> this is the only one that "looks" to me to fit the pattern

How about showing the full set (all 20) using these options so I can see how they fit the pattern that you see?

Anyhow, since I have garbled this problem, here is the solution that I came up with.

Spoiler

#include <iostream>

int main();

    for (int i = 10; i < 20; i++)
    {
        for (int j = i - 10; j < i; j++)
        {
            cout << j % 10;
        }
        cout << endl;

        for (int k = i - 1; k > i - 11; k--)
        {
            cout << k % 10;
        }
        cout << endl;
    }
    return 0;
}

0123456789
9876543210
1234567890
0987654321
2345678901
1098765432
3456789012
2109876543
4567890123
3210987654
5678901234
4321098765
6789012345
5432109876
7890123456
6543210987
8901234567
7654321098
9012345678
8765432109

There may be a better way.

Anyhow, the solutions I see posted here are the type of solutions I would expect a real coder to use to solve this kind of problem.

As you probably have noticed, there are some coders visiting these forums that would have used dozens and dozens of conditional statements often mixed in with loops to solve a simple problem like this. The code used by those coders drives me batty trying to figure out what they are doing especially when they are asking for help as to why their spaghetti code does not work as expected.[/tt]


mmerlinn

http://mmerlinn.com

Poor people do not hire employees. If you soak the rich, who are you going to work for?

"We've found by experience that people who are careless and sloppy writers are usually also careless and sloppy at thinking and coding. Answering questions for careless and sloppy thinkers is not rewarding." - Eric Raymond

 

[strongm]

All of kwbMitel's options are valid (although perhaps slightly less obvious) continuations of the pattern sample you provided in the OP. I'll allow them to explain.

 

[kwbMitel]

9876543210 >> is already used so how could it be next?

It can be next because you have not established that it needs to change at all. The first and 3rd numbers change but there is no requirement of the second number to change. On the 1st and 3rd numbers, you have not actually established a pattern either. 2 instances are not enough for a pattern. The next value could simply toggle back to the first or skip 2 numbers or 3 or 4. Modifying by 1 meets the 21 step requirement however so it is reasonable to use this value. There are probably other patterns that would meet that requirement but I try to apply Occams Razor when I can.​

8765432109 >> when I look at this one, it seems to break the pattern, but then I may be missing something obvious

There are 2 equally valid reasons to apply this pattern. The first is that if the numbers that are counting up are shifting one position up, then the numbers that are counting down should shift one number down. The second is that number in the first position is shifted to the end. This is the pattern I would choose. Additionally, when paired with the the other sequence, adding the two together results in the number 9999999999 which is aesthetically pleasing to me.​

0987654321 >> this is the only one that "looks" to me to fit the pattern

I think you would have difficulty justifying this pattern over either of the other 2 with the information that you provided which was exactly my point. I believe all 3 are roughly equal and I have stated my preference (which does not match yours obviously).​

"So what we have here, is a failure to communicate" ~ From:Cool Hand Luke

Lets say you received Strongm's first solution, my solution, and PHV's as results for your hiring process. Who is the stronger candidate? (I know I did not submit code but imagine I did something like yours but with the second number sequenced my way)

**********************************************
What's most important is that you realise ... There is no spoon.

 

[Olaf Doschke]

I already read the rephrased problem, but can't withstand the urge to irregardless post a solution in Foxpro using the inital line "0123456789" in a string variable transformed by code to give a very straight forward solution, which comes to an end as the 21st value will arrive at the start value.

Spoiler

cLine = "0123456789"
For i = 1 to 10
  ? cLine
  cLine = Chrtran(cLine,"0123456789","9876543210") && invert digits
  ? cLine
  cLine = Chrtran(cLine,"9876543210","1234567890") && shift digits
EndFor i
* ? cLine && uncomment this line to see cLine having the initial value after 10 invert and 10 shift operations
* For those not speaking Foxpro, Chrtran takes the first parameter, looks for any charr given in the second parameter and replaces it with the char at the same position in the third parameter, so chrtran is a doing as many single char string replacements as you want in one step. Eg the first chrtran does replace each 0 with a 9, each 1 with an 8, each 2 with a 7, and so on.

* The nice part about it is it simply takes the 3 given lines of the pattern as part of the code. 
* Change that given part of the pattern and input it here, you might only change the number of iterations needed to repeat, 
* but otherwise the code would not need to adapt to a new pattern. Given you have all digits in each line.

This will output

Spoiler

0123456789
9876543210
1234567890
8765432109
2345678901
7654321098
3456789012
6543210987
4567890123
5432109876
5678901234
4321098765
6789012345
3210987654
7890123456
2109876543
8901234567
1098765432
9012345678
0987654321

and would then continue with
0123456789

Bye, Olaf.

 

[vacunita]

I think all the pattern is doing is moving the current first number to the end. The second part of the pattern simply inverts the current pattern.

Without starting with the patterned number in a string, you can do something like this. Language is PHP.

Spoiler

<?php
$max=10;
$collector = array();

for($i=0;$i<=$max-1;$i++)
	{
			$collector[] = $i;
	}
	$string = implode('', $collector);
	echo $string . "<br>";
do
{
	$invString='';
	for($i=count($collector)-1;$i>=0;$i--)
	{
		$invString .= $collector[$i];	
	}
	echo $invString . "<br>";
	$moved = array_shift($collector);
	$newArr = array_push($collector, $moved);
	$string = implode('', $collector);
	
	echo $string . "<br>";
	
}while($collector[0]!=0)



?>

----------------------------------
Phil AKA Vacunita
----------------------------------
Ignorance is not necessarily Bliss, case in point:
Unknown has caused an Unknown Error on Unknown and must be shutdown to prevent damage to Unknown.

Web & Tech

 

[strongm]

Trouble is, Phil, that your code is banned under the rules introduced by mmerlinn's second post, since your for loop essentially builds the same string that I wasn't allowed to use in my initial solution ...

 

[vacunita]

But it builds it on the fly, which is the requirement. mmerlin just did not want you to create a string with the numbers directly in it. And my code does not build a string., it builds an array, which it then uses to loop.

How else would you dynamically build the string then?

----------------------------------
Phil AKA Vacunita
----------------------------------
Ignorance is not necessarily Bliss, case in point:
Unknown has caused an Unknown Error on Unknown and must be shutdown to prevent damage to Unknown.

Web & Tech

 

[SamBones]

I feel like I'm a little late to the party, but here's my solution in C.

The digits being output are a single stream of digits that just happen to get cut to a new line every 10 digits. In other words, the entire set of digits being output is just a single stream pattern. (Not sure if I'm saying that correctly). The pattern is a saw tooth that goes up 10, then down 10, increments by 1, then repeats.

The value of [tt]digit[/tt] goes well above "9", but we only print its value mod 10, so we only get a single digit value.

#include <stdio.h>
#include <stdlib.h>

int main ( int argc, char ** argv )
{
        int     x;
        int     digit           = 0;
        int     direction       = 1;

        for ( x = 0; x < 200; ++x )
                {
                printf("%d", digit % 10);
                if (! ((x+1) % 10))
                        {
                        direction *= -1;
                        if ( direction < 0 ) digit += 1;
                        printf("\n");
                        }
                digit += direction;
                }
}

0123456789
9876543210
1234567890
0987654321
2345678901
1098765432
3456789012
2109876543
4567890123
3210987654
5678901234
4321098765
6789012345
5432109876
7890123456
6543210987
8901234567
7654321098
9012345678
8765432109

 

[SamBones]

Sorry for not "Spoilerizing" my code. It seems unneeded this late in the thread. Apologies if I assumed incorrectly.

 

[strongm]

Phil,

It's not me arguing the toss. I'm more than happy for a fixed or dynamic string or array to be used. But mmerlinn specifically states: "The results must be generated by your code one digit at a time", " No part of the input pattern may be assigned to a variable" and "without assigning any part of the pattern to a string variable.". Your code doesn't follow any of these rules ... perhaps you'd like to join those of us who think the rules are odd.

 

[vacunita]

I'm just trying to understand.


1. The results must be generated by your code one digit at a time: It generates the number one digit at a time in a loop. Once its fully generated there's no reason to generate it again. That would be silly.

2. No part of the input string is assigned to a variable. Technically the variable is dynamically generated. But if you can never have the built string stored anywhere, how do you use the pattern?

3. I only assign the pattern to a string when I need to output.

But o.k, lets try this on for size:

no more spoilers

$top = 10;
$pos=0;
do{
	
	$arrpos=0;
	$arr=array();
	
	for($i=$pos;$i<=($pos + $top)-1;$i++)
	{
		if($i>=10)
		{
			echo $i-10;
			$arr[$arrpos]=$i-10;
			
		}
		else
		{
			echo $i;
			$arr[$arrpos]=$i;
		}
		$arrpos++;
	}
	echo "<br>";
	$invString='';
	for($j=count($arr)-1;$j>=0;$j--)
	{
		$invString .= $arr[$j];	
	}
	echo $invString;
	$pos++;
	echo "<br>";	

}while ($pos<=10)

But yes, the rules are quite odd indeed.

----------------------------------
Phil AKA Vacunita
----------------------------------
Ignorance is not necessarily Bliss, case in point:
Unknown has caused an Unknown Error on Unknown and must be shutdown to prevent damage to Unknown.

Web & Tech