Facing problem while solving Josephus Problem in BASH

unclesamcrazy · 05-13-2015, 03:12 AM

I want to solve this question using BASH

100 people standing in a circle in an order 1 to 100. No. 1 has a sword. He kills the next person (i.e. No. 2) and gives the sword to the next (i.e. No. 3). All people do the same until only 1 survives. Which number survives at the last?

If input is taken by keyboard, it should print the saved person number. Not only for hard coded 100 person.

Suppose I enter 5 as user input, it should print "3 is safe".
if I enter 11, it should print "7 is safe".
Please help me to write this script.

Thanks

chrism01 · 05-13-2015, 04:54 AM

We're not going to write this for you, but we WILL help you write it.
Show us what you've written so far and what you think the problem is and we'll help you.
Have you read any good tutorials; there are plenty on the web.
You could look at this one http://rute.2038bug.com/index.html.gz

unclesamcrazy · 05-14-2015, 09:35 AM

I am using array but I am not getting correct results.

Code:

#!/bin/bash
arrayName=(1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20)
var=$(echo "${#arrayName[@]}")
i=1
while :
do
sleep 2
unset arrayName[$i]
i=`expr $i + 2`
if [ $i -gt $var ]
then
var=$(echo "${#arrayName[@]}")
i=1
fi
done
echo "${arrayName[@]}"

millgates · 05-14-2015, 07:28 PM

Hi, just a few minor suggestions:
1/ I would suggest that you use proper indentation to make the code more readable.
2/ When debugging shell scripts, it is a good idea to put set -xv at the begining of the script. That will allow you to follow each step the script does.
3/ When describing your problem, be more specific than "It doesn't work" or "I'm not getting correct results". What exactly does not work? What results are you getting and what results do you expect?
4/

Code:

arrayName=(1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20)

You can use brace expansion here:

Code:

arrayName=({1..20})

5/

Code:

var=$(echo "${#arrayName[@]}")

That's a very useless use of echo. just do

Code:

var="${#arrayName[@]}"

6/

Code:

while :

That's an infinite loop. Please make sure that the loop exits when its purpose is achieved.
7/

Code:

unset arrayName[$i]

I would recommend putting "arrayName[$i]" within double quotes to avoid pathname expansion. Also, keep in mind unsetting an array member will not reset numbering of the other elements.
8/

Code:

i=`expr $i + 2`

better written as

Code:

i=$(expr $i + 2)

or, even better

Code:

((i+=2))

9/

Code:

i=1

Don't forget array indices start at 0 in bash.
10/ I'll leave fixing the remaining flaws in the logic of the program as an exercise for the original poster.

unclesamcrazy · 05-15-2015, 01:53 AM

Thanks for guidance, my mistake I did not paste the code in my question. First I wrote this code

Code:

#!/bin/bash
arrayName=({1..20})
var="${#arrayName[@]}"
echo $var
i=1
while [ $var -gt $i ]
do
unset arrayName[$i]
i=`expr $i + 2`
done
echo "${arrayName[@]}"

but it removes the alternate array values only once, I need to keep removing alternate values until only one remains.
I am facing problem in this part. I want to keep the loop alive but not for ever.
Please help

millgates · 05-15-2015, 02:35 AM

Quote:

Originally Posted by unclesamcrazy

until only one remains.

So, how do you say the same thing using a math expression?

unclesamcrazy · 05-15-2015, 04:30 AM

I would remove them alternatively until I get the answer.

Quote:

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

but not able to find, how to do it using loop.

rtmistler · 05-15-2015, 06:02 AM

Quote:

Originally Posted by millgates

So, how do you say the same thing using a math expression?

I agree with millgates. I'd solve this problem via algorithm/math first and then determine how best to code it. Something like:

Code:

// n[next] = n + 1 accounting for loop around
// n[next2] = n + 2 also accounting for loop around
while (n[next]) exists do
    if (n[next2]) exists then
        destroy (n[next])
        n = (n[next2])
    else
        destroy (n[next])
        // n stays the same
    endif
endwhile

Next thing the instructor may ask is to do this with something like 1347 entries and then maybe start heading for the concept of linked lists.