Home ›

Forfeit game - coding contest since 50 years

Christian Harms's picture
by Christian Harms on Mon, 11/08/2010 - 17:11
in

The game of forfeits is a simple game and one of the classic programming examples since 50 years. I found it in a ALGOL 60 exercise book from 1963: Count the numbers up to 100, but skip all numbers if one of the condition matches:

  • number is divisible by seven
  • number contains a seven
  • sum of digits is divisible by seven
  • sum of digits contains a seven

Develop a function which calculates all numbers based on the given conditions. The only one parameter for the function is the range and the function should return the Array of all valid numbers. Hint: You must not cheat while returning a sliced constant result array. The result of the function with max=100 is: [1, 2, 3, 4, 5, 6, 8, 9, 10, 11, 12, 13, 15, 18, 19, 20, 22, 23, 24, 26, 29, 30, 31, 32, 33, 36, 38, 39, 40, 41, 44, 45, 46, 48, 50, 51, 53, 54, 55, 58, 60, 62, 64, 65, 66, 69, 80, 81, 82, 83, 85, 88, 90, 92, 93, 94, 96, 99, 100].

clean code variant

Matthia's has delivered a clean code variant for the problem and it will be used as the reference for this coding contest. It's not the fastest solution but offers a direct implementation of the problem. Matthias uses an extra function for every condition and put it together in the main loop.

function cleanCodeSolution(n){
        for (var i=0, res=[]; i <= n; i++) {
            if (!(containsSeven(i) || isMultipleOfSeven(i) ||
                  sumContainsSeven(i) || sumIsMultipleOfSeven(i))) {
                res.push(i);
            }
        }
        return res;

        //all helper functions defined in local scope
        function containsSeven (n) {
            return String(n).indexOf("7") !== -1;
        };
        function isMultipleOfSeven (n) {
            return n % 7 === 0;
        };
        function sumContainsSeven (n) {
            return containsSeven(sumOfDigits(n));
        };
        function sumIsMultipleOfSeven (n) {
            return isMultipleOfSeven(sumOfDigits(n));
        } ;
        function sumOfDigits (n) {
            var sum = 0;
            while (n > 0) {
                sum += n % 10;
                n = Math.floor(n / 10);
            }
            return sum;
        };
}

If you are surprised about using the helper function before defining, read more about function defining the the In-depth guide to javascript functions.

Testing your solution

In the following textbox you can test your solution by pasting your javascript function body direct into it. It will be compared to Matthias' clean code version and a performance optimized short clean code version, which works without functions.

/* game of forfeits
   var number {n} numbers to check
   return list of number
*/
function mySolution(n) {

};
Result of your function

You can include my javascript test suite and add your solution. The benchmark will test your function only with n=100.

  1. <script src="http://united-coders.com/sites/default/files/JSLitmus.js.txt" type="text/javascript"></script>
  2. <script src="http://united-coders.com/sites/default/files/forfeits.js.txt" type="text/javascript"></script>
  3. <script type="text/javascript">
  4.   JSLitmus.test("clean code version", com.unitedCoders.forfeits.testClean);
  5.   JSLitmus.test("short version", com.unitedCoders.forfeits.testShort);
  6.   if (com.unitedCoders.forfeits.runTest(myFunction) {
  7.     JSLitmus.test("your version", function() { myFunction(100); } );
  8.   }
  9. </javascript>

more sultions

In older articles (javascript lotto generator or articles with code puzzles tag), here on united-coders.com we linked articles and got comments with solutions in other languages. Feel free to comment or use our tackbacks, but only javascript have the possibility to run directly in the browser.

I will post in the second article the original ALGOL 60 solutions and my 1:1 migration to the javascript variant to benchmark it with today's coding skills. If we got some interesting solutions the third article will comment, link and benchmark all.

AttachmentSize
forfeits.js.txt2.97 KB

Comments

azendal's picture
my results
azendal (not verified) - Wed, 11/10/2010 - 06:33

  1. var cs, i, sum, j, result = [];
  2.     n++;
  3.     for(i = 0; i < n; i++){
  4.         cs = i + '';
  5.         if( !(i % 7 == 0 || cs.indexOf('7') != -1) ){
  6.             if(cs.length == 1 && i % 2 != 0){
  7.                 result.push(i);
  8.                 continue;
  9.             }
  10.             j = i
  11.             sum = 0;
  12.             while (j > 0) {
  13.                 sum += j % 10;
  14.                 j = Math.floor(j / 10);
  15.             }
  16.             if( !(sum % 7 == 0 || (sum + '').indexOf('7') != -1) ){
  17.                 result.push(i);
  18.             }
  19.         }
  20.     }
  21.    
  22.     return result;
  23. <javascript>
  24.  
  25.   //the link is:  http://tinyurl.com/2bgoywn

azendal's picture
correcting mistake
azendal (not verified) - Wed, 11/10/2010 - 06:36

  1. var cs, i, sum, j, result = [];
  2.     n++;
  3.     for(i = 0; i < n; i++){
  4.         cs = i + '';
  5.         if( !(i % 7 == 0 || cs.indexOf('7') != -1) ){
  6.             if(cs.length == 1 && i % 2 == 0){
  7.                 result.push(i);
  8.                 continue;
  9.             }
  10.             j = i
  11.             sum = 0;
  12.             while (j > 0) {
  13.                 sum += j % 10;
  14.                 j = Math.floor(j / 10);
  15.             }
  16.             if( !(sum % 7 == 0 || (sum + '').indexOf('7') != -1) ){
  17.                 result.push(i);
  18.             }
  19.         }
  20.     }
  21.    
  22.     return result;

Christian Harms's picture
solution with factor 2
Christian Harms - Wed, 11/10/2010 - 19:33

Thanx - this variant optimize the big check and is better by factor 2 than the clean code variant.

Keeto's picture
function forfeit(n){        
Keeto (not verified) - Wed, 11/10/2010 - 14:20

  1. function forfeit(n){
  2.         var result = [];
  3.         n++;
  4.         while (n--){
  5.                 var curr = String(n);
  6.                 if ((curr % 7)
  7.                         && !(curr.match(/7/))
  8.                         && (currsum = curr.split('').reduce(function(p, v){ return p + (+v) }, 0))
  9.                         && (currsum % 7)
  10.                         && !(String(currsum).match(/7/))) result.unshift(+curr);
  11.         }
  12.         return result;
  13. }

Keeto's picture
Did I win the slowest award?
Keeto (not verified) - Wed, 11/10/2010 - 14:30

Did I win the slowest award? :D

Christian Harms's picture
solution with factor 0.3
Christian Harms - Wed, 11/10/2010 - 19:44

Hmmm, regular expressions are not the best choice for a performance programming contest. But the usage of reduce to get the checksum is fine!

droope's picture
asda this is how i would have done it
droope (not verified) - Wed, 11/10/2010 - 15:29

asda this is how i would have done it :)

almost the same

  1. function containsSeven (n) {
  2.             return String(n).indexOf("7") !== -1;
  3.         };
  4.         function isMultipleOfSeven (n) {
  5.             return n % 7 === 0;
  6.         };
  7. function sumOfDigits (n) {
  8.             var sum = 0;
  9.             while (n > 0) {
  10.                 sum += n % 10;
  11.                 n = Math.floor(n / 10);
  12.             }
  13.             return sum;
  14.         };
  15. var retArr = [];
  16. for(var x = 0; x <= n; x++) {
  17. if(!containsSeven(x) && !isMultipleOfSeven(x) && !containsSeven(sumOfDigits(x)) && !isMultipleOfSeven(sumOfDigits(x))) {
  18. retArr.push(x);
  19. }
  20. }
  21.  
  22. return retArr;

Matthew's picture
My results:
Matthew (not verified) - Wed, 11/10/2010 - 20:53

  1. function forfeits(n)
  2. {
  3.         a = [];
  4.         i = 0;
  5.         for(var j = 1;j <= n; j++)
  6.         {
  7.                 bBad = false;
  8.                 bBad = checkDiv(j);
  9.                 if(!bBad)
  10.                 {
  11.                         bBad = checkDig(j);
  12.                 }
  13.                 if(!bBad)
  14.                 {
  15.                         bBad = checkSumDiv(j);
  16.                 }
  17.                 if(!bBad)
  18.                 {
  19.                         bBad = checkSumDig(j);
  20.                 }
  21.                 if(!bBad)
  22.                 {
  23.                         a[i] = j;
  24.                         i++;
  25.                 }
  26.         }
  27.         output = "[";
  28.        
  29.         return a;
  30. }
  31.  
  32. function checkDiv(j)
  33. {
  34.         if(j%7 == 0)
  35.         {
  36.                 return true;
  37.         }
  38.         else
  39.         {
  40.                 return false;
  41.         }
  42. }
  43. function checkDig(j)
  44. {
  45.         num = "" + j;
  46.         numArray = num.split("");
  47.         for(var k = 0;k <= numArray.length;k++)
  48.         {
  49.                 if(numArray[k] == "7")
  50.                 {
  51.                         return true;
  52.                 }
  53.         }
  54.         return false;
  55. }
  56.  
  57. function checkSumDiv(j)
  58. {
  59.         num = "" + j;
  60.         total = 0;
  61.         numArray = num.split("");
  62.         for(var k = 0;k < numArray.length;k++)
  63.         {
  64.                 total += parseInt(numArray[k]);
  65.         }
  66.         return checkDiv(total);
  67. }
  68.  
  69. function checkSumDig(j)
  70. {
  71.         num = "" + j;
  72.         total = 0;
  73.         numArray = num.split("");
  74.         for(var k = 0;k < numArray.length;k++)
  75.         {
  76.                 total += parseInt(numArray[k]);
  77.         }
  78.         return checkDig(total);
  79. }

http://tinyurl.com/2fgmwrr

Christian Harms's picture
factor 0.3, make smarter code
Christian Harms - Wed, 11/10/2010 - 23:35

Hi Matthew, your solutions works but is slower than the clean code version. Try to make smarter code. We have some articles here on the blog (JavaScript types, defining functions and type-safe functions) and I will give you some improvements/hints:

line 3,4,...: ALWAYS add "var " before defining (=first usage) a variable - if not the variable is defined in global scope. This means after calling calling checkDig "num" and "numArray" is available in every other function!

line 7-22: Use && or || to combine conditions!

line 23: Adding an item to a list - use the method Array.push instead of incrementing the index and assigning to the current position

line 34: Never just return true or false in the body of an IF-statement

  1. //bad version
  2. if (j%7 == 0) {
  3.   return true;
  4. } else {
  5.   return false;
  6. }
  7. // better version: a condition always return a boolean result
  8. return (j/7 ==0)

line 34, 49: if both terms are with the same type, use type-hard comperator "===" instead "==" (see more on All about types)

line 76: never forget the second parameter for parseInt(str, radix) - see w3scools.

line 58, 69: both function have the same code except the last line - use a function to calculate the sumOfDigit.

sud's picture
in Java using the Decorator Pattern
sud (not verified) - Thu, 11/11/2010 - 03:16

Just for kicks, I implemented the solution in Java using the Decorator Pattern for good OO design.

https://github.com/sudr/sandbox/tree/master/forfeit/

MSM's picture
My Solution
MSM (not verified) - Thu, 11/11/2010 - 06:29

I can't seen to make it run in your test harness, but when I run it in the page shown at https://gist.github.com/672058 it appears to return the correct array.

  1. function forfeit(n)
  2. {
  3.         if (n == 0) return new Array(0);
  4.         if ((n % 7) == 0) return forfeit(n-1);
  5.         if (n.toString().indexOf('7') != -1) return forfeit(n-1);
  6.         if ((sum_of_digits(n) % 7) == 0) return forfeit(n-1);
  7.         if (sum_of_digits(n).toString().indexOf('7') != -1) return forfeit(n-1);
  8.         return forfeit(n-1).concat([n]);
  9.  
  10.         function sum_of_digits(n)
  11.         {
  12.                 if (Math.floor(n / 10) == 0) return (n);
  13.                 return (n % 10) + sum_of_digits(Math.floor(n / 10));
  14.         };
  15. }

MSM's picture
Or, if you like
MSM (not verified) - Thu, 11/11/2010 - 14:53

Same thing, only refactoring all the return statements. Meh.

  1. function forfeit(n)
  2. {
  3.         if (n == 0) return new Array(0);
  4.         if (((n % 7) == 0)                                  ||
  5.            (n.toString().indexOf('7') != -1)                ||
  6.            ((sum_of_digits(n) % 7) == 0)                    ||
  7.            (sum_of_digits(n).toString().indexOf('7') != -1))
  8.            return forfeit(n-1);
  9.         return forfeit(n-1).concat([n]);
  10.  
  11.         function sum_of_digits(n)
  12.         {
  13.                 if (Math.floor(n / 10) == 0) return (n);
  14.                 return (n % 10) + sum_of_digits(Math.floor(n / 10));
  15.         };
  16. }

Christian Harms's picture
factor 1 - works in the testsuite
Christian Harms - Thu, 11/11/2010 - 22:44

MSM, simply add the following line with your function in the textbox. Your function is called recursive and it have to defined in the local scope of the test function.

  1. return forfeit(n);

But it has the same runetime like the clean code variant.

MSM's picture
Thanks
MSM (not verified) - Fri, 11/12/2010 - 01:00

Significant differences between JS runtimes, it appears.

Looks like the Webkit JS runtime has some issues with recursion. I'm not up on the differences in JS interpreters, though I'm impressed with V8 in general here.

MSM's picture
Improvement
MSM (not verified) - Fri, 11/12/2010 - 23:29

I took the array concatenation out of my function and replaced it with a push. Unfortunately, that meant adding a variable assignment. Oh, well. Purity falls to practicality.

  1. function msmforfeit3(n)
  2. {
  3.         if (n == 1) return [n];
  4.         if ((n % 7) == 0) return msmforfeit3(n-1);
  5.         if (n.toString().indexOf('7') != -1) return msmforfeit3(n-1);
  6.         if ((sum_of_digits(n) % 7) == 0) return msmforfeit3(n-1);
  7.         if (sum_of_digits(n).toString().indexOf('7') != -1) return msmforfeit3(n-1);
  8.         a = msmforfeit3(n-1)
  9.         a.push(n);
  10.         return a;
  11.  
  12.         function sum_of_digits(n)
  13.         {
  14.                 if (Math.floor(n / 10) == 0) return (n);
  15.                 return (n % 10) + sum_of_digits(Math.floor(n / 10));
  16.         };
  17. }

This resulted in speedups in all engines:

I think I'm done with this now.

Ian's picture
My solution, dark magic
Ian (not verified) - Thu, 11/11/2010 - 09:20

I'm not very sure if it really work but I think it can be improved.

  1. var nu = [];
  2. var already = [];
  3. nu[0] = -1;
  4. function numeral (n) {
  5.     nu[n]++;
  6.     if (nu[n] == 10) {
  7.         nu[n] = 0;
  8.         ns = n+1;
  9.         if (nu[ns] == undefined) {
  10.             nu[ns] = 0;
  11.         }
  12.         numeral(ns);
  13.     }
  14. };
  15.  
  16. outer:
  17. for (var i=0, res=[], sum, seven=0; i <= n; i++, seven++) {
  18.     numeral(0);
  19.     if (seven == 7) {
  20.         seven = 0;
  21.         continue outer;
  22.     }
  23.     sum = 0;
  24.     for (var j=0, nuLen=nu.length; j < nuLen; j++) {
  25.         if (nu[j] == 7) {
  26.             continue outer;
  27.         }
  28.         sum += nu[j];
  29.     }
  30.     already[i] = true;
  31.     if (already[sum] !== true) {
  32.         continue outer;
  33.     }
  34.     if (i == 0) {
  35.         continue outer;
  36.     }
  37.     res[res.length] = i;
  38. }
  39. return res;

http://tinyurl.com/236wvob

Peter Galiba's picture
Almost clean code
Peter Galiba (not verified) - Thu, 11/11/2010 - 11:18

  1.   var sum, i, res, d, j, s;
  2.  
  3.   for (res = [], i = 1; i <= n; i += 1) {
  4.     s = i + '';
  5.     if (s.indexOf('7') === -1 && (i % 7)) {
  6.       for (sum = 0, d = s.split(''), j = d.length - 1; j >= 0; j -= 1) {
  7.         sum += +d[j];
  8.       }
  9.       if ((sum + '').indexOf('7') === -1 && (sum % 7)) {
  10.         res.push(i);
  11.       }
  12.     }
  13.   }
  14.   return res;

Peter Galiba's picture
Faster version
Peter Galiba (not verified) - Thu, 11/11/2010 - 11:27

  1.   var sum, i, res, j, s;
  2.  
  3.   for (res = [], i = 1; i <= n; i += 1) {
  4.     s = i + '';
  5.     if (s.indexOf('7') === -1 && (i % 7)) {
  6.       for (sum = 0, j = s.length - 1; j >= 0; j -= 1) {
  7.         sum += +s.charAt(j);
  8.       }
  9.       if ((sum + '').indexOf('7') === -1 && (sum % 7)) {
  10.         res.push(i);
  11.       }
  12.     }
  13.   }
  14.   return res;

Peter Galiba's picture
Without JSLint compliance
Peter Galiba (not verified) - Thu, 11/11/2010 - 12:04

  1.   var sum, i, res, j, s;
  2.  
  3.   for (res = [], i = 1; i <= n; i++) {
  4.     s = i + '';
  5.     if (s.indexOf('7') === -1 && (i % 7)) {
  6.       if (i < 10) {
  7.         sum = i;
  8.       }
  9.       else {
  10.         for (sum = 0, j = s.length - 1; j >= 0; j--) {
  11.           sum += +s.charAt(j);
  12.         }
  13.       }
  14.       if ((sum + '').indexOf('7') === -1 && (sum % 7)) {
  15.         res.push(i);
  16.       }
  17.     }
  18.   }
  19.   return res;

Ian's picture
improved one
Ian (not verified) - Thu, 11/11/2010 - 16:54

it should get better performance when n is much greater.
http://tinyurl.com/2f77fq5

  1. var nu = [];
  2. var yet = [];
  3. nu[0] = 0;
  4. function numeral (n) {
  5.     nu[n]++;
  6.     if (nu[n] == 10) {
  7.         nu[n] = 0;
  8.         ns = n+1;
  9.         if (nu[ns] == undefined) {
  10.             nu[ns] = 0;
  11.         }
  12.         numeral(ns);
  13.     }
  14. };
  15.  
  16. outer:
  17. for (var i=1, res=[], sum, seven=1; i <= n; i++, seven++) {
  18.     numeral(0);
  19.     if (seven == 7) {
  20.         seven = 0;
  21.         continue outer;
  22.     }
  23.     sum = 0;
  24.     for (var j=nu.length-1; j >= 0; j--) {
  25.         if (nu[j] == 7) {
  26.             continue outer;
  27.         }
  28.         sum += nu[j];
  29.     }
  30.     yet[i] = true;
  31.     if (yet[sum] !== true) {
  32.         continue outer;
  33.     }
  34.     res[res.length] = i;
  35. }
  36. return res;

Ian's picture
improved for chrome?
Ian (not verified) - Thu, 11/11/2010 - 17:49

http://tinyurl.com/2wr669r

I think it should start from 0 not from 1 as is in the test.

  1. var nu = [];
  2. var yet = [];
  3. nu[0] = 0;
  4. function numeral (n) {
  5.     nu[n]++;
  6.     if (nu[n] == 10) {
  7.         nu[n] = 0;
  8.         n++;
  9.         if (nu[n] == undefined) {
  10.             nu[n] = 0;
  11.         }
  12.         numeral(n);
  13.     }
  14. };
  15.  
  16. outer:
  17. for (var i=1, res=[], sum, seven=1; i <= n; i++, seven++) {
  18.     numeral(0);
  19.     if (seven == 7) {
  20.         seven = 0;
  21.         continue outer;
  22.     }
  23.     sum = 0;
  24.     for (var j=nu.length-1; j >= 0; j--) {
  25.         if (nu[j] == 7) {
  26.             continue outer;
  27.         }
  28.         sum += nu[j];
  29.     }
  30.     yet[i] = true;
  31.     if (yet[sum] !== true) {
  32.         continue outer;
  33.     }
  34.     res[res.length] = i;
  35. }
  36. return res;

azendal's picture
new version
azendal (not verified) - Thu, 11/11/2010 - 18:02

based on adrian's idea

  1. var cs, i, sum, j, result = [];
  2. n++;
  3. for(i = 0; i < n; i++){
  4.     cs = i + '';
  5.     if( !(i % 7 == 0 || cs.indexOf('7') != -1) ){
  6.         if(cs.length == 1 && i % 2 == 0){
  7.             result[result.length] = i;
  8.             continue;
  9.         }
  10.         j = i
  11.         sum = 0;
  12.         while (j > 0) {
  13.             sum += j % 10;
  14.             j = Math.floor(j / 10);
  15.         }
  16.        
  17.         if( !(sum % 7 == 0 || (sum + '').indexOf('7') != -1) ){
  18.             result[result.length] = i;
  19.             continue;
  20.         }
  21.     }
  22. }
  23.  
  24. return result;

http://tinyurl.com/29nzawf

Ian's picture
cool
Ian (not verified) - Thu, 11/11/2010 - 18:59

107.4k

http://tinyurl.com/278l9xu

  1. var nu = [];
  2. var yet = {};
  3. nu[0] = 0;
  4. function numeral (n) {
  5.     nu[n]++;
  6.     if (nu[n] == 10) {
  7.         nu[n] = 0;
  8.         n++;
  9.         if (nu[n] == undefined) {
  10.             nu[n] = 0;
  11.         }
  12.         numeral(n);
  13.     }
  14. };
  15.  
  16. outer:
  17. for (var i=1, res=[], sum, seven=1; i <= n; i++, seven++) {
  18.     numeral(0);
  19.     if (seven == 7) {
  20.         seven = 0;
  21.         continue outer;
  22.     }
  23.     sum = 0;
  24.     for (var j=nu.length-1; j >= 0; j--) {
  25.         if (nu[j] == 7) {
  26.             continue outer;
  27.         }
  28.         sum += nu[j];
  29.     }
  30.     yet[i] = true;
  31.     if (!yet[sum]) {
  32.         continue outer;
  33.     }
  34.     res[res.length] = i;
  35. }
  36. return res;

Christian Harms's picture
Yeah - factor 5 better!
Christian Harms - Thu, 11/11/2010 - 19:42

WOW, you got a better speedup than my own solution (not published yet) with this code. I will put all solutions together for better comparing next week.

Ian's picture
my best for firefox
Ian (not verified) - Thu, 11/11/2010 - 21:17

my best for firefox

http://tinyurl.com/2dzuyev

  1. var yet = {};
  2. for (var i=1, res=[], sum, tmp; i <= n; i++) {
  3.     if (i % 7 == 0 || (i+'').indexOf('7') !== -1) {
  4.         continue
  5.     }
  6.     sum = 0;
  7.     tmp = i;
  8.     while (tmp > 0) {
  9.         sum += tmp % 10;
  10.         tmp = Math.floor(tmp / 10);
  11.     }
  12.     yet[i] = true;
  13.     if (!yet[sum]) {
  14.         continue;
  15.     }
  16.     res[res.length] = i;
  17. }
  18. return res;

MSM's picture
recursion fail
MSM (not verified) - Thu, 11/11/2010 - 21:23

I'm laughing, now that I have the tests running. My recursive solutions above are dreadfully slow. I'm sure the array concatenation is not helping performance either.

Ian's picture
a different aproach
Ian (not verified) - Sat, 11/13/2010 - 23:44

different aproach, but almost the same speed

  1. /* game of forfeits
  2.    var number {n} numbers to check
  3.    return list of number
  4. */
  5. function mySolution(n) {
  6.     var nu = [], yet = {}, i=1;
  7.     nu[0] = 0;
  8.     function numeral (k) {
  9.         var currentNum=nu[k];;
  10.         if (currentNum == 6) {
  11.             nu[k] += 2;
  12.             if (k == 0) {
  13.                 i++;
  14.             } else if (k == 1) {
  15.                 i += 10;
  16.             } else if (k == 2) {
  17.                 i += 100;
  18.             } else {
  19.                 i += Math.pow(10,k);
  20.             }
  21.         } else if (currentNum == 9) {
  22.             nu[k] = 0;
  23.             k++;
  24.             if (nu[k] == undefined) {
  25.                 nu[k] = 1;
  26.             } else {
  27.                 numeral(k);
  28.             }
  29.         } else {
  30.             nu[k]++;
  31.         }
  32.     };
  33.  
  34.     outer:
  35.     for (var res=[], sum, dsum, seven=1; i <= n; i++) {
  36.         numeral(0);
  37.         if (i % 7 == 0) {
  38.             continue outer;
  39.         }
  40.         yet[i] = true;
  41.         sum = 0;
  42.         for (var j=0, nuLength=nu.length; j < nuLength; j++) {
  43.             sum += nu[j];
  44.         }
  45.         if (!yet[sum]) {
  46.             continue outer;
  47.         }
  48.         res[res.length] = i;
  49.     }
  50.     return res;
  51. };

forfeit game - ALGOL 60 solution from 1964 | united-coders.c's picture
Pingback
forfeit game - ALGOL 60 solution from 1964 | united-coders.c (not verified) - Mon, 11/15/2010 - 16:46

[...] found two ALGOL sniplets for the forfeit game contest. My ALGOL 60 programming book (happy birthday for the ALGOL programming language) offer for every [...]

Anonymous's picture
My take, about 7 times faster than clean Code version
Anonymous (not verified) - Tue, 11/16/2010 - 10:13

Despite some comments, RegExes are very fast. Just dont't compile them again and again on each iteration :-)
The trick with tis code is that it only sums up the digits on overflow

  1. var i, res, j, s;
  2. var m= /7/;
  3. var sum= 0, sum7= 0, sumc= 10;
  4. for ( res= [], i = 0; i <= n; i++, sum++, sum7++, sumc-- ) {
  5.     if ( sumc <= 0 ) {
  6.         for ( j=i, sum= 0; j; j= j / 10 | 0 ) sum += j % 10;
  7.         sum7= sum % 7;
  8.         sumc= 10;
  9.     }
  10.     if ( sum7 == 0 || sum7 == 7 || sum7 == 14 ) continue;
  11.     if ( i % 7 == 0 ) continue;
  12.     if ( m.test(String(i) + sum) ) continue;
  13.     res[res.length]= i;
  14. }
  15. return res;

Matthias Reuter's picture
Combined solution
Matthias Reuter - Tue, 11/16/2010 - 10:57

I had a version limited to n < 1700, from which I derived a recursive variant. Unfortunately, the recursive variant is much slower in IE and FF, so here's a combined approach:

  1. var combined = function (n) {
  2.     var level, res = [], k, len, i, isum, j, checksum, sum, bah;
  3.    
  4.     if (n === 0) {
  5.         return res;
  6.     }
  7.    
  8.     if (n < 1700) {
  9.         checksum = 0;
  10.    
  11.         for (k = 0, len = n / 100; k <= len; k++) {
  12.             if (k === 7) {
  13.                 continue;
  14.             }
  15.            
  16.             for (i = 0; i < 10; i++) {
  17.                 if (i === 7) {
  18.                     continue;
  19.                 }
  20.            
  21.                 for (j = 0, checksum = k + i, sum = 100*k + 10*i; j < 10 && sum <= n; j++, checksum++, sum++) {
  22.                     if (j !== 7 && sum % 7 && checksum % 7 && checksum % 10 !== 7) {
  23.                         res[res.length] = sum;
  24.                     }
  25.                 }
  26.             }
  27.         }
  28.        
  29.         return res;
  30.     }
  31.     else {
  32.         bah = function (level, sum, checksum, result, limit) {
  33.             var i;
  34.        
  35.             if (level === 1) {
  36.                 for (i = 0; i < 10 && sum <= limit; i++, checksum++, sum++) {
  37.                     if (i !== 7 && sum % 7 && checksum % 7 && checksum % 10 !== 7 && (checksum < 71 || !("" + checksum).match(/7/))) {
  38.                         result[result.length] = sum;
  39.                     }
  40.                 }
  41.             }
  42.             else {
  43.                 for (i = 0; i < 10; i++) {
  44.                     if (i !== 7) {
  45.                         bah(level - 1, 10 * (sum + i), checksum + i, result, limit);
  46.                     }
  47.                 }
  48.             }
  49.         };
  50.  
  51.         level = ("" + n).length;
  52.         bah(level, 0, 0, res, n);
  53.        
  54.         return res;
  55.     }
  56. };

kyungw00k's picture
Same as others
kyungw00k (not verified) - Fri, 11/26/2010 - 04:12

  1. function forfeits(n) {
  2.         var res = [], i = n+1, sum = 0;
  3.         while ( i-- ) {
  4.                 sum = String(i).split('').reduce(function(a,b){return a+(+b);},0);
  5.                 if ( !(
  6.                         !(i%7)
  7.                         || (String(i).indexOf('7'))+1
  8.                         || !(sum%7)
  9.                         || (String(sum).indexOf('7'))+1
  10.                 ) ) {
  11.                         res.unshift(i);
  12.                 }
  13.         }
  14.         return res;
  15. }

http://tinyurl.com/24y26aa

boxersb's picture
This is my solution..
boxersb (not verified) - Fri, 11/26/2010 - 05:35

function mySolution(n) {
var checkContainSeven = function(digit){
var sd = (digit+"").split(""), ret = 0;

while(sd.length){
var d = parseInt(sd.shift(), 10);
if(d == 7){
ret = 7;
break;
}else{
ret += d;
};
};

return (digit % 7) && (ret % 7) && (ret+"").indexOf("7") == -1;
};

var ret = [], sum = 0;
for(var i=0; i<=n; i++){
checkContainSeven(i) && ret.push(i);
};

return ret;
};

I thought that must using deep depth recursive mechanism.. But your results are not.. It's little strange.. :-)

boxersb's picture
function mySolution(n) {    
boxersb (not verified) - Fri, 11/26/2010 - 05:42

  1. function mySolution(n) {
  2.                 var checkContainSeven = function(digit){
  3.                         var sd = (digit+"").split(""), ret = 0;
  4.                        
  5.                         while(sd.length){                      
  6.                                 var d = parseInt(sd.shift(), 10);
  7.                                 if(d == 7){                    
  8.                                         ret = 7;
  9.                                         break;
  10.                                 }else{
  11.                                         ret += d;
  12.                                 };
  13.                         };
  14.  
  15.                         return (digit % 7) && (ret % 7) && (ret+"").indexOf("7") == -1;
  16.                 };
  17.  
  18.                 var ret = [], sum = 0;
  19.                 for(var i=0; i<=n; i++){
  20.                         checkContainSeven(i) && ret.push(i);
  21.                 };             
  22.                
  23.                 return ret;
  24.         };

Javascript algorithm performance : And the winner is ... | u's picture
Pingback
Javascript algorithm performance : And the winner is ... | u (not verified) - Thu, 12/02/2010 - 11:46

[...] little programming contest was fun and we can learn something about best practices in javascript algorithm performance. I have [...]