Last active
March 27, 2016 19:58
-
-
Save schmich/7993f0253eda4cf80003 to your computer and use it in GitHub Desktop.
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| require 'pp' | |
| require 'set' | |
| winner = [Set.new([4, 8, 19, 27, 34]), 10] | |
| tickets = File.open('numbers.txt').readlines.map { |line| | |
| numbers = line.scan(/\d+/).map { |n| n.to_i } | |
| [Set.new(numbers.take(5)), numbers[numbers.length - 1]] | |
| }.to_a | |
| tickets.each do |ticket| | |
| winning_white = winner[0] | |
| winning_powerball = winner[1] | |
| ticket_white = ticket[0] | |
| ticket_powerball = ticket[1] | |
| matching_white = winning_white & ticket_white | |
| matching_powerball = (winning_powerball == ticket_powerball) | |
| if matching_white.count > 0 || matching_powerball | |
| print "White: #{matching_white.count}, Powerball: #{matching_powerball ? '1' : '0'}" | |
| puts " --> #{ticket_white.to_a.sort.join(' ')} #{ticket_powerball}" | |
| end | |
| end |
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| package main | |
| import "fmt" | |
| import "math/rand" | |
| import "time" | |
| import "sync" | |
| import "os" | |
| import "strconv" | |
| import "sort" | |
| func randRange(r *rand.Rand, lo, hi int) int { | |
| randSpan := hi - lo + 1 | |
| return r.Intn(randSpan) + lo | |
| } | |
| func include(arr []int, x int) bool { | |
| for i := 0; i < len(arr); i++ { | |
| if arr[i] == x { | |
| return true | |
| } | |
| } | |
| return false | |
| } | |
| func randTicket(r *rand.Rand) []int { | |
| ticket := make([]int, 6) | |
| for i := 0; i < 5; i++ { | |
| ball := randRange(r, 1, 69) | |
| if include(ticket, ball) { | |
| i-- | |
| continue | |
| } | |
| ticket[i] = ball | |
| } | |
| ticket[5] = 100 + randRange(r, 1, 26) | |
| return ticket | |
| } | |
| func randTicketGroup(r *rand.Rand, count int) [][]int { | |
| tickets := make([][]int, count) | |
| for i := 0; i < count; i++ { | |
| tickets[i] = randTicket(r) | |
| } | |
| return tickets | |
| } | |
| func combinations(arr []int) <-chan []int { | |
| yield := make(chan []int) | |
| go func() { | |
| for i := 0; i < len(arr); i++ { | |
| for j := i + 1; j < len(arr); j++ { | |
| yield <- []int { arr[i], arr[j] } | |
| } | |
| } | |
| close(yield) | |
| }() | |
| return yield | |
| } | |
| func subsetEqual(left, right []int) bool { | |
| return ((left[0] == right[0]) && (left[1] == right[1])) || ((left[0] == right[1]) && (left[1] == right[0])) | |
| } | |
| func dupSubsetCount(tickets [][]int) int { | |
| dupCount := 0 | |
| subsets := make([][]int, 0) | |
| for _, ticket := range tickets { | |
| for subset := range combinations(ticket) { | |
| subsets = append(subsets, subset) | |
| } | |
| } | |
| for i := 0; i < len(subsets); i++ { | |
| for j := i + 1; j < len(subsets); j++ { | |
| if subsetEqual(subsets[i], subsets[j]) { | |
| dupCount += 1 | |
| } | |
| } | |
| } | |
| return dupCount | |
| } | |
| func printGroup(dupCount int, ticketGroup [][]int) { | |
| fmt.Fprintf(os.Stderr, "Pairs: %d\n", dupCount) | |
| fmt.Println("--------------------------------------------------------------------------------") | |
| fmt.Printf("Pairs: %d\n", dupCount) | |
| fmt.Println("--------------------------------------------------------------------------------") | |
| for i := 0; i < len(ticketGroup); i++ { | |
| ticket := ticketGroup[i] | |
| ticket[len(ticket) - 1] -= 100 | |
| sortedBalls := ticket[0:5] | |
| sort.Ints(sortedBalls) | |
| ticket = append(sortedBalls, ticket[5]) | |
| ticketNum := i + 1 | |
| if ticketNum < 10 { | |
| fmt.Print(" " + strconv.Itoa(ticketNum)) | |
| } else { | |
| fmt.Print(strconv.Itoa(ticketNum)) | |
| } | |
| fmt.Print(" [") | |
| for j := 0; j < len(ticket); j++ { | |
| if (j != 0) { | |
| fmt.Print(" ") | |
| } | |
| if ticket[j] < 10 { | |
| fmt.Print(strconv.Itoa(ticket[j]) + " ") | |
| } else { | |
| fmt.Print(strconv.Itoa(ticket[j])) | |
| } | |
| } | |
| fmt.Print("]\n") | |
| } | |
| } | |
| func searchTicketGroups(mutex *sync.Mutex, ticketCount int, minCount *int) { | |
| r := rand.New(rand.NewSource(time.Now().UnixNano())) | |
| for { | |
| ticketGroup := randTicketGroup(r, ticketCount) | |
| dupCount := dupSubsetCount(ticketGroup) | |
| if dupCount < *minCount { | |
| *minCount = dupCount | |
| mutex.Lock() | |
| printGroup(dupCount, ticketGroup) | |
| mutex.Unlock() | |
| } | |
| } | |
| } | |
| func main() { | |
| if len(os.Args) < 2 { | |
| fmt.Println("Specify ticket count.") | |
| return | |
| } | |
| if len(os.Args) < 3 { | |
| fmt.Println("Specify worker count.") | |
| return | |
| } | |
| ticketCount, _ := strconv.Atoi(os.Args[1]) | |
| workerCount, _ := strconv.Atoi(os.Args[2]) | |
| mutex := &sync.Mutex{} | |
| minCount := 9999 | |
| for i := 0; i < workerCount; i++ { | |
| go searchTicketGroups(mutex, ticketCount, &minCount) | |
| } | |
| <-make(chan bool) | |
| } |
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| require 'set' | |
| require 'pp' | |
| def rand_range(lo, hi) | |
| rand lo..hi | |
| end | |
| def random_ticket | |
| ticket = [] | |
| 5.times do | |
| ball = rand_range(1, 69) | |
| redo if ticket.include? ball | |
| ticket << ball | |
| end | |
| ticket << rand_range(1, 26) | |
| end | |
| def dup_subset_count(tickets, subset_size) | |
| dup_count = 0 | |
| subsets = tickets.map { |ticket| | |
| ticket.combination(subset_size).to_a | |
| }.flatten(1) | |
| unique = Set.new | |
| subsets.each do |subset| | |
| if !unique.add?(subset) | |
| dup_count += 1 | |
| end | |
| end | |
| return dup_count | |
| end | |
| def create_valid_ticket_group(count) | |
| min_count = 9999 | |
| loop do | |
| group = (1..count).to_a.map { random_ticket } | |
| dup_count = dup_subset_count(group, 2) | |
| if dup_count < min_count | |
| min_count = dup_count | |
| puts "-" * 80 | |
| puts "Duplicate subsets: #{min_count}" | |
| puts "-" * 80 | |
| pp group | |
| end | |
| end | |
| end | |
| pp create_valid_ticket_group(80) |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment