Project Euler P.88

• 2x3 , 2+3이 있을 때 product와 sum의 차이는 1이기 때문에 양쪽에 각각 1을 곱하고 더하면 1x2x3 == 1+2+3 이된다. 즉 product와 sum이 같은 3개의 숫자를 구할 수 있다.
• 수를 계속 증가시키면서 factorization한 후 product와 sum의 차이만큼 양쪽에 1을 더하고 곱하면 product와 sum이 같은 set을 구할 수 있다.

#!/usr/bin/env python
#-*- coding:utf-8 -*-
import math
import operator
"""Project Euler Problem 88"""

d = {}
c = set(range(2, 12000+1))

def factorizations(n):
  answer = []
  def sub(n, factor=2, factors=[]):
    for x in range(factor, int(math.sqrt(n))+1):
      if n % x == 0:
        sub(n/x, x, factors + [x])      
    answer.append(factors + [n])
  sub(n)
  return answer

def func(l):
  s = reduce(operator.add, l)
  m = reduce(operator.mul, l)
  length = len(l) + (m-s)
  if length not in d.keys():
    d[length] = m
    c.discard(length)
    print '%6d %6d %s' % (len(c), length, m)

def solve(limit=12000):
  n = 4
  while c:
    map(func, factorizations(n))
    n += 1

  return reduce(operator.add, set( [d[x] for x in range(2, limit+1)] ))
  
if __name__ == '__main__':
  solve()

Project Euler P.159

#!/usr/bin/env python
#-*- coding:utf-8 -*-
import math
import operator
"""Project Euler Problem 159"""

def factorizations(n):
  answer = []
  def sub(n, factor=2, factors=[]):
    for x in range(factor, int(math.sqrt(n))+1):
      if n % x == 0:
        sub(n/x, x, factors + [x])      
    answer.append(factors + [n])
  sub(n)
  return answer

def drs(l):
  def sub(n):
    return n if n < 10 else sub(reduce(operator.add, map(int, str(n))))
  return reduce(operator.add, map(sub, l))

def solve():
  answer = 0
  for i in range(2, 1000000):
    m = max(map(drs, factorizations(i)))
    answer += m

  print 'Answer: ', answer

def test(n):
  l = factorizations(n)
  for x in l:
    print x, drs(x)

if __name__ == '__main__':
  solve()

Project Euler P.259

• 연산의 정확도를 위해서 fractions.Fraction을 사용하면 수행시간이 오래걸림.

#!/usr/bin/env python
# 20101196798

import operator
import sys
from fractions import Fraction

operators = (operator.add, operator.sub, operator.mul, operator.div)
answer = set()

def concat(l):
  c = ''
  for n in l:
    c += str(n)
  return int(c)
    
def func():
  global answer
  for i in range(0, 2 ** 8):
    l = [1]
    digit = 2
    for j in range(0, 8):
      flag = (0 != i & (1 << (7-j)))
      if flag:
        tmp = l.pop()
        l.append(concat( [tmp, digit] ))
      else:
        l.append(digit)
      digit += 1
    print l
    l = map(lambda x: Fraction(x, 1), l)
    if len(l) > 1:
      calculate(l[:2], l[2:])
    else:
      answer.add(int(l[0]))
  print 'Answer: ', reduce(operator.add, answer)

def calculate(s, d):
  global answer
  global maximum
  if len(s) == 1 and len(d) == 0:
    if s[0] > 0 and (s[0].denominator == 1):
      answer.add(s[0])
    return

  if len(s) >= 2:
    a = s[-2]
    b = s[-1]
    for op in operators:
      try:
        c = op(a, b)
        calculate(s[:-2] + [c], d)
      except ZeroDivisionError, ex:
        continue

  if len(d) > 0:
    calculate(s + [d[0]], d[1:])

if __name__ == '__main__':
  func()

Project Euler P.243

$R(d) < \dfrac{\phi(d)}{d}$ 임을 이용해서 $ \dfrac{\phi(d_1)}{d_1} < R(d) < \dfrac{15499}{94744} < \dfrac {\phi(d_2)}{d_2} $ 인 $d_1$을 찾고 $d_1 < d < d_2$ 를 이용해서 $d$를 찾는다.

#!/usr/bin/env python
#-*- coding:utf-8 -*-
import operator

def combinations_with_replacement(iterable, r):
  pool = tuple(iterable)
  n = len(pool)
  if not n and r:
    return
  indices = [0] * r
  yield tuple(pool[i] for i in indices)
  while True:
    for i in reversed(range(r)):
      if indices[i] != n - 1:
        break
    else:
      return
    indices[i:] = [indices[i] + 1] * (r - i)
    yield tuple(pool[i] for i in indices)

def factors(n):
  l = []
  if n % 2 == 0:
    l.append(2)
    while n % 2 == 0:
      n /= 2
  i = 3
  while n > 1:
    if n % i == 0:
      l.append(i)
    while n % i == 0:
      n /= i
    i += 2
  return l

def phi(n):
  f = factors(n)
  p = n
  for factor in f:
    p = p * (factor - 1) / float(factor)
  return p

def gen_primes():
  D = {}
  q = 2

  while True:
    if q not in D:
      yield q
      D[q * q] = [q]
    else:
      for p in D[q]:
        D.setdefault(p + q, []).append(p)
      del D[q]
    q += 1

def r(d):
  d = float(d)
  return (1.0 / (d-1)) * phi(int(d))

def solve(limit = (15499.0 / 94744.0)):
  primes = gen_primes()
  rr = 1.0
  prime = primes.next()
  pl = [ prime ]
  while rr >= limit:
    prime = primes.next()
    pl.append(prime)
    tmp = r( reduce(operator.mul, pl) )
    rr = tmp
  pl.pop()

  additionals = []
  for i in range(1, len(pl)):
    for a in combinations_with_replacement(pl, i):
      m = reduce(operator.mul, a)
      if m not in additionals:
        additionals.append(m)
  additionals.sort()
  for m in additionals:
    d = reduce(operator.mul, pl) * m
    if r(d) < limit:
      print 'Answer: %s' % d
      return

if __name__ == '__main__':
  solve()

DownloadManager

필요한 권한

파일을 다운로드받고 읽기/쓰기 위해서는 다음 권한이 필요한다.

• 인터넷 접속 권한.
  • android:permission.INTERNET
• 저장 매체 읽기 권한.
  • android.permission.READ_EXTERNAL_STORAGE
• 저장 매체 쓰기 권한.
  • android.permission.WRITE_EXTERNAL_STORAGE

DownloadManager

• 안드로이드 시스템 서비스.
  • DownloadManager downdloadManager = (DownloadManager)getSystemService(Context.DOWNLOAD_SERVICE);
• API 9 부터 지원.
• 다운로드 내용이 notification으로 표시된다.
• 각각의 다운로드는 (long) id로 구분된다.
• 다운로드를 요청하기 위해서는 Request를 만들고 DownloadManager에 enqueue()를 호출한다.
• 다운로드의 완료 여부시 알림을 받기 위해서는 Broadcast Receiver를 등록해야 한다.
  • DownloadManager.ACTION_DOWNLOAD_COMPLETE

DownloadManager.Request

• 다운로드할 uri를 생성자의 인자로 설정.
  • DownloadManager.Request(Uri uri)
• 다운로드한 파일을 저장할 위치 지정.
  • Environment.DIRECTORY_DOWNLOADS : default 다운로드 위치
• 표시되 Notification의 title, description등을 설정한다.
• Notification 표시 여부 설정.
  • DownloadManager.Request setNotificationVisibility (int visibility)
• Notification 없이 다운로드 하기 위해서는 permission을 추가해야한다.
  • android.permission.DOWNLOAD_WITHOUT_NOTIFICATION

DownloadManager.Query

• DownloadManager에 요청한 request에 대한 filter를 추가할 때 사용한다.
• ID나 다운로드 상태를 통해 filter가 가능하다.
  • DownloadManager.Query setFilterById (long… ids)
  • DownloadManager.Query setFilterByStatus (int flags)

Example

package com.example.imagedownloader;

import java.io.FileNotFoundException;
import java.util.List;

import android.net.Uri;
import android.os.Bundle;
import android.os.Environment;
import android.os.ParcelFileDescriptor;
import android.app.Activity;
import android.app.DownloadManager;
import android.content.BroadcastReceiver;
import android.content.Context;
import android.content.Intent;
import android.content.IntentFilter;
import android.database.Cursor;
import android.util.Log;
import android.view.Menu;
import android.view.View;
import android.view.View.OnClickListener;
import android.widget.Button;
import android.widget.EditText;
import android.widget.ImageView;
import android.widget.Toast;

public class MainActivity extends Activity implements View.OnClickListener{
  private Button downloadButton;
  private EditText downloadUrl;
  private ImageView imgView;

  private long lastedId = -1;

  private DownloadManager downloadManager;
  private DownloadManager.Request downloadRequest;
  private Uri urlToDownload;

  private BroadcastReceiver completeReceiver = new BroadcastReceiver() {
    @Override
    public void onReceive(Context context, Intent intent) {
      DownloadManager.Query query = new DownloadManager.Query();
      query.setFilterById(lastedId);
      long id = intent.getLongExtra(DownloadManager.EXTRA_DOWNLOAD_ID, -1L);

      if (id != lastedId) {
        Toast.makeText(context, "ID not match: " + id + " " + lastedId, Toast.LENGTH_LONG);
        return;
      }

      Cursor cursor = downloadManager.query(query);
      cursor.moveToFirst();

      int columnIndex = cursor.getColumnIndex(DownloadManager.COLUMN_STATUS);
      int status = cursor.getInt(columnIndex);
      int columnReason = cursor.getColumnIndex(DownloadManager.COLUMN_REASON);
      int reason = cursor.getInt(columnReason);

      Log.e("DOWNLOAD", "download receive:");
      Log.e("DOWNLOAD", "status: " + status);
      Log.e("DOWNLOAD", "reason: " + reason);

      if (status == DownloadManager.STATUS_SUCCESSFUL && reason == 0) {
        Uri uri = downloadManager.getUriForDownloadedFile(lastedId);
        Toast.makeText(context, "Download completed.\n" + uri.toString(), Toast.LENGTH_LONG).show();
        imgView.setImageURI(uri);
      }
      else {
        Toast.makeText(context, "Download Failed[id: " + lastedId + "], Reason: " + reason, Toast.LENGTH_LONG).show();
      }
    }
  };

    @Override
    protected void onCreate(Bundle savedInstanceState) {
        super.onCreate(savedInstanceState);
        setContentView(R.layout.activity_main);

        downloadUrl = (EditText) findViewById(R.id.downloadURL);
        downloadButton = (Button) findViewById(R.id.downloadButton);
        downloadManager = (DownloadManager) getSystemService(Context.DOWNLOAD_SERVICE);
        imgView = (ImageView) findViewById(R.id.imageView);

        downloadButton.setOnClickListener(this);

        downloadUrl.setText("http://10.0.2.2/Android.jpg");
    }


    @Override
    public void onResume() {
      super.onResume();
      IntentFilter completeFilter = new IntentFilter(DownloadManager.ACTION_DOWNLOAD_COMPLETE);
      registerReceiver(completeReceiver, completeFilter);
    }

    @Override
    public void onPause() {
      super.onPause();
      unregisterReceiver(completeReceiver);
    }

    @Override
    public boolean onCreateOptionsMenu(Menu menu) {
        // Inflate the menu; this adds items to the action bar if it is present.
        getMenuInflater().inflate(R.menu.main, menu);
        return true;
    }


  @Override
  public void onClick(View v) {
    // TODO Auto-generated method stub
    urlToDownload = Uri.parse(downloadUrl.getText().toString());
    List pathSegments = urlToDownload.getPathSegments();

    downloadRequest = new DownloadManager.Request(urlToDownload);
    downloadRequest.setMimeType("Image");
    downloadRequest.setTitle("Image Downloader");
    downloadRequest.setDescription("Downloding a image...");
    downloadRequest.setDestinationInExternalPublicDir(Environment.DIRECTORY_DOWNLOADS, pathSegments.get(pathSegments.size() - 1));
    downloadRequest.addRequestHeader("Connection", "close");

    Environment.getExternalStoragePublicDirectory(Environment.DIRECTORY_DOWNLOADS).mkdirs();
    lastedId = downloadManager.enqueue(downloadRequest);

    downloadUrl.setText("http://10.0.2.2/Android.jpg");
  }
}