26
\$\begingroup\$

Part of Advent of Code Golf 2021 event. See the linked meta post for details.

Related to AoC2015 Day 20, Part 1.

Here's why I'm posting instead of Bubbler and why not emanresuA


To keep the Elves busy, Santa has them deliver some presents by hand, door-to-door. He sends them down a street with infinite houses numbered sequentially: 1, 2, 3, 4, 5, and so on.

Each Elf is assigned a number, too, and delivers presents to houses based on that number. Instead of giving out presents at fixed intervals, Santa decides to give them out in longer and longer intervals because apparently he's short of supplies right now. Ignore the fact that the total number of presents delivered is the same after all :P

  • The first Elf (number 1) delivers presents to the houses numbered 1, 1+2, 1+2+3, 1+2+3+4, 1+2+3+4+5, ... (1, 3, 6, 10, 15, ...)
  • The second Elf (number 2) delivers presents to the houses numbered 2, 2+3, 2+3+4, 2+3+4+5, 2+3+4+5+6, ... (2, 5, 9, 14, 20, ...)
  • Elf number 3 delivers presents to houses 3, 3+4, 3+4+5, ... (3, 7, 12, 18, 25, ...)
  • ...

There are infinitely many Elves, numbered starting with 1. Each Elf delivers exactly 1 present at each house.

So, the first nine houses on the street end up like this:

  • House 1 gets 1 present (by Elf 1).
  • House 2 gets 1 present (by Elf 2).
  • House 3 gets 2 presents (by Elves 1 and 3).
  • House 4 gets 1 present (by Elf 4).
  • House 5 gets 2 presents (by Elves 2 and 5).
  • House 6 gets 2 presents (by Elves 1 and 6).
  • House 7 gets 2 presents (by Elves 3 and 7).
  • House 8 gets 1 present (by Elf 8).
  • House 9 gets 3 presents (by Elves 2 (2+3+4), 4 (4+5), and 9).

So the lowest-numbered house that gets at least 3 presents is House 9.

Given a positive number n, what is the lowest house number that will get at least n presents?

Standard rules apply. The shortest code in bytes wins.

Test cases

n -> answer
1 -> 1
2 -> 3
3 -> 9
4 -> 15
5 -> 45
6 -> 45
7 -> 105
8 -> 105
9 -> 225
10 -> 315
12 -> 315
17 -> 1575
25 -> 10395
\$\endgroup\$
1
  • 13
    \$\begingroup\$ +1 for posting at 00:00:00Z ^^ \$\endgroup\$
    – Arnauld
    Dec 4, 2021 at 0:38

17 Answers 17

18
\$\begingroup\$

Pari/GP, 32 bytes

n->i=1;while(numdiv(i)<n,i+=2);i

Try it online!

House \$i\$ gets a present from elf \$j\$ \$\iff\$ \$i=\frac{k(j+k-1)}{2}\$ for some \$k \ge 0\$ \$\iff\$ \$k=\frac{\sqrt{(2j-1)^2+8i}-2j+1}{2}\$ for some \$k\$ \$\iff\$ \$(2j-1)^2+8i=l^2\$ for some \$l\$ \$\iff\$ \$8i=(l+2j-1)(l-2j+1)\$ for some \$l\$ \$\iff\$ \$m-8i/m=4j-2\$ for some divisor \$m\$ of \$8i\$.

So house \$i\$ gets \$n\$ presents \$\iff\$ \$8i\$ has \$n\$ divisors \$d\$ such that \$d\equiv 2 \pmod{4}\$ \$\iff\$ \$i\$ has \$n\$ odd divisors.

But \$i\$ and \$2i\$ has exactly the same number of odd divisors. So we only need to consider the odd numbers, whose divisors are all odd.

\$\endgroup\$
1
  • 2
    \$\begingroup\$ So this is to A038547 as A061799 is to A005179? \$\endgroup\$
    – Neil
    Dec 4, 2021 at 5:35
10
\$\begingroup\$

JavaScript (ES7), 65 bytes

f=(n,k)=>(g=n=>n&&!((4*n*--n+8*k+1)**.5%1)+g(n))(k)>=n?k:f(n,-~k)

Try it online!

How?

The formula giving the \$x\$-th house visited by Elf number \$n\$ is:

$$H_n(x) = \frac{x(x+2n-1)}{2}$$

We want to know whether Elf number \$n\$ is going to visit some house \$k\$, i.e. if there's some \$x>0\$ such that \$H_n(x)=k\$. It means that we have to check if the following quadratic equation has a positive integer solution:

$$\frac{1}{2}x^2+\left(n-\frac{1}{2}\right)x-k=0$$

The determinant is:

$$\Delta = \left(n-\frac{1}{2}\right)^2+2k=n^2-n+2k+\frac{1}{4}$$

Leading to:

$$4\Delta = 4n^2-4n+8k+1 = 4n(n-1)+8k+1$$ $$2\sqrt{\Delta} = \sqrt{4n(n-1)+8k+1}$$

Leading to a unique positive value of \$x\$:

$$x=\frac{\sqrt{\Delta}+1}{2}-n$$

But the only thing we're interested in is to know whether this \$x\$ is an integer. So we just test whether \$\sqrt{4n(n-1)+8k+1}\$ is an integer (which — if it is — is always odd).

Hence the JavaScript test:

!((4 * n * --n + 8 * k + 1) ** 0.5 % 1)

JavaScript (ES6), 57 bytes

This one is a port of alephalpha's great method.

f=(n,i=1)=>eval("for(d=n,k=i;k;)d-=i%k--<1")>0?f(n,i+2):i

Try it online!

\$\endgroup\$
6
\$\begingroup\$

05AB1E, 9 bytes

Another port of alephalpha's approach.

∞·<.ΔÑg›_

Try it online!

A direct brute force approach is a byte longer:

∞.ΔLŒOy¢›_

Try it online!

∞           -- infinite list of positive integers
 ·<         -- double and decrement each; this yields the odd integers
   .Δ       -- find the first value that satisfies:
     Ñg     --   the number of divisors ...
       ›_   --   ... is not less than the input

∞.Δ         -- find the first positive integer y that satisfies:
   L        --   range from 1 to y
    ŒO      --   the sums of each contiguous sublist
            --   these are all of the form sum(a..b) for 1<=a<b<=y
      y¢    --   count the occurrences of y in the sums
        ›_  --   is this not less than the input?
\$\endgroup\$
6
\$\begingroup\$

R, 42 bytes

Or R>=4.1, 35 bytes by replacing the word function with \.

function(n){while(sum(!T%%1:T)<n)T=T+2;+T}

Try it online!

Another port of @alephalpha's solution.

\$\endgroup\$
5
\$\begingroup\$

Husk, 10 9 8 bytes

Edit: -2 bytes thanks to hint from ovs

ḟȯ≥⁰LḊİ1

Try it online!

An alternative Husk approach to rues' answer, here porting alephalpha's method.

\$\endgroup\$
2
  • 1
    \$\begingroup\$ You can save at least 2 bytes by only looking at odd numbers (İ1) like alephalpha's answer \$\endgroup\$
    – ovs
    Dec 4, 2021 at 15:53
  • \$\begingroup\$ @ovs - Aha. I did try that , but only found a solution with the same bytes, so now I'll go back and look for your 2-byte saving... Edit: got it, thanks! \$\endgroup\$ Dec 4, 2021 at 16:17
5
\$\begingroup\$

05AB1E, 25 bytes

[N.µxtExNNn-+N·%>½}¾¹@i,q

Try it here!

Decomposition:

func(n) - Number of presents for a given house 'n'
xt                          # s_max = sqrt(2n)
  E           }             # for s in 1..s_max
   xNNn-+N·                 # n, 2n+s-s^2, 2s
           %>               # if 2n-s^2+s % 2s = 0
             ½              # increment present counter
               ¾            # return present counter

main
[                           # loop n=0..infinity
 N                          # push house number to stack
  .µ                        # reset present counter to zero
    xtExNNn-+N·%>½}¾        # func(n)
                    ¹@      # if func(n) >= p:
                      i,q   # print N, quit

Explanation:

I wanted to find a mathematical approach rather than a computational one, and I'm decently pleased with what I found. Found through very unscientific means, but works for all numbers I've tested.

Making a scatter plot between elf number \$r\$ and house number \$h\$ reveals some nice patterns. Distinct straight lines are formed, which I have named 'series'. Where these series have integer pairs \$(r,h)\$, a house receives one present. An equation was formed to define these series by number: $$ n = sr + \frac{s^2-s}{2} $$ Solving for \$r\$ gives: $$ r = \frac{2n-s^2+s}{2s} $$ Integer solutions for \$r\$ mean that elf \$r\$ visited house \$n\$ on series \$s\$. $$ (2n-s^2+s) \equiv 0 \pmod {2s} $$ means a present was left. All that remains is to iterate over all series for a house to count a number of presents. A maximum series number is defined: $$ s_{max}= \lfloor \sqrt{2n} \rfloor $$ derived approximately from the h-intercept of each series being $$ r = \frac{s(s+1)}{2} $$ This ensures that \$r \geq 1\$. Iterate over series \$1\$ though \$\sqrt{2n}\$ for each house to determine number of presents. Iterate over houses with this function until finding one with sufficient presents!

\$\endgroup\$
1
  • \$\begingroup\$ Welcome to Code Golf, and nice answer! \$\endgroup\$ Dec 4, 2021 at 19:11
4
\$\begingroup\$

Charcoal, 45 bytes

Nθ≔⁰ηW‹№υηθ«≦⊕η≔⟦⟧υFη«≔⁰ζW‹ζη«≦⊕κ≧⁺κζ»⊞υζ»»Iη

Try it online! Link is to verbose version of code. Explanation: Brute force because I'm too tired to work out a formula.

Nθ

Input n.

≔⁰η

Start at house 0.

W‹№υηθ«

Repeat until n visits have been found.

≦⊕η

Try the next house.

≔⟦⟧υ

Start building up the list of houses visited by the elves.

Fη«

Loop over enough elves so that the last elf visits the house. (Note that these elves are 0-indexed.)

≔⁰ζ

Start at house 0.

W‹ζη«

Repeat until the current house has been reached or passed.

≦⊕κ

Increase the gap between houses.

≧⁺κζ

Visit the next house.

»⊞υζ

Save the house the elf ended up visiting.

»»Iη

Output the found house.

Porting @alephalpha's method takes 22 bytes:

Nθ≔¹ηW‹LΦη¬﹪η⊕κθ≧⁺²ηIη

Try it online! Link is to verbose version of code. Explanation:

Nθ

Input n.

≔¹η

Start at house 1.

W‹LΦη¬﹪η⊕κθ

While the current house has fewer than n divisors (which must all be odd)...

≧⁺²η

... visit the next house but one.

Iη

Output the found house.

\$\endgroup\$
4
\$\begingroup\$

Rust, 65 64 bytes

|n|{let mut i=1;while(1..=i).filter(|j|i%j<1).count()<n{i+=2};i}

Try it online!

  • -1 byte by using <1 instead of ==0 (thanks @Kevin Cruijssen)
\$\endgroup\$
1
  • 1
    \$\begingroup\$ ==0 can be <1. \$\endgroup\$ Dec 5, 2021 at 18:04
3
\$\begingroup\$

Python 3, 62 bytes

f=lambda n,v=1:v*(sum(v%-~u<1for u in range(v))>=n)or f(n,v+2)

Try it online!


Python 3, 76 bytes

lambda n:next(v for v in range(3**n)if sum(v%u<1for u in range(1,v+1,2))>=n)

Try it online!

\$\endgroup\$
1
  • \$\begingroup\$ If you're OK with outputting True for 1, you can save 2 bytes with f=lambda n,v=1:n<=sum(v%-~u<1for u in range(v))or 2+f(n,v+2) (TIO). \$\endgroup\$
    – xnor
    Dec 5, 2021 at 10:58
3
\$\begingroup\$

Wolfram Language (Mathematica), 52 32 bytes

1//.i_/;0~DivisorSigma~i<#:>i+2&

Try it online!

-20 bytes thanks to att! Also thanks to ovs.

Based off alephaleph's excellent insight, and probably not a great Wolfram golf but I couldn't resist those builtins. I'll look forward to att setting me straight.

\$\endgroup\$
4
  • 2
    \$\begingroup\$ 37 bytes by porting alephalpha more literally and Tr[1^...] instead of Length \$\endgroup\$
    – ovs
    Dec 4, 2021 at 7:26
  • 2
    \$\begingroup\$ From there 32 bytes with //. instead of For (Tr[1^Divisors@i], 0~DivisorSigma~i, and DivisorSum[i,1&] are all the same length) \$\endgroup\$
    – att
    Dec 4, 2021 at 7:36
  • \$\begingroup\$ @att What is //., I can find that documented. I understand ovs's version but a few things in yours lose me... \$\endgroup\$
    – Jonah
    Dec 5, 2021 at 22:40
  • 1
    \$\begingroup\$ //. is ReplaceRepeated. It performs replacements until the result stops changing. \$\endgroup\$
    – att
    Dec 6, 2021 at 0:47
3
\$\begingroup\$

Husk, 14 12 bytes

Fixed a bug and saved 3 bytes thanks to Dominic Van Essen!

ḟo≥⁰S#ȯṁ∫ṫḣN

Try it online!

\$\endgroup\$
5
  • \$\begingroup\$ I think you're missing an m, like this (the needs to be mapped across each tail)... \$\endgroup\$ Dec 4, 2021 at 22:14
  • \$\begingroup\$ ...but anyway you can get rid of one of the two superscripts in the lambda by changing the other one to ¹, like this. \$\endgroup\$ Dec 4, 2021 at 22:16
  • \$\begingroup\$ @DominicvanEssen Thanks, I didn't notice that! \$\endgroup\$
    – user
    Dec 4, 2021 at 22:25
  • \$\begingroup\$ ...You can also save 1 byte using # as count instead of countf, and then save another using S instead of creating a lambda... \$\endgroup\$ Dec 4, 2021 at 22:27
  • \$\begingroup\$ @DominicvanEssen Thanks again! The S one takes a while to infer, interesting... \$\endgroup\$
    – user
    Dec 4, 2021 at 22:30
3
\$\begingroup\$

Ruby, 66 bytes

->n,*r{w=[];1.step.find{|x|w+=r=[0,*r].map{|y|y+x};w.count(x)>=n}}

Try it online!

\$\endgroup\$
2
\$\begingroup\$

Japt, 11 bytes

@>Xâ Ê*Xu}f

Try it

Port of @alephalpha answer.

\$\endgroup\$
2
\$\begingroup\$

TI-Basic, 32 bytes

Input N
1
While N>sum(seq(not(IfPart(Ans/I)),I,1,Ans
Ans+2
End
Ans

Port of alephalpha's solution. Output is stored in Ans and displayed.

\$\endgroup\$
1
\$\begingroup\$

Python3, 162 bytes:

r=range
q=lambda h,n,l:any(i==h for i in l if i and l.count(i)>=n)
f=lambda n,h=1:h if(v:=q(h,n,[sum(r(x,y+1))for x in r(1, h+1)for y in r(1, h+1)]))else f(n,h+1)

A basic brute-force approach.

Try it online.

\$\endgroup\$
1
\$\begingroup\$

Java, 73 bytes

n->{int r=1,c=1,j;for(;c<n;)for(r+=2,c=j=1;j<r;)if(r%j++<1)c++;return r;}

Port of @alephalpha's Pari/GP answer.

Try it online.

Explanation:

n->{              // Method with integer as both parameter and return-type
  int r=1,        //  Result-integer `r`, starting at 1
      c=1,        //  Count-integer, starting at 1
      j;          //  Temp integer, uninitialized
  for(;c<n;)      //  Loop as long as the count is smaller than the input:
    for(r+=2,     //   Increase `r` by 2
        c=j=1;    //   Reset the count to 1,
        j<r;)     //   Loop `j` in the range [1,r):
      if(r%j++<1) //    If `r` is divisible by `j`:
                  //    (and increase `j` by 1 afterwards with `j++`)
        c++;      //     Increase the count by 1
  return r;}      // After the nested loops: return the result
\$\endgroup\$
1
\$\begingroup\$

TypeScript Types, 302 bytes

//@ts-ignore
type a<N,M=[]>=N extends M["length"]?M:a<N,[...M,0]>;type b<N,E,C,M=[]>=M extends N?[...C,0]:M extends[...N,...0[]]?C:b<N,[...E,0],C,[...M,...E]>;type c<N,M=[0],C=[0]>=N extends M?C:c<N,[...M,0],b<N,M,C>>;type d<N,M=[0]>=c<M>extends[...N,...0[]]?M["length"]:d<N,[...M,0]>;type M<X>=d<a<X>>

Try It Online!

Ungolfed / Explanation

type NumToTuple<N,M=[]> = N extends M["length"] ? M : NumToTuple<N,[...M,0]>
type CheckElf<HouseNum, NumToAdd, PresentCount, Sum=[]> = 
  Sum extends HouseNum
    // If Sum == HouseNum, return ElfCount + 1
    ? [...PresentCount, 0]
    : Sum extends [...HouseNum, ...0[]]
      // Otherwise, if Sum >= HouseNum, return ElfCount
      ? PresentCount
      // Othwerise, add NumToAdd to Sum, increase NumToAdd, and recurse
      : CheckElf<HouseNum, [...NumToAdd, 0], PresentCount, [...Sum, ...NumToAdd]>
type CountPresents<HouseNum, ElfNum=[0], PresentCount=[0]> =
  HouseNum extends ElfNum
    // If HouseNum == ElfNum, return PresentCount
    ? PresentCount
    // Otherwise, check this elf, add one to ElfNum, and recurse
    : CountPresents<HouseNum, [...ElfNum,0], CheckElf<HouseNum, ElfNum, PresentCount>>
type FindHouse<PresentMin, HouseNum=[0]> =
  CountPresents<HouseNum> extends [...PresentMin,...0[]]
    // If the number of presents at this house is >= the minumum, return this house number
    ? HouseNum["length"]
    // Otherwise, check the next house number
    : FindHouse<PresentMin,[...HouseNum,0]>
type Main<X> = FindHouse<NumToTuple<X>>
\$\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.