-
Notifications
You must be signed in to change notification settings - Fork 48
Simple Usage of Lazy Evaluation
Hu JiaJun edited this page Nov 29, 2020
·
1 revision
java -Xss16m Puzzle
import java.util.Objects;
import java.util.List;
import java.util.Arrays;
import java.util.function.BiFunction;
import java.util.function.BinaryOperator;
import java.util.function.Consumer;
import java.util.function.Function;
import java.util.function.Predicate;
import java.util.function.Supplier;
/**
* define freeze(x) (()->(x))
* define LLmake(a, b) new LazyList<>((a), freeze(b))
* define Thunk(T) Supplier<T>
*
* Thunk: The value of the parameter is calculated only when the
* function is actually called (Lazy Evaluation)
*/
public class LazyList<T> {
private static final long START_TIME = System.currentTimeMillis();
private static final long TIME_CONSUMING_OPERATION = 0;
/**
* A LazyList consists of a head of type T,
* whose tail is a Thunk(Supplier<T>) of a LazyList<T>
* The flag amIEmpty indicates if this list is empty.
*/
private final T head;
// private final Thunk(LazyList<T>) tail;
private final Supplier<LazyList<T>> tail;
private final boolean amIEmpty;
/**
* Main list constructor. But users should use the macro:
* LLmake(a, b), which is syntactic sugar for:
* new LazyList(a, freeze(b))
*
* For normal case (ie. without memoization):
* freeze(x) is syntactic sugar for: (()->(x))
* Thunk(T) is syntactic sugar for: Supplier<T>
*
* If memoization is used, then
* freeze(x) is syntactic sugar for: Memo.make(()->(x))
* Thunk(T) is syntactic sugar for Memo<T>
*
* a is Eager Evaluation
* b is Lazy Evaluation
*/
// public LazyList(T a, Thunk(LazyList<T>) b) {
public LazyList(T a, Supplier<LazyList<T>> b) {
this.head = a;
this.tail = b;
this.amIEmpty = false;
}
/**
* Private constructor of an empty list.
*/
private LazyList() {
this.head = null;
this.tail = null;
this.amIEmpty = true;
}
/**
* Convenience function to thaw a thunk.
*/
// public static <T> T thaw(Thunk(T) ice) {
public static <T> T thaw(Supplier<T> ice) {
return ice.get();
}
/**
* Create a Supplier to Supply a LazyList
*
* This freeze() method is not completely correct,
* because when freezing is called, the strategy of
* calling by value is still followed.
*
* Such as freeze(this.tail().map(f)),
* this.tail().map(f) will be executed immediately.
*
* public static <T> Supplier<LazyList<T>> freeze(LazyList<T> x) {
* return () -> {
* // Do time-consuming operation
* try {
* Thread.sleep(TIME_CONSUMING_OPERATION);
* } catch (InterruptedException e) {
* e.printStackTrace();
* }
* return x;
* };
* }
*/
/**
* Create an empty LazyList.
*/
public static <T> LazyList<T> makeEmpty() {
return new LazyList<T>();
}
/**
* Return the head of this list.
*/
public T head() {
if (this.isEmpty()) {
throw new IllegalArgumentException("head() called on empty list!");
}
return this.head;
}
/**
* Thaw the tail of the list, and return it.
*/
public LazyList<T> tail() {
if (this.isEmpty()) {
throw new IllegalArgumentException("tail() called on empty list!");
}
return thaw(Objects.requireNonNull(this.tail));
}
/**
* Return true if this list is empty, false otherwise.
*/
public boolean isEmpty() {
return this.amIEmpty;
}
@Override
public boolean equals(Object obj) {
if (this == obj) {
return true;
} else if (obj instanceof LazyList) {
LazyList<?> ll = (LazyList<?>) obj;
return this.hasSameContent(ll);
} else {
return false;
}
}
/**
* Whether the two LazyLists have the same content
*/
public boolean hasSameContent(LazyList<?> other) {
if (this.isEmpty() && other.isEmpty())
return true;
else if (!this.isEmpty() && !other.isEmpty())
return this.head().equals(other.head()) &&
this.tail().hasSameContent(other.tail());
else
return false;
}
/**
* Return a human-readable string of this list.
*/
@Override
public String toString() {
if (this.isEmpty())
return "**empty**";
return String.format("head: %s, tail: thunk! %s",
Objects.requireNonNull(this.head).toString(),
Objects.requireNonNull(this.tail).toString());
}
/**
* Print all the elements in this list. This thaws all the
* elements. If this list is infinite, then the printing
* could go on forever.
*/
public void print() {
LazyList<T> me = this;
System.out.print("(* ");
while (!me.isEmpty()) {
System.out.println(me.head() + " print executing (" +
(System.currentTimeMillis() - START_TIME) + "), ");
me = me.tail();
}
System.out.println("*)");
}
/**
* Convenience function to make a LL of multiple arguments.
*/
@SafeVarargs
public static <T> LazyList<T> fromList(T ... items) {
List<T> list = Arrays.asList(items);
return helper(list);
}
/**
* Convert a list to a LazyList
*/
private static <T> LazyList<T> helper(List<T> list) {
if (list.isEmpty()) {
return LazyList.makeEmpty();
} else {
/**
* new LazyList<T>((a), freeze(b))
* return LLmake(list.get(0), helper(list.subList(1,list.size())));
* Supplier method is freeze method.
*/
return new LazyList<T>(list.get(0),
new Supplier<LazyList<T>>() {
@Override
public LazyList<T> get() {
// Do time-consuming operation
try {
Thread.sleep(TIME_CONSUMING_OPERATION);
} catch (InterruptedException e) {
e.printStackTrace();
}
return helper(list.subList(1,list.size()));
}
});
}
}
/**
* Apply the mapping function f onto each element of this list,
* and return a new LL containing the mapped elements.
*
* head: f(head).
* tail: pass the Function f into the tail so that the tail which is
* the next ll can call the Function f.
*
* Note: tail() is called, time-consuming operation will be evaluated,
* it means that the mapping is executing when map() is called.
*/
public <R> LazyList<R> map(Function<T,R> f) {
System.out.print("mapping executing (" + (System.currentTimeMillis() - START_TIME) + ") ");
if (this.isEmpty()) {
return LazyList.makeEmpty();
} else {
/**
* return LLmake(f.apply(this.head()), this.tail().map(f));
* Supplier method is freeze method.
*/
return new LazyList<R>(f.apply(this.head()),
new Supplier<LazyList<R>>() {
@Override
public LazyList<R> get() {
// Do time-consuming operation
try {
Thread.sleep(TIME_CONSUMING_OPERATION);
} catch (InterruptedException e) {
e.printStackTrace();
}
return LazyList.this.tail().map(f);
}
});
}
}
/**
* Apply the mapping function f onto each element of this list, and
* return a new LL containing all the flattened mapped elements.
* Note that f produces a list for each element. But the returned
* LL flattens them all, ie. removes nested lists.
*/
public <R> LazyList<R> flatmap(Function<T, LazyList<R>> f) {
System.out.print("flatmap executing (" + (System.currentTimeMillis() - START_TIME) + ") ");
if (this.isEmpty()) {
return LazyList.makeEmpty();
} else {
return f.apply(this.head())
.concat(this.tail().flatmap(f));
}
}
/**
* Return a new LL whose elements (from this list)
* pass the test of the predicate pred.
*
* Note: tail() is called, time-consuming operation will be evaluated,
* it means that the filter is executing when filter() is called.
*/
public LazyList<T> filter(Predicate<T> pred) {
System.out.print("filter executing (" + (System.currentTimeMillis() - START_TIME) + ") ");
if (this.isEmpty()) {
return LazyList.makeEmpty();
}
/**
* If the head() of the ll passes the test,
* return a new ll object with current head and test its tail().
* Supplier method is freeze method.
*/
else if (pred.test(this.head())) {
return new LazyList<T>(this.head(),
new Supplier<LazyList<T>>() {
@Override
public LazyList<T> get() {
// Do time-consuming operation
try {
Thread.sleep(TIME_CONSUMING_OPERATION);
} catch (InterruptedException e) {
e.printStackTrace();
}
return LazyList.this.tail().filter(pred);
}
});
}
/**
* Skip the current ll and test its tail().
*/
else {
return this.tail().filter(pred);
}
}
/**
* Return a new LL of length maxSize.
* The new list contains the same elements as this one.
*/
public LazyList<T> limit(long maxSize) {
if (maxSize == 0) {
return LazyList.makeEmpty();
} else {
/**
* return LLmake(this.head(), this.tail().limit(maxSize - 1));
* Supplier method is freeze method.
*/
return new LazyList<T>(this.head(),
new Supplier<LazyList<T>>() {
@Override
public LazyList<T> get() {
// Do time-consuming operation
try {
Thread.sleep(TIME_CONSUMING_OPERATION);
} catch (InterruptedException e) {
e.printStackTrace();
}
return LazyList.this.tail().limit(maxSize - 1);
}
});
}
}
/**
* Return a new LL whose elements are the combination, element-wise,
* of this and other list. The combination is specified by the
* BinaryOperator binOp, and thus could be addition, multiplication, etc.
*/
public LazyList<T> elementWiseCombine(LazyList<T> other, BinaryOperator<T> binOp) {
System.out.print("elementWiseCombine executing (" + (System.currentTimeMillis() - START_TIME) + ") ");
if (this.isEmpty() || other.isEmpty()) {
return LazyList.makeEmpty();
} else {
/**
* return LLmake(binOp.apply(this.head(), other.head()),
* this.tail().elementWiseCombine(other.tail(), binOp));
* Supplier method is freeze method.
*/
return new LazyList<T>(binOp.apply(this.head(), other.head()),
new Supplier<LazyList<T>>() {
@Override
public LazyList<T> get() {
// Do time-consuming operation
try {
Thread.sleep(TIME_CONSUMING_OPERATION);
} catch (InterruptedException e) {
e.printStackTrace();
}
return LazyList.this.tail().elementWiseCombine(other.tail(), binOp);
}
});
}
}
/**
* Return the element at position given by idx.
* idx starts from 0, and should be non-negative.
*/
public T get(int idx) {
System.out.print("get executing (" + (System.currentTimeMillis() - START_TIME) + ") ");
if (this.isEmpty() || idx < 0) {
return null;
} else if (idx == 0) {
return this.head();
} else {
return this.tail().get(idx - 1);
}
}
/**
* Convenience function: return a LazyList<Integer> of integers
* from a (inclusive) to b (exclusive)
*/
public static LazyList<Integer> intRange(int a, int b) {
System.out.print("intRange executing (" + (System.currentTimeMillis() - START_TIME) + ") ");
if (a >= b) {
return LazyList.makeEmpty();
} else {
/**
* return LLmake(a, intRange(a + 1, b));
* Supplier method is freeze method.
*/
return new LazyList<Integer>(a,
new Supplier<LazyList<Integer>>() {
@Override
public LazyList<Integer> get() {
// Do time-consuming operation
try {
Thread.sleep(TIME_CONSUMING_OPERATION);
} catch (InterruptedException e) {
e.printStackTrace();
}
return intRange(a + 1, b);
}
});
}
}
/**
* Concatenate other list to this one.
* Keep returning LazyList.this.tail().concat(other) until
* the current LazyList is empty, which means all the
* elements of LazyList are traversed, then return other,
* which is the concatenated LazyList.
*/
public LazyList<T> concat(LazyList<T> other) {
System.out.print("concat executing (" + (System.currentTimeMillis() - START_TIME) + ") ");
if (this.isEmpty()) {
return other;
} else {
/**
* return LLmake(this.head(), this.tail().concat(other));
* Supplier method is freeze method.
*/
return new LazyList<T>(this.head(),
new Supplier<LazyList<T>>() {
@Override
public LazyList<T> get() {
// Do time-consuming operation
try {
Thread.sleep(TIME_CONSUMING_OPERATION);
} catch (InterruptedException e) {
e.printStackTrace();
}
return LazyList.this.tail().concat(other);
}
});
}
}
/**
* Return a new list whose elements are those from this list,
* but in reverse order.
*
* Keep calling this.tail().tail().tail()...tail() until the tail
* is empty, then call concat()
*/
public LazyList<T> reverse() {
System.out.print("reverse executing (" + (System.currentTimeMillis() - START_TIME) + ") ");
if (this.isEmpty()) {
return this;
} else {
/**
* return this.tail().reverse().concat(LLmake(this.head(), LazyList.makeEmpty()));
* Supplier method is freeze method.
*/
return this.tail()
.reverse()
.concat(new LazyList<T>(this.head(),
new Supplier<LazyList<T>>() {
@Override
public LazyList<T> get() {
// Do time-consuming operation
try {
Thread.sleep(TIME_CONSUMING_OPERATION);
} catch (InterruptedException e) {
e.printStackTrace();
}
return LazyList.makeEmpty();
}
}));
}
}
/**
* Combine this LazyList with other, using generic combiner.
* This may be used to generate cartesian product of the 2 lists.
*/
public <U,R> LazyList<R> combine(LazyList<U> other, BiFunction<T,U,R> combiner) {
return this.flatmap(x ->
other.map(y -> combiner.apply(x,y)));
}
/**
* Invoke the consumer eat on every element in this list.
* This is an eager operation: the entire list will be thawed.
*/
public void forEach(Consumer<T> eat) {
if (!this.isEmpty()) {
eat.accept(this.head());
this.tail().forEach(eat);
}
}
/**
* Accumulate all the elements in this list, using the accumulator and identity.
* This is an eager operation: the entire list will be thawed.
*/
public T reduce(T identity, BinaryOperator<T> accumulator) {
System.out.print("reduce executing (" + (System.currentTimeMillis() - START_TIME) + ") ");
if (this.isEmpty()) {
return identity;
} else {
return accumulator.apply(this.head(),
this.tail().reduce(identity,
accumulator));
}
}
/**
* Add the elements in two LazyLists in order
*/
public LazyList<T> add(LazyList<T> other, BinaryOperator<T> add) {
if (this.isEmpty() || other.isEmpty()) {
return LazyList.makeEmpty();
} else {
/**
* return LLmake(add.apply(this.head(), other.head()),
* this.tail().add(other.tail(), add));
* Supplier method is freeze method.
*/
return new LazyList<T>(add.apply(this.head(), other.head()),
new Supplier<LazyList<T>>() {
@Override
public LazyList<T> get() {
return LazyList.this.tail().add(other.tail(), add);
}
});
}
}
/**
* Create an integer LazyList start from n, must set limit()
*/
public static LazyList<Integer> integersFrom(int n) {
System.out.print("integersFrom executing (" + (System.currentTimeMillis() - START_TIME) + ") ");
/**
* return LLmake(n, integersFrom(n + 1));
* Supplier method is freeze method.
*/
return new LazyList<Integer>(n,
new Supplier<LazyList<Integer>>() {
@Override
public LazyList<Integer> get() {
return integersFrom(n + 1);
}
});
}
/**
* Sieve Prime
*/
public static LazyList<Integer> sieve(LazyList<Integer> s) {
System.out.print("sieve executing (" + (System.currentTimeMillis() - START_TIME) + ") ");
/**
* return LLmake(s.head(), sieve(s.tail().filter(x-> (x % s.head()) != 0)));
* Supplier method is freeze method.
*/
return new LazyList<Integer>(s.head(),
new Supplier<LazyList<Integer>>() {
@Override
public LazyList<Integer> get() {
return sieve(s.tail().filter(x-> (x % s.head()) != 0));
}
});
}
}
import java.util.function.Predicate;
import java.util.ArrayList;
import java.util.List;
/**
* Program to compare the computation efficiency of LazyLists
* versus ArrayLists.
*/
public class Primes {
/**
* Finds the kth prime in a given range by:
* 1. Generating an LazyList of ints from a to b
* 2. Filter this list with prime predicate.
*
* Notice that the predicate is instrumented to count
* the number of times it is called.
*/
static void findKthPrimeLL(int a, int b, int k) {
int prime = LazyList.intRange(a, b)
.filter(predInstrument(Primes::isPrime))
.get(k - 1);
printPrime(k, prime);
printCounter();
}
/**
* Finds the kth prime in a given range by:
* 1. Generating an ArrayList of ints from a to b
* 2. Filter this list with prime predicate.
*
* Notice that the predicate is instrumented to count
* the number of times it is called.
*/
static void findKthPrimeArr(int a, int b, int k) {
var primesArrayList = listFilter(
predInstrument(Primes::isPrime),
intRangeArr(a, b)
);
int prime = primesArrayList.get(k - 1);
printPrime(k, prime);
printCounter();
}
/**
* Static counter to count the number of times a predicate
* is invoked. Convenience methods to increment and print
* the counter are also provided.
*/
static int counter = 0;
static void incrCounter() {
counter++;
}
static void printCounter() {
System.out.printf("isPrime was called %d times%n", counter);
}
/**
* Prints the usage of this program.
*/
static void printUsage() {
System.out.println("Usage: java Primes <a> <b> <k> <w>");
System.out.println("where: <a> is the lower limit of the range, <a> is included,");
System.out.println("\t<b> is the upper limit of the range, <b> is excluded,") ;
System.out.println("\t<k> is the k-th prime to find,");
System.out.println("\t<w> is 0 (run the ArrayList version) or 1 (the LazyList version)");
System.out.println("\n*** Note that <a> must be larger than 1.\n");
System.out.println("To time how fast it runs, use the time bash command");
System.out.println("\t\t eg: time java Primes 2 1000 3 1");
System.out.println("\twill find the 3rd prime between 2 and 1000 using");
System.out.println("\tthe LazyList version, and report the time taken to run.\n");
}
/**
* Convenience functions to parse command line input,
* and to print the result.
* Also a function to instrument a predicate.
*/
static int[] parse(String[] args) {
if (args.length != 4) {
printUsage();
throw new RuntimeException();
}
int[] result = new int[4];
for (int i = 0; i < 4; i++)
result[i] = Integer.parseInt(args[i]);
return result;
}
static void printPrime(int k, int p) {
System.out.println(String.format("The %d-th prime is %d", k, p));
}
/**
* A Predicate to test whether an element is prime,
* and count the testing times.
*/
static <T> Predicate<T> predInstrument(Predicate<T> p) {
return x-> {
incrCounter();
return p.test(x);
};
}
/**
* Various methods to generate an ArrayList of primes.
*/
static List<Integer> intRangeArr(int a, int b) {
List<Integer> result = new ArrayList<>();
for (int x = a; x < b; x++) {
result.add(x);
}
return result;
}
/**
* Test all the elements in the list, and return a new
* list with all primes.
*/
static <T> List<T> listFilter(Predicate<T> p, List<T> list) {
List<T> newList = new ArrayList<>();
for (T item : list) {
if (p.test(item)) {
newList.add(item);
}
}
return newList;
}
/**
* Predicate to test if n is prime.
* This is a naive algorithm that performs trial division:
* it checks if n is divisible by all integers from 2 to to sqrt(n)
*/
static boolean isPrime(int n) {
for (int i = 2; i*i <= n; i++) {
if (n%i == 0) {
return false;
}
}
return true;
}
/**
* Main method
*/
public static void main(String[] args) {
// See printUsage for how to run this program.
var inputs = parse(args);
if (inputs[3] == 0) {
findKthPrimeArr(inputs[0], inputs[1], inputs[2]);
} else if (inputs[3] == 1) {
findKthPrimeLL(inputs[0], inputs[1], inputs[2]);
} else {
System.out.println("Wrong value for <w>!");
}
}
}
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.function.Supplier;
import java.util.stream.IntStream;
public class Puzzle {
static boolean pzczSatisfies(LazyList<Integer> term) {
int c = term.get(0);
int h = term.get(1);
int m = term.get(2);
int p = term.get(3);
int u = term.get(4);
int z = term.get(5);
// Insert your code here.
// Return true only when both m,p are not 0,
// and the given equation is satisfied.
int pzcz = p * 1000 + z * 100 + c * 10 + z;
int muchz = m * 10000 + p * 1000 + z * 100 + c * 10 + z;
return m != 0 && p != 0 && pzcz * 15 == muchz;
}
/**
* Permutation: The number of all permutations of choosing
* m(m≤n) elements from n different elements
* Return a List of Permutations
*
* Return a LazyList of LazyList<Integer>
* LazyList.intRange(1, 5);
*
*
* x = 1,
* permute(LazyList of 2, 3, 4, 5, 2)
*/
public static LazyList<LazyList<Integer>> permute(LazyList<Integer> LL, int r) {
/**
* If r = 1, then this is a list of singleton lists of each of the elements in L. Example:
* for L = (1, 2, 3, 4), there are four 1-Permutations: ((1), (2), (3), (4)).
*
* map LazyList<Integer> -> LazyList<LazyList<Integer>>
*
* For example: 4P1
* LazyList of 1, 2, 3, 4: LazyList<>(1, freeze(2))
* r = 1
*
* Convert (LazyList of 1, 2, 3, 4) to
* LazyList of (LazyList<>(1, empty), LazyList<>(2, empty), LazyList<>(3, empty), LazyList<>(4, empty))
* return LazyList<>(LazyList<>(1, empty), freeze(LazyList<>(2, empty)))
*/
if (r == 1) {
return LL.map(x -> new LazyList<Integer>(x, new Supplier<LazyList<Integer>>() {
@Override
public LazyList<Integer> get() {
return LazyList.makeEmpty();
}
}));
}
/**
* If r > 1, take each element x in turn from L, recursively compute the (r − 1)-
* Permutation of L − x (ie. L with x removed). This will give a list of (r −
* 1)−Permutations. We now insert x to the front of each of these.
*
* flatmap: LazyList<LazyList<Integer>> -> LazyList<LazyList<Integer>>
*
* For example: 4P3
* 1 2 3
* 1 2 4
* 1 3 2
* 1 3 4
* 1 4 2
* 1 4 3
* ...
* LazyList of 1, 2, 3, 4: LazyList<>(1, freeze(2))
* r = 3 > 1
*
* Calculator 3P2
* For x = 1
* LazyList of 2, 3, 4: LazyList<>(2, freeze(3))
* 2 3
* 2 4
* 3 2
* 3 4
* 4 2
* 4 3
* ...
* We can find that insert x to the front of each of 2-Permutations of 3
* can become 3-Permutations of 4
*
* Use map convert
* 2 3 --> LazyList of (LazyList<>(2, freeze(3)), LazyList<>(3, empty))
* 2 4
* 3 2
* 3 4
* 4 2
* 4 3
* ...
*
* LazyList of 2, 3, 4, 5: LazyList<>(2, freeze(3))
*/
else {
return LL.flatmap(x ->
permute(remove(LL, x), r - 1).map(y ->
new LazyList<Integer>(x, new Supplier<LazyList<Integer>>() {
@Override
public LazyList<Integer> get() {
return y;
}
})
)
);
}
}
/**
* Remove one element in the LazyList
*/
public static LazyList<Integer> remove(LazyList<Integer> LL, int n) {
return LL.filter(x -> x != n);
}
public static void bruteForceForLoop() {
List<List<Integer>> allSolutions = new ArrayList<>();
for (int c = 0; c < 10; c++)
for (int h = 0; h < 10; h++)
if (h != c)
for (int m = 1; m < 10; m++)
if (m != c && m != h)
for (int p = 1; p < 10; p++)
if (p != c && p != h && p != m)
for (int u = 0; u < 10; u++)
if (u != c && u != h && u != m && u != p)
for (int z = 0; z < 10; z++)
if (z != c && z != h && z != m && z != p && z != u) {
int pzcz = p * 1000 + z * 100 + c * 10 + z;
int muchz = m * 10000 + u * 1000 + c * 100 + h * 10 + z;
if (pzcz * 15 == muchz)
allSolutions.add(Arrays.asList(c, h, m, p, u, z));
}
System.out.println(allSolutions);
}
public static void betterForLoop() {
List<Integer> allSolutions = new ArrayList<>();
for (int n = 1000; n < 10000; n++)
if (isPZCZ(n) && isProductMuchz(n))
allSolutions.add(n);
System.out.println(allSolutions);
}
/**
* check that: pzcz * 15 has 5 digits, it has C,Z in the right positions,
* and all digits are distinct from PZCZ.
*/
public static boolean isProductMuchz(int pzcz) {
int muchz = pzcz * 15;
if (!(10000 <= muchz && muchz < 100000))
return false;
String strPZCZ = String.valueOf(pzcz);
char p = strPZCZ.charAt(0);
char z = strPZCZ.charAt(1);
char c = strPZCZ.charAt(2);
String strMUCHZ = String.valueOf(muchz);
char mm = strMUCHZ.charAt(0);
char uu = strMUCHZ.charAt(1);
char cc = strMUCHZ.charAt(2);
char hh = strMUCHZ.charAt(3);
char zz = strMUCHZ.charAt(4);
return z == zz && c == cc && mm != p && mm != z && mm != c &&
uu != mm && uu != p && uu != z && uu != c &&
hh != mm && hh != uu && hh != p && hh != z && hh != c;
}
/**
* check that: n has 4 digits, its format is PZCZ, and P, C, Z are distinct
*/
public static boolean isPZCZ(int n) {
if (!(1000 <= n && n < 10000))
return false;
String strPZCZ = String.valueOf(n);
char p = strPZCZ.charAt(0);
char z = strPZCZ.charAt(1);
char c = strPZCZ.charAt(2);
char last = strPZCZ.charAt(3);
return z == last && p != z && p != c && z != c;
}
// SEND + MORE = MONEY
static boolean moneySatisfies(LazyList<Integer> term) {
int d = term.get(0);
int e = term.get(1);
int m = term.get(2);
int n = term.get(3);
int o = term.get(4);
int r = term.get(5);
int s = term.get(6);
int y = term.get(7);
int send = s * 1000 + e * 100 + n * 10 + d;
int more = m * 1000 + o * 100 + r * 10 + e;
int money = m * 10000 + o * 1000 + n * 100 + e * 10 + y;
return m != 0 && s != 0 && (send + more == money);
}
/**
* We can use the same idea with IntStream
*/
static void streamSolution() {
IntStream.range(1000, 10000)
.filter(Puzzle::isPZCZ)
.filter(Puzzle::isProductMuchz)
.forEach(System.out::println);
}
public static void main(String[] args) {
permute(LazyList.intRange(1,10), 6)
.filter(Puzzle::pzczSatisfies)
.forEach(LazyList::print);
bruteForceForLoop();
permute(LazyList.intRange(0, 10), 8)
.filter(Puzzle::moneySatisfies)
.forEach(LazyList::print);
betterForLoop();
streamSolution();
}
}
Peer Learning
Codecrunch Contributions
Piazza Contributions
Wiki Contributions
Guides
Setting Up Checkstyle
Setting Up Java
Setting Up MacVim
Setting Up Sunfire
Setting Up Unix For Mac
Setting Up Unix For Windows
Setting Up Vim
Setting up SSH Config
CS2030 Contents
Lecture 1 SummaryCompile-run vs Run-time Summary
Quick Guide To Abstraction
Generics and Variance of Types
Comparable vs Comparator
Summary of completable future
CS2030S Notes
ELI5 Optional.map vs Optional.flatMap
PECS Example Code
Java Collection Framework (Iterator)
Generic
Generic Type Parameter and Generic Wildcard
Calculator
Lambda-Expression
Single Abstract Method (SAM)
Method Reference
Functional Interfaces 2
Simple Usage of Sandbox
Associative-but-not-commutative
Higher Order function
Functional Programming
Calculator With Functor
Eager Evaluation VS Lazy Evaluation
Simple Usage of Lazy Evaluation
Lazy Evaluation for LazyList
Lazy Evaluation for BinaryTree
Stream
Parallel Stream
Optional
Simple Usage of Stream
Asynchronous Programming
Notes on CompletableFuture
Notes on CompletableFuture 2
Simple Usage of CompletableFuture
Mind Map
Exception Handling
Links
CS2030 Java Style Guide
CS2030 Javadoc Specification
JDK 11 Download Link
JDK 11 API Docs
Codecrunch
Piazza Forum