1: '''
2: Program to generate pentagonal numbers
3: for a maximum size of 100.
4: Pentagonal numbers of the form (3*n-1)(n/2)
5: Created on Mar 24, 2014
6: @author: Mridul J Kurup
7: '''
8: MAX_SIZE=100
9: START_INDEX=1
10: # Pentagonal Numbers
11: def generatePentagonalNumbers(size):
12: if(size<=MAX_SIZE):
13: rowCtr=0
14: print("The pentagonal numbers are : ")
15: #get the max number of digits
16: maxdigit=computeNoOfDigits(round((3*size-1)*(size/2)))
17: size=size+1 #incrementing to reach 100
18: for i in range(START_INDEX,size):
19: rowCtr+=1
20: candidate=round((3*i-1)*(i/2))
21: noOfSpaces=maxdigit-computeNoOfDigits(candidate)
22: print(candidate, end=computeGap(noOfSpaces," "))
23: if rowCtr==10:
24: print()
25: rowCtr=0
26: # method to compute the no of digits
27: def computeNoOfDigits(number):
28: digit=0
29: while(number>0):
30: number=number//10;
31: digit+=1
32: return digit
33: # compute the number of gaps
34: # char specifies the char to be filled in
35: def computeGap(size, char):
36: space=char
37: size+=1
38: for i in range(1,size):
39: space+=char
40: return space
41: '''
42: method invocation
43: '''
44: generatePentagonalNumbers(int(
45: eval(input("Enter the size of the numbers : ")))) Monday, March 24, 2014
Pentagonal numbers from 1 to 100- Python
Monte Carlo Simulation- Python
1: '''
2: Program to compute the value of PI and to compute
3: the hit rate on the odd segments of a square
4: using Monte Carlo Simulation
5: Created on Mar 24, 2014
6: @author: Mridul J Kurup
7: '''
8: import random, sys
9: # method to compute the value of PI using monte carlo simulation
10: def MonteCarloSimulation(datasize):
11: datasize+=datasize # incrementing for end value
12: hitsWithinCircle=0
13: for i in range(datasize):
14: x=random.random()
15: y=random.random()
16: if x*x+y*y <= 1 :
17: hitsWithinCircle+=1
18: print("PI is : ",(4*hitsWithinCircle/datasize))
19: # method to compute the hit rate on a square
20: # divided into four parts.With part 2 and 3 half the size of 1 or 4.
21: # objective is to see the hit rate on the odd number regions
22: # As per the diagram the hit rate should be around 62.5%
23: def AdvancedMonteCarloSimulation(datasize):
24: datasize+=datasize # incrementing for end value
25: hitsInOdd=0
26: hitsInEven=0
27: for i in range(datasize):
28: x=random.random()*2
29: y=random.random()*2
30: # region of 1
31: if (x>0 and x<=1 and y>0 and y<=2):
32: hitsInOdd+=1
33: # region of 3
34: elif ((x>1 and x<=2) and (y>1 and y<=2) and (x*y <=2.25)):
35: hitsInOdd+=1
36: else:
37: hitsInEven+=1
38: print("The probability of the dart falling in odd region is : ",
39: round((hitsInOdd/datasize),4))
40: print("The probability of the dart falling in even region is : ",
41: round((hitsInEven/datasize),4))
42: '''
43: Function invocations
44: '''
45: # MonteCarloSimulation(int(eval(input("Enter the number of data points: "))))
46: # Throwing darts
47: MIN_RANGE=1
48: MAX_RANGE=100000
49: sentinel=True
50: while sentinel:
51: datasize=int(eval(input("Enter the no of simulations ({0}-{1}): ".
52: format(MIN_RANGE,MAX_RANGE))))
53: if (datasize<MIN_RANGE or datasize>MAX_RANGE):
54: print("Please enter data within range")
55: break
56: else:
57: AdvancedMonteCarloSimulation(datasize) Friday, March 21, 2014
Recursion-Fibonacci number generation with caching to prevent exponential time computation
1: package com.mridul.java.algorithms;
2: import java.util.Arrays;
3: import com.mridul.java.helpers.Console;
4: /*
5: * Program to calculate Fibonacci
6: * numbers using Recursion.
7: * This Recursion implements a cache to
8: * increase the speed
9: */
10: public class Recursion {
11: //constants
12: private static final int CACHE_SIZE=100;
13: private static final int MAX_SIZE=92;
14: //static variables
15: private static Recursion rec;
16: private static long[] cache;
17: private static String error_message;
18: /**
19: * Default Constructor
20: */
21: public Recursion(){
22: //create cache and add first two numbers
23: cache=new long[CACHE_SIZE];
24: //initializing array to zero
25: Arrays.fill(cache,0);
26: cache[0]=0;
27: cache[1]=1;
28: error_message=String.format(
29: "Please enter a valid positive integer in the range 0-%d !",
30: MAX_SIZE);
31: }
32: /**
33: * main
34: * @param args
35: */
36: public static void main(String[] args) {
37: try{
38: int size=0;
39: rec= new Recursion();
40: //infinite loop
41: do{
42: System.out.println(
43: "Enter the size of fibonacci numbers: ");
44: size=Integer.parseInt(
45: Console.readFromConsole());
46: if(validate(size)){
47: System.out.println(
48: "The fibonacci sum is : ");
49: System.out.println(rec.computeFibonacci(size));
50: }else{
51: System.out.println(error_message);
52: }
53: }while(size<0);
54: }catch(NumberFormatException ne){
55: System.out.println(error_message);
56: }
57: catch(Throwable t){
58: t.printStackTrace();
59: }
60: }
61: /*
62: * method to validate data
63: */
64: private static boolean validate(int size) {
65: if(size>=0 && size<=MAX_SIZE){
66: return true;
67: }
68: return false;
69: }
70: /*
71: * method which calculates the fibonacci sequence
72: *
73: */
74: private long computeFibonacci(int size) {
75: if(size==0)return 0;
76: if(size==1)return 1;
77: if(cache[size]!=0) return cache[size];
78: cache[size]=computeFibonacci(size-1)+computeFibonacci(size-2);
79: return cache[size];
80: }
81: //End of Recursion
82: } Program to wrap up Console input without using inbuilt NIO
1: package com.mridul.java.helpers;
2: import java.io.BufferedReader;
3: import java.io.IOException;
4: import java.io.InputStreamReader;
5: /**
6: * Helper class to ease Console read
7: * @author Mridul J Kurup
8: * @date 2014-03-21
9: */
10: public class Console {
11: /*
12: * private default constructor
13: */
14: private Console(){
15: //marking default constructor as private
16: //to prevent initialization
17: }
18: /*
19: * method to read from console
20: */
21: public static String readFromConsole() throws IOException{
22: BufferedReader br=new BufferedReader(
23: new InputStreamReader(System.in));
24: return br.readLine();
25: }
26: //End of Console
27: } Tuesday, March 18, 2014
Euclid's Algorithm to calculate the GCD and LCM of two given positive integers
1: package com.mridul.java.dump;
2: import java.io.BufferedReader;
3: import java.io.IOException;
4: import java.io.InputStreamReader;
5: /**Program to compute GCD and LCM of two numbers
6: * by using EuclidsAlgorithm
7: * @author Mridul Jayan
8: * @date 03/18/2014
9: */
10: public class EuclidsAlgorithm {
11: /*
12: * main method
13: */
14: public static void main(String[] args) {
15: try{
16: int gcd=0,lcm=0;
17: EuclidsAlgorithm ea=new EuclidsAlgorithm();
18: int num1=Integer.parseInt(ea.readConsoleInput(
19: "Enter the first number : "));
20: int num2=Integer.parseInt(ea.readConsoleInput(
21: "Enter the second number : "));
22: //re-align parameters based on size
23: if(num1<0 || num2<0){
24: System.out.println("\nPlease do not enter negative integers.");
25: }else if(num1==0 || num2==0){
26: System.out.println("\nThe GCD and LCM if one input is 0 is 0.");
27: }else{
28: if(num1<num2){
29: int temp=num1;
30: num1=num2;
31: num2=temp;
32: }
33: //calculate gcd and lcm
34: gcd=ea.computeGCD(num1,num2);
35: lcm=ea.computeLCM(num1,num2,gcd);
36: System.out.println(String.format(
37: "\nThe GCD is %d and the LCM is %d\n"
38: +"for the numbers %d and %d."
39: ,gcd,lcm,num1,num2));
40: }
41: }catch(Throwable t){
42: t.printStackTrace();
43: }
44: }
45: /*
46: * method to read input from console
47: */
48: private String readConsoleInput(String message) throws IOException{
49: System.out.println(message);
50: //read input from console
51: BufferedReader br=new BufferedReader(
52: new InputStreamReader(System.in));
53: return br.readLine();
54: }
55: /*
56: * method to compute GCD
57: * using Euclid's Algorithm
58: */
59: private int computeGCD(int large, int small){
60: int rem;
61: do{
62: rem=large%small;
63: large=small;
64: small=rem;
65: }while(rem>0);
66: //large will contain the gcd
67: System.out.println("large : "+large);
68: return large;
69: }
70: /*
71: * method to compute LCM
72: * as a result of the product of the numbers
73: * divided by their GCD
74: */
75: private int computeLCM(int large, int small, int gcd){
76: return ((large*small)/gcd);
77: }
78: //End of EuclidsAlgorithm
79: } Monday, March 17, 2014
Sieve of Eratosthenes- Prime number Generator
1: package com.mridul.java.dump;
2: import java.io.BufferedReader;
3: import java.io.IOException;
4: import java.io.InputStreamReader;
5: import java.util.Arrays;
6: /**Program to compute the prime numbers
7: * by using the Sieve of Eratosthenes
8: * @author Mridul Jayan
9: * @date 03/17/2014
10: */
11: public class SieveOfEratosthenes{
12: /*
13: * main method-program starting point
14: */
15: public static void main(String[] args) {
16: try{
17: SieveOfEratosthenes soe=new SieveOfEratosthenes();
18: int limit=Integer.parseInt(soe.readConsoleInput(
19: "Enter the limit till prime is to be generated:"));
20: System.out.println(String.format(
21: "The prime numbers from 0 till %d are : ", limit));
22: int prime=0; //index for the primes
23: //increment limit by one to account for zero index
24: for(boolean candidate:soe.computePrime(++limit)){
25: if(candidate){
26: System.out.println(prime);
27: }
28: ++prime;
29: }
30: }catch(Throwable t){
31: System.out.println("An error occured!");
32: t.printStackTrace();
33: }
34: }
35: /*
36: * method to generate prime
37: * based on Sieve of Eratosthenes
38: */
39: private boolean[] computePrime(int limit){
40: boolean[] prime=new boolean[limit];
41: //assume that all numbers are prime by default
42: Arrays.fill(prime,true);
43: //setting 0 and 1 as non-primes
44: prime[0]=false;
45: prime[1]=false;
46: //starting from 2 use the sieve to weed out non-primes
47: int index=2;
48: //speed up technique
49: int sqrRoot=(int)Math.sqrt(limit);
50: while(index<sqrRoot){
51: if(prime[index]){
52: //eliminate all multiples of that index
53: for(int ctr=index*index;ctr<limit;ctr=ctr+index){
54: prime[ctr]=false;
55: }
56: }
57: //increment to the next prime
58: ++index;
59: }
60: return prime;
61: }
62: /*
63: * method to read input from console
64: */
65: private String readConsoleInput(String message) throws IOException{
66: System.out.println(message);
67: //read input from console
68: BufferedReader br=new BufferedReader(
69: new InputStreamReader(System.in));
70: return br.readLine();
71: }
72: //End of Sieve of Eratosthenes
73: } Program to Crash JVM-Attempt 2- Linear Solution-Takes time
1: package com.mridul.java.dump;
2: import java.util.ArrayList;
3: /**Program to crash the JVM
4: * as per a problem on the Passionate
5: * Programmer book. This solution results
6: * in an OutOfMemory Error. The actual
7: * solution might require JNI as per
8: * discussion on forums
9: * WARNING: WILL CRASH YOUR MACHINE REQUIRING REBOOT
10: * @author Mridul Jayan
11: * @date 03/17/2014
12: */
13: public class CrashJVM2 implements Runnable {
14: static int instanceCount=0;
15: ArrayList<CrashJVM2> instances;
16: public static void main(String... args){
17: try{
18: System.out.println("Attempting Crash JVM 2");
19: ArrayList<Thread> threadInstances=new ArrayList<Thread>();
20: Thread t;
21: //linear solution-takes more time to crash
22: while(true){
23: ++instanceCount;
24: t=new Thread(new CrashJVM2());
25: t.start();
26: threadInstances.add(t);
27: }
28: }catch(Throwable t){
29: if(t instanceof OutOfMemoryError){
30: System.out.println("JVM Crashed due to OutOfMemoryError!");
31: }
32: t.printStackTrace();
33: }
34: }
35: @Override
36: public void run() {
37: // TODO Auto-generated method stub
38: System.out.println("Created Instance : "+instanceCount);
39: int count=0;
40: System.out.println("Starting Infinite Loop!");
41: while(true){
42: System.out.println("Inside run() for run : "+count);
43: ++count;
44: }
45: }
46: //End of CrashJVM2
47: } Program to Crash JVM-Attempt 1- Exponential infinite loop
1: package com.mridul.java.dump;
2: import java.util.ArrayList;
3: /**Program to crash the JVM
4: * as per a problem on the Passionate
5: * Programmer book. This solution results
6: * in an OutOfMemory Error. The actual
7: * solution might require JNI as per
8: * discussion on forums
9: * WARNING: WILL CRASH YOUR MACHINE REQUIRING REBOOT
10: * @author Mridul Jayan
11: * @date 03/09/2014
12: */
13: public class CrashJVM implements Runnable {
14: @Override
15: public void run() {
16: System.out.println("Attempting to Crash JVM!");
17: ArrayList<CrashJVM> crashJVM=new ArrayList<CrashJVM>();
18: int ctr=0;
19: double expctr=0.0;
20: //exponentials tend to scale faster
21: while(true){
22: expctr=Math.exp((double)ctr);
23: for(double ictr=0.0;ictr<expctr;ictr++){
24: crashJVM.add(new CrashJVM());
25: System.out.println("Created Instance "+(++ctr));
26: }
27: }
28: }
29: public static void main(String[] args) {
30: try {
31: ArrayList<Thread> childThread=new ArrayList<Thread>();
32: while(true){
33: Thread t=new Thread(new CrashJVM());
34: childThread.add(t);
35: t.start();
36: }
37: }catch(Throwable t){
38: if(t instanceof OutOfMemoryError){
39: System.out.println("The JVM has crashed!");
40: }
41: t.printStackTrace();
42: }
43: }
44: //End of CrashJVM
45: } Sunday, March 16, 2014
Program to shift all zeros in an integer array to the end
1: package com.mridul.java.dump;
2: import java.io.BufferedReader;
3: import java.io.InputStreamReader;
4: /**
5: * Program to all sort zeros to end of an
6: * integer array. The algorithm is O(n)
7: * @author Mridul J Kurup
8: * @date 03/17/2014
9: *
10: */
11: public class NumSort{
12: static int len=0;
13: static int data[];
14: /*
15: * Private static method to sort the array
16: * with all zeros transposed to the end
17: */
18: private static void sortArray(String input){
19: data=new int[len];
20: int numOfZeroes=0;
21: //store all non zero digits
22: System.out.println("The re-arranged numbers are : ");
23: for(int index=0;index<len;index++){
24: int currDigit=Integer.parseInt(String.valueOf
25: (input.charAt(index)));
26: //skip if zero is encountered
27: if(currDigit==0){
28: ++numOfZeroes;
29: continue;
30: }else{
31: //add rest of the digits to array
32: data[index]=currDigit;
33: System.out.print(data[index]);
34: }
35: }
36: //attach all zeros to end
37: for(int index=(len-numOfZeroes-1);index<len;index++){
38: data[index]=0;
39: System.out.print(data[index]);
40: }
41: //new line
42: System.out.println();
43: }
44: /*
45: * program start point
46: */
47: public static void main(String... args) {
48: try{
49: System.out.println("Enter the int array including zeros");
50: BufferedReader bsr=new BufferedReader(
51: new InputStreamReader(System.in));
52: String input=bsr.readLine();
53: System.out.println("The input is "+input);
54: len=input.length();
55: //test for length
56: if(len>0){
57: sortArray(input);
58: }else{
59: System.out.println("Please enter valid int array");
60: }
61: }catch(Throwable t){
62: t.printStackTrace();
63: }
64: }
65: //End of NumSort.java
66: } Sunday, March 9, 2014
Problem 1.6.1 - The 3n+1 Problem - Java
1: package chapter1; 2: import java.util.Scanner; 3: /**Program to determine the cycle-length of integers 4: * Start with an integer n 5: * If even-divide the integer n by 2 6: * If odd-compute using the formula 3*n+1 7: * cycle-length is the number of outputs till n=1 8: * n ranges from (0,1000000)-open interval 9: * range is given a (i,j) 10: * 11: * @author mridul 12: * @date 03/09/2014 13: */ 14: public class Problem_161 { 15: //constant declarations 16: private static int MIN_RANGE=0; 17: private static int MAX_RANGE=1000000; 18: public static void main(String[] args) { 19: try { 20: //method variables 21: Scanner scan=new Scanner(System.in); 22: int min, max; 23: System.out.println("Enter two integers in ascending order from " 24: + "the range (0,1000000):"); 25: //create a problem instance 26: Problem_161 problem= new Problem_161(); 27: System.out.print("Enter first argument : "); 28: min=Integer.parseInt(scan.nextLine()); 29: System.out.print("\nEnter second argument : "); 30: max=Integer.parseInt(scan.nextLine()); 31: System.out.println("\n\n"); 32: scan.close(); 33: //proceed if input is valid 34: if(problem.testInput(min,max)){ 35: System.out.println("The output in the order min, max, " 36: + "maximum cyclength is : "); 37: System.out.println(min+" "+max+" "+problem.computeCycleLength(min,max)); 38: }else{ 39: System.out.println("Invalid Input, please rerun with correct input!"); 40: } 41: }catch(Exception e){ 42: System.out.println("An exception was encountered as given below : "); 43: e.printStackTrace(); 44: } 45: } 46: /*private method to compute cycle length 47: * returns the cycle length 48: */ 49: int computeCycleLength(int min,int max){ 50: int cycleMax=0; //max cycle length 51: int candidate=min; 52: while(candidate<=max){ 53: int cycleLength=1; //accounting for 1 54: //if even divide by 2 else compute 3n+1 55: //till candidate is greater than 1 56: while(candidate>1){ 57: if(candidate%2==0){ 58: candidate=candidate/2; 59: }else{ 60: candidate=(3*candidate)+1; 61: } 62: ++cycleLength; 63: } 64: //increment candidate to next value 65: candidate=++min; 66: //replace cycleMax if cycleLength is greater 67: cycleMax =(cycleLength>cycleMax)? cycleLength:cycleMax; 68: } 69: return cycleMax; 70: } 71: /* private method to test input validity 72: * provided testLimits method returns true 73: * returns true if input is in ascending order 74: */ 75: boolean testInput(int min, int max){ 76: //if within limits test for order 77: if(testLimits(min) && testLimits(max)){ 78: if(min<max){ 79: return true; 80: } 81: } 82: return false; //default return 83: } 84: /*private method to test if input is within limits 85: * returns true if condition is satisfied 86: */ 87: boolean testLimits(int number){ 88: if(number>MIN_RANGE && number<MAX_RANGE){ 89: return true; 90: } 91: return false; //default return 92: } 93: //End of Problem_161 94: }
Subscribe to:
Posts (Atom)