Simple Asterisk Pattern with Recursion

October 18, 2010 at 14:23 (code golf, java)

Background: I introduced code golf in a previous post.

I recently came across an easy but fun problem posted on Yahoo! Answers. It could make for a good code golf exercise. I will write the problem statement in a purposely vague manner, but clear enough to make the goal obvious; specifics can be added according to any particular contest or testing environment.

Using only recursion and no loops, print a triangular pattern of asterisks according to the following example:

Input:

1
3

Output:

*
*
**
***
**
*

Read the rest of this entry »

Permalink Leave a Comment

Reflexive Assignment in Java

October 11, 2010 at 06:54 (code golf, java)

Background: Code golf is a game in which the goal is to solve programming problems using as few keystrokes as possible. It has its roots in Perl golf, and anyone with golfing experience knows that Perl is particularly well suited to such challenges. J and K, as well as the more esoteric GolfScript, are also known for combining terse syntax with powerful features. Obfuscation is a related topic.

In this post, I will discuss a snippet of Java code one might not normally think to write. I understand that “Java code golf” is practically an oxymoron, since it seems the goal of Java is to write code using as many keystrokes as possible, but let us overlook this point for now.

Suppose we want to increment a variable by an integer from standard input, but only if that integer is positive. We could use this code fragment:

Read the rest of this entry »

Permalink Leave a Comment

Java Custom addSlashes()

October 1, 2010 at 06:56 (java, javascript, tutorial, web dev)

Java regexes can get pretty clunky due to the dual use of the backslash character, as is commonly known. Although there’s not a lot to it, below is some code to add slashes for these characters: backslash, line feed, carriage return, null, single quote. It is used in a web application to format JSON strings on the server before passing to the client, where the objects are then processed by JavaScript/Ext JS. Maybe someone will find it useful!

public class StringUtil {
    public static String addSlashes(String s) {
        s = s.replaceAll("\\\\", "\\\\\\\\");
        s = s.replaceAll("\\n", "\\\\n");
        s = s.replaceAll("\\r", "\\\\r");
        s = s.replaceAll("\\00", "\\\\0");
        s = s.replaceAll("'", "\\\\'");
        return s;
    }
}

Incidentally, there are other places where the following JavaScript replacement is necessary:

s = s.replace(/"/g, '"');

Permalink Leave a Comment

Frobenius Numbers – Round Robin Algorithm

September 20, 2010 at 14:50 (algorithm, java, math.NT)

Frobenius numbers are solutions to the coin problem. Let \displaystyle 0<a_1<\cdots<a_n be coin denominations; what is the smallest sum of money that cannot be obtained using these coins? More formally, define the Frobenius number \displaystyle g(a_1,\,\ldots\,,a_n) as the greatest number that is not a linear combination \sum_{i=1}^n x_ia_i with \displaystyle 0 \le x_i \in \mathbb{Z} . The Frobenius number exists if and only if \displaystyle a_1 > 1 and \displaystyle \gcd(a_1,\,\ldots\,,a_n)=1 . A special case of Frobenius numbers involves the interestingly named McNugget numbers, and there is a well-known formula when \displaystyle n=2 given by \displaystyle g(a_1,a_2)=a_1a_2-a_1-a_2 sometimes known as the Chicken McNugget Theorem.

Read the rest of this entry »

Permalink Leave a Comment

How To: SPOJ TEST Using JAR File

September 12, 2010 at 07:39 (java, tutorial)

Background: Sphere Online Judge (SPOJ) is an online judge system accepting a wide variety of programming languages. It’s a great way to test your skills as a programmer, and can be quite addictive if you like a good challenge.

While browsing the SPOJ forums, I did not find a thread detailing how to successfully submit a JAR for the first problem, TEST. So, here’s a quick guide. I’m using Windows, but there should be little difference with other operating systems since everything is done through the command line. I will assume you already have the JDK installed and paths set up such that if you type java, javac, or jar from the command line the appropriate programs will be executed.

Read the rest of this entry »

Permalink 3 Comments

Clustered k-Subsets

July 11, 2010 at 04:39 (algorithm, java, math.CO)

This post is mostly copied and pasted from my posts in this thread on MHF.

Problem statement: Let \displaystyle S_n = \{1,\ \dots\ ,n\} and let \displaystyle f(n,k,x) be the number of k-subsets of \displaystyle S_n such that when the elements are ordered from least to greatest, the absolute difference of any two adjacent elements is less than \displaystyle x. Find a formula or algorithm to determine \displaystyle f(n,k,x) for arbitrary \displaystyle n,k,x \in \mathbb{Z}, n\ge 0.

Read the rest of this entry »

Permalink Leave a Comment

Continued Fractions of Square Roots – Steps

July 4, 2010 at 19:31 (algorithm, java, math.NT, tutorial)

Everyone knows what continued fractions are, right? Continued fractions have interesting properties and can be used to obtain best rational approximations for real numbers, among other things. Here is an example of a finite continued fraction:

8.309 = 8+\cfrac{1}{3+\cfrac{1}{4+\cfrac{1}{4+\cfrac{1}{3+\cfrac{1}{2+\cfrac{1}{2}}}}}}

Read the rest of this entry »

Permalink Leave a Comment

2×2 Squares on a Randomly Filled m×n Board

June 28, 2010 at 17:03 (algorithm, java, math.PR)

This post, like the last one, is an offshoot of a thread on Math Help Forum. The situation is: Suppose there is an m×n chess-like board and we wish to fill in all the (1×1) squares according to: all squares are either black or white, and the probability that a square is black is p . What is the probability that a randomly filled board will contain at least one 2×2 black square?

Read the rest of this entry »

Permalink Leave a Comment

Blackjack Basic Strategy – Infinite Deck

May 24, 2010 at 06:24 (algorithm, java, math.PR)

I came across a good programming exercise over on this thread at Math Help Forum (I’m “undefined”), and here are the results. This program reproduces the charts and expected value on this page over at The Wizard of Odds for an infinite deck. I realise the code could be cleaner, but I’m pleased with the performance of the underlying algorithms. On my laptop with modest specs, calculation takes about 20 milliseconds.

Read the rest of this entry »

Permalink Leave a Comment