Author Archive: Paul Epps

I Wish I Was the Moon

21 Apr 2018 /

Walking in the Rain

19 Apr 2018 /

I’m walking in a California spring rain . . . no umbrella, just like my caveman ancestors.

Granted, cavemen couldn’t record their favorite TV shows and watch them at their leisure like we can, but they had a more authentic relationship with the natural world . . .


Fish and Whistle

18 Apr 2018 /

Father forgive us for what we must do
You forgive us and we’ll forgive you
We’ll forgive each other till we both turn blue
And we’ll whistle and go fishing in heaven

— John Prine, “Fish and Whistle”

See You in Hell

18 Apr 2018 /

Satan

[See You in Hell is a feature by our guest blogger, Satan — PE]

A woman was sucked out the window of a Southwest Airlines plane . . . not a black woman, fortunately, so Southwest won’t have to shut down for racial bias training.

In other news, David Hogg is telling his Twitter followers to boycott the BlackRock and Vanguard investment firms.

“David Hogg’s Twitter followers” . . . I’m rolling that phrase around on my tongue. “David Hogg’s Twitter followers.” Might be a good name for an improv group.

When I think of all the great men — Nietzsche, Van Gogh . . . you can think of your own favorite examples — who lived as anonymous failures and died as broken-down loonies, the thought of people actively tracking the musings of David Hogg amuses me greatly.

See you in Hell!


Competitive Programming: POJ 1426 – Find The Multiple

18 Apr 2018 /

Description

Given a positive integer n, write a program to find out a nonzero multiple m of n whose decimal representation contains only the digits 0 and 1. You may assume that n is not greater than 200 and there is a corresponding m containing no more than 100 decimal digits.
Input

The input file may contain multiple test cases. Each line contains a value of n (1 <= n <= 200). A line containing a zero terminates the input.

Output

For each value of n in the input print a line containing the corresponding value of m. The decimal representation of m must not contain more than 100 digits. If there are multiple solutions for a given value of n, any one of them is acceptable.

Sample Input

2
6
19
0

Sample Output

10
100100100100100100
111111111111111111

Link to problem

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
/*
 * There are at least 3 ways to solve this:
 * 
 * 1. NUMERICAL METHODS
 * 
 * I found several links to numerical methods and couldn't understand any of them.
 * Here's a sample:
 * 
 * https://math.stackexchange.com/questions/164986/smallest-multiple-whose-digits-are-only-ones-and-zeros
 * 
 * 2. CHEAT
 * 
 * Input is guaranteed to be no more than 200, and results have been computed 
 * for far more numbers than that (see http://oeis.org/A004290/b004290.txt). 
 * Put the answers in a hash table and just look them up.
 * 
 * 3. BREADTH-FIRST SEARCH (BFS)
 * 
 * Every node of the search tree will be a binary digit number. For each number x, 
 * the next-level nodes will be x0 and x1 (x concatenated with 0 and 1).
 * 
 * We start by adding 1 to the queue, which will then add 10 and 11 and so on.
 * After taking a number from the queue, we’ll check whether the number is a 
 * multiple of the given number or not. If yes, we have our answer.
 * 
 * Optimization: we're using a set for mod values. If a number has a 
 * previously seen mod value, we don’t add this new number to the queue. 
 * Explanation: Let x and y be numbers that give the same value mod N. 
 * Let x < y. Let z be another number which, when appended to y gives a 
 * number divisible by N. Then we can also append this number to x and 
 * get a number divisible by N. So we can safely ignore y.
 * 
 * NOTE: The sample outputs given for inputs 6 and 19 are "acceptable" but 
 * much smaller answers are available. 
 * 
 */

import java.util.ArrayDeque;
import java.util.Deque;
import java.util.HashSet;
import java.util.Scanner;
import java.util.Set;

public class Main {

	// returns smallest multiple which has
	// only 1s and 0s
	static long getMinimumMultiple(int N)
	{
		Deque<Long> q = new ArrayDeque<Long>();
		Set<Long> visit = new HashSet<Long>();
	 
	    long t = 1;
	 
	    //  starting with 1 in queue
	    q.add(t);
	 
	    //  loop while queue is not empty
	    while (!q.isEmpty())
	    {
	        // Take the first number from queue.
	        t = q.pop();
	 
	        // Find remainder of t with respect to N.
	        long rem = t % N;
	 
	        // if remainder is 0 then we have
	        // found our solution
	        if (rem == 0)
	            return t;
	 
	        // If this remainder is not previously seen,
	        // then add t + '0' and t + '1' to queue
	        else if(!visit.contains(rem))
	        {
	            visit.add(rem);
	            q.add(t * 10);
	            q.add(t * 10 + 1);
	        }
	    }
	    return -1; //something went wrong
	}
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		
		while (N != 0) {
			System.out.println(getMinimumMultiple(N));
			N = sc.nextInt();
		}
		
		sc.close();
	}
}

Passenger Sucked Out of Plane Window: Another Reason I Prefer to Just Stay Home

18 Apr 2018 /

Southwest passenger died after broken plane window nearly sucked her outCNN

You are now free to move about the country!

Thanks, but I’d prefer to move about the country from inside the plane . . .


Competitive Programming: POJ 2084 – Game of Connections

18 Apr 2018 /

Description

This is a small but ancient game. You are supposed to write down the numbers 1, 2, 3, . . . , 2n – 1, 2n consecutively in clockwise order on the ground to form a circle, and then, to draw some straight line segments to connect them into number pairs. Every number must be connected to exactly one another. And, no two segments are allowed to intersect.

It’s still a simple game, isn’t it? But after you’ve written down the 2n numbers, can you tell me in how many different ways can you connect the numbers into pairs? Life is harder, right?

Input

Each line of the input file will be a single positive number n, except the last line, which is a number -1.
You may assume that 1 <= n <= 100.

Output

For each n, print in a single line the number of ways to connect the 2n numbers into pairs.

Sample Input

2
3
-1

Sample Output

2
5

Link to problem

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
import java.math.BigInteger;
import java.util.Scanner;

/*
 * There are two ways to solve it.
 * 
 * 1. RECURSIVE
 * 
 * Select a fixed point O from one of the 2n points on the circle. A line going 
 * from this point would have to divide the circle into two regions, each 
 * containing an even number of points. There are thus n possible choices for a 
 * chord leaving from O (try drawing it).
 * 
 * Choosing one such chord will lead to unique divisions of the circle (two 
 * different chords leaving from O will give different divisions). Any division 
 * of the circle would match with one of these chords. So we have divided the 
 * problem into a set of disjoint subproblems.
 * 
 * Then, to get a recursive formula, we need to count, for each possible chord,
 * how many points are on each side of the chord : the regions have 
 * (2k, 2(n?k?1)) points, for 0 ? k ? n?1.
 * 
 * So a recursive formula for h(n) would be:
 * 
 *      h(n) = sum, from k = 0 to k = n-1, of h(k) * h(n?k?1)
 *      
 * 2. CLOSED FORM
 * 
 * The solution is the set of Catalan numbers. The nth Catalan number can be 
 * calculated directly as:
 * 
 *     the product, from k = 2 to k = n, of (n + k) / k
 *     
 * NOTE: We use BigIntegers because Catalan numbers get big very quickly. 
 * (See https://oeis.org/A000108)
 *  
 */
public class Main {

	static BigInteger catalan(int n) {

		// dp array containing the sum
		BigInteger[] dpArray = new BigInteger[n + 1];

		dpArray[0] = BigInteger.ONE;
		dpArray[1] = BigInteger.ONE;

		for (int i = 2; i <= n; i++) {
			dpArray[i] = BigInteger.ZERO;

			for (int k = 0; k < i; k++) {
				dpArray[i] = dpArray[i].add(dpArray[k].multiply(dpArray[i - k - 1]));
			}
		}

		return dpArray[n];
	}

	static BigInteger catalanClosedForm(int n) {

		if (n <= 1)
			return BigInteger.ONE;

		BigInteger num = BigInteger.ONE;
		BigInteger denom = BigInteger.ONE;
		
		for (int k = 2; k <= n; k++) {
			num = num.multiply(new BigInteger((n + k) + ""));
			denom = denom.multiply(new BigInteger(k + ""));
		}
		
		return num.divide(denom);
	}

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);

		int n = sc.nextInt();

		while (n != -1) {
			System.out.println(catalan(n).toString());
			n = sc.nextInt();
		}
		sc.close();
	}
}

Where it Went

17 Apr 2018 /

Candle

I saw a child carrying a light.
I asked him where he had brought it from.
He put it out and said:
“Now you tell me where it is gone.”

— Hasan of Basra

Competitive Programming: USACO Big Barn

16 Apr 2018 /

Farmer John wants to place a big square barn on his square farm. He hates to cut down trees on his farm and wants to find a location for his barn that enables him to build it only on land that is already clear of trees. For our purposes, his land is divided into N x N parcels. The input contains a list of parcels that contain trees. Your job is to determine and report the largest possible square barn that can be placed on his land without having to clear away trees. The barn sides must be parallel to the horizontal or vertical axis.

EXAMPLE

Consider the following grid of Farmer John’s land where ‘.’ represents a parcel with no trees and ‘#’ represents a parcel with trees:

          1 2 3 4 5 6 7 8
        1 . . . . . . . .
        2 . # . . . # . .
        3 . . . . . . . .
        4 . . . . . . . .
        5 . . . . . . . .
        6 . . # . . . . .
        7 . . . . . . . .
        8 . . . . . . . .

The largest barn is 5 x 5 and can be placed in either of two locations in the lower right part of the grid.

PROGRAM NAME: bigbrn

INPUT FORMAT

Line 1: Two integers: N (1 <= N <= 1000), the number of parcels on a side, and T (1 <= T <= 10,000) the number of parcels with trees
Lines 2..T+1: Two integers (1 <= each integer <= N), the row and column of a tree parcel

SAMPLE INPUT (file bigbrn.in)

8 3
2 2
2 6
6 3

OUTPUT FORMAT

The output file should consist of exactly one line, the maximum side length of John’s barn.

SAMPLE OUTPUT (file bigbrn.out)

5

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
import java.io.BufferedWriter;
import java.io.File;
import java.io.FileWriter;
import java.io.IOException;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.Scanner;

/*
 * ID: paul9
 * LANG: JAVA
 * TASK: bigbrn
 * 
 * Dynamic programming solution: 
 * 
 * Initialize another matrix (dp) with the same dimensions as the original.
 * dp(i,j) represents the side length of the maximum square whose bottom 
 * right corner is the cell with index (i,j) in the original matrix.
 * 
 * Starting from index (1,1), for every '.' found in the original matrix, 
 * update the value of the current element as
 * 
 *   dp(i, j) = min ( dp(i-1, j), dp(i-1, j-1), dp(i, j-1) ) + 1. 
 * 
 * We also remember the size of the largest side length found so far. 
 * In this way, we traverse the original matrix once and find the maximum 
 * side length.
*/

class bigbrn {

	static int maximalSquare(char[][] matrix) {
		int rows = matrix.length, cols = rows > 0 ? matrix[0].length : 0;
		int[][] dp = new int[rows + 1][cols + 1];
		int maxsqlen = 0;
		for (int i = 1; i <= rows; i++) {
			for (int j = 1; j <= cols; j++) {
				if (matrix[i - 1][j - 1] == '.') {
					dp[i][j] = Math.min(Math.min(dp[i][j - 1], dp[i - 1][j]), dp[i - 1][j - 1]) + 1;
					maxsqlen = Math.max(maxsqlen, dp[i][j]);
				}
			}
		}
		return maxsqlen;
	}

	public static void main(String[] args) throws IOException {
		long start = System.currentTimeMillis();
		Scanner sc = new Scanner(new File("bigbrn.in"));
		PrintWriter out = new PrintWriter(new BufferedWriter(new FileWriter("bigbrn.out")));

		int N = sc.nextInt();
		int T = sc.nextInt();

		char[][] grid = new char[N][N];

		// initialize the grid
		for (int i = 0; i < grid.length; i++) {
			char[] row = new char[N];
			Arrays.fill(row, '.');
			grid[i] = row;
		}

		for (int i = 0; i < T; i++) {
			// converting from 1-based to 0-based
			int x = sc.nextInt() - 1;
			int y = sc.nextInt() - 1;

			grid[x][y] = '#';
		}

		sc.close();

		out.println(maximalSquare(grid));
		out.close();

		System.out.println("$:" + (System.currentTimeMillis() - start));

	}
}

Competitive Programming: POJ 1654 – Area

16 Apr 2018 /

Description

Consider an infinite full binary search tree (see the figure below), the numbers in the nodes are 1, 2, 3, …. In a subtree whose root node is X, we can get the minimum number in this subtree by repeating going down the left node until the last level, and we can also find the maximum number by going down the right node. Now you are given some queries as “What are the minimum and maximum numbers in the subtree whose root node is X?” Please try to find answers for the queries.

BST

Input

In the input, the first line contains an integer N, which represents the number of queries. In the next N lines, each contains a number representing a subtree with root number X (1 <= X <= 231 – 1).

Output

There are N lines in total, the i-th of which contains the answer for the i-th query.

Sample Input

2
8
10

Sample Output

1 15
9 11

Link to problem

import java.util.Scanner;

/*
There's a pattern with the lowest-order set bit of the numbers:
  - For leaf-node numbers, the lowest order set bit is 1.
  - Go up one level and the lowest order set bit is 2.
  - Go up one more level and the lowest order set bit is 4.
  - Etc.

That said, we can take advantage of Bit Hack #7 from 
http://www.catonmat.net/blog/low-level-bit-hacks-you-absolutely-must-know/
to isolate the lowest-order set bit.

Each node will have one less than that number of nodes in each subtree.
 */

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);

		int N = sc.nextInt();
		while (N-- > 0) {
			int x = sc.nextInt();
			int diff = (x & (-x)) -1;
			System.out.println((x - diff) + " " + (x + diff));
		}

		sc.close();
	}
}

You Will Know Whether it Has All Been True

16 Apr 2018 /

How does a life flash before one’s eyes
At the end? How is there time for so much time?
You pick up the book and hold it, knowing
Long since the failed romance, the strained
Marriage, the messenger, the mistake,
Knowing it all at once, as if looking through
A lighted dormer on the dark crest of a barn.
You know who is inside, and who has always been
At the other edge of the wood. She is waiting
For no one in particular. It could be you.
If you can discover which tree she has become,
You will know whether it has all been true.

— J.D. McClatchy, “Wolf’s Trees”

If liberty means anything at all it means the right to tell people what they do not want to hear. — George Orwell, Animal Farm


Competitive Programming: POJ 2242 — The Circumference of the Circle

14 Apr 2018 /

Description

To calculate the circumference of a circle seems to be an easy task – provided you know its diameter. But what if you don’t?

You are given the cartesian coordinates of three non-collinear points in the plane.
Your job is to calculate the circumference of the unique circle that intersects all three points.

Input

The input will contain one or more test cases. Each test case consists of one line containing six real numbers x1,y1, x2,y2,x3,y3, representing the coordinates of the three points. The diameter of the circle determined by the three points will never exceed a million. Input is terminated by end of file.

Output

For each test case, print one line containing one real number telling the circumference of the circle determined by the three points. The circumference is to be printed accurately rounded to two decimals. The value of pi is approximately 3.141592653589793.

Sample Input

0.0 -0.5 0.5 0.0 0.0 0.5
0.0 0.0 0.0 1.0 1.0 1.0
5.0 5.0 5.0 7.0 4.0 6.0
0.0 0.0 -1.0 7.0 7.0 7.0
50.0 50.0 50.0 70.0 40.0 60.0
0.0 0.0 10.0 0.0 20.0 1.0
0.0 -500000.0 500000.0 0.0 0.0 500000.0

Sample Output

3.14
4.44
6.28
31.42
62.83
632.24
3141592.65

Link to problem

import java.util.Scanner;

public class Main
{
	static final double EPS = 1e-12;

	static double dot(PT p, PT q) {
		return p.x * q.x + p.y * q.y;
	}

	// distance squared
	static double dist2(PT p, PT q) {
		return dot(p.subtract(q), p.subtract(q));
	}

	static double cross(PT p, PT q) {
		return p.x * q.y - p.y * q.x;
	}

	static PT RotateCW90(PT p) {
		return new PT(p.y, -p.x);
	}

	// compute intersection of line passing through a and b
	// with line passing through c and d, assuming that unique
	// intersection exists; for segment intersection, check if
	// segments intersect first
	static PT ComputeLineIntersection(PT a, PT b, PT c, PT d) {
		b = b.subtract(a);
		d = c.subtract(d);
		c = c.subtract(a);
		assert (dot(b, b) > EPS && dot(d, d) > EPS);
		return a.add(b.multiply(cross(c, d)).divide(cross(b, d)));
	}

	// compute center of circle given three points
	static PT ComputeCircleCenter(PT a, PT b, PT c) {
		b = (a.add(b)).divide(2);
		c = (a.add(c)).divide(2);
		return ComputeLineIntersection(b, b.add(RotateCW90(a.subtract(b))), c,
						c.add(RotateCW90(a.subtract(c))));
	}

	public static void main(String[] args) {
		
//		long start = System.currentTimeMillis();

		Scanner sc = new Scanner(System.in);
		Scanner lineTokenizer;
		
		while (sc.hasNextLine()) {
			lineTokenizer = new Scanner(sc.nextLine());
			
			PT p1 = new PT(lineTokenizer.nextDouble(), lineTokenizer.nextDouble());
			PT p2 = new PT(lineTokenizer.nextDouble(), lineTokenizer.nextDouble());
			PT p3 = new PT(lineTokenizer.nextDouble(), lineTokenizer.nextDouble());
			
			lineTokenizer.close();
			
			PT center = ComputeCircleCenter(p1, p2, p3);
			
			// distance from point to center
			double radius = Math.sqrt(dist2(p1, center));
			
			System.out.printf("%.2f\n", Math.PI * radius * 2);
		}
		
		sc.close();
//		System.out.println("$:" + (System.currentTimeMillis() - start));
		}
}

class PT {
	double x, y;

	PT() {
	}

	PT(double x, double y) {
		this.x = x;
		this.y = y;
	}

	PT(PT p) {
		this.x = p.x;
		this.y = p.y;
	}

	PT add(final PT p) {
		return new PT(x + p.x, y + p.y);
	}

	PT subtract(final PT p) {
		return new PT(x - p.x, y - p.y);
	}

	PT multiply(double c) {
		return new PT(x * c, y * c);
	}

	PT divide(double c) {
		return new PT(x / c, y / c);
	}

	@Override
	public String toString() {
		return "(" + x + "," + y + ")";
	}
}

The More We Rely on Technology . . .

14 Apr 2018 /

No Internet Today

We had a brief network outage at the office, during which Mr. Frick walked over to Mr. Frack’s desk and said, “The network’s down. We can’t do the screen share,” i.e., they can’t see each other’s computer screen over the network because it’s down.

I was waiting for one of them — Frick or Frack — to say “Let’s just sit together in front of the one computer here like they used to in olden days” but neither of them ever did . . .


Foot of Pride

14 Apr 2018 /

Billy Sunday

Yeah, from the stage they’ll be tryin’ to get water outta rocks
A whore will pass the hat, collect a hundred grand and say thanks
They like to take all this money from sin, build big universities to study in
Sing “Amazing Grace” all the way to the Swiss banks

Well, there ain’t no goin’ back when your foot of pride come down
Ain’t no goin’ back

— Bob Dylan, “Foot of Pride”

Essay on the One Hand and the Other

14 Apr 2018 /

Consider the palms. They are faces,
eyes closed, their five spread fingers
soft exclamations, sadness or surprise.
They have smile lines, sorrow lines, like faces.
Like faces, they are hard to read.

Somehow the palms, though they have held my life
piece by piece, seem young and pale.
So much has touched them, nothing has remained.
They are innocent, maybe, though they guess
they have a darker side that they cannot grasp.

The backs of my hands, indeed, are so different
that sometimes I think they are not mine,
shadowy from the sun, all bones and strain,
but time on my hands, blood on my hands—
for such things I have never blamed my hands.

One hand writes. Sometimes it writes a reminder
on the other hand, which knows it will never write,
though it has learned, in secret, how to type.
That is sad, perhaps, but the dominant hand is sadder,
with its fear that it will never, not really, be written on.

They are like an old couple at home. All day,
each knows exactly where the other is.
They must speak, though how is a mystery,
so rarely do they touch, so briefly come together,
now and then to wash, maybe in prayer.

I consider my hands, palms up. Empty, I say,
though it is exactly then that they are weighing
not a particular stone or loaf I have chosen
but everything, everything, the whole tall world,
finding it light, finding it light as air.


Say One More Stupid Thing to Me

10 Apr 2018 /

Sing me one more song, about you love me to the moon and the stranger
And your fall by the sword love affair with Errol Flynn
In these times of compassion when conformity’s in fashion
Say one more stupid thing to me before the final nail is driven in.

— Bob Dylan, “Foot of Pride”

A Set Pattern That MUST Be Followed

8 Apr 2018 /

Mr Boffo


Thomas Jefferson on Hillary Clinton

7 Apr 2018 /
Thomas Jefferson

My fellow Americans —

Hillary Clinton is still rattling off all the “reasons” she lost the 2016 presidential election: misogyny, the FBI, sexism, the NRA, Russia . . .

To my knowledge, she has never correctly identified the actual culprits: the patriotic men and women of this country.

Thomas Jefferson


How You Should Think Of Me

7 Apr 2018 /
Harper's Muslims and Christians

A disciple came to Maruf Kharki and said:

“I have been talking to people about you. Jews claim that you are a Jew; Christians revere you as one of their own saints; Muslims insist that you are the greatest of all Muslims.”

Maruf answered:

“This is what humanity says in Baghdad. When I was in Jerusalem, Jews said that I was a Christian, Muslims that I was a Jew, and Christians that I was a Muslim.”

“What must we think of you, then?” the man said.

“Some do not understand me and they revere me. Others do not either, so they revile me. That is what I have come to say. You should think of me as one who has said this.”


Next Page »