Monday, July 14, 2014

Problem 90 - Java Bytecode!

So, after solving problem 89 in Parrot Assembly, I claimed that I was interesting in trying out Java Bytecode. So, I did indeed use it. Turns out Java Bytecode is not exactly the world's most user friendly language to write in. Its not a standard assembly language, but is rather stack based, with some commands taking arguments directly, but most only directing with the stack, which makes things certainly different. Also, thank god I didn't have to invoke too many methods that weren't static in my own class...I wrote a helper function that is a wrapper for System.out.println, it was so frustrating to call it for debugging purposes!

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