Javascript: Travelling Salesman Problem using Genetic Algorithms

<!DOCTYPE html>

<head>
  <title>Traveling Salesman Problem with Genetic Algorithm</title>
  <script src='ga_tsp.js'></script> remove comments
</head>

<body>
    <h1>Genetic Algorithm for Traveling Salesman Problem</h1>
    <br>
    
    NO_CITIES: <input style='position: absolute; left:200px' id='no-cities' value='20'><br>
    MAP_WIDTH: <input style='position: absolute; left:200px' id='map-width' value='400'><br>
    MAP_HEIGHT: <input style='position: absolute; left:200px' id='map-height' value='400'><br>
    POPULATION_SIZE: <input style='position: absolute; left:200px' id='population-size' value='200'><br>
    CROSSOVER_RATE: <input style='position: absolute; left:200px' id='crossover-rate' value='0.8'><br>
    MUTATION_RATE: <input style='position: absolute; left:200px' id='mutation-rate' value='0.05'><br>
    MAX_GENERATIONS: <input style='position: absolute; left:200px' id='max-generations' value='1000000'><br>
    
    <br>
    <button id='start'>Start</button>
    <button id='stop' disabled>Stop</button>
    
    <br>
    <br>
    <canvas id='tsp-canvas' width='400' height='400' style='border:1px solid black'>
    </canvas>
    
    <br>
    <div id='output'>
    </div>
</body>

<script>
	var __message = '';
	function display_message(m)
    {
        __message = m;
        document.getElementById('output').innerHTML = __message;
    }
    
    var NO_CITIES = 20;
    var MAP_WIDTH = 400;
    var MAP_HEIGHT = 400;
    var POPULATION_SIZE = 200;  // use even number
    var CROSSOVER_RATE = 0.8;
    var MUTATION_RATE = 0.05;  // for each new individual
    var MAX_GENERATIONS = 1000000;
    var crossed_generation = [];
    var canvas;
    var ctx;

	var elite = [];
    var cities;
    var population;
    var previous_population_fitness;
    var current_population_fitness;

    var previous_population_fitness;
    var current_population_fitness;
    var improvement;
    var the_best = [];
    var previous_population_best = [];
    var timer;
    var count;
	var low;
    
    document.getElementById('start').addEventListener('click', function() {
        this.disabled = true;
        document.getElementById('stop').disabled = false;
        
        NO_CITIES = document.getElementById('no-cities').value;
        MAP_WIDTH = document.getElementById('map-width').value;
        MAP_HEIGHT = document.getElementById('map-height').value;
        POPULATION_SIZE = document.getElementById('population-size').value;
        CROSSOVER_RATE = document.getElementById('crossover-rate').value;
        MUTATION_RATE = document.getElementById('mutation-rate').value;
        MAX_GENERATIONS = document.getElementById('max-generations').value;
        
        canvas = document.getElementById("tsp-canvas");
        canvas.width = MAP_WIDTH;
        canvas.height = MAP_HEIGHT;
        ctx = canvas.getContext("2d");

        cities = initial_cities(NO_CITIES, MAP_WIDTH, MAP_HEIGHT);  // It is like a map.
                                                                // cities[i].x, cities[i].y
		console.log('start = ')												
		population = get_initial_population(POPULATION_SIZE, cities);  // Each inidividual is an array of city numbers from 0 to NO_CITIES-1.
                                                                 // E.g., population[i] = [2, 5, 12, 56, 22, ...]
	
		low = get_tour_length(population[0],cities);//assign the first population to the best
        the_best = get_best_individual(population, cities);
        draw_individual(the_best, cities, ctx, canvas);

        count = 0;
        timer = setInterval(run, 5);  // every 5 ms
    });
    
    document.getElementById('stop').addEventListener('click', stop);
    function stop() {
        clearInterval(timer);
        this.disabled = true;
        document.getElementById('start').disabled = false;
    };
    
    /*
    * main loop for the genetic algorithm
    */
    
    function run()//dont modify
    {
		
        var next_population = get_next_population(population, cities);
        population = next_population;
        
        the_best = get_best_individual(population, cities);
		
        draw_individual(the_best, cities, ctx, canvas);
        
        if (!(count++ < MAX_GENERATIONS))
            clearInterval(timer);
    }
	
    function get_next_population(population, cities)
    {
        var next_population = [];
		
		//do the whole ga thing here
        for(var i = 0; i < POPULATION_SIZE; i++){
		
			fitness_evaluation(population[i]);
			next_population = population.slice();//transfer to next population array
		}
		
        return next_population;
    }
	
    function get_best_individual(population, cities)     
    {	
		var the_best_individual = [];//transfer to new array
		var temp = 0;
        //check the best distance value
        for(var i = 0; i < POPULATION_SIZE; i++){
			temp = get_tour_length(population[i],cities);
			console.log('trying... ' + i + ' ' + population[i]);
			console.log('Score ' + temp);
			if(temp < low){
				low = temp;
				elite.push(population[i]);
				
				the_best_individual = population[i].slice();
				previous_population_best = population[i].slice();
				console.log('low ' + low);
			}
			
		}
		if(the_best_individual.length > 0){   
			//there was a good one we do nothing since it was chosen already
		}else{
		   //out of this population there was no good individual that beat the last one
		   the_best_individual = previous_population_best;
		}
			
		
        display_message('Generation = ' + count + ' Tour length = ' + Math.floor(low) + '\n' +
		'Best Route = ' + the_best_individual);
        return the_best_individual;
    }
    
    
	function fitness_evaluation(population){
		var lengths = [];
		for (var i = 0; i < POPULATION_SIZE; i++) {
			lengths[i] = get_tour_length(population, cities);
		}
		var sum = 0;
		for (var i = 0; i < POPULATION_SIZE; i++)
			sum += 1 / lengths[i];
		var fitnesses = [];
		
		sum2 = 0;
		for (var i = 0; i < POPULATION_SIZE; i++){
			fitnesses[i] = (1.0 / lengths[i]) /  sum;  // The sum of fitnesses[i]’s = 1
		}
		//select parents
		parent_selection(fitnesses);//includes crossover, and roulette
		mutation();
		
		

	}
	function roulette_selection(fitnesses){
		var r = Math.random();  // r is in [0, 1)
		var sum = 0;//have to sum up the roulette 
		var selected_individual_index;
		
		for (var i = 0; i < POPULATION_SIZE; i++){
			
			if (r <= sum) {
				selected_individual_index = i;
				break;
			}
			sum += fitnesses[i];
			
		}
		
		//else didn't find r, just assume last one
		if(selected_individual_index == null)
			selected_individual_index = POPULATION_SIZE-1; 
			
		//returns the roulette parent
		return selected_individual_index;

	}
	function parent_selection(fitnesses){
		//Select two parent individuals with CROSSOVER_RATE;
		var roulette = [];
		var fitIndex = 0;
		var parent1;
		var parent2;
		var crossover_point1;
		var crossover_point2;
		var r = Math.random();
		var same_parent = false;
		if(r <= 100){
			//I am using a different crossover method: ordered crossover..
			
			//elitism crossover, preserve the good genes to next generation
			var eliteoffset = elite.length;
			for(var i = 0; i < eliteoffset; i++){
				roulette[i] = elite[i];
				//console.log('elite working? = ' + elite[i]);
			}
			//roulette selection to get fit parents
			for(var i = eliteoffset; i < POPULATION_SIZE; i++){
			    fitIndex = roulette_selection(fitnesses);
				roulette[i] = population[fitIndex]; //select the new individuals based on fitness
			}
			
			
			//cross them
			for(var i = 0; i < POPULATION_SIZE-1; i++){
				//parent i crosses with parent i+1 to produce two new chilren
				crossover_point1 = get_crossover_point(NO_CITIES);  // [1, individual_size); Math.floor(Math.random() * (individual_size-1)) + 1
				crossover_point2 = get_crossover_point(NO_CITIES);
				
				//ensure crossover_point1 is always smaller
				if(crossover_point1 > crossover_point2){
					var temp = crossover_point1;
					crossover_point1 = crossover_point2;
					crossover_point2 = temp;
				
				}
				//create the new population with the child
				crossed_generation[i] = cross(roulette[i], roulette[i+1], crossover_point1, crossover_point2);
				
			}
			//last one..
			crossed_generation[POPULATION_SIZE-1] = cross(roulette[crossover_point1], roulette[crossover_point2], crossover_point1, crossover_point2).slice();
			
			//copy children to the population
			for(var i = 0; i < POPULATION_SIZE; i++){
				//ensure only the good generation gets passed on to the next one
				if(get_tour_length(crossed_generation[i],cities) < get_tour_length(population[i],cities))
					population[i] = crossed_generation[i];
			}
		}//else don't cross parents
	}
	
	//ordered crossover
	function cross(parent1, parent2, startPos, endPos){
		var child=[];
		
		for(var i = 0; i < NO_CITIES;i++){
			child[i] = -1;
		}
		// Loop and add the sub tour from parent1 to our child
        for (var i = 0; i < NO_CITIES; i++) {
            // If our start position is less than the end position
            if (i > startPos && i < endPos) {
                child[i] = parent1[i];
            } 
        }
		// Loop through parent2's city tour
        for (var i = 0; i < NO_CITIES; i++) {
            // If child doesn't have the city add it
			if (!containsCity(child, parent2[i])) {
                // Loop to find a spare position in the child's tour
				for (var j = 0; j < NO_CITIES; j++) {
						// Spare position found, add city
						if (child[j] == -1) {
							child[j] = parent2[i];
							break;
						}
				}
			}
        }
		return child;
	}
	function containsCity(individual,city){
		var i = individual.length;
		while (i--) {
		   if (individual[i] === city) {
			   return true;
		   }
		}
		return false;
	}
	
	function mutation(){
	
		for (i = 0; i < POPULATION_SIZE; i++) {
			var r = Math.random();
			//If it is with MUTATION_RATE,
			if(r < MUTATION_RATE){
				//idea 1: move the second to follow the first, shifting rest along
				//shift_city ZzZZZZzz
				
				var a = Math.floor(Math.random() * (NO_CITIES-1))+1; //[0, no-cities-1] 0 - 19;
				var b = Math.floor(Math.random() * (NO_CITIES-1))+1; //[0, no-cities-1] 0 - 19;
				var temp;
				//swap if a > b
				if(a > b){
					temp = a;
					a = b;
					b = temp;
				}
				//console.log(i + ' pop:' + population[i] + ' a = ' + a +' b = ' + b);
				for(var j = a; j < b-1; j++){
					arraymove(population[i],a+1,b);
				}
				//idea 2: swap mutation for permuatations
				//swap
				/*
				var a = Math.floor(Math.random() * (NO_CITIES-1)); //[0, no-cities-1] 0 - 19;
				var b = Math.floor(Math.random() * (NO_CITIES-1)); //[0, no-cities-1] 0 - 19;
				var temp = population[i][a];
				population[i][a] = population[i][b];
				population[i][b] = temp;
				*/
			}//else no mutation
		}
			

	}
	
	function arraymove(arr, fromIndex, toIndex) {
		var element = arr[fromIndex];
		arr.splice(fromIndex, 1);
		arr.splice(toIndex, 0, element);
	}

	function get_tour_length(population, cities){
		var tour = 0;
		var distance = 0;

		for(var i = 0; i < NO_CITIES-1; i++){
			//get distance from city of population i and i+1
			distance = get_distance_between_two_cities(population[i], population[i+1], cities);
			tour += distance;	
		}
		
		//connect the last city to the first one to make an actual tour, not just a path
		lastCity = population[population.length-1];
		firstCity = population[0];
		distance = get_distance_between_two_cities(firstCity, lastCity, cities);
		tour += distance;
		
		return tour;
	}
	
</script>

Output:

Javascript: 8 Puzzle using A star algorithm

<!DOCTYPE html>

<head>
  <title>n-Puzzle Game</title>
  <script src='api.js'></script>
</head>
<body>
    <div id='output'>
    </div>
</body>

<script>
    var __message = '';
    function print_message(m)
    {
        __message += m + '<br>';
        document.getElementById('output').innerHTML = __message;
    }
    
    var SIZE = 3;  // 3 x 3 game board
    var EMPTY_CELL = 0;
    
    var visited_queue = new Queue();
    var expanded_queue = new Queue();// Queue also can be used
    
    var board = initial_board(SIZE);  // get the initial board
    print_message('Initial board = ' + board);
    
	//first time
    var current_board = board;
    var node = {
        id: get_id_of_board(current_board),  // get_id_of_board() should be implemented
        board: current_board, 
        gvalue: 0, 
        hvalue: get_heuristic_value(current_board),  // get_heuristic_value() should be implemented
        fvalue: 0 + get_heuristic_value(current_board), 
        parent: null  // to keep the track of path from the initial board to the goal board
    };
    visited_queue.push(node.id, node.fvalue, node);  // node.fvalue is the priority
	
	
    //expanded_queue.push(id, p, obj)
    while ( !is_final_state(node.board))//if current_board is solved (goal)
    {	
		get_neighbor_node(node);

        //select next node to visit:
        node = expanded_queue.popTheHighestPriorityOne();
		console.log('best value of g ' +node.id);
		current_board = visited_queue.push(node.id,node.fvalue,node);
		
		
    }
    
    /*
    *   Put the boards on the solution path into a queue
    */
    var path = [];
    path.push(node.board);  // node is the goal node.
    while (node.parent != null) {
	   node = node.parent;
       path.push(node.board);
    }
    
    /*
    *   Print the boards from the initial board to the goal board
    */
    var g =0;
    for (var i = path.length-1; i >=0; i--) 
    {   
		print_message('tree level ' + g + ' = '  + path[i]);
		g++;
	}
	print_message('END');
	
	function get_id_of_board(board){
		var str ="";
		for(var i = 0; i < board.length; i++){
			str += board[i];
		}
		console.log(str);
		return parseInt(str);
	}
	
	function put_in_queue(current_node, expanded_board)
    {
        if (!visited_queue.isIn(get_id_of_board(expanded_board)))
		{
            var expanded_node = 
			{
				id: get_id_of_board(expanded_board), 
				board: expanded_board, 
				gvalue: current_node.gvalue + 1, 
				hvalue: get_heuristic_value(expanded_board), 
				fvalue: current_node.gvalue + 1 + get_heuristic_value(expanded_board), 
				parent: current_node
			};
				
            if (expanded_queue.isIn(expanded_node.id)) 
			{
                var temp_node = expanded_queue.get(expanded_node.id);
				console.log(expanded_node.gvalue + '<' + temp_node.gvalue);
                if (expanded_node.gvalue < temp_node.gvalue)
				{
					console.log('a better g value, update');
                    expanded_queue.update(expanded_node.id, expanded_node.fvalue, expanded_node);
					
				}
            }
            else{
				console.log('a new state, add');
                expanded_queue.push(expanded_node.id, expanded_node.fvalue, expanded_node);
			}
		}
    }
	
	function get_neighbor_node(puzzle){
		var empty = puzzle.board.indexOf(0);
		//empty index to decide where it can move
		console.log('index of 0: '+empty);
;		if(empty == 0){
			//first cell 
			put_in_queue(puzzle, exchange(0,1,puzzle.board));
			put_in_queue(puzzle, exchange(0,3,puzzle.board));
		}else if(empty == 1){
			put_in_queue(puzzle, exchange(1,0,puzzle.board));
			put_in_queue(puzzle, exchange(1,4,puzzle.board));
			put_in_queue(puzzle, exchange(1,2,puzzle.board));
		}else if(empty == 2){
			put_in_queue(puzzle, exchange(2,1,puzzle.board));
			put_in_queue(puzzle, exchange(2,5,puzzle.board));
		}else if(empty == 3){
			put_in_queue(puzzle, exchange(3,0,puzzle.board));
			put_in_queue(puzzle, exchange(3,4,puzzle.board));
			put_in_queue(puzzle, exchange(3,6,puzzle.board));
		}else if(empty == 4){
			put_in_queue(puzzle, exchange(4,1,puzzle.board));
			put_in_queue(puzzle, exchange(4,5,puzzle.board));
			put_in_queue(puzzle, exchange(4,7,puzzle.board));
			put_in_queue(puzzle, exchange(4,3,puzzle.board));
		}else if(empty == 5){
			put_in_queue(puzzle, exchange(5,2,puzzle.board));
			put_in_queue(puzzle, exchange(5,8,puzzle.board));
			put_in_queue(puzzle, exchange(5,4,puzzle.board));
		}else if(empty == 6){
			put_in_queue(puzzle, exchange(6,7,puzzle.board));
			put_in_queue(puzzle, exchange(6,3,puzzle.board));
		}else if(empty == 7){
			put_in_queue(puzzle, exchange(7,4,puzzle.board));
			put_in_queue(puzzle, exchange(7,6,puzzle.board));
			put_in_queue(puzzle, exchange(7,8,puzzle.board));
		}else if(empty == 8){
			put_in_queue(puzzle, exchange(8,7,puzzle.board));
			put_in_queue(puzzle, exchange(8,5,puzzle.board));
			
		}
	}
	
	function exchange(i,j,puzzle)//swap tile with EMPTY_CELL
    {
        var temp_board = [];
        for (var x = 0; x < puzzle.length; x++)
            temp_board[x] = puzzle[x];
            
        var temp = temp_board[i];
        temp_board[i] = temp_board[j];
        temp_board[j] = temp;
        
        return temp_board;
    }
    	
	//Manhatan function
	function get_heuristic_value(state) 
	{
		var tboard = state;
		var distance = 0;

		// the heuristic of the Manhatan distance
		for (var i = 0; i < tboard.length; i++)
			if (tboard[i] != EMPTY_CELL) {
				if (tboard[i]-1 != i) {
					var c_row, c_col, t_row, t_col;
					c_row = Math.floor(i / SIZE); c_col = i % SIZE; 
					t_row = Math.floor((tboard[i]-1) / SIZE); t_col = (tboard[i]-1) % SIZE; 
					distance += Math.abs(c_row - t_row) + Math.abs(c_col - t_col);
			}
		}

	return distance;

	}
	
	//check if is goal
	function is_final_state(state) 
	{
	  for (var i = 0; i < SIZE*SIZE-1; i++)  // should be length-1, not length
	    if (state[i]-1 != i)
		  return false;
	  return true;  // 1 2 3 4 ... empty
	}
	
</script>


Output:

ACM: Problem 7371

Problem 7371 Triangle


/*
Problem 7371

Sample Input
3 4 5
4 3 5
3 4 6
4 6 3
39 52 65
25 60 65


Sample Output
YES
NO
NO
*/


import java.io.*;
import java.util.*;

class Main
{
    static String ReadLn (int maxLg)  // utility function to read from stdin
    {
        byte lin[] = new byte [maxLg];
        int lg = 0, car = -1;
        String line = &quot;&quot;;

        try
        {
            while (lg &lt; maxLg)
            {
                car = System.in.read();
                if ((car &lt; 0) || (car == '\n')) break;
                lin [lg++] += car;
            }
        }
        catch (IOException e)
        {
            return (null);
        }

        if ((car &lt; 0) &amp;&amp; (lg == 0)) return (null);  // eof
        return (new String (lin, 0, lg));
    }

    public static void main (String args[])  // entry point from OS
    {
        Main myWork = new Main();  // create a dinamic instance
        myWork.Begin();            // the true entry point
    }

	void Begin()
	{
		String input;
		StringTokenizer idata;
		double[] tri1 = new double[3];
		double[] tri2 = new double[3];
		String yesno = &quot;YES&quot;;
		
		while ((input = Main.ReadLn (255)) != null)
		{
			yesno = &quot;YES&quot;;
			idata = new StringTokenizer (input);	
				
			if(!idata.hasMoreElements())//handle blank line at the end of parsing
				break;
			
			//read first triangle		
			for(int i = 0; i &lt; 3; i++){
				tri1[i]= Integer.parseInt (idata.nextToken()); 
			}
			
			input = Main.ReadLn(255);
			idata = new StringTokenizer (input);
			
			//read second triangle
			for(int i = 0; i &lt; 3; i++){
				if(!idata.hasMoreElements())//handle blank line at the end of parsing
					break;
				tri2[i]= Integer.parseInt (idata.nextToken()); 
			}
			
			Arrays.sort(tri1);
			Arrays.sort(tri2);
			
			for(int i = 0; i &lt; 3; i++){
				//System.out.println(tri2[i] + &quot; &quot; + tri1[i]);
				if(tri1[i] != tri2[i]){
					yesno = &quot;NO&quot;;
				}
			}
			if(yesno.equals(&quot;YES&quot;)){
				double hyp = Math.sqrt((tri1[0]*tri1[0]) + (tri2[1]*tri2[1]));
				if(hyp != tri1[2]){
					yesno = &quot;NO&quot;;
				}

			}
			System.out.println(yesno);		
		}
		
	}
}

ACM: Problem 7372

Problem 7372 Excellence


/*
Problem 7372

Sample:
input:
4
1
2
3
5
2
18
16
4
13
12
19
14


output:
5
34
27
*/


import java.io.*;
import java.util.*;

class Main
{
    static String ReadLn (int maxLg)  // utility function to read from stdin
    {
        byte lin[] = new byte [maxLg];
        int lg = 0, car = -1;
        String line = &quot;&quot;;

        try
        {
            while (lg &lt; maxLg)
            {
                car = System.in.read();
                if ((car &lt; 0) || (car == '\n')) break;
                lin [lg++] += car;
            }
        }
        catch (IOException e)
        {
            return (null);
        }

        if ((car &lt; 0) &amp;&amp; (lg == 0)) return (null);  // eof
        return (new String (lin, 0, lg));
    }

    public static void main (String args[])  // entry point from OS
    {
        Main myWork = new Main();  // create a dinamic instance
        myWork.Begin();            // the true entry point
    }

	void Begin()
	{
		String input;
		StringTokenizer idata;
		int contestants = 0;
		int cities=0;
		int count = 0;
		
		while ((input = Main.ReadLn (255)) != null)
		{
			idata = new StringTokenizer (input);	
			
			if(!idata.hasMoreElements())//handle blank line at the end of parsing
				break;
					
			contestants = Integer.parseInt (idata.nextToken()); 
			int[] arr = new int[contestants];
               	
			for(int i = 0; i &lt; contestants; i++){
				input = Main.ReadLn (255);
				if(input.indexOf(&quot;\r&quot;) != -1)
					arr[i] = Integer.parseInt (input.substring(0, input.indexOf(&quot;\r&quot;)));
				else
					arr[i] = Integer.parseInt (input);
			}
			Arrays.sort(arr);
			
			int low = 10000000;
			for(int i = 0; i &lt; contestants; i++){
				
				if(arr[i] + arr[contestants-1-i] &lt; low)
					low = arr[i] + arr[contestants-1-i];
			}
			System.out.println(low);
			
		}
	}
}

ACM: Problem 7391

pdf of problem


/*
 * Problem 7391
Sample:
input:
2
7
saskatoon
toronto
winnipeg
toronto
vancouver
saskatoon
toronto
3
edmonton
edmonton
edmonton

output:
4
1
*/


import java.io.*;
import java.util.*;

class Main
{
    static String ReadLn (int maxLg)  // utility function to read from stdin
    {
        byte lin[] = new byte [maxLg];
        int lg = 0, car = -1;
        String line = &quot;&quot;;

        try
        {
            while (lg &lt; maxLg)
            {
                car = System.in.read();
                if ((car &lt; 0) || (car == '\n')) break;
                lin [lg++] += car;
            }
        }
        catch (IOException e)
        {
            return (null);
        }

        if ((car &lt; 0) &amp;&amp; (lg == 0)) return (null);  // eof
        return (new String (lin, 0, lg));
    }

    public static void main (String args[])  // entry point from OS
    {
        Main myWork = new Main();  // create a dinamic instance
        myWork.Begin();            // the true entry point
    }

	void Begin()
	{
		String input;
		StringTokenizer idata;
		int travels = 0;
		int cities=0;
		int count = 0;
		
		
		while ((input = Main.ReadLn (255)) != null)
		{
			idata = new StringTokenizer (input);
			if(count == 0){
				travels = Integer.parseInt (idata.nextToken());
				count++;
				continue;
			}
			
			if(count == travels+1)
				break;
				
			count++;
			cities = Integer.parseInt (idata.nextToken()); 
			HashSet&lt;String&gt; hset = 
               new HashSet&lt;String&gt;();
               	
			for(int i = 0; i &lt; cities; i++){
				input = Main.ReadLn (255);
				hset.add(input);
			}
			
			System.out.println (hset.size());
		}
	}
}

Problem 30: Distinct Powers

Problem 30
Turned integer into a string, took each character and did the operations added the powers that way. Then I just checked the numbers if they were equal.


/**
Surprisingly there are only
 three numbers that can be written
  as the sum of fourth powers of their digits:

1634 = 14 + 64 + 34 + 44
8208 = 84 + 24 + 04 + 84
9474 = 94 + 44 + 74 + 44
As 1 = 14 is not a sum it is not included.

The sum of these numbers is 1634 + 8208 + 9474 = 19316.

Find the sum of all the numbers 
that can be written as the sum of fifth powers of their digits.
 */
import java.util.*;
public class problem29 {
    
    public static boolean isDigitFifth(int num){
    	String strNum = Integer.toString(num);
    	int sum = 0;
    	for(int i = 0; i &lt; strNum.length(); i++)
    	{
    		sum += Math.pow(
    			Integer.parseInt(
    				Character.toString(
    					strNum.charAt(i))),5);
    	}
    	if(sum == num)
    		return true;
    	else return false;
    }
    public static void main(String[] args) {
    	int sum = 0;
        for(int i = 2; i &lt; 1000000; i++)
        {
        	if(isDigitFifth(i)){
        		sum += i;
        		System.out.println(i);
        	}       		
        }
        System.out.println(sum);
    }
}



Output
——————–Configuration: ——————–
4150
4151
54748
92727
93084
194979
443839

Process completed.

Project Euler: Problem 28: Number Spiral Diagonals

Problem 28

Quite a simple implementation, I just noticed a pattern that the odd squares are multiples of 2 apart, so i added the corners (by subtracting the multiples of 2’s) to get the final result.



/**
Starting with the number 1 and moving
 to the right in a clockwise direction 
 a 5 by 5 spiral is formed as follows:

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

It can be verified that the sum of 
the numbers on the diagonals is 101.

What is the sum of the numbers on the 
diagonals in a 1001 by 1001 spiral 
formed in the same way?
 */
import java.util.*;

public class problem28 {

	public static boolean perfect(double num){
		
		if(Math.sqrt(num) - Math.floor(Math.sqrt(num)) &gt; 0)
			return false;
		else return true;
	}
    
    public static void main(String[] args) {
    	
		double sum = 1;
		int diag = 0;
		
		for(int i=2; i &lt; 1001*1001+1; i++){
			if(perfect(i) &amp;&amp; i % 2 != 0){
				diag += 2;
				sum += i + (i - diag) + (i - 2*diag) + (i - 3*diag);
			}
		}
	
	    System.out.println(sum);
    }
}



Output

——————–Configuration: ——————–
6.69171001E8

Process completed.

Java: primes

The purpose of this program is to display a sieve of eratosthenes in a Java program to see how long it would calculate all primes in the range of 1 to 10^9. Since hardware is a major factor in performance I have included my pc specifications.

prime.java

/**
 * prime.java
 *
 * Name: Michael Peng
 * ID No.: T00055798
 * Course: Comp 3050 Algorithm Design and Analysis
 * Purpose: Compute all primes between 2 to n(max) and store them into an array
 * Language: Java
 * Editor: Notepad++
 * Compiler Version: jdk1.7.0_79
 * Operating System: Windows 7
 * Computer Specifications:
 * - CPU: Intel i7-4770 @3.40GHz
 * - Memory: 16GB ram
 * - GPU: AMD Radeon HD 8570 Graphics
 *
 */

public class prime {

	//time when program executes
    final static long startTime = System.nanoTime();

	/*
	* Pre: have an integer max in param that is greater then 2
	*
	* Post: return an array of booleans with associated index's be 
	*		either true or false depending on whether they are prime
	*
	* Algorithm: Loop through once to make all values true, then 
	*			 use a sieve of eratosthenes (link below) to determine if a 
	*			 number is not prime, make that index false if not prime.
	*
	* Source: https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes
	*/
    public static boolean[] Store_Prime(int max){

    	boolean[] A = new boolean[max];

		//loop for making all values true
    	for(int i = 2; i &lt; max; i++)
    		A[i] = true;

		//loop for sieve
    	for(int i = 2; i*i &lt; max - 1; i++)
    	{
    		if(A[i] == true)
    		{
				//if there is a number that is a multiple of another number
    			for(int j = 2; j*i &lt; max; j++)
    			{
    				A[j*i] = false;
    			}
    		}
    	}
    	return A;
    }

	/*
	* Pre: have used the Store_Prime function to calculate all the primes
	*	   in a boolean array
	*
	* Post: return the number of primes that is in the array and 
	* 		print the primes in reverse order and only the first 50
	*
	* Algorithm: Loop through the array once and check if 
	*			 the index is true, if so print and store it in a counter
	*
	*/
    public static int Print_Prime(boolean[] A){

		int count = 0;

		//loops through array backwards printing first 50 primes
    	for(int i = A.length-1; i &gt;= 2 ; i--)
    	{
    		if(A[i] == true)
    		{
				count++;
				if(count &lt; 49)
    				System.out.print(i + &quot; &quot;);
    		}
    	}
    	return count;
    }

	//This is the main tester
    public static void main(String[] args) {

		int n;
		n = 1000000000;//n = 10^9


		System.out.println(&quot;\n\nNumber of primes = &quot; + Print_Prime(Store_Prime(n)));

		//Program end time, to calculate how long it ran subtract start time
        final long duration = System.nanoTime() - startTime;
        System.out.println(&quot;When n = &quot; + n + &quot; it took &quot; + duration / 1000000.0 + &quot; milliseconds&quot;);
    }
}

output:

Number of primes = 50847534
When n = 1000000000 it took 21504.819887 milliseconds

C++: Friends, example using distances

Distance.cpp

#include &lt;iostream&gt;
#include &lt;conio.h&gt;
//using namespace std;

class Distance
{
private:
   int feet;
   float inches;
public:

    Distance()          //constructor1
    {
        feet=0;
        inches=0;
    }

    Distance(int ft,float inch)       //constructor2
    {
        feet=ft;
        inches=inch;
    }

    void getdata()
    {
        std::cout&lt;&lt;&quot;Enter Feet and inches respectively: &quot;;
        std::cin&gt;&gt;feet&gt;&gt;inches;
    }

    void display()
    {
        std::cout&lt;&lt;&quot;Feet : &quot;&lt;&lt;feet&lt;&lt;std::endl;
        std::cout &lt;&lt;&quot;Inches :&quot;&lt;&lt;inches;
    }

    //Operator declaration in Class
    friend Distance operator + (Distance &amp;ob1, Distance &amp;ob2)
    {
        Distance temp;
        temp.feet   = ob1.feet   + ob2.feet;
        temp.inches = ob1.inches + ob2.inches;
        if(temp.inches &gt;= 12)
        {
           temp.inches -= 12;
           temp.feet++;
        }
        return(temp);
    }
    friend Distance operator - (Distance &amp;ob1, Distance &amp;ob2)
    {
        Distance temp;
        temp.feet   = ob1.feet   - ob2.feet;
        temp.inches = ob1.inches - ob2.inches;
        if(temp.inches &gt; 0)
        {
            temp.inches -= 12;
            temp.feet++;
        }
        return(temp);
    }

    friend Distance operator *(int d, Distance &amp;ob)
    {
        Distance temp;
        temp.feet   = ob.feet * d;
        temp.inches = ob.inches * d;
        if(temp.inches &gt;= 12)
        {
           temp.inches -= 12;
           temp.feet++;
        }
        return(temp);
    }

    friend int operator ==(Distance &amp;ob1, Distance &amp;ob2)
    {
        if(ob1.feet == ob2.feet){
            if(ob1.inches == ob2.inches)
                return 1;
            else return 0; //inches unequal
        }
        else return 0; //feet unequal
    }

    friend int operator &lt; (Distance &amp;ob1, Distance &amp;ob2)
    {
       if(ob1.feet &lt; ob2.feet){
            if(ob1.inches &lt; ob2.inches)
                return 1; //ob2 is greater
            else return 0; //ob1 is less
        }
        else return 0; //ob1 is less
    }

    friend int operator &gt; (Distance &amp;ob1, Distance &amp;ob2)
    {
       if(ob1.feet &gt; ob2.feet){
            if(ob1.inches &gt; ob2.inches)
                return 1; //ob2 is less
            else return 0; //ob1 is greater
        }
        else return 0; //ob1 is greater
    }

};

prog25modified.cpp

#include &quot;distance.cpp&quot;
#include &lt;iostream&gt;
#include &lt;conio.h&gt;
using namespace std;
/*
prog25Modified.cpp

completed distance.cpp which calculates the distance
in feet and inches for addition, subtraction etc.

*/
int main()
{
//  clrscr();
  Distance ob1;
  Distance ob2;
  Distance ob3;  //Invoked constructor1

  cout&lt;&lt;&quot;\n=====Enter Data for OBJECT1=====\n&quot;;
  ob1.getdata();
  cout&lt;&lt;&quot;\n\n=====Enter Data for OBJECT2=====\n&quot;;
  ob2.getdata();
 int opt=0;
  int choice=1,data;
  while(choice !=0)
  {opt=0;

    cout&lt;&lt;&quot;\nChose your choice\n&quot;;
    cout&lt;&lt;&quot;1)  Addition            ( + )\n&quot;;
    cout&lt;&lt;&quot;2)  Subtraction         ( - )\n&quot;;
    cout&lt;&lt;&quot;3)  Multiplication      ( * )\n&quot;;
    cout&lt;&lt;&quot;4)  Comparision         ( == )\n&quot;;
    cout&lt;&lt;&quot;5)  Comparision         ( &lt; )\n&quot;;
    cout&lt;&lt;&quot;6)  Comparision         ( &gt; )\n&quot;;
    cout &lt;&lt;&quot;0)  Quit                \n&quot;;
    cout&lt;&lt;&quot;Enter your choice:-&quot;;
    cin&gt;&gt;choice;
    cout&lt;&lt;endl&lt;&lt;endl;
    switch(choice)
    {
       case 1 : { ob3 = ob1 + ob2; opt=1;
         break;}
       case 2 :  {ob3 = ob1 - ob2; opt=1;
         break;}
       case 3 :    cout&lt;&lt;&quot;\nEnter integer to be multiplied:-&quot;;
           cin&gt;&gt;data;
           ob3 = data * ob1; opt=1;
         break;
       case 4 :
           {
            if(ob1 == ob2)
           { cout&lt;&lt;&quot;\nBoth Objects are equal or same value\n&quot;;}
         else
           { cout&lt;&lt;&quot;\nThey are Unequal\n&quot;;}
         getch();

         break;}
    case 5 :  {
        if(ob1 &lt; ob2)

           { cout&lt;&lt;&quot;\nObject1 is Less than Object2\n&quot;;}
         else
           { cout&lt;&lt;&quot;\nObject2 is Less than Object1\n&quot;;}
         getch();

        break;
    }

    case 6 :
        {
            if(ob1 &gt; ob2)
           { cout&lt;&lt;&quot;\nObject1 is Greater than Object2\n&quot;;}
         else
           { cout&lt;&lt;&quot;\nObject2 is Greater than Object1\n&quot;;}
         getch();

         break;
        }


      case 0:  cout&lt;&lt;&quot;\n\nHave a nice day....\n&quot;;
          getch();
          break;

          default : cout &lt;&lt; &quot;Invalid option &quot;;
    }
    if (opt==1) {
        cout&lt;&lt;&quot;\n\nResult in OBJECT3 as under\n&quot;;
        ob3.display();
        getch();
    }
}


return 1;
}

Output:
output
output2
output3

C++: Operator Overloading, example using “-” for birthday

Date.cpp

#include &lt;iostream&gt;
#include &lt;conio.h&gt;
//using namespace std;

class Date
{
private:
   int month;
   int year;
   int day;
public:

    Date()          //constructor1
    {
        month=0;
        day=0;
        year=0;
    }

    Date(int m, int d, int y)       //constructor2
    {
        month = m;
        day = d;
        year = y;
    }

    void getdata()
    {
        std::cout&lt;&lt;&quot;Enter month, day and year respectively: &quot;;
        std::cin&gt;&gt;month&gt;&gt;day&gt;&gt;year;
    }

    void display()
    {
        std::cout&lt;&lt;&quot;Month : &quot;&lt;&lt;month&lt;&lt;std::endl;
        std::cout&lt;&lt;&quot;Day : &quot;&lt;&lt;day&lt;&lt;std::endl;
        std::cout&lt;&lt;&quot;Year : &quot;&lt;&lt;year&lt;&lt;std::endl;
    }

    //Operator declaration in Class
    friend Date operator - (Date &amp;ob1, Date &amp;ob2)
    {
        Date temp;
        temp.year = ob1.year - ob2.year;
        temp.month = ob1.month - ob2.month;
        temp.day = ob1.month - ob2.month;

        //same month as current day, but different days
        if(temp.month == 0)
        {
            if(temp.day &gt; 0)
                temp.year--;
        }
        else if(temp.month &lt; 0)
        {
            temp.year--;
        }
        return(temp);
    }

    int getAge(){
        return year;
    }

};

DateDriver.cpp

#include &quot;distance.cpp&quot;
#include &lt;iostream&gt;
#include &lt;conio.h&gt;
#include &quot;Date.cpp&quot;
#include &lt;ctime&gt;

using namespace std;
/*
DateDriver.cpp

compute age from your DOB

*/
int main()
{
//  clrscr();
    Date Birthdate;

    time_t t = time(0);   // get time now
    struct tm * now = localtime( &amp; t );

    //set current date automatically
    Date currentDate(now-&gt;tm_mon+1, now-&gt;tm_mday, now-&gt;tm_year+1900);
    Date year;

    cout&lt;&lt;&quot;\n=====Enter Data for OBJECT1=====\n&quot;;
    Birthdate.getdata();

    //operator overload
    year = currentDate - Birthdate;

    cout &lt;&lt; &quot;Your age is: &quot; &lt;&lt; year.getAge();


    return 1;

}

Output:
output