Iterating through array and shift elements to the end of the array

Question

I'm trying to implement a simple game where the array symbolizes people standing in a circle, drawing an integer at the beginning of the game. each iteration is the size of the integer and removes people from the game.

so if array[]={a,b,c,d} and integer=3; c is the first to be removed. Then b , then d. the winner is a. at the end I need to print the array with the results by order of removal. so the printed array should be: a, d, b, c. I'm trying to accomplish this only with use of pointers with no additional arrays.

Here's what i got, the problem is i'm trying to restart the for loop from the correct index and iterate through the remaining players who have not yet lost and cant get it right:

char *names[] = {"Tyrion Lannister","Daenerys Targaryen","Jon Snow","Arya Stark","Theon Greyjoy", "Joffrey Baratheon","Khal Drogo","Ted Mosby","Marshall Eriksen","Robin Scherbatsky","Barney Stinson", "Lily Aldrin", "Tracy McConnell", "Ted Mosby", "Leonard Hofstadter","Sheldon Cooper", "Penny", "Howard Wolowitz", "Raj Koothrappali", "Bernadette Rostenkowski-Wolowitz","Amy Farrah Fowler", "Gregory House", "Lisa Cuddy", "James Wilson","Eric Foreman", "Allison Cameron", "Robert Chase" ,"Lawrence Kutner", "Chris Taub","Remy 13 Hadley", "Amber Volakis"};
int Length = 31;
int number = 10;
char *tmp;
int i = 0, j;
int boom = number;
for (int i = number - 1; i < Length; i += boom - 1)
{

    tmp = *(names + i);

    for (int index = i; index < Length - 1; index++)
    {
        *(names + index) = *(names + index + 1);
    }

    *(names + Length - 1) = tmp;


    Length--;
    if (((number - 1) + i) >= Length)
    {
        int tempIndex = i;
        i = tempIndex - Length;
        printf("tmep index is %d, i is %d, Length is %d\n", tempIndex, i, Length);
    }
}
for (i = 0; i < 31; i++)
    printf("%s\n", names[i]);

I also tried another way with % operator, but couldn't quite get it done. Help would be much appreciated:

for (int i = number - 1; i < Length * (number - 1); i += boom - 1)  
{
    int t = i % Length;
    printf("%d\n", t);
    if (t < size)
    {
        counter++;
        tmp = *(names + t);
        // tmptwo = *(names + 31 - j);
        for (int index = t; index < size - 1; index++)
        {
            *(names + index) = *(names + index + 1);
        }

        *(names + size - 1) = tmp;
        size--;
        printf("size %d\n", size);
    }
}

"Standing in circle" - sounds like some unused piece of information. — Eugene Sh.
– Eugene Sh., Commented Dec 14, 2018 at 21:02
Unrelated to your problem, but for any pointer or array a and index i, the expression *(a + i) is exactly equal to a[i]. The latter is usually easier to understand, and a couple of characters less to write. That means that e.g. *(names+index)=*(names+index+1) is equal to names[index] = names[index+1]. — Some programmer dude
– Some programmer dude, Commented Dec 14, 2018 at 21:08
As a side note - don't try to save memory (not using extra arrays) at a cost of program complexity and readability. Well, unless it becomes an issue, but that's not your case. — Eugene Sh.
– Eugene Sh., Commented Dec 14, 2018 at 21:12
It's a class exercise focusing on pointers. no additional arrays are allowed , and no array syntax as well ( [ ]) — user2023203
– user2023203, Commented Dec 14, 2018 at 21:17
To be honest, considering that any sane compiler would turn array syntax (e.g. a[i]) into pointer arithmetic (as in *(a + i)) not being allowed to use the array variant is kind of useless and a waste of good typing (IMO) :) Tell your teacher that! — Some programmer dude
– Some programmer dude, Commented Dec 14, 2018 at 23:47

David C. Rankin · Accepted Answer · 2018-12-15 01:44:11Z

You are thinking along the correct lines, but this is one circumstance where declaring and defining a simple function to shift elements down within an array moving the losing index to the end will simplify your life. By doing it this way, your only chores within the body of your code will be to provide the losing index and keeping track of the live number of players that remain with a simple counter.

An implementation of a function to move a given index to the last index for a given size could be similar to the following where a is the array to be reordered, elem_idx is the element index to move to the last element within sz elements:

void element_to_last (int *a, int elem_idx, int sz)
{
    if (elem_idx > sz - 1) {    /* valdate index in range */
        fprintf (stderr, "error: index %d out of range for size %d\n",
                elem_idx, sz);
        return;
    }

    int i = elem_idx,   /* declare, initialize i, tmp */
        tmp = *(a + i);

    if (elem_idx == sz - 1)     /* elem_idx is last index */
        return;     /* no-swap */

    for (; i < sz - 1; i++)     /* loop shifting elements down */
        *(a + i) = *(a + i + 1);

    *(a + i) = tmp;     /* set last to tmp */
}

(note: you will want to validate the element index to move to the end is within the valid range of indexes, and there is no need to perform the swap if the losing index is already the last in range).

A short working example where the WRAP constant simply controls output of no more than WRAP values per-line when printing results and the added DEBUG define allows outputting of additional information showing each operation if -DDEBUG is included in your compile string, e.g.

#include <stdio.h>

#ifndef WRAP
 #define WRAP 10
#endif

void element_to_last (int *a, int elem_idx, int sz)
{
    if (elem_idx > sz - 1) {    /* valdate index in range */
        fprintf (stderr, "error: index %d out of range for size %d\n",
                elem_idx, sz);
        return;
    }

    int i = elem_idx,   /* declare, initialize i, tmp */
        tmp = *(a + i);

    if (elem_idx == sz - 1) {   /* elem_idx is last index */
#ifdef DEBUG
        fprintf (stderr, " index %d (%d) is last index %d - no swap.\n",
                elem_idx, tmp, sz - 1);
#endif
        return;     /* no-swap */
    }

#ifdef DEBUG
    printf (" index %d (%d) to end %d\n", elem_idx, tmp, sz - 1);
#endif

    for (; i < sz - 1; i++)     /* loop shifting elements down */
        *(a + i) = *(a + i + 1);

    *(a + i) = tmp;     /* set last to tmp */
}

void prn_array (int *a, int sz, int wrap)
{
    for (int i = 0; i < sz; i++) {
        if (i && i % wrap == 0)
            putchar ('\n');
        printf (" %2d", *(a + i));
    }
    putchar ('\n');
}

int main (void) {

    int a[] = {0,1,2,3,4,5,6,7,8,9},    /* original array order */
        sz = sizeof a/sizeof *a,        /* nelem in original */
        n = sz,                         /* n tracks remaining size */
        loser[] = {2,0,7,3,2,3,2,1,1},  /* order of losing indexes */
        lsz = sizeof loser/sizeof *loser;   /* nelem in loser array */

    puts ("before:");
    prn_array (a, sz, WRAP);

    puts ("\nelimination\n(remove indexes 2,0,7,3,2,3,2,1,1):");
    for (int i = 0; i < lsz; i++) {
        element_to_last (a, loser[i], n > 0 ? n-- : n);
        prn_array (a, sz, WRAP);
    }

    puts ("\nafter:");
    prn_array (a, sz, WRAP);
}

(note: the remaining players, e.g. the remaining number of elements is tracked with n while sz preserves the original size of the full array. lsz is used for the size of the loser array)

Example Use/Output

Without DEBUG defined, the output simply shows the state of the array after a loser is moved to the end of the remaining players:

$ ./bin/array_rotate
before:
  0  1  2  3  4  5  6  7  8  9

elimination
(remove indexes 2,0,7,3,2,3,2,1,1):
  0  1  3  4  5  6  7  8  9  2
  1  3  4  5  6  7  8  9  0  2
  1  3  4  5  6  7  8  9  0  2
  1  3  4  6  7  8  5  9  0  2
  1  3  6  7  8  4  5  9  0  2
  1  3  6  8  7  4  5  9  0  2
  1  3  8  6  7  4  5  9  0  2
  1  8  3  6  7  4  5  9  0  2
  1  8  3  6  7  4  5  9  0  2

after:
  1  8  3  6  7  4  5  9  0  2

DEBUG Output

With DEBUG defined, additional information showing each index and (value) being moved to the end index shown, along with a note whether then end index was the loser in which case "no-swap" was attempted:

$ ./bin/array_rotate
before:
  0  1  2  3  4  5  6  7  8  9

elimination
(remove indexes 2,0,7,3,2,3,2,1,1):
 index 2 (2) to end 9
  0  1  3  4  5  6  7  8  9  2
 index 0 (0) to end 8
  1  3  4  5  6  7  8  9  0  2
 index 7 (9) is last index 7 - no swap.
  1  3  4  5  6  7  8  9  0  2
 index 3 (5) to end 6
  1  3  4  6  7  8  5  9  0  2
 index 2 (4) to end 5
  1  3  6  7  8  4  5  9  0  2
 index 3 (7) to end 4
  1  3  6  8  7  4  5  9  0  2
 index 2 (6) to end 3
  1  3  8  6  7  4  5  9  0  2
 index 1 (3) to end 2
  1  8  3  6  7  4  5  9  0  2
 index 1 (8) is last index 1 - no swap.
  1  8  3  6  7  4  5  9  0  2

after:
  1  8  3  6  7  4  5  9  0  2

Look things over and let me know if you have further questions.

Bregell · Accepted Answer · 2018-12-16 03:25:12Z

0

This code should solve the problem by using modulo.

int size = 31;
int inc = 10;

for (int i = 0; i < size; i++)
{
    int t = ((i + 1) * inc) % (size - i);
    int *tmp = *(names + t);
    printf("%d\n", t);

    for (int j = t; j < (size - 1); j++)
    {
        *(names + j) = *(names + j + 1);
    }

    *(names + size - 1) = tmp;
}

edited Dec 16, 2018 at 3:25

answered Dec 14, 2018 at 23:57

Bregell

13910 bronze badges

Collectives™ on Stack Overflow

Iterating through array and shift elements to the end of the array

2 Answers 2

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related