8
\$\begingroup\$

I need to call my friends but the buttons of my cordless phone are not working properly. The only buttons I can press are [Up], [Down] and [Call]. [Up] and [Down] can be used to navigate in my recent calls and [Call] can be used to call the selected name. My phone has a list that holds N recent calls, and I know that all the friends I need to call are in this list.

Task:

You'll receive a number N and a list of names L:

  • N is the number of recent calls my phone can remember;
  • L has the names in the order I need to call.

You must output the number of button presses I need to make in an optimal arrangement of the recent call list.

Example:

-> Input:

Calling Anna, Bob and then Anna again. With a recent calls list of size 5.

5 Anna Bob Anna

-> Output:

Possible optimal arrangement: Anna, Foo, Bar, Foobar, Bob

5 # Key presses: [Call] Anna, [Up] + [Call] Bob, [Down] + [Call] Anna

More test cases:

Input: 5, Anna, Bob, Carl Output: 5 Input: 5, Anna, Bob, Carl, Anna Output: 8 Input: 5, A, B, C, D, E, A Output: 11 Input: 6, A, B, C, D, E, A Output: 12 Input: 4, A, B, C, B, A Output: 10

Rules:

  • Your cursor will always start in the first position of the list;
  • You can take the input N and L from any source: keyboard, parameters, file, etc;
  • The names in the list can be in any reasonable format such as: strings, integers, chars;
  • When you reach the end of the recent calls list and presses [Down] again, your cursor wraps around. The same happens when you're at the begining of the recent calls list and presses [Up];
  • When you call someone, that person's name will be moved to the first position of the recent calls list and the rest will be pushed down;
  • When you call someone, your cursor will be moved to the first position;
  • A friend name cannot appear more than once in the recent calls list;
  • You can fill your recent calls list with dummy entries (see example);
  • The number of friends to call will not be greater than N.
Improve this question
\$\endgroup\$
0

3 Answers 3

Reset to default
3
\$\begingroup\$

Python 3, 195 185 164 bytes

-4 bytes thanks to @notjagan
-27 bytes thanks to @FelipeNardiBatista

lambda n,l:min(g([*x],l,n)for x in permutations(range(n))) def g(x,l,n,r=0): for p in l:a=x.index(p);x=[x.pop(a)]+x;r-=~min(a,n-a) return r from itertools import*

Try it online!

L is taken as a list of integers from [0, N)

Improve this answer
\$\endgroup\$
4
  • \$\begingroup\$ -4 bytes. \$\endgroup\$ Commented Jul 19, 2017 at 15:04
  • \$\begingroup\$ @notjagan This is not working as x=[x[a]]+x[:a]+x[a+1:] assigns x to a new list object. i would still be the indexmethod on the old list object \$\endgroup\$ Commented Jul 19, 2017 at 15:06
  • \$\begingroup\$ @ovs -10 bytes using Felipe's suggestion and the ones I had other than x.index. \$\endgroup\$ Commented Jul 19, 2017 at 15:19
  • \$\begingroup\$ 164 bytes \$\endgroup\$ Commented Jul 19, 2017 at 16:26
2
+100
\$\begingroup\$

Ruby, 97 95 94 bytes

->n,a{r=a.size;1.upto(r-1){|i|r+=[p=a[(a[0,i].rindex(a[i])||i-2)+1...i].uniq.size,n-p].min};r}

Try it online!

In an optimal arrangement, the first name will take one press (Call). Names that have not been called yet take two presses (Up Call), and names that have take varying numbers depending on how many other unique names have been called since then and whether that places them closer to the top or the bottom of the list.

I think this is a strategy similar or identical to WaffleCohn's.

Improve this answer
\$\endgroup\$
1
\$\begingroup\$

JavaScript (SpiderMonkey), 213 143 bytes

(N,L)=>L.reduce((t,v,i)=>{x=0,a=[v] for(j=i;j-->=0&!~a.indexOf(L[j]);x++)a+=L[j]+"," return i?t+((x=L.indexOf(v)-i?x:1)<N-x?x:N-x):t},L.length)

Try it online!

Generates an optimal arrangement of the given names then counts the number of key presses.

Skipped the generation and just counted how many key presses it would take each name in the optimal arrangement

Improve this answer
\$\endgroup\$

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.