2
\$\begingroup\$

It is widely known that Santa Claus delivers presents to houses all over the world in December. However, not many people know what he does during the rest of the year. You see, Santa enjoys a jolly good prank, and he'll often find himself pranking entire cities when he's not busy making or delivering toys.

One place that he particularly enjoys pranking is the South Pole. You might be saying, "The South Pole isn't a city." You would be right, but Santa doesn't care. There are h houses in the South Pole, which are conveniently numbered from 1 to h. Whenever Santa is in the mood for pranking, he'll start at a particular house, s. He rings the doorbell, then runs to another house.

He always visits houses in order, but just so he doesn't arouse suspicion, he only knocks on every kth house (for example, every 2nd or 3rd house), where k2. This is because the residents (who are penguins) would know that something's up if one or both of their next door neighbors were pranked as well. Once Santa pranks p houses that day (or passes house number h), he goes back home to the North Pole.

After pranking houses for d days, though, Santa feels bad for pranking the penguins so many times. To make things right, he decides that next Christmas he will award the biggest and best gift to the penguin who got pranked the most. If there are multiple houses that got pranked the most, he will award the gift to the penguin in the lowest numbered house.

The Problem: Help Santa by telling him which house should receive the biggest and best gift the following Christmas. Santa, of course, wants to make amends each and every year so he needs your suggestion for each one.

The Input: Two integers, h and d, representing the number of houses and the number of days that Santa pranked the South Pole that year, respectively. Additionally, take in multiple sets of three integers, s, k, and p, denoting the starting house, the number representing his frequency of visiting houses (he skips k-1 houses), and the maximum number of houses he pranks that day. Note that he will visit p houses unless he passes the very last house. You may take these inputs in any reasonable format.

Output g, where g is the house number that should receive the biggest and best gift (the house that got pranked the most, and the lowest house number in the case of a tie). Note that you may not use zero-based indexing, because Santa doesn't know what a computer is.

Test cases:

4 3
1 2 1 
3 4 2 
2 2 2
Output: 1

10 2
2 3 2
3 2 5
Output: 5

50 100
10 10 36
17 7 1
37 2 19
28 2 49
29 3 29
48 3 12
35 3 25
28 4 20
38 8 27
39 3 19
26 4 9
20 7 8
47 10 1
6 10 43
31 3 29
35 2 23
24 9 44
10 3 25
29 10 37
32 5 47
21 5 31
44 5 43
46 4 47
16 10 5
5 3 18
7 8 10
48 5 31
29 4 7
31 8 5
23 9 43
34 8 4
41 10 38
30 6 23
17 7 1
43 5 24
29 2 37
22 10 19
17 6 43
37 3 22
42 10 9
48 4 47
11 6 3
29 7 42
11 9 28
3 4 9
39 9 7
20 9 5
47 5 29
20 4 4
44 10 30
30 6 21
39 10 38
7 9 18
32 10 47
14 9 13
7 2 8
44 3 19
40 4 12
4 10 12
3 5 46
3 5 37
29 9 45
16 4 26
27 9 32
37 10 16
30 5 39
36 2 26
25 2 28
13 3 16
8 8 27
27 6 29
39 10 10
34 7 47
5 4 17
39 2 9
45 2 24
4 6 11
8 10 24
50 7 30
7 4 37
35 10 44
35 9 28
49 10 7
20 5 17
30 4 50
18 7 4
4 7 14
38 9 40
27 3 15
39 5 13
8 2 46
15 4 13
21 9 49
28 6 29
48 5 35
8 8 5
27 3 41
35 10 23
14 4 15
12 2 22
Output: 48

Scoring: Number of bytes. Subtract 20 bytes from your score if your program can handle inputs of up to 100,000 (both days and houses) in less than 5 seconds on a standard desktop PC. Note that in all these inputs k will be less than or equal to 10.

\$\endgroup\$
  • \$\begingroup\$ Yes, you can take input as parameters \$\endgroup\$ – bushdid911 Jul 15 '17 at 1:41
3
\$\begingroup\$

Jelly, 20 bytes

Ḣrm⁸Ḣ¤ḣ⁸
ç€FµĠLÐṀḢḢị

A dyadic link taking a list of lists of numbers, the list of s,k,p values, and a number h (d is just the length of the list so is redundant), returning the house number.

Try it online!

How?

Builds lists of house numbers visited each day, then finds those visited the most and returns the minimal numbered one.

Ḣrm⁸Ḣ¤ḣ⁸ - Link 1, get houses visited on one day: list, [s,k,p]; number, h
Ḣ        - head  = s (modifies the list to become [k,p])
 r       - inclusive range = [s,s+1,s+2,...,h]
     ¤   - nilad followed by link(s) as a nilad:
   ⁸     -   chain's left argument = [k,p]
    Ḣ    -   head = k (modifies the list to become [p])
  m      - modulo slice (take the 1st item then every kth item of the range)
       ⁸ - chain's left argument = [p]
      ḣ  - head to index (vectorises) (take the first p items, or all if less
         -   this will yield a list of length 1 containing the truncated list)

ç€FµĠLÐṀḢḢị - Link: list of lists [[s1,k1,p1],[s2,k2,p2],...]; number, h
ç€          - call the last link as a dyad for €ach
  F         - flatten into a single list (all the houses visited)
   µ        - monadic chain separation, call that v
    Ġ       - group indexes by value (indexes of smallest houses will go first)
      ÐṀ    - filter to keep only those with maximal:
     L      -   length (the groups containing indexes of houses visited most)
        Ḣ   - head (get the first such group)
         Ḣ  - head (get the fist index from the group)
          ị - index into v (get the house number)
\$\endgroup\$
  • 1
    \$\begingroup\$ I edited the problem to make the input format more reasonable as you suggested. \$\endgroup\$ – bushdid911 Jul 15 '17 at 1:54
0
\$\begingroup\$

Python 3, 158 bytes

r=range
def f(h,_,x):
 L=[0]*h
 for s,k,p in x:
  n=0
  for i in r(s,h+1,k):
   if n>p:break
   L[i-1]+=1
   n+=1
 return[i for i in r(h)if L[i]==max(L)][0]+1

Try it online

So this is barely golfed or optimized, but it's a start. I may return to it if I think of better ways to do it. And it doesn't get the bonus. v_v

\$\endgroup\$
  • \$\begingroup\$ Hint: Don't process the days one at a time. Abuse the fact that k <= 10. (for the bonus_ \$\endgroup\$ – bushdid911 Jul 15 '17 at 7:58
  • \$\begingroup\$ You don't need to take input when you don't need it, so you can remove your second input. \$\endgroup\$ – ovs Jul 15 '17 at 10:31
0
\$\begingroup\$

Python 2, 78 bytes

h,a=input();l=[]
for s,k,p in a:l+=range(s,h+1,k)[:p]
print max(l,key=l.count)

Try it online!

Takes input without the numbers of days.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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