Тест "Счастливые билеты"

МК-161 (версия прошивки 1.20), полный тест: 1 час 32 мин

подборка статей из Кванта и других популярных изданий про "Счастливые билеты":
http://www.ega-math.narod.ru/Quant/Tickets.htm

Допилил "Счастливые билеты" под Форт на msp430g2553. Результат: 40 секунд.

4E4th R0.34 Apr 28 2012|110001110 Cold
VARIABLE t ok
VARIABLE n1 ok
VARIABLE n2  ok
VARIABLE n3 ok
VARIABLE n4 ok
VARIABLE n5 ok
VARIABLE n6 ok
VARIABLE ls ok
VARIABLE rs ok
0 t ! ok
: howmuch
red cclr
green cclr
10 0 DO i n1 !
10 0 DO i n2 !
10 0 DO i n3 !
10 0 DO i n4 !
10 0 DO i n5 !
10 0 DO i n6 !
n1 @ n2 @ + n3 @ + ls !
n4 @ n5 @ + n6 @ + rs !
ls @ rs @ = IF 1 t +! THEN
LOOP
LOOP
LOOP
LOOP
LOOP
LOOP
red cset
t @ u. ; ok
howmuch 55252 ok

Casio 9750 GII

0→s
For 0→x  to 9
For 0→y  to 9
For 0→z  to 9 
For 0→a  to 9
For 0→b  to 9
For 0→c  to 9
If (x+y+z)= (a+b+c) :then
s+1→s
IfEnd
Next
Next
Next
Next
Next
Next
s˛

Результат 55252 1час 36мин

SHARP PC-G850S

main() {
int  x,y,z,a,b,c,n=9;
long  s=0;
for(x=0;x<=n;x++) {
   for(y=0;y<=n;y++) {
      for(z=0;z<=n;z++) {
         for(a=0;a<=n;a++) {
            for(b=0;b<=n;b++) {
               for(c=0;c<=n;c++) {
	         if (x+y+z==a+b+c)
                  s++;
               }
             }
           }
         }
       }
     }
    printf (“s=%d “,s);
}

Результат s=55252 22мин 54c

С оптимизацией
SHARP PC-G850S

main() {
int  x,y,z,a,b,c,k=0,n=9;
long  s=0;
for(x=0;x<=n;x++) {
   for(y=0;y<=n;y++) {
      for(z=0;z<=n;z++) {
         for(a=0;a<=n;a++) {
            for(b=0;b<=n;b++) {
            k=0;
               for(c=0;c<=n;c++) {
	 if (x+y+z==a+b+c){
         k=1;s++;break;}
    }
         if ((k==1)&(c==0))
         break;
   }
          if ((k==1)&(b==0)&(c==0))
         break; 
 }
         }
       }
     }
    printf (“s=%d “,s);
}

Результат s=55252 13мин 22c

C оптимизацией
Casio 9750 GII

0→s
For 0→x  to 9
For 0→y  to 9
For 0→z  to 9 
For 0→a  to 9
For 0→b  to 9
0→k
For 0→c  to 9
If (x+y+z)= (a+b+c):then
1→k :s+1→s:Break
IfEnd
Next
If k= 1 and c=0:  then
Break
IfEnd
Next
If k= 1 and c=0 and b=0:  then
Break
IfEnd
Next
Next
Next
Next
s˛

Результат 55252 56мин 05с

HP35s для 4-значных билетов: 20 минут

01 LBL H      15 RCL W      29 STO Z   
02 9e-3       16 IP         30 ISG Y   
03 STO A      17 RCL V      31 GTO H010
04 STO Z      18 IP         32 RCL A
05 STO Y      19 +          33 STO Y
06 STO W      20 x!=y?      34 ISG W
07 STO V      21 GTO H026   35 GTO H010
08 0          22 RCL T      36 RCL A
09 STO T      23 1          37 STO W
10 RCL Z      24 +          38 ISG V
11 IP         25 STO T      39 GTO H010
12 RCL Y      26 ISG Z      40 VIEW T
13 IP         27 GTO H010   41 RTN   
14 +          28 RCL A 

T = 670.0000

Для 6-значных билетов, в идеальном случае: 20х100 минут или 33 часа с половиной часа, тестировать я поленился.

UPDATE:
Из теста 8-ферзей:
http://pmk.arbinada.com/node/30

N-Queens Problem
4:17       HP-35S           Keystroke / RPN
15.3       MK-161           Keystroke / RPN / Ver.1.03

МК-161 с той прошивкой быстрее hp35s в 16.8 раз. Исходя из этого, "Счастливые билеты" для HP35s для 6 цифр должны быть около 1550 минут.

В любом случае HP35s тормоз чуть менее чем полностью.

Программа для HP-50g на UserRPL.

<<
  TICKS #0d
  #0d #9d FOR A
    #0d #9d FOR B
      #0d #9d FOR C
        #0d #9d FOR D
          #0d #9d FOR E
            #0d #9d FOR F
              A B C + +
              D E F + +
              IF == THEN
                #1d +
              END
            NEXT   
          NEXT   
        NEXT   
      NEXT   
    NEXT   
  NEXT   
  SWAP TICKS SWAP - B->R 8192. /
  400 2 BEEP
>>

Результат:
# 55252d
16963.7645264, то есть 282 минуты

P.S. Ждем выхода newRPL :)

Casio fx-9860G Slim
Результат: 55252 46мин 48с ( Программа аналогична Casio fx-9750G II c оптимизацией)

Casio fx-9860G SD
Результат: 55252 49мин 07с ( Программа аналогична Casio fx-9750G II c оптимизацией)

Программы для разных калькуляторов, увы, кодируют разные алгоритмы и поэтому выполняются за разное время.

Вот самый быстрый алгоритм прямого перебора, укладывающегося в условие задачи. Реализовав его для своего любимого калькулятора, можно немножко приподнять его в топе. :-)

int a,b,c, d,e,f, ab, abc, h, S;

S = 0;
for (a = 0; a < 10; ++a)
  for (b = 0; b < 10; ++b)
  { ab = a + b ;
    for (c = 0; c < 10; ++c)
    { abc = ab + c ;
      for (d = 0; d < 10; ++d)
      { g = abc - d;
        for (e = 0; e < 10; ++e)
    	{ h = g - e ;
          for (f = 0; f < 10; ++f)
            if ( f == h )
		++S;
	}
      }	
    }
  }
Печать (S);

Циклы «с нулём» действительно быстрее. Вот псевдокод, в котором переменные цикла сравниваются с нулём.

int a,b,c, d,e,f, ab,abc, g,h, S;

S = 0;
for (a = 9; a >= 0; --a)
  for (b = 9; b >= 0; --b)
  { ab = a + b ;
    for (c = 9; c >= 0; --c)
    { abc = ab + c ;
      for (d = 9; d >= 0; --d)
      { g = abc - d;
        for (e = 9; e >= 0; --e)
    	{ h = g - e ;
          for (f = 9; f >= 0; --f)
            if ( f == h )
		++S;
	}
      }	
    }
  }
Печать (S);

Если важно экономить регистры (уменьшить количество переменных), можно использовать ab, abc, g и h в качестве переменных циклов напрямую — избавившись от более очевидных (для читателя программы) b, c, d и e. Конечно, инициализация переменной цикла станет сложнее, как и условие окончания цикла. Зато в циклах не будет лишней арифметической операции.

Вот этот псевдокод:

int a,f, ab,abc, g,h, S;

S = 0;
for (a = 9; a >= 0; --a)
  for (ab = a+9; ab >= a; --ab)
    for (abc = ab+9; abc >= ab; --abc)
      for (g = abc-9; g <= abc; ++g)
        for (h = g-9; h <= g; ++h)
          for (f = 9; f >= 0; --f)
            if ( f == h )
		++S;
Печать (S);

<< TICKS 0 'S' LSTO
0 9 FOR 'A'
  0 9 FOR 'B'
    0 9 FOR 'C'
      0 9 FOR 'D'
        0 9 FOR 'E'
          0 9 FOR 'F'
            A B C + +
            D E F + +
            IF == THEN
              'S' INCR DROP
            END
          NEXT   
        NEXT   
      NEXT   
    NEXT   
  NEXT   
NEXT   
TICKS SWAP - 1E6 / S SWAP
>>

Вывод:
55252
37.6 секунд

Версия с использованием ранее вычисленных сумм - 23,4 секунды :)

<< TICKS 0 'S' LSTO
0 9 FOR 'A' A
  0 9 FOR 'B' DUP B +
    0 9 FOR 'C' DUP C +
      0 9 FOR 'D' DUP D -
        0 9 FOR 'E' DUP E -
          0 9 FOR 'F' DUP F -
            0 IF == THEN
              'S' INCR DROP
            END
          NEXT   
        DROP NEXT   
      DROP NEXT    
    DROP NEXT   
  DROP NEXT   
DROP NEXT   
TICKS SWAP - 1E6 / S SWAP
>>

P.S. Интерфейс у newRPL пока неудобный.

Питание от батареи: 31 мин 40 сек; от USB: 12 мин 35 сек. Подробнее тут.

HP Prime G2
Прямым перебором

EXPORT PROG()
BEGIN
S:=0;
Q:=9;
 FOR X FROM 0 TO Q DO
  FOR Y FROM 0 TO Q DO
   FOR Z FROM 0 TO Q DO
    FOR A FROM 0 TO Q DO
     FOR B FROM 0 TO Q DO
      FOR C FROM 0 TO Q DO
       IF X+Y+Z==A+B+C THEN
        S:=S+1;
       END;
      END;
     END;
    END;
   END;
  END;
 END;
S;
END;

Результат 24.5 сек.