Friday, August 30, 2013

Batch - Bash was nice enough, so why not... (Problem 34)

Well, yesterday I solved problem 33 in Bash, and that was a walk in the park compared to a lot of things I have had to do for this challenge. I decided that if Bash could be so relatively nice to work with, with tons of features that make programming nice - functions, good support for arithmetic, etc. - how bad could the Windows scripting equivalent, Batch be, even if I have heard many bad things about it? Turns out it can be pretty bad. First of all, I had some difficulty getting off the ground working on this problem - apparently neither dosbox nor wine cmd.exe correctly emulate batch file interpreting on Linux, so after a while trying to get those to work I had to move to a Windows computer to do the rest of my work. Once there, things seemed to be going swimmingly (after getting used to the annoying syntax of %..% for variable accesses and needing to use "set /a" for all assignments...this made me miss the $var notation I previously hated in bash and PHP), until I noticed that my program ran far, far more slowly than it should...it took about 30 seconds to test numbers from 1 to 1000, so then I had to fix my solution to be less brute-forcing...which led to the wonderful mess that is my program below, due to batch's lack of full support for for loops...(for loops can't have labels in them...and there was basically no way to do what I needed to do without a goto or two), so now my code has 10-fold nested loops implemented with gotos...fun stuff. despite all my work to make it run faster, this still takes about 20 seconds on my machine to find the correct answer (Windows doesn't have the nice command-line "time" command, and I didn't feel like taking the time to do more precise timing)

Anyway, despite the difficulties, I am now done with problem 34 and with trying to write project euler solution type problems in batch.
Also, I am pretty sure this program now takes the prize for most lines of code I have written for a solution for this challenge. (not counting the writing of the Shakespeare compiler)
@echo off
goto main

rem  *I originally wrote this factorial method, but it
rem  *is slower than the lookup method, which is plenty
rem  *suitable for the needs of this problem
:factorialreal
set /a counter=1
set /a result=0
:loop1
    set /a test=input+1
    if "%counter%"=="%test%" (
        goto end
    ) else (
        set /a result*=%counter%
    )
    set /a counter+=1
    goto loop1
:end1
goto aftercall

:factorial
if %input%==0 (
    set /a result=1
) else if %input%==1 (
    set /a result=1
) else if %input%==2 (
    set /a result=2
) else if %input%==3 (
    set /a result=6
) else if %input%==4 (
    set /a result=24
) else if %input%==5 (
    set /a result=120
) else if %input%==6 (
    set /a result=720
) else if %input%==7 (
    set /a result=5040
) else if %input%==8 (
    set /a result=40320
) else (
    set /a result=362880
)
goto aftercall
:main

rem  *we check all possible sums of factorials with reasonable digit
rem  *frequencies and see if these sums are the sums of the factorials
rem  *of their digits. This is really big and sloppy...but oh well,
rem  *and the brute-force method (check all numbers from 1 to an upperbound,
rem  *see if that number is the sum of the factorial of its digits) was
rem  *far too slow

set /a test=0
set /a answer=0
set /a c1=0
:loop-01
 set /a c2=0
  :loop-2
   set /a c3=0
    :loop-3
     set /a c4=0
      :loop-4
       set /a c5=0
        :loop-5
         set /a c6=0
          :loop-6
           set /a c7=0
            :loop-7             
             set /a c8=0
              :loop-8               
               set /a c9=0
                :loop-9
                 set /a test+=c1
                 set /a test+=c2*2
                 set /a test+=c3*6
                 set /a test+=c4*24
                 set /a test+=c5*120
                 set /a test+=c6*720
                 set /a test+=c7*5040
                 set /a test+=c8*40320
                 set /a test+=c9*362880
                 set /a j=test
                 set /a digifacsum=0
                 :testloop
                  if %digifacsum% GTR %test% (
                   goto endtest
                  )
                  if %j%==0 (
                   goto endtest
                  )
                  set /a input=j %% 10
                  set /a j/=10
                  goto factorial
                  :aftercall
                  set /a digifacsum+=result
                  goto testloop
                 :endtest
                 if %test% GTR 10 (
                  if %digifacsum%==%test% (
                     set /a answer+=test
                  )
                 )
                 set /a test=0
                 if not %c9%==0 (
                  set /a c9+=1
                  goto loop-9
                 )
                :end9
               if not %c8%==1 (
                set /a c8+=1
                goto loop-8
               )
              :end8
             if not %c7%==1 (
              set /a c7+=1
              goto loop-7
             )
            :end7
           if not %c6%==1 (
            set /a c6+=1
            goto loop-6
           )
          :end6
         if not %c5%==2 (
          set /a c5+=1
          goto loop-5
         )
        :end5
       if not %c4%==3 (
        set /a c4+=1
        goto loop-4
       )
      :end4
     if not %c3%==3 (
      set /a c3+=1
      goto loop-3
     )
    :end3
   if not %c2%==2 (
    set /a c2+=1
    goto loop-2
   )
  :end2
 if not %c1%==2 (
  set /a c1+=1
  goto loop-01
 )
:end01
echo %answer%

No comments:

Post a Comment