I found this assignment on C++ forum as was browsing to see little where I am in my mostly C little C++ thrown in understanding of C++ and if I should try to increase my knowledge in that language.

I could not believe my eyes! The OP is completely lost what to do and what approach to take and do not finish in time. Ok, we must consider that I have read this post for main points before but I do one experiment.

  1. I paste the description on this post and log the time
  2. I write the function for the checking part but by my way
  3. I adapt solution to do two other ways and menu for choices

Let's see how I do now is 21:50 GMT+3. I start. Description of assignment:

A lottery ticket buyer purchases 10 tickets a week. always playing the same 10 5-digit "lucky" combinations. Write a program that reads the numbers from an input file, initializes an array with these numbers and then lets the player enter this week's winning 5-digit numbers (Use random number generator to generate 5 numbers in the range 1 through 49 for the winning combination rather than letting the user enter the winning number combination).

The program should perform both, linear and binary search though the list of the player's numbers and report whether or not one of the tickets is a winner this week. You should present the user with the menu to find out if he/she is a winner through linear or binary search.

Here are the numbers:

11-18-20-24-25
8-10-23-32-36
1-6-12-18-34
23-29-31-32-34
1-15-17-23-32
4-6-13-25-27
8-9-26-29-34
14-17-19-24-30
1-8-25-28-29
13-17-24-29-33


1. I do not want to do the stupid way they suggest so I do it first the easy way.

  • Preparing file
  • read it in by splitting as list of sets
  • generate correct row
  • compare to the lucky numbers with set intersection

I'll keep the numbers as strings, just to do it 'difficult way' according to C++ thread.
My coding took 1,5 hours to do (with linear search working after 20 minutes), including cleaning up the code and basic testing of the final code (and getting up the children to school :) )

from __future__ import print_function
try:
    input = raw_input
except:
    pass

# LOG:
#start time 21:51
#22:11, finished for the day
#restart time 6:11
#Finished 7:03 (including waking children)
#TOTAL: 21:51 TO 22:11 = 20 MIN + 6:11 TO 7:03 = 52 MIN, final testing and clean up 18 MIN => 90 MINUTES
# IT TOOK 1,5 HOURS TO PROGRAM

import random

import bisect

FILE = 'lucky.txt'
MAX_NUMBER, HOW_MANY = 49, 5
lottery = 1


def choose_winner(lottery):
    winner = random.sample(list(range(1, MAX_NUMBER + 1)), HOW_MANY)
    print('Week %i winner row is: %s' % (lottery, sorted(winner, key=int)))
    return winner

binary_lucky = None
with open(FILE) as number_file:
    lucky_numbers = [set(line.strip().split('-')) for line in number_file]

print('Your lucky numbers:')
for lucky in lucky_numbers:
    print(lucky)
print()

while True:
    search_type = input('''
Type B for binary search check,
     Q to quit,
     anything else gives you linear search.\n\t''').upper()
    if search_type and search_type in 'BQ':
        if search_type == 'Q':
           raise SystemExit('Bye, bye!')
        # binary search
        print('Binary search selected')
        if not binary_lucky:
            binary_lucky = sorted(sorted(int(number) for number in numbers) for numbers in lucky_numbers)
            print('Numbers as integers, sorted, for binary search.')
            for lucky in binary_lucky:
                print(lucky)
            print()
        winner = choose_winner(lottery)
        # winner = sorted(map(int,'1-15-17-23-32'.split('-'))) # debug: check that the winner finding works
        print('You got winner'.center(40,'*')
                    if binary_lucky[bisect.bisect(binary_lucky, winner) - 1] == winner
                    else 'No luck this time')
    else:
        winner = set(map(str, choose_winner(lottery)))
        #winner = set('1-15-17-23-32'.split('-')) # debug: check that the winner finding works, worked first time
        print('Best try had these correct:', max((box.intersection(winner) for box in lucky_numbers), key = len))
        print('You got winner'.center(40,'*') if winner in lucky_numbers else 'No luck this time')

Edited 5 Years Ago by pyTony: n/a

Of course one thing was left out because first code had limit of number of tries and for loop and I changed it at end for infinite loop. So I forgot to put in increment of the counter. This should be at last line inside the while loop:

lottery += 1

If you want to take out program doing search first time with max and second time with in change last lines from else to:

else:
        winner = set(map(str, choose_winner(lottery)))
        #winner = set('1-15-17-23-32'.split('-')) # debug: check that the winner finding works, worked first time
        best = max((box.intersection(winner) for box in lucky_numbers), key = len)
        print('Best try had these correct:', best)
        print('You got winner'.center(40,'*') if best == winner else 'No luck this time')
    lottery += 1

Or take out the extra functionality for finding the best box of numbers in linear search.

Edited 5 Years Ago by pyTony: n/a

IMHO, you found Python easier because:

  • It is interpreted, which makes the compile/test/edit cycle faster
  • It was a tiny problem, so the execution speed did not matter
  • The OP doesn't know how to make best use of C++: Using the standard containers makes C++ almost as expressive as Python (and much faster to run)
  • Python had the advantage of not needing to be backward compatible with C

I do agree: Python is easier.

Edited 5 Years Ago by griswolf: n/a

Yes I agree that we should look for the case of very tight loop of action with long running time to get better case for C++. Then just study the Boost library (I saw) to use C++ instead of C code from Python.


How about this for strategy of coding for Python guy:

This is case to use Python philosophy of not doing premature optimisations.

  1. Do the proof of concept in Python
  2. Test the functionality and in the end speed.
  3. Improve the algorithm in Python solution in hot spot you found.
  4. If hot spot is not fast enough, and simple to do, do C extension with swing or ctypes and dll (? no experience yet).
  5. If the hot spot is important enough to speed up and complicated for C solution, learn C++ and Boost library and recode that part in C++.

Edited 5 Years Ago by pyTony: n/a

Python is designed to be friendly and concise, though for this problem I wouldn't say that C++ fares too badly in the comparison:

#include <algorithm>
#include <cctype>
#include <cstdlib>
#include <ctime>
#include <functional>
#include <fstream>
#include <iomanip>
#include <iostream>
#include <iterator>
#include <sstream>
#include <stdexcept>
#include <string>
#include <vector>

namespace jsw {
    template <typename To, typename From>
    To lexical_cast(const From& rhs)
    {
        std::stringstream conv;
        To result;

        if (!(conv<< rhs && conv>> result))
            throw std::runtime_error("Bad lexical_cast");

        return result;
    }

    template <typename T>
    std::vector<T> split(const std::string& src, char delim)
    {
        std::istringstream splitter(src);
        std::vector<T> result;
        std::string field;

        while (std::getline(splitter, field, delim))
            result.push_back(jsw::lexical_cast<T>(field));

        return result;
    }

    template <typename T>
    std::string join(const std::vector<T>& src, char delim)
    {
        std::string result;

        for (std::vector<T>::size_type i = 0; i != src.size(); i++) {
            result += jsw::lexical_cast<std::string>(src[i]);

            if (i != src.size() - 1)
                result += delim;
        }

        return result;
    }
}

namespace {
    struct random_lotto {
        int operator()() { return 1 + rand() % 49; }
    };
}

int main()
{
    using namespace std;

    typedef vector<int> pick_t;
    typedef vector<pick_t> pick_list_t;

    ifstream in("test.txt");

    if (in) {
        pick_list_t lotto_picks;
        string line;

        // Get the lottery picks from file and extract into a convenient testing format
        while (getline(in, line)) {
            lotto_picks.push_back(jsw::split<pick_t::value_type>(line, '-'));
            sort(lotto_picks.back().begin(), lotto_picks.back().end());
        }

        pick_t winning_numbers;

        // Generate this week's winning numbers
        srand((unsigned)time(0));
        std::generate_n(std::back_inserter(winning_numbers), winning_numbers.size(), random_lotto());

        bool good_input = false;
        string opt;
        function<bool(int)> counter;

        // Do a linear or binary search based on user input
        while (!good_input) {
            cout<<"Search for winners with (L)inear or (B)inary search: ";

            if (!getline(cin, opt) || opt.size() == 0)
                return 0;

            switch (toupper(opt.front())) {
            case 'L':
                counter = [&winning_numbers] (int pick) -> bool { 
                    return find(winning_numbers.begin(), winning_numbers.end(), pick) != winning_numbers.end();
                };
                good_input = true;
                break;
            case 'B':
                counter = [&winning_numbers] (int pick) -> bool { 
                    return binary_search(winning_numbers.begin(), winning_numbers.end(), pick);
                };
                good_input = true;
                break;
            default:
                cerr<<"Invalid option\n";
                break;
            }
        }

        // Calculate and display the results
        for (pick_list_t::const_iterator it = lotto_picks.begin(); it != lotto_picks.end(); ++it) {
            if (count_if(it->begin(), it->end(), counter) == it->size())
                cout<<"*** Winner! ***\t";
            else
                cout<<"Not a winner\t";

            cout<<'{'<< jsw::join(*it, '-') << "}\n";
        }
    }
}

Naturally there's some manual labor involved with the strings because C++ is notoriously bad at string processing. ;) Total development time, maybe 30 minutes including tidying up. But how long it takes depends heavily on the programmer and their familiarity with the language.

Comments
Thanks for sharing your knowledge!

Nice coding, Narue. I can half guess the meaning.

By the way, when I was in shower, came one little unconventional way this "problem" could have been solved:

Instead of reading in lines of lotto, the number of lotto box could be recorded to each number in the lucky numbers as list/set, immediately as we keep boxes which had all numbers read before, if get one number which is not in any of those (trivially not in any box), we could short cut the checking immediately and say 'No winner'. If we read and accept the last number of that weeks line, we got winner. We could read maximum that many numbers as box with most correct numbers has correct numbers assuming we do not want to check for smaller winnings.

Edited 5 Years Ago by pyTony: n/a

This question has already been answered. Start a new discussion instead.