25
3
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:
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!
You said "your program must return...", but in your example you have provided something that resembles a function. It may be better to reword your question so that it is either a program, or a function, or a program or a function. – user12205 – 2014-03-31T18:42:29.430
It that more clear? This is my first question, so I'm not 100% clear on the specifics. – Platatat – 2014-03-31T18:54:47.080
2Is the input a comma-separated string or three separate parameters? – user80551 – 2014-03-31T18:57:28.030
1@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. – user12205 – 2014-03-31T19:53:52.183
1@Platatat can you please answer user80551's question, as this is really important to design the code – RononDex – 2014-03-31T20:02:20.717
Let's say the input is a comma separated string – Platatat – 2014-03-31T21:10:26.270
3You 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. – Dennis – 2014-03-31T22:57:49.187What about the same paths in reverse order ?
d
must be greater or equal. I think you should remove movements like7,2
(not neighbours) and5,6,4
(overlapping), they add difficulty to an already hard challenge. – A.L – 2014-04-01T02:13:55.147can you explain why
5,9,6,4
is considered a valid path? it appears you are crossing over (but not including)5
to get from6
to4
– ardnew – 2014-04-02T02:43:18.410Yes, you are crossing over 5, but since 5 has already been used it isn't considered illegal. "A path cannot cross directly over a dot without including that dot" was as best as I could word this, and basically since this path DOES use 5 before it jumps over it, the path is legal. This is how actual android phones work, too. – Platatat – 2014-04-02T02:54:18.740
Just because it's how it works in Android doesn't mean it's interesting in the context of code golf. There was a typo in my previous comment,
d
must be superior or equal to 2. – A.L – 2014-04-03T02:31:24.4873But 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? – Platatat – 2014-04-03T05:21:46.917