2015년 8월 25일 화요일

digital sum

https://codefights.com/challenge/hmnrz6mxXZWNRAkZu

35char가 말이 되나?
답이 나오면 꼭 봐야지.

int Digital_sum(int a) {
  return a%9 ?: 9;  
}

9거법.
내가 한심하다.
작성자: 시간: 댓글 없음:
라벨:

last digit

아 오늘 할것 있었는데 한문제에 또 낚여가지고.. ㅜㅜ

아래 식을 구하는 프로그램이다.
https://codefights.com/challenge/BNLZseQgvXBRPPBFr

$$ \sum _1 ^n n^n \mod 10 $$

일단 내 나름의 답은 아래와 같다.
int s,g,j,t,i,last(std::string N) {
  t = N.size();
  for(;++j<=atoi(N.substr(t>2?t-2:0).c_str());s+=g)
    for(g=1,i=j;i--;)
      g = g*j%10;
  return s%10;
}


나중에 1, 2등의 답안을 보니 atoi대신 stoi를 썼으면 몇자 더 줄일 수 있었다.
1등답안은 또 같은 사람인데, 이번엔 2등답안이 더 훌륭하다. 2등이 조금만 더 신경썼어도 여유롭게 1등할 수 있었을텐데 쓸모없는 변수조차 지우지 않는 여유를 부렸다.
1등답안은 좀 찬찬히 살펴봐야겠다 아직 이해가 안감.
int n, i, r, last(std::string N) {
  N="0"+N;
  for(r=N[n=N.size()-2]*7-6; i<4; )
r+="                                         "[N[n]%2*40+4*N[n+1]-192+i]%2<<i++;
  return r%10;


}
(with l in vim. all spaces are replaced to underscore.
int_n,_i,_r,_last(std::string_N)_{$
__N="0"+N;$
__for(r=N[n=N.size()-2]*7-6;_i<4;_)$
r+="____^I___^I_^I__^I_____^I^I^I__^I__^I_^I_____^I^I^I^I_____^I___^I^I^I______^I^I_^I___^I^I^I___^I____^I^I^I^I_"[N[n]%2*40+4*N[n+1]-192+i]%2<<i++;$
__return_r%10;$
}$
)
공백은 캐릭터 숫자로 포함되지 않아서 그것을 이용한 뭔가 굉장히 tricky한 방법 같은데 도무지 알수가 없다. abusing에 가깝지 않은가 싶기도 하고. 

성의없는 2등답안은 다음과 같은데,
int n, l, h, m, last(std::string N)
{
  n = N.size();
  l = std::stoi( N.substr( --n ? --n : 0));
  for(m = 0; l; l--)
    m += pow(l, l % 4 ? l % 4 : 4);
    
  return m % 10;
}
약간만 손보면 다음과 같이 된다.
int n, l, m, last(std::string N)
{
  n = N.size();
  l = stoi( N.substr( --n ? --n : 0));
  for(;l; l--)
    m += pow(l, l%4 ? : 4);

  return m%10;
}

문제를 처음 봤을 때 2등답안같은 답이 가능할것 같아서 좀 찾아봤는데 워낙 수학실력이 형편없다보니 저런 단순한 식에는 접근조차 못했다.
In[233]:= i = Range[100]; 

In[234]:= r1234 = PadRight[Range[4], Length@i, Range[4]]

Out[234]= {1, 2, 3, 4, 1, 2, 3, 4, 1, 2, 3, 4, 1, 2, 3, 4, 1, 2, 3, \
4, 1, 2, 3, 4, 1, 2, 3, 4, 1, 2, 3, 4, 1, 2, 3, 4, 1, 2, 3, 4, 1, 2, \
3, 4, 1, 2, 3, 4, 1, 2, 3, 4, 1, 2, 3, 4, 1, 2, 3, 4, 1, 2, 3, 4, 1, \
2, 3, 4, 1, 2, 3, 4, 1, 2, 3, 4, 1, 2, 3, 4, 1, 2, 3, 4, 1, 2, 3, 4, \
1, 2, 3, 4, 1, 2, 3, 4, 1, 2, 3, 4}

In[239]:= Mod[i^i , 10] == Mod[i^r1234, 10]

Out[239]= True

아름답다.


작성자: 시간: 댓글 없음:
라벨:

2015년 8월 24일 월요일

overlap point

이번에도 역시 codefight
https://codefights.com/challenge/7BLpypv6zjpr25iPY/solutions

1등은 이번에도 역시 같은 사람
코드는
#define f(x) hypot(i/9-4-x 0], i%9-4-x 1])<=x 2]
int i, r;
template <class T>
int overlapPoint(T a, T b) {
  for(;i++<99;)
      r+=f(a[) & f(b[);
  return r;
}

볼때마다 배울 것이 생기니까 아직까지는 지루하지 않다. 볼 시간이 많지 않은것이 흠이라면 흠.

핵심은 두가지다. 하나는 hypot함수, 하나는 평면의 격자를 루프 한번에 해결하는 것.
hypot함수 외에도 math.h에 희한한 함수들이 더 있는 것 같은데 처음 봤다. 짬날때 봐야 할 것 같다(하지만 보지 않겠지 -_-)

평면의 모든 격자는 예를 들어 다음과 같이 하면 쉽다
for(; x--; )
  for(; y--; )
    // do sth. (x,y) coord.

위에서는 변수를 하나만 만들고 정수 나눗셈과 modular를 이용해서 모든 격자점을 구해낸다. 참 놀라운 아이디어다.
99까지밖에 루프를 돌지 않는데 이건 테스트케이스가 작아서 운이 좋았던 것 같다. 그래도 예상할 수 있는 모든 범위에 대해 확장할 수 있으니 큰 문제는 없어보인다.

아래는 mathematica로 격자점을 구해본것. 격자점이 어떻게 모두 구해지는지 조금 더 직관적으로 볼 수 있다.
In[148]:= i = Range[0, 99]

 Out[148]= {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, \
17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, \
34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, \
51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 64, 65, 66, 67, \
68, 69, 70, 71, 72, 73, 74, 75, 76, 77, 78, 79, 80, 81, 82, 83, 84, \
85, 86, 87, 88, 89, 90, 91, 92, 93, 94, 95, 96, 97, 98, 99}

 In[157]:= i / 9 - 4 // Floor

 Out[157]= {-4, -4, -4, -4, -4, -4, -4, -4, -4, -3, -3, -3, -3, -3, \
-3, -3, -3, -3, -2, -2, -2, -2, -2, -2, -2, -2, -2, -1, -1, -1, -1, \
-1, -1, -1, -1, -1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, \
1, 1, 2, 2, 2, 2, 2, 2, 2, 2, 2, 3, 3, 3, 3, 3, 3, 3, 3, 3, 4, 4, 4, \
4, 4, 4, 4, 4, 4, 5, 5, 5, 5, 5, 5, 5, 5, 5, 6, 6, 6, 6, 6, 6, 6, 6, \
6, 7}

 In[158]:= Mod[i, 9] - 4

 Out[158]= {-4, -3, -2, -1, 0, 1, 2, 3, 4, -4, -3, -2, -1, 0, 1, 2, 3, \
4, -4, -3, -2, -1, 0, 1, 2, 3, 4, -4, -3, -2, -1, 0, 1, 2, 3, 4, -4, \
-3, -2, -1, 0, 1, 2, 3, 4, -4, -3, -2, -1, 0, 1, 2, 3, 4, -4, -3, -2, \
-1, 0, 1, 2, 3, 4, -4, -3, -2, -1, 0, 1, 2, 3, 4, -4, -3, -2, -1, 0, \
1, 2, 3, 4, -4, -3, -2, -1, 0, 1, 2, 3, 4, -4, -3, -2, -1, 0, 1, 2, \
3, 4, -4}

 In[160]:= {%157, %158} // Transpose

 Out[160]= {{-4, -4}, {-4, -3}, {-4, -2}, {-4, -1}, {-4, 0}, {-4, 
  1}, {-4, 2}, {-4, 3}, {-4, 
  4}, {-3, -4}, {-3, -3}, {-3, -2}, {-3, -1}, {-3, 0}, {-3, 1}, {-3, 
  2}, {-3, 3}, {-3, 4}, {-2, -4}, {-2, -3}, {-2, -2}, {-2, -1}, {-2, 
  0}, {-2, 1}, {-2, 2}, {-2, 3}, {-2, 
  4}, {-1, -4}, {-1, -3}, {-1, -2}, {-1, -1}, {-1, 0}, {-1, 1}, {-1, 
  2}, {-1, 3}, {-1, 4}, {0, -4}, {0, -3}, {0, -2}, {0, -1}, {0, 
  0}, {0, 1}, {0, 2}, {0, 3}, {0, 
  4}, {1, -4}, {1, -3}, {1, -2}, {1, -1}, {1, 0}, {1, 1}, {1, 2}, {1, 
  3}, {1, 4}, {2, -4}, {2, -3}, {2, -2}, {2, -1}, {2, 0}, {2, 1}, {2, 
  2}, {2, 3}, {2, 4}, {3, -4}, {3, -3}, {3, -2}, {3, -1}, {3, 0}, {3, 
  1}, {3, 2}, {3, 3}, {3, 4}, {4, -4}, {4, -3}, {4, -2}, {4, -1}, {4, 
  0}, {4, 1}, {4, 2}, {4, 3}, {4, 
  4}, {5, -4}, {5, -3}, {5, -2}, {5, -1}, {5, 0}, {5, 1}, {5, 2}, {5, 
  3}, {5, 4}, {6, -4}, {6, -3}, {6, -2}, {6, -1}, {6, 0}, {6, 1}, {6, 
  2}, {6, 3}, {6, 4}, {7, -4}}
작성자: 시간: 댓글 없음:
라벨:

2015년 8월 21일 금요일

(;;)

means ever

 see this phrase.


for(;;)
작성자: 시간: 댓글 없음:

2015년 8월 17일 월요일

line land fuel



입력으로 벡터와 그 벡터 내의 인덱스를 주면, 해당 인덱스와 다른 모든 원소들간의 거리를 구해서 그 min값과 max값을 보여주는 프로그램.
예를들어,

std::vector<int> b({-5,-2,2,7});
a = LineLandFuel(0, b);

이렇게 주면 b의 0번째 원소인 -5와 나머지 원소들간의 차 중에 가장 큰것(12)과 작은것(3)을 반환하면 된다. 입력은 항상 정렬되어 있다.

아래는 1위 작품. 이번에도 역시 매일 우승하던 오렌지프로필을 가진 그친구다.

int x, y=1e9;
template <class T>
T shortest(int i, T a) {
for(int v: a) v=abs(a[i]-v), x>v?:x=v, y<v|!v?:y=v;
return { x, y };
}


(1) 난 INT_MAX를 썼는데 1e9를 썼다. 이건 약간 lucky하게 test case를 통과한것 아닌가 싶다.
(2) 템플릿함수는 리턴타입이나 인자만으로 추정해서 부를 수 있나보다. 위의 함수는 다음과 같이 그냥 부를수 있다.

std::vector<int> a, b({-5,-2,2,7});
 a = shortest(0,b);

 또 하나 배웠다. 함수 선언까지 코드 길이에 포함되므로 리턴타입과 받는 인자가 std::vector<int> 같은 긴 이름일때 매우 유용할듯 하다. 실제 업무에 쓸일은 있을까 싶지만.
(3) 작성하면서 min값을 판별할 때 자기 자신과의 차(0)는 어떻게 제외할까 고민했었는데 저렇게 간단히(y<v|!v?:y=v)해결되는 것이었다. 이것과 관련해 의문이 생겨서 stackoverflow에 질문을 했다가 몇개 또 배웠다.
(3-1) ternary operator에서 true-expression을 생략하는 것은 warning이지만, false-expression을 생략하면 error다. 이건 gcc extension이다. a?:y 는 a?a:y와 같다. 이 둘의 차이는 a가 한번 evaluation되느냐 두번 evaluation되느냐 이다.
(3-2) a|!b와 !a&b는 다를 수 있다. bool로 conversion이 되다 안되다 할 수 있다. 위 질문링크에 y=3, v=2일 때, y>v|!v 와 y<v&v가 값이 같다는 답글이 있다.
(4) comma로 expression을 계속 잇는 것과 ternary operator에 익숙하면 타이핑을 많이 절약할 수 있을 것 같다.
(5) v도 한번 재활용 되었다.

작성자: 시간: 댓글 없음:
라벨:

find primes

https://codefights.com/challenge/ZbGabd7jjYHRqePHy

std::vector< int > r, PrimeNumbers(int a, int b) {
  for(int i; i=a<=b; i==a++?r.push_back(i),0:0)
    for(; ++i<a&&a%i; );
  return r;
}

정말 타고 나긴 타고 나나 보다.
약간 보기 좋게 바꾸면,

std::vector<int> PrimeNumbers(int a, int b) {
  for(int i; i=a<=b;)
    {
      for(; ++i<a&&a%i; )
{
          //skip non-prime numbers                                                                                                              
}
      if(i==a++) {
r.push_back(i);
      }
    }
  return r;

}

r 선언은 내 gcc로는 에러나는데 codefight에서는 되는것 같다. 여튼간에,
받은 변수(a)를 잘 이용해서 새로운 변수를 선언하지 않는 것이나,  전위, 후위 연산자를 적절하게 이용하는 것, for문을 잘 이용하는 것등은 익숙한데,  i==a++?r.push_back(i),0:0 이거 하나 더 배웠다. expression을 만들기 위해 0을 넣다니.

i는 종료조건에 다다르기 전까지 무조건 1에서부터 시작하고(그렇지 않다면 0으로 for가 종료된다) for문 처음에 ++i가 있어서 1을 제외하는 문제는 자연스럽게 해결된다. (1은 소수가 아니니까 제외해야 한다). 목표점(a)에 다다를때까지 어떤 숫자로도 나눠지지 않으면 소수이고, 마지막에 a++때문에 b에 도달할때까지 차례로 모든 수를 검사하게 된다.






작성자: 시간: 댓글 없음:
라벨:

2015년 8월 6일 목요일

sum of 3’s or 5’s multiples

숫자 입력 N보다 작거나 같은 수 중에 3의 배수이거나 5의 배수인 수를 모두 합하는 프로그램.
codefights.com에서 본 것인데 shortest code가 정말 예술이다.

int s,Sum_Of_Multiples_3_Or_5(int N) {
for(;N--;)
      N%3 * N%5 ?:s+=N;
   return s;
}

아름답다.
작성자: 시간: 댓글 없음:
라벨:
피드 구독하기: 글 (Atom)