How does the approach to solve Josephus problem work?

Josephus problem:

There are people standing in a circle waiting to be executed. The counting out begins at some point in the circle and proceeds around the circle in a fixed direction. In each step, a certain number of people are skipped and the next person is executed. The elimination proceeds around the circle (which is becoming smaller and smaller as the executed people are removed), until only the last person remains, who is given freedom.

The task is to choose the place in the initial circle so that you are the last one remaining and so survive.

The approach:

Lets say we have to find the solution for n=5 and k=3 (We kill every 3rd person)

Step 1: Kill the kth person (in our case, kill the 3rd person). "2" will be removed and the counting out begins at "3"

Step 2: Instead of finding the solution for the above diagram, we can simply find the solution of the following diagram. Note that 3 is mapped to 0 and 4 is mapped to 1 and so on..

(To find the solution of the above diagram we use the same approach from step1. I'd like to ignore that part.)
The solution for n=4 and k=3 is 0.

Now look at the first diagram. We know that 0 is mapped to 3 in step2 which is the required solution.


Thanks to xorfire for teaching me this awesome problem.

Comments are welcome.

My AI tron bot

Tron is just similar to the snake game you play on mobile. There is a slight variation that at every step, the snake keeps growing on it's size. You hit anywhere, you die.

The movie Tron Legacy is entirely based on this game.

My tron AI was ranked 31/672 bots in Codingame. I actually didn't use any machine learning techniques. Instead I learnt myself by watching the replays of a lot of games to decide my strategy.

The challenge in this game is that our code should work for any number of opponents into the arena and it should run in 100 milli seconds. And within 100ms, our bot should decide the next move (left/right/up/down).

This is the core logic of my tron AI.

struct Direction{
    int dir;
};

//Just a comparator which could compare two directions and returns true if directionA is better than directionB

inline bool operator < (Direction A, Direction B){
    if(A.dir==B.dir)
        return false;
   
    if(isSafe[A.dir]!=isSafe[B.dir])
    {
        if(isSafe[A.dir])
            return true;
        return false;
    }

    if(selfish[A.dir]!=selfish[B.dir])
    {
        if(selfish[A.dir])
            return true;
        return false;
    }       
    if(defend[A.dir]!=defend[B.dir])
    {
        if(defend[A.dir])
            return true;
        return false;
    }
   
    if(attack[A.dir]!=attack[B.dir])
    {
        if(attack[A.dir])
            return true;
        return false;
    }

    if(!(target[A.dir]==target[B.dir]))
        return target[A.dir]<target[B.dir];    
           
    if(futureful[A.dir]!=futureful[B.dir])
    {
        if(futureful[A.dir])
            return true;
        return false;
    }
   
    if(best[A.dir]!=best[B.dir])
    {
        if(best[A.dir])
            return true;
        return false;
    }

    if(closer[A.dir]!=closer[B.dir])
    {
        if(closer[A.dir])
            return true;
        return false;
    }
   
    if(safeTouch[A.dir]!=safeTouch[B.dir])
    {
        if(safeTouch[A.dir])
            return true;
        return false;
    }
   
    if(touches[A.dir]!=touches[B.dir])
    {
        if(touches[A.dir])
            return true;
        return false;
    }
   
    return A.dir<B.dir;
}

Step1: Choose a safe move. An unsafe move is a move which lets your bot die.
Step2: Be selfish. Choose the direction containing maximum free spaces. This might sound crazy. But if you don't take this path, you are probably going to lose anyhow. It's better to take a selfish move which might help you if your opponent makes mistakes.
Step3:

Proof: If player X can reach a point (x,y) faster than any other player, then regardless of the shortest path X choose, no one can stop X in reaching (x,y).

By finding the nearest player for all the points in the map, we could know the points a player can reach faster than anyone else.

A defensive direction is a direction which will make the number of nearest points to be maximum (points we can reach faster than all enemies should be maximum). Choose such a direction.

Step4: Choose an attacking direction if possible.
Let S be the set of points we can reach faster than all the enemies.
For each point in S, draw a line from S[i] to current position and check whether the enemies have less survival time than us. Choose a point for which ∑(survivalTime[me]-survivalTime[enemy[i]]) is maximum and move towards that direction.

Step5: In case we have many possible positions to attack with equal score, choose the target which is closer and move towards it.

Step6: We should think at least one step ahead in order to utilize maximum space on the board. We need not waste spaces on the board. (Edit:  This can help to utilize more spaces than that of this step.)

Step7: Block all the points enemies can reach faster than us. Now choose the direction with maximum survival time.

Step8: Get closer towards the farthest enemy faster!. Going towards the farthest enemy can give us some space to breathe in.

Step9: Once we know that an enemy is about to die, we should try to occupy that space. It's better not to touch the enemy who is about to die. This should be done only when aliveEnemies>1.

Step10: It's always safer to move on the edges of walls to occupy more spaces.


You probably could have got bored if I had shared my entire 1035 lines of code.
Hope you liked it :) Share your suggestions/improvements.

How to start programming?

A bit about myself:

      I did my schooling in Madurai, India. I love mathematics. In my early school days, I started solving sudoku. I also liked playing Tetris, Bomber man, Super Mario and what not. I like to compete. What’s the fun in playing Fruit Ninja without having friends to brag about our high scores?

Why I started programming?

      I felt goosebumps when a computer bot with artificial intelligence played wiser in a video game. I saw a program which could solve any Sudoku puzzle within a fraction of a second. I saw a program which could chat to me like a human. I saw a robot which could solve any rubik’s cube.  I realized that I could solve such problems by mathematics and little programming. And that’s how I started.

How can you start programming?

      Step 1: Learn a programming language. There are lots of books to learn programming. If you can’t afford a book you can use some Library. If you hate books, you can learn online through w3schools.com. The syntax and the procedures will trouble you initially. But it’s worth it.

      Step 2: Start solving some real time problems. There are many websites where you can start solving real time problems. You can start with SPOJ, ProjectEuler and MyCodeSchool.

      Step 3: After solving few basic problems you should start learning Data Structures and Algorithms which could help you solve challenging and interesting real time problems. As MyCodeSchool provides nice video tutorials, I recommend you to learn and practice there.

      Step 4: Get like-minded friends and participate in programming camps and competitions. Compete in Topcoder where all the programmers in the world take part regularly. Participate in IOI if you are in school and participate in ICPC if you are in college. Win a GOLD for our country.

Data Structures and Algorithms are very important. In addition if you want to learn Game Programming, learn openGL and keep in touch with Vector Algebra and Trigonometry. If you want to create programs which can think like humans you should learn Artificial Intelligence and Machine Learning.

In case if you love mathematics and computers, it’s neither late nor early to learn programming. Start now!.

                                                            - Prakash D(Game Developer @ Smackall Games)

Why should one take part in programming contests?

This post is only for students who are interested in math, puzzle solving and programming.

Why do students avoid programming contests?

1) New to online learning

2) Afraid of problems

3) Feeling shy to see their name lower in the ranklist

4) Academics

5) Entertainment

6) Girlfriend 

Why should one take part in programming contests?

1) Its competitive and fun.

2) At the end of every contest, you learn to solve atleast one new problem.

3) Finish laboratory exams quicker. 

4) The preliminary written tests in symposiums are equialent to the interview questions. More you take part, more likely you will crack the interviews.

5) You can turn any idea into a code.

6) You can be the first one to bring India a gold medal in ACM ICPC, the world's biggest programming contest.

7) You will take efficient and right decisions in your real life.

Don't do it for money. Do it only if you have the passion

The path to success is not just MARKS -> GRADES -> GPA -> INTERNS -> JOBS -> MONEY -> MARRIAGE. You have to aim higher.

What is it like doing a final year project at CEG

I'm currently working on the thesis of my fyp and I felt like writing a blog post about how I feel now.

I didn't do the project. I bought it outside for money. Because I didn't have a good idea for a project. When I was in 2nd year, I really got inspired by one of my seniors' final year project on image processing which takes a video of a cricket match (without audio) as input and produces a video with auto generated commentary. He had a great idea!. He was able to find some IEEE base papers on image processing and could have faced the further troubles.

The first trouble that we face is, choosing the project guide. Every project guide can handle only two teams. We are forced to choose a project guide sooner even if we don't have any idea of what we are going to do. My project guide was good in networks. Me and all my team members were bad at networks. But if we chose a project without involving networks, it would have been rejected/ignored. Our current fyp panel wants us to have at least 5 base papers (should take the results of 5 other projects and improve) which clearly restricts the students' creativity. 

How CEG final year projects are

I really respect those projects which actually help some people. But I lacked in idea. I didn't want to waste 6 months in my teen age to do a project which is of no use. I also didn't want my teammates to lose marks because of my attitude. So I bought the project for money.

I know that Ok you bought the project outside. Y are you still frustrated? is the question in your mind. Here is me answering

There are 3 project reviews. For each review, we had to face most of the following problems

1) Preparation of ppts and documentation for 2 days

2) Waiting for project review at the review hall for 2 days

3) Postponing of the review date several times 

4) Meet the mam at least twice before every review in which the professor wants you to change the ppt and documentation repeatedly.

5) Have to take several printouts.

6) We must not attend any interviews on all such timings.

7) We must concentrate on our font size and alignment 75 percent more than how much we concentrate on our code.

Even if you cross all those hurdles, you have to climb the everest called THESIS (Project report). You have to prepare a book about your project with at least 50 pages. You have to understand that preparing a book of 50 pages is 51 times harder than typing 50 pages. You will be forced to spend at least 2 weeks and 500Rs for this paper work. Finally this book goes to the dustbin.

Disclaimer:
Note that ppl who didn't buy the project, dayscholars could have faced more troubles.