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