Archive for April, 2008

Minimal Pythagorean circles

Sunday, April 27th, 2008

Let us define a Pythagorean circle, as a circle in the plane, centered at origin, with one or more points of the circle having both x and y coordinates as integers. Given the symmetry of the situation, the number of such points is divisible by four, so let us divide the number of points by four and call this the degree of the Pythagorean circle. If we have a Pythagorean circle of degree X, where there are no Pythagorean circles with a smaller radius and degree X, we call that a minimal Pythagorean circle for that degree. The radius of such a circle might not be integer, but its radius squared will always be (to find the radius squared, take one of the points with integer x and y, and calculate x^2+y^2, and this will be the radius squared, by simple trigonometry.)

Let us list a few minimal Pythagorean circles, and their radius squared:

R^2 Degree Points in the first quadrant
1 1 (0,1)
5 2 (1,2) (2,1)
25 3 (0,5) (3,4) (4,3)
65 4 (1,8) (4,7) (7,4) (8,1)
625 5 (0,25) (7,24) (15,20) (20,15) (24,7)
325 6 (1,18) (6,17) (10,15) (15,10) (17,6) (18,1)

Now looking at R^2 you might notice a pattern. Lets see the factorizations of the radius squared of these minimal Pythagorean circles:

Degree R^2 factorized
1 1
2 5
3 5^2
4 5*13
5 5^4
6 5^2*13
7 5^6
8 5*13*17
9 5^2*13^2
10 5^4*13
12 5^2*13*17
14 5^6*13

Now, the challenges: What is the next prime factor to show itself in this kind of factorization? What is the minimal Pythagorean circle for degree 11 and 13? What is the complete pattern, and is there a formula for finding the minimal Pythagorean circle for a given degree?

Update: added this diagram of a pythagorean circle of degree 3, with radius squared 25 (and radius 5): Pythagorean circle

Update2: a hint is that no sum of two square numbers can be written as 4x+3, where x is integer

FizzBuzz object oriented

Tuesday, April 15th, 2008

An approach I didn’t use in my last post (well, I did, somewhat, with the enum method) is the object oriented approach. Of course, if we’re going to make it object oriented, we should strive to write reusable components for any part of it, and to use interfaces when possible. So here it is, in all its glory:


/*
 * This code is written by W (aka Raymond Wold) and is released into the public domain.
 *  - It's not my code, I just wrote it.
 */
package com.w_wins.fizzbuzz;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Iterator;
import java.util.List;
import java.util.NoSuchElementException;

public class FizzBuzz implements Runnable{
    private final Facilitator<Integer, String> facilitator;

    public FizzBuzz(){
        final List<ConditionalAdaptor<Integer, String>> list=new ArrayList<ConditionalAdaptor<Integer, String>>();
        final FizzBuzzConditionFactory fizzBuzzConditions=new FizzBuzzConditionFactory();
        list.add(fizzBuzzConditions.generateFizzBuzzAdaptor());
        list.add(fizzBuzzConditions.generateFizzAdaptor());
        list.add(fizzBuzzConditions.generateBuzzAdaptor());
        facilitator=new Facilitator<Integer, String>(list, new ToStringAdaptor<Integer>());
    }

    @Override
    public void run(){
        facilitator.runOn(new IntegerRangeGenerator(1, 100), new Outputter());
    }
}

interface Adaptor<F, T>{
    public T convert(F value);
}

interface Condition<V>{
    public boolean matches(V value);
}

interface ConditionalAdaptor<F, T> extends Adaptor<F, T>,Condition<F>{
}

interface Handler<T>{
    public void handle(T value);
}

class Facilitator<F, T>{
    final List<ConditionalAdaptor<F, T>> conditionalAdaptors;
    final Adaptor<F, T> finalAdaptor;

    public Facilitator(final List<ConditionalAdaptor<F, T>> conditionalAdaptors, final Adaptor<F, T> finalAdaptor){
        this.conditionalAdaptors=conditionalAdaptors;
        this.finalAdaptor=finalAdaptor;
    }

    public void runOn(final Iterator<F> iterator, final Handler<T> handler){
        while(iterator.hasNext())
            handler.handle(runAdaptors(iterator.next()));
    }

    public T runAdaptors(final F value){
        for(ConditionalAdaptor<F, T> adaptor : conditionalAdaptors)
            if(adaptor.matches(value)) {
                return adaptor.convert(value);
            }
        return finalAdaptor.convert(value);
    }
}

class ConditionConditionalAdaptor<F, T> implements ConditionalAdaptor<F, T>{
    private final Condition<F> condition;
    private final Adaptor<F, T> adaptor;

    public ConditionConditionalAdaptor(final Condition<F> condition, final Adaptor<F, T> adaptor){
        this.condition=condition;
        this.adaptor=adaptor;
    }

    @Override
    public boolean matches(F value){
        return condition.matches(value);
    }

    @Override
    public T convert(F value){
        return adaptor.convert(value);
    }
}

class AndCondition<V> implements Condition<V>{
    final List<Condition<V>> conditions;

    public AndCondition(final Condition<V> a, final Condition<V> b){
        conditions=new ArrayList<Condition<V>>();
        conditions.add(a);
        conditions.add(b);
    }

    public AndCondition(final List<Condition<V>> conditions){
        this.conditions=conditions;
    }

    public AndCondition(final Condition<V>[] conditions){
        this.conditions=Arrays.asList(conditions);
    }

    @Override
    public boolean matches(V value){
        for(Condition<V> condition : conditions)
            if(!condition.matches(value)){
                return false;
            }
        return true;
    }
}

class FizzBuzzConditionFactory{
    private static final String FIZZ="Fizz",  BUZZ="Buzz";
    private final Condition<Integer> fizzCondition,  buzzCondition;

    public FizzBuzzConditionFactory(){
        fizzCondition=new IntegerDivisibleBy(3);
        buzzCondition=new IntegerDivisibleBy(5);
    }

    public ConditionalAdaptor<Integer, String> generateFizzBuzzAdaptor(){
        return new ConditionConditionalAdaptor<Integer, String>(new AndCondition<Integer>(fizzCondition, buzzCondition), new FixedStringAdaptor<Integer>(FIZZ+BUZZ));
    }

    public ConditionalAdaptor<Integer, String> generateFizzAdaptor(){
        return new ConditionConditionalAdaptor<Integer, String>(fizzCondition, new FixedStringAdaptor<Integer>(FIZZ));
    }

    public ConditionalAdaptor<Integer, String> generateBuzzAdaptor(){
        return new ConditionConditionalAdaptor<Integer, String>(buzzCondition, new FixedStringAdaptor<Integer>(BUZZ));
    }
}

class FixedStringAdaptor<T> implements Adaptor<T, String>{
    private final String string;

    public FixedStringAdaptor(String string){
        this.string=string;
    }

    @Override
    public String convert(T value){
        return string;
    }
}

class IntegerDivisibleBy implements Condition<Integer>{
    private final int modulo;

    public IntegerDivisibleBy(final int modulo){
        this.modulo=modulo;
    }

    @Override
    public boolean matches(Integer value){
        return value%modulo==0;
    }
}

class ToStringAdaptor<T> implements Adaptor<T, String>{
    @Override
    public String convert(T value){
        return value.toString();
    }
}

class IntegerRangeGenerator implements Iterator<Integer>{
    private int current;
    private final int end;

    public IntegerRangeGenerator(final int fromInclusive, final int toInclusive){
        this.current=fromInclusive;
        this.end=toInclusive;
    }

    @Override
    public boolean hasNext(){
        return current<=end;
    }

    @Override
    public Integer next(){
        if(!hasNext()) {
            throw new NoSuchElementException();
        }
        return current++;
    }

    @Override
    public void remove(){
        throw new UnsupportedOperationException("The integers are a fixed set");
    }
}

class Outputter implements Handler<String>{
    @Override
    public void handle(final String value){
        System.out.println(value);
    }
}

FizzBuzz code

Saturday, April 12th, 2008

And no, it’s not to be taken seriously.
package com.w_wins.fizzbuzz;

import java.util.HashMap;
import java.util.Map;
import java.util.concurrent.Callable;
import java.util.concurrent.ExecutionException;
import java.util.concurrent.ExecutorService;
import java.util.concurrent.Executors;
import java.util.concurrent.Future;
import java.util.concurrent.FutureTask;

/**
 * @author W
 */
public class Main {
    public static void main(String[] args) {
        try {
            fizzbuzz1();
            fizzbuzz2();
            fizzbuzz3();
            fizzbuzz4();
            fizzbuzz5();
        } catch (Exception ex) {
            ex.printStackTrace();
        }
    }
    
    public static void fizzbuzz1() {
        final String[] fizzBuzz=new String[15];
        fizzBuzz[0]="FizzBuzz";
        for(int t=1;t<5;++t)fizzBuzz[t*3]="Fizz";
        for(int t=1;t<3;++t)fizzBuzz[t*5]="Buzz";
        for(int t=1;t<=100;++t)System.out.println(fizzBuzz[t%15]==null?Integer.toString(t):fizzBuzz[t%15]);
    }
    
    public static void fizzbuzz2() {
        for(int t=1;t<=100;++t){
            boolean number=true;
            if(t%3==0){
                number=false;
                System.out.print("Fizz");
            }
            if(t%5==0){
                number=false;
                System.out.print("Buzz");
            }
            System.out.println(number?t:"");
        }
    }
    
    public static void fizzbuzz3() {
        for(int t=1;t<=100;++t){
            switch(t%15){
                case 1:
                case 2:
                case 4:
                case 7:
                case 8:
                case 11:
                case 13:
                case 14:
                    System.out.println(t);
                    break;
                case 3:
                case 6:
                case 9:
                case 12:
                    System.out.println("Fizz");
                    break;
                case 0:
                    System.out.print("Fizz");
                case 5:
                case 10:
                    System.out.println("Buzz");
                    break;
            }
            
        }
    }
    
    public static void fizzbuzz4() throws InterruptedException, ExecutionException {
        final ExecutorService service=Executors.newCachedThreadPool();
        final Map> futures=new HashMap>(100);
        for(int d=1;d<=100;++d){
            final int t=d;
            final FutureTask future=new FutureTask(new Callable() {
                public String call() throws Exception {
                    if(t%15==0)return ”FizzBuzz”;
                    if(t%3==0)return ”Fizz”;
                    if(t%5==0)return ”Buzz”;
                    return Integer.toString(t);
                }
            });
            service.submit(future);
            futures.put(t,future);
        }
        for(int t=1;t<=100;++t){
            System.out.println(futures.get(t).get());
        }
        final boolean isEmpty=service.shutdownNow().isEmpty();
        assert(isEmpty);
    }

    public static enum FizzBuzz{
        FIZZBUZZ(true,true,false){
            protected boolean matches(final int t){
                return t%15==0;
            }
        },FIZZ(true,false,false){
            protected boolean matches(final int t){
                return t%3==0;
            }
        },BUZZ(false,true,false){
            protected boolean matches(final int t){
                return t%5==0;
            }
        },NUMBER(false,false,true){
            protected boolean matches(final int t){
                return true;
            }
        };
        private final boolean fizz,buzz,number;
        protected abstract boolean matches(int t);
        FizzBuzz(final boolean fizz,final boolean buzz,final boolean number){
            this.fizz=fizz;
            this.buzz=buzz;
            this.number=number;
        }
        
        public void printNumber(final int t){
            if(fizz)System.out.print("Fizz");
            if(buzz)System.out.print("Buzz");
            if(number)System.out.print(t);
            System.out.println();
        }
        
        public static FizzBuzz getFizzBuzz(final int t){
            for(FizzBuzz fizzBuzz:FizzBuzz.values()){
                if(fizzBuzz.matches(t)){
                    return fizzBuzz;
                }
            }
            throw new Error("Can't happen");
        }
    }
    
    public static void fizzbuzz5() {
        for(int t=1;t<=100;++t){
            FizzBuzz.getFizzBuzz(t).printNumber(t);
        }
    }
}

fizzbuzz4() 52.4ms, fizzbuzz5() 29.0ms, fizzbuzz3() 25.7ms, fizzbuzz2() 19.6ms, fizzbuzz1() 19.5ms