25
\$\begingroup\$

Intro

You are sitting in a board room at the end of a long table. You look around and see Tim Cook, the Apple Board of Directors, the ghost of Steve Jobs, and Jack Donaghy. Apple has called this meeting because they have realized how much cooler the Android lock screen is, and they want to 1-UP them. Everyone in the room stares at you as Ghost Steve cries, "Help me, CodeGolf Man! You're my only hope!"

The Problem

The Android lock screen is a 3 x 3 grid of dots that can be connected by swiping a finger from one dot to the next, creating a path. A password is considered any possible path that includes any number of dots, and excludes any number of dots. (On an actual phone, the path must be at least 4 dots long. For this challenge, ignore that restriction.) Apple plans to replace the 3 x 3 grid with an M x N grid, which is (M*N)/9 times better!

Rules:

  • A zero dot path is not a password, but a 1 dot path is
  • A path can cross itself
  • A path cannot cross directly over a dot without including that dot
  • A dot can only be used once
  • Paths that are identical by rotation are not the same password
  • Paths that are identical but ordered in reverse are not the same password
  • For example, on a 3x3 grid with dots numbered from 1 to 9:

    1 2 3
    4 5 6
    7 8 9
    

    Some valid paths are:

    1
    3
    7,2,3
    1,5,9,2
    1,8,6,5,4
    4,2,3,5,6,7,8,9
    5,9,6,4
    

    And some invalid paths are:

    1,3
    1,9,5
    7,5,4,7
    4,6
    

    Your input will be three numbers:

    (M,N,d)
    

    Where the grid is M x N, and d is the length of the path

    1 <= M <= 16
    1 <= N <= 16
    1 <= d <= M * N
    

    Your program or function will be given the input as a comma separated string, and it must return the number of possible passwords of that length. For example:

    Input:  2,2,1 
    Output: 4
    Input:  2,2,2
    Output: 12
    Input:  7,4,1
    Output: 28
    

    Standard code golf rules apply, shortest code wins!

    //If I've made a mistake or the rules are unclear, please correct me!
    
    \$\endgroup\$
    12
    • 2
      \$\begingroup\$ Is the input a comma-separated string or three separate parameters? \$\endgroup\$
      – user80551
      Mar 31, 2014 at 18:57
    • 1
      \$\begingroup\$ @user80551 Based on the context, I think it will be a string if it is input to a program, or separate parameters if it is used to call the function. \$\endgroup\$
      – user12205
      Mar 31, 2014 at 19:53
    • 1
      \$\begingroup\$ @Platatat can you please answer user80551's question, as this is really important to design the code \$\endgroup\$
      – RononDex
      Mar 31, 2014 at 20:02
    • 3
      \$\begingroup\$ You should decide if there's going to be a time limit for both the compile and execution time of a given solution. Without such a limit, it's easy to write a program that, in theory, verifies which of all 256! permutations of the dots on the 16 x 16 grid represent a valid unlock pattern. In practice, such a program would never terminate. \$\endgroup\$
      – Dennis
      Mar 31, 2014 at 22:57
    • 3
      \$\begingroup\$ But I said the problem was based on the android lock system... So why shouldn't I use the same rules as the android lock system? \$\endgroup\$
      – Platatat
      Apr 3, 2014 at 5:21

    1 Answer 1

    14
    \$\begingroup\$

    Python - 170 bytes

    from fractions import*
    p=lambda m,n,d,l=0,s=set():d<1or sum([p(m,n,d-1,i,s|{i})for i in range(m*n)if not(s and(s&{i}or set(range(l,i,abs(i-l)/gcd(i%n-l%n,i/n-l/n)))-s))])
    

    I realize that the brackets inside sum([...]) are not strictly necessary, but there's a large performance penalty for not including them.

    Output for all 3x3s:

    for i in range(4, 10):
      print p(3, 3, i)
    

    Produces:

    1624
    7152
    26016
    72912
    140704
    140704
    

    For testing/confirmation purposes, the first 6 values for a 4x5 board:

    20
    262
    3280
    39644
    459764
    5101232
    

    4x5 is an interesting case to verify, because it has 2x2, 3x3, and 2x4 peg jumps.


    Brief Explanation

    In general, this is an exhaustive search, with cumulative pruning. For example, because p(3, 3, 4) is 1624, p(3, 3, 5) will only check 8120 posibilities, rather than naïvely checking all 15120. Most of the logic is contained in the condition:

    if not(s and(s&{i}or set(range(l,i,abs(i-l)/gcd(i%n-l%n,i/n-l/n)))-s))
    

    In plain english, this can be understood as:

    If no pegs have been used yet
         OR
       the target peg has not yet been used
         AND
       each of the pegs directly between the target peg and the
       current peg (a.k.a. "jumped over") have already been used
    
    \$\endgroup\$
    4
    • 2
      \$\begingroup\$ Could you explain what in the world is going on here? \$\endgroup\$ Apr 1, 2014 at 5:22
    • 1
      \$\begingroup\$ You can save a few bytes by having s be a set instead of a list. I'm not seeing the large performance penalty of dropping the brackets; why would there be such a penalty? \$\endgroup\$ Apr 1, 2014 at 7:15
    • 1
      \$\begingroup\$ @user2357112 one is summing over a Generator, the other over a List. With CPython, you're right, there isn't much difference (only about 20% slower). With PyPy, it's over 5 times as slow. \$\endgroup\$
      – primo
      Apr 1, 2014 at 7:38
    • 1
      \$\begingroup\$ @user2357112 I finally see what you meant by defining s as a set. My python lesson for today: {i} evaluates as set([i]). I would have expected a syntax error. Appending an item to a set then becomes s|{i}, and it also allows i in s to be replaced by s&{i}. \$\endgroup\$
      – primo
      Apr 9, 2014 at 4:28

    Your Answer

    By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

    Not the answer you're looking for? Browse other questions tagged or ask your own question.