Anyway, problem 90 was a rather simple problem, being capable of being expressed in terms of bitwise operations. Just lots of ors and ands and shifts, treating integers as sets, and iterating over all pairs of possible sets of {0...9}. This is only 1024 * 1024 =~ 1 million sets, and as the operations per pair of sets is exceedingly simple (and most can be thrown out very quickly for not having enough elements to represent a die), this was an entirely reasonable amount of work. Almost all the difficulty with this problem came from the problem, and not the language (well, the only problem related issue was me forgetting that, despite 6 and 9 being identified, a die could still have both, but I only forgot that exceedingly briefly, thanks to the example on the project euler page).
Anyway, below is my code...I would apologize for the lack of comments, as (I know) it makes it hard to read, but at least the ByteCode assembler I used didn't seem to have any syntax for allowing comments...so though unfortunate, it is what it is. Code runs in about 150ms, though it is notable that much of that is probably just starting up the JVM. Maybe my next language will be wonderfully low level again, or maybe I will go up to more sophisticated languages soon. Anyway, here is the beautiful code:
.class public e90 .super java/lang/Object .method public static printInt(I)V .limit stack 100 .limit locals 100 getstatic java/lang/System out Ljava/io/PrintStream; iload_0 invokevirtual java/io/PrintStream println (I)V return .end method .method public static sixBitsSet(I)I .limit stack 100 .limit locals 100 iconst_1 istore_1 iconst_0 istore_2 BITSETLOOP: iload_1 iload_0 if_icmpgt BITSETLOOP_END iload_1 iload_0 iand ifeq NOADD iinc 2 1 NOADD: iload_1 iconst_1 ishl istore_1 goto BITSETLOOP BITSETLOOP_END: bipush 6 iload_2 if_icmpeq RETURN_TRUE iconst_0 ireturn RETURN_TRUE: iconst_1 ireturn .end method .method public static setContains(II)I .limit stack 100 .limit locals 100 iconst_1 iload_1 ishl iload_0 iand ifgt RETURN_SUCCESS iconst_0 ireturn RETURN_SUCCESS: iconst_1 ireturn .end method .method public static check(III)I .limit stack 100 .limit locals 100 iload_0 invokestatic e90/sixBitsSet(I)I iload_1 invokestatic e90/sixBitsSet(I)I iadd iconst_2 if_icmpne RETURN_FAILURE iload_0 sipush 512 iand ifeq SKIP_ADDSIX1 iload_0 sipush 64 ior istore_0 SKIP_ADDSIX1: iload_1 sipush 512 iand ifeq SKIP_ADDSIX2 iload_1 sipush 64 ior istore_1 SKIP_ADDSIX2: iload_2 bipush 10 irem istore_3 iload_3 bipush 9 if_icmpne SKIP_SIXIFY bipush 6 istore_3 SKIP_SIXIFY: iload_0 iload_3 invokestatic e90/setContains(II)I istore 4 iload_1 iload_3 invokestatic e90/setContains(II)I istore 5 iload_2 bipush 10 idiv istore_3 iload_3 bipush 9 if_icmpne SKIP_SIXIFY2 bipush 6 istore 3 SKIP_SIXIFY2: iload_0 iload_3 invokestatic e90/setContains(II)I istore 6 iload_1 iload_3 invokestatic e90/setContains(II)I istore 7 iload 4 iload 7 iand iload 5 iload 6 iand ior ireturn RETURN_FAILURE: iconst_0 ireturn .end method .method public static main : ([Ljava/lang/String;)V .limit stack 100 .limit locals 100 iconst_0 istore 6 bipush 9 newarray int astore 4 iconst_0 istore_0 INITLOOP: iload_0 bipush 9 if_icmpge INITLOOP_END aload 4 iload_0 iinc 0 1 iload_0 iload_0 imul iastore goto INITLOOP INITLOOP_END: iconst_0 istore_0 OUTERLOOP: iload_0 sipush 1024 if_icmpge OUTERLOOP_END iload_0 istore_1 INNERLOOP: iload_1 sipush 1024 if_icmpge INNERLOOP_END iconst_0 istore 5 INNERMOSTLOOP: iload 5 bipush 9 if_icmpge INNERMOSTLOOP_END_SUCCESS iload_0 iload_1 aload 4 iload 5 iaload invokestatic e90/check(III)I ifeq INNERMOSTLOOP_END_FAILURE iinc 5 1 goto INNERMOSTLOOP INNERMOSTLOOP_END_SUCCESS: iinc 6 1 INNERMOSTLOOP_END_FAILURE: iinc 1 1 goto INNERLOOP INNERLOOP_END: iinc 0 1 goto OUTERLOOP OUTERLOOP_END: iload 6 invokestatic e90/printInt(I)V return .end method
No comments:
Post a Comment