urgent: Mid() in c++

[markman]

im at a programming copetition in c++ and dont know it well. we have 45 mins left for unrestricted practice:

How do I do Mid() in c++?

[The Hobo]

Someone posted an example of this not too long ago. Do a quick search.

[markman]

oh wel, its over now. They disabled our internet access when it started. I finished 2 of the programs, anfd the judges has only one of them work with their data :(

I just started c++ anyways

[SteveCRM]

some type of contest? :confused:

[markman]

yeah. A local university put on a programming contest in C++ or java (you got to choose) and I went as a guest. Only two other people showed up from our school, so I got promoted to a competitor even though I barely know c++. There were 10 probelsm you could do, the one who did the most in the leat amount of time won. The problems had you read a file of a given format, do something with the gathered data, then make an output file. The judges would look at the output file generated by their input file to see if you succeeded. A could of the problems were really tough, like one where you were given a grid in one file:

5
5

(5x5 grid)
and you were supposed to make a spiral of sequencial numbers:

1 2 3 4 5
16 17 18 19 6
15 24 25 20 7
14 23 22 21 8
13 12 11 10 9

(look at the order of the numbers if you are confused)
I got one of them correct, and came close to a hard one, but ran out of time. The winners (who all had 7 correct) each got a Dell laptop and a scholarship to the university.

I got three free floppy disks out of it :D

[SteveCRM]

DAMN THATS A NICE PRIZE!!!!! heh but Im guessing most are college aged with a lot of experience. Thats really cool that you have stuff like that near you :)

how much time were you given? (I really wish they'd have something like this near us!)

oh and congrats on the free floppys :D

[markman]

It was just us high schoolers from around florida. Its a pretty good college (embry-riddle) that deals with mostly aviation, about a 20 min drive.
We had 3 hours to answer 10 problems in colsole applications.

[Alan777]

I posted a question on this a couple of days ago too. Havn't got an answer either but I have managed to work out how to do some of these functions myself. Here is what I have got for doing Mid():


#include <string>
using namespace std;

string Mid(string, long, long);

string Mid(string String, long Start, long Length){

string result;
Start--;
result = String.assign(String, Start, Length);
return result;
}


The reason I have got Start-- is so the first character can be number 1 like in VB.
This works.
This might be a $#!+ way of doing it, but it's hard to get an answer in this forum. Hope it helps.

[flamewavetech]

thats cool, id be satisfied with the floppy disks. especially since i need them to flash my BIOS and im to lazy to go buy one.

[markman]

Id be happier if i got the laptop
The results should be on their webpage; ill try and find it

[Zaei]

I posted several string functions about a month back. Search the forums before posting, or complaining that you dont get answers.

Z.

[markman]

I actually saw those, but didnt use them. Im just wondering if there is a short way to do mid, like the way parksie gave me for split()

[sbasak]

char* mid(char* str,int s,int f)
{
char *nstr;

nstr=str; // store starting address of str in nstr
nstr=str+f; // point to f th position of string
*nstr='\0'; // assign \0 at that position, so indicate end of string by force!
nstr=str; // again store starting address of str in nstr
str=str+s-1;// modify str's starting address to begin from s th position
return str; // return address of str, it now contains required mid string

}

[kedaman]

memcpy should do the trick
target=memcpy (target, source+offset,length);

[CornedBee]

I think string::substr is the same as mid...

[markman]

thanks everyone

(again)
(note thread date) :rolleyes:

[MoMad]

Originally posted by Alan777
I posted a question on this a couple of days ago too. Havn't got an answer either but I have managed to work out how to do some of these functions myself. Here is what I have got for doing Mid():


#include <string>
using namespace std;

string Mid(string, long, long);

string Mid(string String, long Start, long Length){

string result;
Start--;
result = String.assign(String, Start, Length);
return result;
}


The reason I have got Start-- is so the first character can be number 1 like in VB.
This works.
This might be a $#!+ way of doing it, but it's hard to get an answer in this forum. Hope it helps.

Doesnt string class have its own mid?

[MoMad]

Hah, I didnt read the entire thing b4 posting... but anyways, here's a quick mid function (C compliant):


char * Mid (char * dest, const char * src, int start, int length) {
strcpy (dest, src+start);
dest[length] = 0;
return dest;
}

[MoMad]

BTW, its been quite some time... lol

[CornedBee]

Yep. Interesting thing with the number spiral btw...

[plenderj]

Actually I'd be interested to see the code for the spiral.
It looks like a pain in the hole.

I'm guessing it would involve subtracting the (row + column) or something from twenty or some variation or something of that...

[CornedBee]

No, I just built a finite state machine that fill a 2d array, then outputted the array.

Code is attached.

[CornedBee]

I couldn't come up with a formula that gives me the value based on xy-coordinates and table dimensions.

[plenderj]

Actually I wouldn't mind giving that algorithm a go.
Gimme a few minutes :)

[plenderj]

Christ its difficult :eek:

[CornedBee]

Yeah, indeed. I'm sure it's possible, but I have no idea how.

The finite state machine approach is slower but far simpler.

[plenderj]

I think you're doing it the only way it can be done.
You would have to create some algorithm, that simple "goes left", then "goes up" etc.

I can't see how this could be done with loops.
Well, not without a huge number of if statements - in which case you'd be nearly better off just writing out the numbers :rolleyes:

[CornedBee]

No, because it needs to be dynamic. Look at the code I attached (a little bit above). It is the whole code needed to solve that, and the main algorithm contains one for loop, one switch and 4 if. Not that much.

[plenderj]

We've come up with a way of doing with loops sorta.
Illl post the englishy algorithm with pictures in a sec

[plenderj]

Basically, you do it by creating nested squares, and then fill those squares.

So if you had a 3x3 box thang, it'd be :
http://www.everyman.ie/Images/3x3.JPG

So you would go around the outer box, and then go around each nested box.
If the total number of elements is odd, then you will have a square with one element in the middle.
Otherwise, you will have four elements in the middle.
So for a 4x4 box :
http://www.everyman.ie/Images/4x4.JPG

You would go around the outside, counting upwards.
And then move into the inner box, and again, count upwards from the top left.
So you could probably use a recursive function to do the counting in each box and sub box.

[CornedBee]

Problem is, my code is really fast for the method it uses (which has a theoretical difference to your algorithm but no practical), the only good way to speed it up would be a formula that you pass the x and y dimensions and the x and y coordinates and it would return the number there, without loops or such a thing.
Like:
int getatxy(int x, int y, int sizeX, int sizeY);

int i = getatxy(3,3,5,5);
So i would be 25.

This speeds it up because only then you can go line by line left to right and output the data. Any other way and you have to store it in a temporary 2d array (as I did) or use some sort of gotoxy function (which requires stupid calculations where to go).

[plenderj]

I dont think there's a calculation though to work out what the value at position (x, y) would be though...

[jim mcnamara]

Assuming I got what you're discussing -- for an iterative approach
start with this spiral algorithm:


#define K1 1 // constant ... <1 slows growth >1 speeds growth of radius
#define TRANSFORM 1 // transform to origin = 360, 360
#define VALUE 360
void spiral(double *x, double *y, double theta){
double radius;
radius = K1 * exp( ( M_E * theta) / (2 * M_PI) );
*x=cos(theta)*radius;
*y=sin(theta)*radius;
if(TRANSFORM){
*y+=VALUE;
*x+=VALUE;
}
return;
}


usage:

max=*M_PI;
double x,y;
for(x=0,y=0,theta=0;theta<4*M_PI;theta+=.01,plot(x,y));

plot() draws the point on the device.

CB's method would be better than this one for a fibonacci spiral - IMO.

[MoMad]

Wow, and how long did you have to do this again?? Lemme see if i can come up with something without copying or looking at anyone's code



[danm, no formula, the array method is sooooo much simpler]
-- and all i could come up with...

[CornedBee]

jim, no you misunterstood this. The problem we're trying to solve is stated somewhere early in this thread. It goers like this.

Read in two integers a,b. Then output a table with dimensions axb with the fields filled with increasing numbers starting at 1, going around the box in a spiral.
E.g. if the input is 5, 6 then output

1 2 3 4 5
18 19 20 21 6
17 28 29 22 7
16 27 30 23 8
15 26 25 24 9
14 13 12 11 10


This must work for any a and b entered (except of course if it goes so far to the right that it automatically goes to the next line)

[kedaman]

there's 4 quadrants in the spiral in which the numbers are incrementing in 4 different directions. I decide to call them A,B,C and D in the order they are passed trough from start. A the top quadrant, B the right C the bottom D the left. My function f(x,y) retrieves the value in the incrementing spiral depending on in which quadrant, which revolution and the position in the quadrant relative to just passed corner.

To efficiently determine quadrant we first determine the excentricity of the rectangle e=W>H, the smaller side quadrants should be triangle shaped while the larger side quadrant should be trapezoids, and it would be easier to determine if it were in the triangles first and then determine which side of the half of the rectangle if not in the triangles. The special case when theres a hole in the middle E, when W and H are not even is left when all else fails.
The quadrant Q(x,y)={
if not e:
A if |floor((W-1)/2)|-y<=floor((W-1)/2)
C if |floor(W/2)|+y-H+1<=floor(W/2)
B if x>ceil(W/2)
D if x<floor(W/2)
E if none of the above
if e:
B if |floor((H-1)/2)|+x-W+1<=floor((H-1)/2)
D if |floor(H/2)|-x<=floor(H/2)
B if y>ceil(W/2)
D if y<floor(W/2)
E if none of the above
}
A and C side length are W-1 decrementing with 2 each revolution
similarly B and D are H-1-2R
each full revolution is thus 2(H+W)-8R, and the cumulative sum is
2R(H+W)-8*sumof(R)=2(H+W)-4R(R-1)
The revolution R for the quadrants are
y for A
W-x-1 for B
H-y-1 for C
x for D
and the position P is
x-y for A
y-W+x for B
W-x+y for C
H-y-x for D
The value should be 2R(H+W)-8*sumof(R)=2(H+W)-4R(R-1) + S + P
where S=
0 for A
W-1-2R for B
W+H-2-2R for C
2W+H-3-2R for D

[plenderj]

But surely you're assuming the dimensions of the grid ?

[kedaman]

forgot to mention, W and H are the grid dimensions, f(x,y) should be W*H for E obviously

[CornedBee]

My head is spinning.

What would that mean in code?

[kedaman]

lots of ifs and stuff, I think writing it in SQ would look considerably cleaner and consise

[kedaman]

lots of ifs and stuff, I think writing it in SQ would look considerably cleaner, readable and consise

[jim mcnamara]

CB - you're right.

But - other than for pedagogy what practical app is this?
I've used Reynolds numbers for spiral flow, and Ulam's prime number spiral for fun (this looks like it's a relative).

Here's a picture and discussion of a prime number spiral with a box created somewhat the way these are.

http://hermetic.nofadz.com/pns/pns.htm

[CornedBee]

Pure pedagogy. It was invented for it. I just thought it's an interesting problem.

[kedaman]

maybe it makes sense looking at a visual example, so i drawed this (was drawn first on paper when i tried to solve the problem)