Keskustelu: Yleinen keskustelu: Mikä on pienin yhteismäärä, jos prosenttiosuudet tiedetään?

#!/usr/bin/env python3

from sys import argv, exit
from math import ceil
from optparse import OptionParser  # Python 3.1 ja uudemmat
import itertools

class Prosenttiosuus:
    def __init__(self, s, sep='.'):
        '''s: liukuluku merkkijonona väliltä [0.0, 100.0]'''
        osat = s.split(sep)
        if len(osat) > 2:
            raise ValueError('Liikaa desimaalierottimia')
        if not (''.join(osat)).isnumeric():
            raise ValueError('Vain numerot sallittu desimaalierottimen lisäksi')

        self.osuus = float(s) / 100
        if not (0.0 <= self.osuus <= 1.0):
            raise ValueError('Yksittäisen osuuden pitää olla nollan ja sadan välissä')
        self.desimaaleja = len(osat[1]) if len(osat) == 2 else 0

    def pyoristysrajat(self):
        dx = 0.5 / (100 * 10 ** self.desimaaleja)
        return (self.osuus - dx, self.osuus + dx)

    def __str__(self):
        return '{0:.{1}f} %'.format(100 * self.osuus, self.desimaaleja)


def sovita_osumat_kokonaismaaraan(kokmaara, osumat):
    minimi, maksimi = [sum(x) for x in zip(*osumat)]
    if not (minimi <= kokmaara <= maksimi):
        return False

    # ratkaisu löytyi, tutkitaan kavennetaanko osumarajoja
    maksimista_vajaa = maksimi - kokmaara
    minimista_yli = kokmaara - minimi
    for vali in osumat:
        alaraja, ylaraja = vali
        # yhden luvun alaraja voi olla ylärajan alle korkeintaan sen verran kuin mitä
        # tarkka kokonaismäärä on kaikkien osumarajojen yhteenlaskettua maksimia pienempi
        vali[0] = max(ylaraja - maksimista_vajaa, alaraja)
        vali[1] = min(alaraja + minimista_yli, ylaraja)

    return True

def kokonaismaarat(osuudet, haarukka, taysi=False, lkm=None):
    '''palauta kokonaisluku, jolle löytyy annettuja prosenttiosuuksia vastaavat kokonaisluvut

    jos taysi = True, edellytä että osuuksien summa täsmää kokonaismäärään
    jos vahintaan on kokonaisluku, iteroi kaikki ratkaisut siihen asti, muuten loputtomasti

    '''
    rajat = [o.pyoristysrajat() for o in osuudet]
    osumia = 0
    for kokmaara in haarukka:
        osumat = []
        for ala, yla in rajat:
            x_min, x_max = ceil(ala * kokmaara), ceil(yla * kokmaara)
            if x_min == x_max:
                break  # ei kokonaislukua välissä
            osumat.append([x_min, x_max - 1])  # prosenttiosuutta vastaava kokonaislukuväli
        else:
            # kaikille prosenttiosuuksille löytyi vastaavat kokonaisluvut
            if (not taysi) or sovita_osumat_kokonaismaaraan(kokmaara, osumat):
                yield (kokmaara, osumat)
                osumia += 1

        if lkm is not None and osumia == lkm:
            break

def tulosta_vastaus(pym, osuudet, rajat):
    print('%d on mahdollinen kokonaismäärä, jolle annetut prosenttiosuudet täsmäävät' % pym)
    for o, r in zip(osuudet, rajat):
        if r[0] == r[1]:
            # vain yksi kokonaisluku osuu annettuun prosenttiosuuteen
            print('{0} / {1} = {2}'.format(r[0], pym, o))
        else:
            print('{0}..{1} / {2} = {3}'.format(r[0], r[-1], pym, o))

def luo_argumenttijasennin():
    kuvaus = 'Etsii pienimmän/t kokonaisluvun, johon annetut prosenttiosuudet sopivat. ' + \
             'Anna osuudet prosentteina, esim. 3 tai 74.25.'
    kaytto='usage: %prog [optiot] [osuudet]'
    jasennin = OptionParser(usage=kaytto, description=kuvaus)
    jasennin.add_option('-k', '--kaikki', dest='kaikki', action='store_true', default=False, \
                      help='tarkista että osuuksien summa on 100 % eli kaikki vaihtoehdot ovat mukana')
    jasennin.add_option('-n', '--lukumaara', dest='lkm', type='int', default=1, \
                      help='näytettävien ratkaisujen lukumäärä (oletus = 1)')
    jasennin.add_option('-y', '--ylaraja', dest='yraja', type='int', default=0, \
                      help='hae ratkaisut tähän ylärajaan asti (oletus = ei rajaa). ' + \
                           'Jos tämä on annettu, määräoptiota ei huomioida.')
    jasennin.add_option('-a', '--alaraja', dest='araja', type='int', default=1, \
                      help='hae ratkaisut tästä alarajasta asti (oletus = 1).')
    jasennin.add_option('-t', '--tarkka', dest='tarkka', type='int', default=0, \
                      help='hae mahdollinen ratkaisu vain tästä määrästä')
    return jasennin

def main():
    jasennin = luo_argumenttijasennin()
    (opt, args) = jasennin.parse_args()

    try:
        osuudet = list(map(Prosenttiosuus, args))
    except ValueError as e:
        print('Virhe argumenteissa: %s' % e)
        exit(-1)

    if not args:
        jasennin.print_help()
        return

    if opt.kaikki:
        # tarkista että osuuksien summa on 100 % pyöristysrajat huomioiden
        rajat = (o.pyoristysrajat() for o in osuudet)
        minimi, maksimi = [sum(x) for x in zip(*rajat)]
        if not (minimi <= 1.0 <= maksimi):
            print('Virhe: Annettujen prosenttiosuuksien summa ei ole 100')
            exit(-1)

    if opt.tarkka:
        rajat = [opt.tarkka]
    elif opt.yraja:
        rajat = range(opt.araja, opt.yraja + 1)
    else:
        rajat = itertools.count(opt.araja)

    for pym, osumat in kokonaismaarat(osuudet, rajat, opt.kaikki, opt.lkm):
        tulosta_vastaus(pym, osuudet, osumat)

if __name__ == '__main__':
    main()