Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

C/++/# Can you detect any formula here?

Tags:
  1. Oct 10, 2016 #1
    I'm trying to figure out a basic formula from the below

    1 -> 1
    2 -> 1
    3 -> 1
    4 -> 2
    5 -> 3
    6 -> 4
    7 -> 5
    8 -> 7
    9 -> 10
    10 -> 14
    11 -> 19
    12 -> 26
    13 -> 36
    14 -> 50
    15 -> 69
    16 -> 86
    17 -> 117
    18 -> 167
    19 -> 180
    20 -> 238
    21 -> 352
    22 -> 319
    23 -> 374
    24 -> 625
    25 -> 480
    26 -> 505
    27 -> 875
    28 -> 603
    29 -> 501
    30 -> 965
    31 -> 658
    32 -> 378
    33 -> 808
    34 -> 581
    35 -> 2386
    36 -> 580

    If you're curious where I'm getting these results from, it's a brute force algorithm I wrote that gets the number of configurations of blocks of size 1x4 and 4x1 blocks that can cover a 4xN board. But I'd ideally like to make this an O(1) algorithm if I can figure out what the formula is ...
     
  2. jcsd
  3. Oct 10, 2016 #2
    Okay, I should probably post the code I wrote that generated that mapping. This is part of a larger problem I'm trying to solve.

    Code (Text):

    using System;
    using System.Collections.Generic;
    using System.IO;
    using System.Linq;

    public class Solution
    {
        public static int Factorial(int k)
        {
            int p = 1;
            for(; k > 1; --k)
                p *= k;
            return p;
        }
       
        public static int NumberCombinations(int m, int n)
        {
            return Factorial(m + n) / (Factorial(n) * Factorial(m));
        }
       
        static int NumberConfigurations(int n)
        {  
            var range = Enumerable.Range(0, n + 1); // 0, 1, ..., n
            return (from i in range
                   from j in range
                    where (i * 4 + j) == n
                    select i * j == 0 // either i or j is 0
                          ? 1
                          : NumberCombinations(i,j)
                    ).Sum();
           
        }
       
        public static void Main(String[] args)
        {
            for(int i = 1; i < 50; ++i)
                Console.WriteLine(i.ToString() + " -> " + NumberConfigurations(i).ToString());
        }
    }
     
     
  4. Oct 10, 2016 #3

    Ibix

    User Avatar
    Science Advisor

    To cover a 4xN grid with 4x1 tiles takes N tiles, surely? Each one covers a row.
     
  5. Oct 10, 2016 #4
    4x1 or 1x4 tiles.

    For example, if N=5 you could use 5 4x1 tiles, 1 4x1 tile followed by 4 1x4 tiles stacked, or 4 1x4 tiles stacked followed by one 4x1 tiles.

    I see this as equivalent to first solving the equation

    4i + j = n

    for non-negative integers i,j and then for the pairs where i,j>0 you have (i+j)!/(i! * j!) ways of arranging them.
     
  6. Oct 10, 2016 #5

    Hmmmm I'm wondering whether my algorithm is even correct. Because this is failing most of the test cases. I may as well admit that what I'm trying to solve is https://www.hackerrank.com/challenges/red-john-is-back

    Code (Text):

    using System;
    using System.Collections.Generic;
    using System.IO;
    using System.Linq;

    public class PrimeNumberChecker
    {
        private Dictionary<long,bool> cache = new Dictionary<long,bool>();
       
        public bool IsPrime(long k)
        {
            if(cache.ContainsKey(k))
                return cache[k];
           
            bool isPrime = true;
            for(long j = 2; j < k; j++)
            {
                if(k % j == 0)
                {
                    isPrime = false;
                    break;
                }
            }
            cache[k] = isPrime;
            return isPrime;      
        }
    }

    public class FormulaMachine
    {
        private PrimeNumberChecker pChecker = new PrimeNumberChecker();
       
        public IEnumerable<long> PrimeNums(long num)
        {
            for(long i = 2; i <= num; i++)
                if(pChecker.IsPrime(i))
                    yield return i;
        }
       
        private static long Factorial(long k)
        {
            long p = 1;
            for(; k > 1; --k)
                p *= k;
            return p;
        }
       
        private static long NumberCombinations(long m, long n)
        {
            return Factorial(m + n) / (Factorial(n) * Factorial(m));
        }
       
        public long NumberConfigurations(long n)
        {  
            var range = Enumerable.Range(0, (int)(n + 1)); // 0, 1, ..., n
            return (from i in range
                   from j in range
                    where (i * 4 + j) == n
                    select NumberCombinations(i,j)
                    ).Sum();
           
        }
    }

    public class Solution
    {  
        public static void Main(String[] args)
        {
            var machine = new FormulaMachine();
            for(long t = 0, T = long.Parse(Console.ReadLine()); t < T; ++t)
            {
                long N = long.Parse(Console.ReadLine());
                long configs = machine.NumberConfigurations(N);
                long primes = machine.PrimeNums(configs).Count();
                Console.WriteLine(primes);
            }
        }
    }
     
     
  7. Oct 10, 2016 #6

    Ibix

    User Avatar
    Science Advisor

    Sorry - misread the question. You could observe that there is one way to do it solely with horizontal tiles and N-3 ways to do it with only four vertical tiles. Each choice of a position gives you two sub-problems, the range above the four verticals and the range below, so you can divide and conquer, and you can store previously solved problems to save time.
     
  8. Oct 10, 2016 #7

    wle

    User Avatar

    This is easy: i ranges from 0 to n / 4 and j is just n - 4 * i. (According to documentation, the result of dividing two integers is another integer, so, e.g., as far as C# is concerned 11 / 4 == 2.)

    I don't know C# but my guess is this means you can simplify your code computing the number of arrangements to something like

    Code (C#):
        static int NumberConfigurations(int n)
        {
            var range = Enumerable.Range(0, n / 4 + 1);
            return (from i in range
                    select NumberCombinations(i, n - 4 * i)).Sum();
        }
    (If you've written NumberCombinations() correctly then it should return 1 if either of its arguments are zero, so you don't need to check for this explicitly.)

    The results in your first post look wrong starting with ##N = 16##. This is probably a result of integer overflow. You compute the number of combinations by literally computing the factorial of i + j and then dividing by the factorials of i and j. The problem is that the factorial is a rapidly increasing function: the factorial of 13 is already too large to store as a signed 32 bit int, and the factorial of 21 won't fit in a signed 64 bit long. In the ##N = 16## case the code in your second post tries to compute the factorial of 13 (with i = 1 and j = 12), so you get the overflow.

    One way to mitigate this (to some extent) is to rewrite your NumberCombinations() method to avoid computing excessively large intermediate integer results. (For instance, you can buy some breathing room using that ##\tfrac{(i + j)!}{i!} = (i + j) \times (i + j - 1) \times \cdots \times (i + 1)##.)
     
    Last edited: Oct 10, 2016
  9. Oct 10, 2016 #8

    robphy

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted



Similar Discussions: Can you detect any formula here?
  1. Can you help me ? (Replies: 2)

Loading...