The 16th offline real-time how to write reference problem to solve with Python

The problem is here. http://nabetani.sakura.ne.jp/hena/ord16lcove/

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

def cut(m):
    '''Search a maximum rectangle area on 0 at the upper left corner'''
    area = 0
    x = m[0].index('BLACK')
    for y in xrange(1, len(m)):
        if 'BLACK' in m[y][:x]:
            area = max(area, x * y)
            x = m[y].index('BLACK')
    return area

def solve(data):
    points = [map(int, p) for p in data.split(',')]
    points_x, points_y = zip(*points)
    min_x, min_y = min(points_x), min(points_y)
    max_x, max_y = max(points_x), max(points_y)
    w, h = (max_x - min_x + 1), (max_y - min_y + 1)
    area = w * h
    if area == 1: return str(3)
    m = map(list, [['WHITE'] * w] * h)
    for x, y in points: m[y - min_y][x - min_x] = 'BLACK'
    c = max(cut(m),                             # original   for upper left
            cut(m[::-1]),                       # reverse Y  for lower left
            cut([x[::-1] for x in m]),          # reverse X  for upper right
            cut([x[::-1] for x in m[::-1]]))    # reverse XY for lower right
    return str(area - c) if c > 0 else str(area + 1) if area < 10 * 10 else '-'

def test(data, correct):
    answer = solve(data)
    print "OK" if answer == correct else "NG", answer, correct, data

if __name__ == "__main__":
    0, test( "41,33,26,55,74,58,68", "39" );
    1, test( "00,99,09,90", "-" );
    2, test( "09", "3" );
    3, test( "05,05,05", "3" );
    4, test( "45", "3" );
    5, test( "38,39", "3" );
    6, test( "38,47", "3" );
    7, test( "45,66", "4" );
    8, test( "12,34,56,78", "33" );
    9, test( "12,34,56,78,45", "37" );
    10, test( "00,09,00", "11" );
    11, test( "00,90", "11" );
    12, test( "99,09", "11" );
    13, test( "99,90", "11" );
    14, test( "11,12,21,22", "5" );
    15, test( "42,45,92,95,83,62", "25" );
    16, test( "42,45,92,83,62", "14" );
    17, test( "34,38,78,74,56,35,77,48,54", "26" );
    18, test( "38,78,74,56,35,77,48,54", "23" );
    19, test( "31,41,21,71,21", "7" );
    20, test( "46,45,42,44,45", "6" );
    21, test( "00,99,09", "19" );
    22, test( "99,09,90,24", "64" );
    23, test( "99,16,61,34,17,24,42,26,18,71,19,91,81,43,33,62,52,25", "75" );  
    24, test( "55,43,16,91,61,19,24,18,33,34,71,81,42,62,52,26,17,25", "53" );  
    25, test( "71,26,81,62,17,16,25,42,33,52,19,18,91,24,61,34,43", "45" );
    26, test( "39,49,19,93,78,58,48,91,95,29,68,92,86,87,94,77", "39" );
    27, test( "69,89,25,26,58,12,37,36,68,24,11,13,48,14,79", "37" );
    28, test( "58,67,92,38,83,29,91,76,84,57,75,48,85,19,66", "51" );
    29, test( "00,83,76,85,48,19,75,29,92,57,66,67,91,58,38,84", "91" );
    30, test( "11,92,57,38,58,66,91,67,84,48,83,19,75,85,76,29", "72" );
    31, test( "36,07,45", "9" );
    32, test( "57,23,24,74", "21" );
    33, test( "92,20,32,12,65", "39" );
    34, test( "24,54,66,48,54,15", "21" );
    35, test( "05,17,42,20,48,22,13", "39" );
    36, test( "53,84,55,56,25,14,84,43", "26" );
    37, test( "06,77,56,59,15,24,09,66,71", "51" );
    38, test( "53,36,47,45,45,67,66,46,63,75", "21" );
    39, test( "35,53,93,33,02,84,83,48,54,32,28", "50" );
    40, test( "55,74,32,84,41,64,24,44,15,14,26,53", "39" );
    41, test( "47,60,34,32,19,67,24,83,94,38,47,05,79", "88" );
    42, test( "63,32,42,74,66,64,35,41,74,25,48,62,44,54", "42" );
    43, test( "00,86,16,19,09,92,51,10,68,23,14,63,21,46,03", "91" );
    44, test( "56,46,54,14,15,25,53,84,58,85,44,37,54,76,26,76", "42" );
    45, test( "71,87,39,43,76,38,91,69,98,33,43,26,56,69,73,52,89", "66" );
    46, test( "43,26,84,64,52,48,36,23,66,53,41,57,76,36,84,57,35,41", "47" );  
    47, test( "81,02,85,93,36,46,80,27,72,28,02,99,13,41,36,40,18,97,38", "91" );
    48, test( "63,46,75,58,42,26,58,37,14,75,35,63,32,36,52,46,85,14,48,23", "47" );
    49, test( "66,92,64,12,17,33,10,28,75,05,81,05,42,86,52,57,56,78,87,81,10", "82" );
    50, test( "48,25,58,76,15,74,43,44,24,62,33,67,34,34,42,48,37,33,51,43,46,67", "50" );

Recommended Posts

The 16th offline real-time how to write reference problem to solve with Python
The 19th offline real-time how to write reference problem to solve with Python
The 15th offline real-time how to write reference problem in Python
The 14th offline real-time how to write reference problem in python
The 18th offline real-time how to write reference problem in Python
The 15th offline real-time I tried to solve the problem of how to write with python
The 16th offline real-time how to write problem was solved with Python
The 17th offline real-time how to write reference problem implemented in Python
The 15th offline real-time how to write problem was solved with python
The 14th offline real-time writing reference problem with Python
The 17th Offline Real-time How to Solve Writing Problems in Python
20th Offline Real-time How to Write Problems in Python
How to write offline real time I tried to solve the problem of F02 with Python
13th Offline Real-time How to Solve Writing Problems in Python
How to write offline real-time Solving E05 problems with Python
The 10th offline real-time writing reference problem. Implementation example by Python.
Offline real-time how to write Python implementation example of E15 problem
The 11th offline real-time writing reference problem. Implementation example by python.
How to write offline real time Solve F01 problems with Python
Answer to "Offline real-time how to write F02 problem"
The 18th offline real-time writing problem in Python
Answer to "Offline Real-time How to Write F01 Problem"
Answer to "Offline Real-time How to Write E13 Problem"
The 19th offline real-time writing problem in Python
How to write offline real time I tried to solve E11 with python
How to write offline real time I tried to solve E12 with python
Try to solve the internship assignment problem with Python
I tried to solve the problem with Python Vol.1
Part 1 I wrote the answer to the reference problem of how to write offline in real time in Python
The twelfth offline real-time writing reference problem. Implementation by python
Part 1 I wrote an example of the answer to the reference problem of how to write offline in real time in Python
Offline real-time how to write E11 ruby and python implementation example
How to write offline real time Solve E04 problems in Python
I wanted to solve the ABC164 A ~ D problem with Python
Try to solve the fizzbuzz problem with Keras
Try to solve the Python class inheritance problem
Try to solve the man-machine chart with Python
[Introduction to Python] How to write a character string with the format function
Try to solve the traveling salesman problem with a genetic algorithm (Python code)
[Introduction to Python] How to iterate with the range function?
I tried to solve the soma cube with python
[Python] How to specify the download location with youtube-dl
[Python] How to rewrite the table style with python-pptx [python-pptx]
Write to csv with Python
[Note] How to write QR code and description in the same image with python
I tried to simulate how the infection spreads with Python
I wanted to solve the Panasonic Programming Contest 2020 with Python
A story about how to deal with the CORS problem
How to get into the python development environment with Vagrant
[Introduction to Python] How to get data with the listdir function
How to write a Python class
Python: How to use async with
[Python] Write to csv file with Python
How to get the Python version
How to get started with Python
[Python] How to import the library
How to use FTP with Python
How to calculate date with python
I tried to solve the ant book beginner's edition with python
Try to solve the N Queens problem with SA of PyQUBO
[Python] Explains how to use the format function with an example