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]

Ah - and now you'll see that you've pretty much come up with the exact same solution as the rest of us. Which comes as no surprise, since the restated rules give little opportunity for anything much different, and why I don't really think that this ended up being a test "to determine how well they can visualize and code on the fly"

I think it would be interesting to hear mmerlinn's response to kwbMitel's question of 4th May

 

[SamBones]

I think my solution is unique in it's approach from the others submitted. Every solution submitted either has two inner loops to deal with the reversed pattern, or there is a string reverse function called to print it.

My solution outputs a single stream of characters, each one calculated from only the previous character.

[tt]0123456789987654321012345678900987654321234567890110987...[/tt]

But then inserts a return after every 10 characters, giving this...

[tt]0123456789
9876543210
1234567890
0987654321
2345678901
10987...[/tt]

The pattern I see is a triangle wave that is increasing by 1 every cycle, passed through a mod 10 filter. The output grouping by 10 is just for readability.

 

[strongm]

Indeed, SamBones - and should certainly score something for originality. Mind you it only really works as long as the pattern is not one of kwbMittel's legitimate alternatives. All of the looping solutions should be able to deal with those with very minor changes.

Still awaiting further feedback from mmerlinn

 

[SamBones]

Well, any time there's ambiguity in the specs, you have to either get clarification, or make assumptions.

This could also be the fourth number in the sequence: 8888888888

I have a sequence rule in mind where that would be a valid next value.

This reminds me of this:

http://www.youtube.com/watch?v=vKA4w2O61Xo

 

[strongm]

Well, that one was easy ...

 

[ChrisHirst]

Okay then, tempted in by this forum appearing in the "top discussions" I thought I'd throw in a quick and sort of 'dirty' offering in Python.

#! /usr/bin/env python
SEED = "0123456789"
sfwd = SEED
done = 0
while True:
	srev = sfwd[::-1]
	print(sfwd)
	print(srev)
	s = sfwd[0]
	sfwd = sfwd[1:] + s
	if SEED == sfwd:
		print(sfwd)
		break

# quit()

Chris.

Indifference will be the downfall of mankind, but who cares?
Time flies like an arrow, however, fruit flies like a banana.
Webmaster Forum

 

[kwbMitel]

@Sambones

Re:each one calculated from only the previous character

I like your solution but your description is not as simple as you make it out to be. Your pattern needs to track through 20 characters and then do a shift by not duplicating the previous number as you would after 10 characters. Basically you also have 2 loops, one keeping track of the character count and 1 generating a new number based on the previous number.

I've highlighted in Yellow where you duplicate and in Green where you dont

012345678[highlight #FCE94F]99[/highlight]87654321[highlight #8AE234]0[/highlight]123456789[highlight #FCE94F]00[/highlight]98765432[highlight #8AE234]1[/highlight]234567890[highlight #FCE94F]11[/highlight]0987

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

 

[SamBones]

Basically you also have 2 loops...

True, I may have simplified my description, but there is only one loop. Generating the next character is just incrementing or decrementing the previous character. The one keeping track of the character count decides (after every 10) whether to change direction, print a new line, and whether it needs to increment the number by one (which gives us our shift due to the digit being printed modulo 10).

I'm not sure what you're saying about duplicating or not. That looks correct to me and matched the other expected sequences (not taking into account the "alternate" sequences suggested). The duplication is the start of the reversal of the previous 10. The non-duplication is the start of the next character cycle where a character has been shifted. That matches what's displayed when only 10 characters are displayed per line.

I'm wondering if it could be generalized to a function that takes the offset into the sequence as an input, and outputs the digit at that position.

 

[SamBones]

Ok, I've generalized the formula for calculating any digit within the sequence, just based on it's offset.

#include <stdio.h>

int     thedigit(int);

int main ( int argc, char ** argv )
{
        int     x;

        for ( x = 0; x < 200; ++x )
                {
                printf("%d", thedigit(x));

                if (! ((x+1) % 10)) printf("\n");
                }
}

int thedigit( int offset )
{
        int     decade = (int) (offset / 10);

        return( decade % 2 ? ((9 + ((decade - 1)/2)) - (offset % 10)) % 10 : ((decade / 2) + (offset % 10)) % 10 );
}

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

 

[kwbMitel]

@Sambones, I can see were your going now but you can understand me questioning a number being "calculated from only the previous character".

The directionality of the change govenrns whether you repeat a digit after the line feed or change the digits. Directionality cannot be determined by only the previous character.

Assume for a moment that the actual pattern is to take the digit in the first position and shift it to the end. Can your method be modified to accomodate that sequence?

It would need to look like this.

012345678998765432101234567890876543210923456789017654321098


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

 

[ChrisHirst]

Assume for a moment that the actual pattern is to take the digit in the first position and shift it to the end. Can your method be modified to accomodate that sequence?

So my python solution wasn't that 'dirty' after all

and if you would want it to repeat the sequences continuously (without line breaks).

#! /usr/bin/env python
import sys

SEED = "0123456789"
sfwd = SEED
while True:
	srev = sfwd[::-1]
	sys.stdout.write(sfwd)
	sys.stdout.write(srev)
	s = sfwd[0]
	sfwd = sfwd[1:] + s

Sample output

01234567899876543210123456789009876543212345678901109876543234567890122109876543456789012332109876545678901234432109876567890123455432109876789012345665432109878901234567765432109890123456788765432109012345678998765432101234567890098765432123456789011098765432345678901221098765434567890123321098765456789012344321098765678901234554321098767890123456654321098789012345677654321098901234567887654321090123456789987654321012345678900987654321234567890110987654323456789012210987654345678901233210987654567890123443210987656789012345543210987678901234566543210987890123456776543210989012345678876543210901234567899876543210123456789009876543212345678901109876543234567890122109876543456789012332109876545678901234432109876567890123455432109876789012345665432109878901234567765432109890123456788765432109012345678998765432101234567890098765432123456789011098765432345678901221098765434567890123321098765456789012344321098765678901234554321098767890123456654321098789012345677654321098901234567887654321090123456789987654321012345678900987654321234567890110987654323456789012210987654345678901233210987654567890123443210987656789012345543210987678901234566543210987890123456776543210989012345678876543210901234567899876543210123456789009876543212345678901109876543234567890122109876543456789012332109876545678901234432109876567890123455432109876789012345665432109878901234567765432109890123456788765432109012345678998765432101234567890098765432123456789011098765432345678901221098765434567890123321098765456789012344321098765678901234554321098767890123456654321098789012345677654321098901234567887654321090123456789987654321012345678900987654321234567890110987654323456789012210987654345678901233210987654567890123443210987656789012345543210987678901234566543210987890123456776543210989012345678876543210901234567899876543210123456789009876543212345678901109876543234567890122109876543456789012332109876545678901234432109876567890123455432109876789012345665432109878901234567765432109890123456788765432109012345678998765432101234567890098765432123456789011098765432345678901221098765434567890123321098765456789012344321098765678901234554321098767890123456654321098789012345677654321098901234567887654321090123456789987654321012345678900987654321234567890110987654323456789012210987654345678901233210987654567890123443210987656789012345543210987678901234566543210987890123456776543210989012345678876543210901234567899876543210123456789009876543212345678901109876543234567890122109876543456789012332109876545678901234432109876567890123455432109876789012345665432109878901234567765432109890123456788765432109012345678998765432101234567890098765432123456789011098765432345678901221098765434567890123321098765456789012344321098765678901234554321098767890123456654321098789012345677654321098901234567887654321090123456789987654321012345678900987654321234567890110987654323456789012210987654345678901233210987654567890123443210987656789012345543210987678901234566543210987890123456776543210989012345678876543210901234567899876543210123456789009876543212345678901109876543234567890122109876543456789012332109876545678901234432109876567890123455432109876789012345665432109878901234567765432109890123456788765432109012345678998765432101234567890098765432123456789011098765432345678901221098765434567890123321098765456789012344321098765678901234554321098767890123456654321098789012345677654321098901234567887654321090123456789987654321012345678900987654321234567890110987654323456789012210987654345678901233210987654567890123443210987656789012345543210987678901234566543210987890123456776543210989012345678876543210901234567899876543210123456789009876543212345678901109876543234567890122109876543456789012332109876545678901234432109876567890123455432109876789012345665432109878901234567765432109890123456788765432109012345678998765432101234567890098765432123456789011098765432345678901221098765434567890123321098765456789012344321098765678901234554321098767890123456654321098789012345677654321098901234567887654321090123456789987654321012345678900987654321234567890110987654323456789012210987654345678901233210987654567890123443210987656789012345543210987678901234566543210987890123456776543210989012345678876543210901234567899876543210123456789009876543212345678901109876543234567890122109876543456789012332109876545678901234432109876567890123455432109876789012345665432109878901234567765432109890123456788765432109012345678998765432101234567890098765432123456789011098765432345678901221098765434567890123321098765456789012344321098765678901234554321098767890123456654321098789012345677654321098901234567887654321090123456789987654321012345678900987654321234567890110987654323456789012210987654345678901233210987654567890123443210987656789012345543210987678901234566543210987890123456776543210989012345678876543210901234567899876543210123456789009876543212345678901109876543234567890122109876543456789012332109876545678901234432109876567890123455432109876789012345665432109878901234567765432109890123456788765432109012345678998765432101234567890098765432123456789011098765432345678901221098765434567890123321098765456789012344321098765678901234554321098767890123456654321098789012345677654321098901234567887654321090123456789987654321012345678900987654321234567890110987654323456789012210987654345678901233210987654567890123443210987656789012345543210987678901234566543210987890123456776543210989012345678876543210901234567899876543210123456789009876543212345678901109876543234567890122109876543456789012332109876545678901234432109876567890123455432109876789012345665432109878901234567765432109890123456788765432109012345678998765432101234567890098765432123456789011098765432345678901221098765434567890123321098765456789012344321098765678901234554321098767890123456654321098789012345677654321098901234567887654321090123456789987654321012345678900987654321234567890110987654323456789012210987654345678901233210987654567890123443210987656789012345543210987678901234566543210987890123456776543210989012345678876543210901234567899876543210123456789009876543212345678901109876543234567890122109876543456789012332109876545678901234432109876567890123455432109876789012345665432109878901234567765432109890123456788765432109012345678998765432101234567890098765432123456789011098765432345678901221098765434567890123321098765456789012344321098765678901234554321098767890123456654321098789012345677654321098901234567887654321090123456789987654321012345678900987654321234567890110987654323456789012210987654345678901233210987654567890123443210987656789012345543210987678901234566543210987890123456776543210989012345678876543210901234567899876543210123456789009876543212345678901109876543234567890122109876543456789012332109876545678901234432109876567890123455432109876789012345665432109878901234567765432109890123456788765432109012345678998765432101234567890098765432123456789011098765432345678901221098765434567890123321098765456789012344321098765678901234554321098767890123456654321098789012345677654321098901234567887654321090123456789987654321012345678900987654321234567890110987654323456789012210987654345678901233210987654567890123443210987656789012345543210987678901234566543210987890123456776543210989012345678876543210901234567899876543210123456789009876543212345678901109876543234567890122109876543456789012332109876545678901234432109876567890123455432109876789012345665432109878901234567765432109890123456788765432109012345678998765432101234567890098765432123456789011098765432345678901221098765434567890123321098765456789012344321098765678901234554321098767890123456654321098789012345677654321098901234567887654321090123456789987654321012345678900987654321234567890110987654323456789012210987654345678901233210987654567890123443210987656789012345543210987678901234566543210987890123456776543210989012345678876543210901234567899876543210123456789009876543212345678901109876543234567890122109876543456789012332109876545678901234432109876567890123455432109876789012345665432109878901234567765432109890123456788765432109012345678998765432101234567890098765432123456789011098765432345678901221098765434567890123321098765456789012344321098765678901234554321098767890123456654321098789012345677654321098901234567887654321090123456789987654321012345678900987654321234567890110987654323456789012210987654345678901233210987654567890123443210987656789012345543210987678901234566543210987890123456776543210989012345678876543210901234567899876543210123456789009876543212345678901109876543234567890122109876543456789012332109876545678901234432109876567890123455432109876789012345665432109878901234567765432109890123456788765432109012345678998765432101234567890098765432123456789011098765432345678901221098765434567890123321098765456789012344321098765678901234554321098767890123456654321098789012345677654321098901234567887654321090123456789987654321012345678900987654321234567890110987654323456789012210987654345678901233210987654567890123443210987656789012345543210987678901234566543210987890123456776543210989012345678876543210901234567899876543210123456789009876543212345678901109876543234567890122109876543456789012332109876545678901234432109876567890123455432109876789012345665432109878901234567765432109890123456788765432109012345678998765432101234567890098765432123456789011098765432345678901221098765434567890123321098765456789012344321098765678901234554321098767890123456654321098789012345677654321098901234567887654321090123456789987654321012345678900987654321234567890110987654323456789012210987654345678901233210987654567890123443210987656789012345543210987678901234566543210987890123456776543210989012345678876543210901234567899876543210123456789009876543212345678901109876543234567890122109876543456789012332109876545678901234432109876567890123455432109876789012345665432109878901234567765432109890123456788765432109012345678998765432101234567890098765432123456789011098765432345678901221098765434567890123321098765456789012344321098765678901234554321098767890123456654321098789012345677654321098901234567887654321090123456789987654321012345678900987654321234567890110987654323456789012210987654345678901233210987654567890123443210987656789012345543210987678901234566543210987890123456776543210989012345678876543210901234567899876543210123456789009876543212345678901109876543234567890122109876543456789012332109876545678901234432109876567890123455432109876789012345665432109878901234567765432109890123456788765432109012345678998765432101234567890098765432123456789011098765432345678901221098765434567890123321098765456789012344321098765678901234554321098767890123456654321098789012345677654321098901234567887654321090123456789987654321012345678900987654321234567890110987654323456789012210987654345678901233210987654567890123443210987656789012345543210987678901234566543210987890123456776543210989012345678876543210901234567899876543210123456789009876543212345678901109876543234567890122109876543456789012332109876545678901234432109876567890123455432109876789012345665432109878901234567765432109890123456788765432109012345678998765432101234567890098765432123456789011098765432345678901221098765434567890123321098765456789012344321098765678901234554321098767890123456654321098789012345677654321098901234567887654321090123456789987654321012345678900987654321234567890110987654323456789012210987654345678901233210987654567890123443210987656789012345543210987678901234566543210987890123456776543210989012345678876543210901234567899876543210123456789009876543212345678901109876543234567890122109876543456789012332109876545678901234432109876567890123455432109876789012345665432109878901234567765432109890123456788765432109012345678998765432101234567890098765432123456789011098765432345678901221098765434567890123321098765456789012344321098765678901234554321098767890123456654321098789012345677654321098901234567887654321090123456789987654321012345678900987654321234567890110987654323456789012210987654345678901233210987654567890123443210987656789012345543210987678901234566543210987890123456776543210989012345678876543210901234567899876543210123456789

I'll let somebody else count the iterations

Chris.

Indifference will be the downfall of mankind, but who cares?
Time flies like an arrow, however, fruit flies like a banana.
Webmaster Forum

 

[strongm]

>So my python solution wasn't that 'dirty' after all

Nope - pretty much the same as my initial solution, but deemed illegal given the revised conditions provided by mmerlinn

Unfortunately

SEED = "0123456789"

breaches

>No part of the input pattern may be assigned to a variable
>results must be entirely generated by the code, one digit at a time, without starting with any fixed variable(s).

 

[ChrisHirst]

That's no big deal

Python password generator for you.

import string
import random
SEED = ''.join(random.choice(string.letters + string.digits) for _ in range(10))

Chris.

Indifference will be the downfall of mankind, but who cares?
Time flies like an arrow, however, fruit flies like a banana.
Webmaster Forum

 

[SamBones]

kwbMitel, I agree with you completely. I should never use absolutes like "only".

My statement about only calculating from the previous character was incorrect. It was actually using three things, previous character, offset into sequence, and current direction. But I have now shown that you can calculate any character based solely on it's position within the sequence.

So, the rules are...

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

[ol ]
[li]One digit at a time, check![/li]
[li]String variables only for output. I don't use any, so check![/li]
[li]No part of the input pattern may be assigned to a variable. I don't use an "input pattern", so check![/li]
[li]Results must be generated one digit at a time. Definitely! Check![/li]
[li]...without starting with any fixed variables. Definitely! Check![/li]
[/ol]

I think I hit them all!

 

[CajunCenturion]

@mmerlinn - So who got the job?

--------------
Good Luck
To get the most from your Tek-Tips experience, please read
FAQ181-2886
Wise men speak because they have something to say, fools because they have to say something. - Plato

 

[strongm]

I think we've scared them off

 

[kwbMitel]

So, rather than post my code for my solution (which would be archaic for those here) I will instead post my logic that could easily be converted into code

Using the 3 lines provided for reference

Reference line 3
Line 4 = subtract line 3 from 9999999999
Line 5 = Increment each digit of line 3 by 1 and Truncate left digit if >=10
Repeat until line 21 = 01234567890

Now would you like to see that using basic? I'm sure I could dig out my manual.

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

 

[lionelhill]

I'm also late to the party, but I'm going to have a moan.

It's a nice puzzle, but I'm worried that puzzles like this won't recruit the best and most creative staff (well, depending on the job, at least). What the question really asks is "Who thinks most like me?". If you want a problem-solver, it's best to make sure that the constraints are only real ones, not artificial ones. If someone can solve your problem in a way you didn't expect, and which is more elegant than your thought, employ them quickly! They may outshine you sometimes, but they'll make your product better than you could!

Of course there are real constraints in the real world that are actually annoyingly rubbish. If the boss insists on Fortran, that is a constraint. If the database only accepts files with the extension .hiThere and written in binary spelled out as text, backwards, then even though it's utterly stupid, the good employee must do the task (possibly hinting that it's ripe for an overhaul).

I'm also worried about next-number-in-the-sequence problems. These were certainly very popular in IQ tests when I was little, but that was before the online encyclopedia of integer series. If you take a typical IQ test of 30 years ago and enter the numers in OEIS, it frequently comes up with huge numbers of logical continuations. The problem with this sort of puzzle is that it tests the IQ of the tester, as much as the testee: it tests how far they can find a series that, with their limitations, appears to have only one continuation. An infinitely intelligent life-form from outer-space will always fail because there are an infinte number of continuations.

There is also a comment from Michael Abrash, I think, complaining that true coders leap in to a problem far too fast, realising they can see a solution, and often missing a much better solution that requires a more detailed think.

Sorry to be a grumpy old man, but I think recruitment is soooo important that it's vital to be careful how it is done. And thanks for the puzzle anyway!

 

[ChrisHunt]

What I would look for in a coder when dealing with this problem is that they should challenge this statement:

Everything you need to know is posted above. There should be no reason for me to answer any questions

If all they're given is a minimal list of desired outputs and no real guidance as to how those outputs have been produced, they should be demanding a proper spec - rather than guessing at what might be wanted and rushing to provide it.

If the required functionality isn't explicitly laid out in the spec, how will anyody test it to make sure it's working?

-- Chris Hunt
Webmaster & Tragedian
Extra Connections Ltd

 

[lionelhill]

Yes, ChrisHunt. Misunderstandings are at the root of nearly all disasters. I would bet half a Mars-bar that nearly all big IT catastrophes that end up costing the public sector millions and get on the front page of newspapers (and probably also the private sector equivalents) are because someone didn't specify what was needed exactly enough, leading to a realisation mid-project that different people had different specifications in mind, and some people's aims were not going to fulfil what the project was actually supposed to do (in Layman's terms), leading to sudden "changes" in specification mid-project, which in turn leads to escalating costs as different teams find that they've been working at cross-purposes and now need to re-do old things, and develop work-arounds to deal with differences of opinion that they didn't expect, and also need to tackle whole new problems of which they hadn't been aware...

Having seen a few database developers in action, the best ones (I think) are the ones who keep on calmly asking what the point of the database is, what the users are trying to do, and how they currently do it, until both sides have agreed expectations. This often involves the users learning quite a lot about their own job, and realising that their data and working practices are quite different to what they thought! It takes considerable interpersonal skills as well as a good ability to combine overview of a complex problem with understanding of its nitty-gritty detail; an ability to observe and understand current approaches, but not be limited by them unnecessarily. I don't think many people can do it.