109 Python Problems for CCPS 109 CCPS 109 Computer Science I Labs Ilkka Kokkarinen Chang School of Continuing Education Ryerson University Version of January 12, 2022 Generalrequirements This...

1 answer below »

109 Python Problems for CCPS 109
CCPS 109 Computer Science I Labs
Ilkka Kokkarinen
Chang School of Continuing Education
Ryerson University
Version of January 12, 2022 

General    requirements
This     document     contains     speci0ications     for     the     lab     problems     in     the     course     CCPS     109     Computer    
Science     I,     as     taught     by     Ilkka     Kokkarinen     for     Chang     School     of     Continuing     Education,     Ryerson    
University,    Toronto,    Canada.    It    contains    109    individual    problems    (plus    0ive    bonus    problems)    for    you    
to    choose    your    battles    from.    The    problems    are    presented    roughly    in    order    of    increasing    complexity.    
All     problems     are     designed     to     allow     solutions     using     only     the     core     computation     structures    
introduced    during    the    enough    practice    problems    at     the    excellent    CodingBat    Python     interactive     training     site,     or    acquired    
the    equivalent    knowledge    from    earlier    studies.    Except    for    a    handful    of    problems    that    explicitly    point    
out     the     standard     li
ary    modules     that     are     useful     to     solve     them,     no     knowledge     of     any     specialized    
Python     li
aries     is     required.     Despite     this,     you     are     allowed     to     use     anything     in     the     Python     3    
standard    li
ary    that    you    0ind    useful    in    constructing    your    program    logic.    In    computer    science    and    
all    of    programming,    no    problem    should    ever    have    to    be    solved    twice!    
Each    co
ectly    solved    problem    is    worth    the    exact    same    one    point    to    your    course    grade.    Your    
grade    starts    from    the    baseline    of    40    points,    by    itself    not    quite    enough    to    pass    this    course.    Solving    ten    
problems     makes     your     course     grade     reach     50     points,     which     co
esponds     to     the     lowest     possible    
passing    course    grade    of    D    minus.    Solving    0ifty    problems    (yes,    yes,    for    grownup    realsies,    those    0ifty    
problems    can    be    any    0ifty)    takes    you    up    to    90    points    where    the    highest    possible    grade    of    A+    awaits.    
You    must    implement    all    these    functions    in    a    single    source    code    allows     you     to     run     the     tester109.py      script     at     any     time     to     validate     the     functions     you     have    
completed    so    far,    so    you    always    know    exactly    where    you    are    standing    on    this    course.    These    tests    are    
executed    in    the    same    order    that    your    functions    appear    inside    the    labs109.py    0ile.    
Your     functions    may     assume     that     the     arguments     given     to     them     them     are     as     promised     in     the    
problem    speciwhose    value    or    type    is    invalid.    Your    functions    must    especially    handle    zero    integers    and    empty    lists    
co
ectly    whenever    they    can    be    legitimate    argument    values.    
The     test     for     each     individual     function     should     take     at    most     a     couple     of     seconds     to     complete    
when    executed    on    an    off-the-shelf    desktop    from    the    past    couple    of    years.    If    some    test    takes    a    minute    
or    more    to    complete,    your    code    is    too    slow    and    its    logic    desperately    needs    to    be    streamlined.    This    is    
usually    achieved    by    shaving    off    one    level    of    nesting    from    the    structured    loops,    occasionally    with    the    
aid     of     a    set      or     a    dict      to     remember     the     stuff     that     your     function    has     seen     and    done     so     far.     The    
automated    tester    imposes    a    twenty    second    cutoff    for    each    test    to    complete,    after    which    the    test     is    
forcefully    terminated.    
Silence    is    golden.    None    of    your    functions    should    print    anything    on    the    console,    but    return    the    
expected    result    silently.    You    can    do    some    debugging    outputs    during    the    development,    but    remember    
to    comment    all    of    them    out    before    submission.    
https:
github.com/ikokkari/PythonExamples
https:
github.com/ikokkari/PythonExamples
http:
www.scs.ryerson.ca/~ikokkari
https:
codingbat.com/python
http:
www.catb.org/~es
faqs/hacker-howto.html#believe2
https:
github.com/ikokkari/PythonProblems
lo
maste
tester109.py
http:
www.catb.org/~es
writings/taoup/html/ch11s09.html
This     speci0ication     document     and     the     automated     tester     are     released     under     GNU     Public     License    
version    3    so    that    they    can    be    adapted    and    distributed    among    all    teachers    and    students    of    computer    
science.    The    author    compiled    these    problems    over    time    from    a    gallimaufry    of    sources    ranging    from    
the     original     lab     and     exam     problems     of     his     old     Java     version     of     this     course     to     a     multitude     of    
programming    puzzle    and    code    challenge    sites    such    as    LeetCode,    CodeA
ey,    Stack    Exchange    Code    
Golf,     and    Wolfram     Programming     Challenges.     Classic     recreational    mathematics     (yes,     that     is     a     real    
thing)    columns    by    Martin    Gardner    and    his    spiritual    disciples    also    inspired    many    problems.    
The    author    has     tried     to    dodge    not     just     the    Scylla    of     the    well-worn    problems     that     you     can     0ind     in    
asically     all     textbooks     and     online     problem     collections,     but     also     the     Charybdis     of     pointless    make-
work    drudgery     that    doesn’t    have    any     inherent    meaning    or    purpose    on     its    own,    at     least    above     the    
lunt    0inger    practice    to    provide    billable    “jobs    for    the    boys”    to    maintain    the    illusion    that    The    Machine    
is    still    churning    as    intended.    Some    of    these    seemingly    simple    problems    also    touch    the    deeper    issues    
of     computer     science     that     you     will     encounter     in     your     later     undergraduate     and     graduate     courses.    
Occasionally     these     problems     even     relate     to     entirely     separate     0ields     of     human     endeavour,     which    
makes    them    have    nontrivial    worldview    implications,    both    philosophical    and    practical.    
This     problem     set     also     has     an     of0icial     associated     su
eddit    
ccps109     for     students     to     discuss     the    
individual    problems    and    associated    issues.    This    discussion    should    take    place    at    the    level    of    ideas,    so    
that    no    solution    code    should    be    posted    or    requested.    Any    issues    with    course    management    and    the    
course     schedule     in     any     particular     semester     should     be     kept     out     of     this     su
eddit     to     give     a     more    
permanent    and    fundamental    nature.    Furthermore,    no    student    should    at    any    time    be    stuck    with    any    
one    problem.    Once    you    embark    on    solving    these    problems,    you    should    read    ahead    to     0ind    at     least    
0ive    problems    that    interest    you.    Keep    them    simmering    on    your    mental    back    burner    as    you    go    about    
your    normal    days.    Then    when    you    get    on    an    actual    keyboard,    work    on    the    problem    where    you    feel    
yourself    being    closest    to    a    working    solution.    
The     author     wishes     to     thank     past     students     Shu     Zhu     Su,     Rimma     Konoval,    Mohammed    Waqas,    
Zhouqin    He    and    Karel    Tutsu    for    going    above    and    beyond    the    call    of    duty    in    solving    these    problems    
in    ways    that    either    revealed    e
ors    in    the    original    problem    speci0ications    or    the    instructor's    private    
model     solutions,     or     more     fortunately,     independently     agreed     with     the     instructor's     private     model    
solution     and     by     doing     so    massively     raised     the     con0idence     to     the     co
ectness     of     both.     A     legion     of    
individual    students    who    pointed    out    ambiguities,    e
ors    and    inconsistencies    in    particular    problems    
effectively    acted    as    a    giant    Zamboni    to    plane    the    ice    for    all    future    students    to    skate    over    a    little    bit    
easier.    Members     of     that     horde,     you     all     know    who     you     are.     All     remaining     e
ors,     ambiguities     and    
inconsistencies    both    logical    and    extracu
icular    remain    the    sole    responsibility    of    Ilkka    Kokkarinen.    
Report    any    and    all    such    e
ors    as    discovered    to     XXXXXXXXXX.    
https:
leetcode.com/problemset/all
http:
www.codea
ey.com/index/task_list
https:
codegolf.stackexchange.com
https:
codegolf.stackexchange.com
https:
challenges.wolfram.com
https:
en.wikipedia.org/wiki/Recreational_mathematics
https:
en.wikipedia.org/wiki/Recreational_mathematics
https:
www.reddit.com
ccps109
List    of    Problems
Ryerson    letter    grade         10
Ascending    list         11
Rif0le    shuf0le    kerfuf0le         12
Even    the    odds         13
Cyclops    numbers         14
Domino    cycle         15
Colour    trio         16
Count    dominators         17
Beat    the    previous         18
Subsequent    words         19
Taxi    ℤum    ℤum         20
Exact    change    only         21
Rooks    on    a    rampage         22
Try    a    spatula         23
Words    with    given    shape         24
Chirality         25
The    card    that    wins    the    trick         26
Do    you    reach    many,    do    you    reach    one?         27
Sevens    rule,    zeros    drool         28
Fulcrum         29
Fail    while    daring    greatly         30
All    your    fractions    are    belong    to    base         31
Recamán's    sequence         32
Count    the    balls    off    the    
ass    monkey         33
Count    growlers         34
Bulgarian    solitaire         35
Scylla    or    Charybdis?         36
Longest    arithmetic    progression         37
Best    one    out    of    three         38
Collecting    numbers         39
Count    Troikanoff,    I    presume         40
Crack    the    crag         41
Three    summers    ago         42
Sum    of    two    squares         43
Ca
y    on    Pythonista         44
As    below,    so    above         45
Expand    positive    integer    intervals         46
Collapse    positive    integer    intervals         47
Prominently    featured         48
Like    a    kid    in    a    candy    store,    except    without    money         49
Dibs    to    dubs         50
Nearest    smaller    element         51
Interesting,    intersecting         52
So    shall    you    sow         53
That's    enough    of    you!         54
Brussel's    choice         55
Cornered    cases         56
Count    consecutive    summers         57
McCulloch's    second    machine         58
That's    enough    for    you!         59
Crab    bucket    list         60
What    do    you    hear,    what    do    you    say?         61
Bishops    on    a    binge         62
Dem’s    some    mighty    tall    words,    pardner         63
Up    for    the    count         64
Revorse    the    vewels         65
Everybody    on    the    0loor,    come    do    the    Scrooge    Shuf0le         66
Rational    lines    of    action         67
Ve
os    regulares         68
Hippity    hoppity,    abolish    loopity         69
Where    no    one    can    hear    you    bounce         70
Nearest    polygonal    number         71
Don’t    wo
y,    we    will    0ix    it    in    the    post         72
Fractran    interpreter         73
Permutation    cycles         74
Whoever    must    play,    cannot    play         75
ztalloc    ecneuqes         76
The    solution    solution         77
Reverse    ascending    sublists         78
Brangelin-o-matic    for    the    people         79
Line    with    most    points         80
Om    nom    nom         81
Autoco
ect    for    sausage    0ingers         82
Uambcsrlne    the    wrod         83
Substitution    words         84
Manhattan    skyline         85
Count    overlapping    disks         86
Ordinary    cardinals         87
Count    divisibles    in    range         88
Bridge    hand    shape         89
Milton    Work    point    count         90
Never    the    twain    shall    meet         91
Bridge    hand    shorthand    form         92
Points,    schmoints         93
Bulls    and    cows         94
Frequency    sort         95
Calling    all    units,    B-and-E    in    progress         96
Lunatic    multiplication         97
Distribution    of    abstract    
idge    hand    shapes         98
Fibonacci    sum         99
Wythoff    a
ay         100
Rooks    with    friends         101
Possible    words    in    Hangman         102
All    
anches    lead    to    Rome         103
Be    there    or    be    square         104
Flip    of    time         105
Bulgarian    cycle         106
Square    it    out    amongst    yourselves         107
Sum    of    distinct    cubes         108
Count    maximal    layers         109
Maximum    checkers    capture         110
Collatzy    distance         111
Van    Eck    sequence         112
Tips    and    trips         113
Balanced    ternary         114
Lords    of    Midnight         115
Optimal    crag    score         116
Painted    into    a    corner         117
Go    for    the    Grand:    In0inite    Fibonacci    word         118
Bonus    problem    110:    Reverse    the    Rule    110         119
Bonus    problem    111:    Aye,    eye,    I         120
Bonus    problem    112:    Count    domino    tilings         121
Bonus    problem    113:    Invaders    must    die         122
Bonus    problem    114:    Stepping    stones     123
Ryerson letter grade
def ryerson_letter_grade(pct):
Given    the    percentage    grade,    calculate    and    return    the    letter    grade    that    would    appear    in    the    Ryerson    
grades    transcript,    as    de0ined    on    the    page    Ryerson    Grade    Scales.    This    letter    grade    should    be    returned    
as    a    string    that    consists    of    the    uppercase    letter    followed    by    the    modi0ier    '+'    or    '-',    if    there    is    one.    
This    function    should    work    co
ectly    for    all    values    of    pct    from    0    to    150.    
Same     as     all     other     programming     problems     that     follow     this     problem,     this     can     be     solved     in     various    
different    ways.    The    simplest    way    to    solve    this    problem    would    probably    be    to    use    an    if-else    ladder.    
The    0ile    labs109.py    given    in    the    repository    ikokkari/PythonProblems    already    contains    an    
implementation     of     this     function     for     you     to     run     the     tester     script     tester109.py      to     verify     that    
everything    is    hunky    dory.        
As    you    learn    more    Python    and    techniques    to    make    it    dance    for    you,    you    may    think    up    other    ways    to    
solve     this     problem.     Some     of     these     would     be     appropriate     for     actual     productive     tasks     done     in     a    
professional     coding     environment,     whereas     others     are     intended     to     be     taken     in     jest     as     a     kind     of    
conceptual    performance    art.    A    popular    genre    of    recreational    puzzles    in    all    programming    languages    
is     to     solve     some     straightforward     problem     with     an     algorithmic     equivalent     of     a     needlessly    
complicated    Rube    Goldberg    machine,    to    demonstrate    the    universality    and    unity    of    all    computation.
pct Expected    result
45 'F'
62 'C-'
89 'A'
107 'A+'
https:
www.ryerson.ca
egistra
faculty/grading/gradescales_ugrad
https:
github.com/ikokkari/PythonProblems
lo
maste
labs109.py
https:
github.com/ikokkari/PythonProblems
https:
github.com/ikokkari/PythonProblems
lo
maste
tester109.py
https:
en.wikipedia.org/wiki/Rube_Goldberg_machine
Ascending list
def is_ascending(items):
Determine    whether    the    sequence    of    items      is    strictly    ascending     so    that    each    element     is    strictly    
larger     (not     just     merely     equal     to)     than     the     element     that     precedes     it.     Return    True      if     the     list     of    
items    is    strictly    ascending,    and    return    False    otherwise.    
Note    that    the    empty    sequence    is    ascending,    as    is    also    every    one-element    sequence,    so    be    careful    that    
your     function     returns     the     co
ect     answers     in     these     seemingly     insigni0icant     edge     cases     of     this    
problem.     (If     these    sequences    were    not    ascending,    pray     tell,    what    would    be     the     two    elements     that    
violate    the    requirement    and    make    that    particular    sequence    not    be    ascending?)    
In    the    same    spirit,    note    how    every    possible    universal    claim    made    about    the    elements    of    an    empty    
sequence    is    trivially    true!    For    example,    if    items    is    the    empty    sequence,    the    two    claims    “All    elements    
of    items    are    odd”    and    “All    elements    of    items    are    even”    are    both    equally    true,    as    is    also    the    claim    
“All    elements    of    items    are    colourless    green    ideas    that    sleep    furiously.”
items Expected    result
[] True
[-5, 10, 99, 123456] True
[2, 3, 3, 4, 5] False
[-99] True
[4, 5, 6, 7, 3, 7, 9] False
[1, 1, 1, 1] False
https:
en.wikipedia.org/wiki/Colorless_green_ideas_sleep_furiously
Riffle shuffle kerfuffle
def riffle(items, out=True):
Given    a    list    of    items     whose    length    is    guaranteed    to    be    even    (note    that    “oddly”    enough,    zero    is    an    
even    number),     create     and     return     a     list     produced    by    performing     a    perfect    rifinterleaving    the    items    of    the    two    halves    of    the    list    in    an    alternating    fashion.    
When    performing    a    perfect    rif0le    shuf0le,    also    known    as    the    Faro    shuf0le,    the    list    of    items    is    split    in    
two    equal    sized    halves,    either    conceptually    or    in    actuality.    The    0irst    two    elements    of    the    result    are    
then    the    0irst    elements    of    those    halves.    The    next    two    elements    of    the    result    are    the    second    elements    
of    those    halves,    followed    by    the    third    elements    of    those    halves,    and    so    on    up    to    the    last    elements    of    
those    halves.    The    parameter    out    determines    whether    this    function    performs    an    out    shuf0le    or    an    in    
shuf0le    that    determines    which    half    of    the    deck    the    alternating    card    is    0irst    taken    from.    
items out Expected    result
[1, 2, 3, 4, 5, 6, 7, 8] True [1, 5, 2, 6, 3, 7, 4, 8]
[1, 2, 3, 4, 5, 6, 7, 8] False [5, 1, 6, 2, 7, 3, 8, 4]
[] True []
['bob', 'jack'] True ['bob', 'jack']
['bob', 'jack'] False ['jack', 'bob']
https:
en.wikipedia.org/wiki/Faro_shuffle
https:
en.wikipedia.org/wiki/Out_shuffle
https:
en.wikipedia.org/wiki/In_shuffle
https:
en.wikipedia.org/wiki/In_shuffle
Even the odds
def only_odd_digits(n):
Check    that    the    given    positive    integer    n    contains    only    odd    digits    (1,    3,    5,    7    and    9)    when    it    is    written    
out.    Return    True      if     this     is     the     case,     and    False      otherwise.    Note     that     this    question     is    not     asking    
whether    the    number    n    itself    is    odd    or    even.    You    therefore    will    have    to    look    at    every    digit    of    the    given    
number    before    you    can    proclaim    that    the    number    contains    no    odd    digits.    
To    extract    the    lowest    digit    of    a    positive    integer    n,    use    the    expression    n%10.    To    chop    off    the    lowest    
digit    and    keep    the    rest    of    the    digits,    use    the    expression    n
10.    Or,    if    you    don't    want    to    be    this    fancy,    
you    can    0irst    convert    the    number    into    a    string    and    work    from    there    with    string    operations.    
n Expected    result
8 False
XXXXXXXXXXTrue
42 False
71358 False
0 False
Cyclops numbers
def is_cyclops(n):
A    nonnegative    integer    is    said    to    be    a    cyclops    number    if    it    consists    of    an    odd    number    of    digits    so    
that     the    middle    (more    poetically,     the    “eye”)    digit     is    a    zero,    and    all    other    digits    of     that    number    are    
nonzero.    This    function    should    determine    whether    its    parameter    integer    n    is    a    cyclops    number,    and    
eturn    either    True    or    False    accordingly.    
As     an     extra     challenge,     you     can     try     to     solve     this     problem    using    only     loops,     conditions     and     integer    
arithmetic     operations,    without     0irst     converting     the     integer     into     a     string     and    working     from     there.    
Dividing    an    integer    by    10    with    the    integer    division    
    effectively    chops    off    its    last    digit,    whereas    the    
emainder     operator    %      can     be     used     to     extract     that     last     digit.     These     operations     allow    us     to     iterate    
through    the    digits    of    an    integer    one    at    the    time    from    lowest    to    highest,    almost    as    if    that    integer    were    
some    kind    of    lazy    sequence    of    digits.    
Even    better,    this    operation    doesn't    work    merely    for    the    familiar    base    ten,    but    it    works    for    any    base    
y    using     that    base    as     the    divisor.    Especially    using     two    as     the    divisor     instead    of     ten    allows    you     to    
iterate     through     the    bits     of     the    binary     representation     of     any     integer,    which    will     come     handy     in    
problems     in    your     later    courses     that    expect    you     to    be    able     to    manipulate     these     individual    bits.     (In    
practice     these    division    and    remainder    operations    are    often     further    condensed     into    equivalent    but    
faster    bit    shift    and    bitwise    and    operations.)
n Expected    result
0 True
101 True
98053 True
XXXXXXXXXXFalse
1056 False
XXXXXXXXXXFalse
Domino cycle
def domino_cycle(tiles):
A    single    domino    tile    is    represented    as    a    two-tuple    of    its    pip    values,    such    as    (2,5)    or    (6,6).    This    
function    should    determine    whether    the    given    list    of    tiles    forms    a    cycle    so    that    each    tile    in    the    list    
ends    with    the    exact    same    pip    value    that    its    successor    tile    starts    with,    the    successor    of    the    last    tile    
eing    the    0irst    tile    of    the    list    since    this    is    supposed    to    be    a    cycle    instead    of    a    chain.    Return    True     if    
the    given    list    of    tiles    forms    such    a    cycle,    and    False    otherwise.    
tiles Expected    result
[(3, 5), (5, 2), (2, 3)] True
[(4, 4)] True
[] True
[(2, 6)] False
[(5, 2), (2, 3), (4, 5)] False
[(4, 3), (3, 1)] False
Colour trio
def colour_trio(colours):
This     problem     was     inspired     by     the     Mathologer     video     “Secret     of     Row     10”.     To     start,     assume     the    
existence    of     three     values     called     “red”,     “yellow”     and     “blue”.     These    names     serve     as     colourful     (heh)    
mnemonics    and    could    as    well    have    been    0,    1,    and    2,    or    “foo”,    “bar”    and    “baz”;    no    connection    to    actual    
physical    colours    is     implied.    Next,    de0ine    a    rule    to    mix    such    colours    so    that    mixing    any    colour    with    
itself    gives    that    same    colour,    whereas    mixing    any    two    different    colours    always    gives    the    third    colour.    
For     example,    mixing     blue     to     blue     gives     that     same     blue,    whereas    mixing     blue     to     yellow     gives     red,    
same    as    mixing    yellow    to    blue,    or    red    to    red.    
Given    the    0irst    row    of    colours     as    a    string    of    lowercase    letters,    this    function    should    construct    the    
ows    below    the    0irst    row    one    row    at    the    time    according    to    the    following    discipline.    Each    row    is    one    
element    shorter    than    the    previous    row.    The    i:th    element    of    each    row    comes    from    mixing    the    colours    
in    positions    i    and    i    +    1    of    the    previous    row.    Rinse    and    repeat    until    only    the    singleton    element    of    the    
ottom     row     remains,     returned     as     the     0inal     answer.     For     example,     starting     from     the     0irst     row    
'rybyr'    leads    to    '
',    which    leads    to    'yry',    which    leads    to    '
',    which    leads    to    'b'    for    the    
0inal    answer,    Regis.    When    the    Python    virtual    machine    laughingly    goes    '
',    that    will    lead    to    
'y
',    '
'    ,    'y
',    and    '
'    for    the    0inal    answer    'y'    for    “Yes,    please!”    
(Today's    0ive-dollar    power    word    to    astonish    your    friends    and    coworkers    is    "quasigroup".)
colours Expected    result
'y' 'y'
'
' 'b'
'rybyry' 'r'
'
y
' 'r'
'
yry
y
' 'y'
'y
yyry
' 'b'
https:
www.youtube.com/channel/UC1_uAIS3r8Vu6JjXWvastJg
https:
www.youtube.com/watch?v=9JN5f7_3YmQ&t=1457s
https:
en.wikipedia.org/wiki/Quasigroup
Count dominators
def count_dominators(items):
We    shall    de0ine    an    element    of    a    list    of    items     to    be    a    dominator     if    every    element    to    its    right    (not    
just     the    one    element     that     is     immediately     to     its    right)     is    strictly    smaller     than    that    element.    By     this    
de0inition,     the     last     item     of     the     list     is     automatically     a     dominator.     This     function     should     count     how    
many    elements    in    items    are    dominators,    and    return    that    count.    For    example,    the    dominators    of    the    
list    [42, 7, 12, 9, 13, 5]    would    be    its    elements    42,    13    and    5.    The    last    element    of    the    list    is    
trivially    a    dominator,    regardless    of    its    value,    since    nothing    greater    follows    it.    
Before     starting     to     write     code     for     this     function,     you     should     consult     the     parable     of     "Shlemiel     the    
painter"    and    think    how    this    seemingly    silly    tale    from    a    simpler    time    relates    to    today's    computational    
problems    performed    on     lists,     strings    and    other    sequences.    This    problem    will    be     the     0irst    of    many    
that    you    will    encounter    during    and    after     this    course     to     illustrate     the     important    principle    of    using    
only    one    loop    to    achieve    in    a    tiny    fraction    of    time    the    same    end    result    that    Shlemiel    achieves    with    
two    nested     loops.    Your    workload     therefore     increases    only     linearly    with    respect     to     the    number    of    
items,     whereas     the     total     time     of     Shlemiel’s     back-and-forth     grows     quadratically,     that     is,     as     a    
function    of    the    square    of    the    number    of    items.    
Trying     to    hide     the     inner     loop    of    some    Shlemiel    algorithm    inside    a     function    call     (and    this     includes    
Python    built-ins    such    as    max    and    list    slicing)    and    pretending    that    this    somehow    makes    those    inner    
loops     take     a     constant     time     will     only     summon     the     Gods     of     Compubook     Headings     to     return     with    
tumult    to    claim    their    lion's    share    of    execution    time.
items Expected    result
[42, 7, 12, 9, 2, 5] 4
[] 0
[99] 1
[42, 42, 42, 42] 1
ange(10**7) 1
ange(10**7, 0, XXXXXXXXXX
http:
wiki.c2.com/?ShlemielThePainte
http:
wiki.c2.com/?ShlemielThePainte
Beat the previous
def extract_increasing(digits):
Given    a    string    of    digits    guaranteed     to    only    contain    ordinary     integer    digit    characters    0     to    9,    create    
and     return     the     list     of     increasing     integers     acquired     from    reading     these    digits     in    order     from     left     to    
ight.    The    0irst    integer    in    the    result    list    is    made    up    from    the    0irst    digit    of    the    string.    After    that,    each    
element     is    an     integer    that    consists    of    as    many    following    consecutive    digits    as    are    needed    to    make    
that    integer    strictly    larger    than    the    previous    integer.    The    leftover    digits    at    the    end    of    the    digit    string    
that    do    not    form    a    suf0iciently    large    integer    are    ignored.    
This     problem     can     be     solved    with     a     single     for-loop     through     the    digits      that     looks     at     each     digit    
exactly    once     regardless    of     the    position    of     that    digit     in     the    beginning,     end    or    middle    of     the     string.    
Keep     track    of     the    cu
ent      number     (initially     zero)    and     the    previous      number     to    beat     (initially    
equal    to    minus    one).    Each    digit    d      is    then    processed    by    pinning    it    at    the    end    of    cu
ent     number    
with    the    assignment    cu
ent=10*cu
ent+int(d).    
digits Expected    result
'600005' [6]
'045349' [0, 4, 5, 34]
'777 XXXXXXXXXX' [7, 77, 777, 7777, 77777, 777777]
'1 XXXXXXXXXX' [1, 2, 23, 33, 44, 445, 555, 566,
666]
'27182 XXXXXXXXXX
471352 XXXXXXXXXX
957496 XXXXXXXXXX
475945 XXXXXXXXXX
466391 XXXXXXXXXX
66 XXXXXXXXXX'
[2, 7, 18, 28, 182, 845, 904,
5235, 36028, 74713, 526624,
977572, XXXXXXXXXX, XXXXXXXXXX,
XXXXXXXXXX, XXXXXXXXXX, XXXXXXXXXX,
XXXXXXXXXX, XXXXXXXXXX,
XXXXXXXXXX, XXXXXXXXXX,
XXXXXXXXXX]
'1234' * 100 A    list    with    38    elements,    the    last    one    equal    to    
3 XXXXXXXXXX
'420' * 420 A    list    with    56    elements,    the    last    one    equal    to    
4204204204204 XXXXXXXXXX
XXXXXXXXXX
Subsequent words
def words_with_letters(words, letters):
This    problem     is     an    excuse     to     introduce     some    general    discrete    math     terminology     that    helps    make    
many    later    problem    speci0ications    less    convoluted    and    ambiguous.    A    substring    of    a    string    consists    
of    characters    taken    in    order     from    consecutive    positions.    Contrast    this    with    the    similar    concept    of    
subsequence     of     characters     still     taken     in     order,     but     not     necessarily     at     consecutive     positions.     For    
example,    each    of     the     0ive    strings    '',    'e',    'put',    'ompu'     and    'computer'      is    both    a    substring    
and    subsequence    of    the    string    'computer',    whereas    'cper'     and    'out'     are    subsequences,    but    
not    substrings.    
Note     how     the     empty     string     is     always     a     substring     of    
Answered Same DayApr 09, 2022

Solution

Sathishkumar answered on Apr 10 2022
10 Votes
SOLUTION.PDF

Answer To This Question Is Available To Download

Related Questions & Answers

More Questions »

Submit New Assignment

Copy and Paste Your Assignment Here