Programátorský úkol

[kojot4]

Řešil jsem to před lety na pohovoru v Javě, je to úkol, který jsem tehdá napsal snad na 3 třídy, přes 100 řádek kódu, a psal jsem to den. Teď jsem to po 3 letech, kdy si nepamatuji původní koncept zkusil znovu v Pythonu, a napsal jsem to na 17 řádek (podle mě by to šlo i kratší, ale to nebyl cíl),  a podle mě jsem zvolil mnohem lepší koncept řešení.

Problém
Máte obdelník/čtverec složený z čísel, a ten prolézáte jako had po směru hodinových ručiček do středu, a vypisujete čísla za sebou jako posloupnost. Důležité je to, že to nemusí být nutně čtverec, ale může to být i obdelník. Jazyk je na vás.

Příklad 1

Kód: [Vybrat]

print(snake(
    [[1,2],
     [3,4]]
))Výsledek:

Kód: [Vybrat]

[1, 2, 4, 3]
Příklad 2

Kód: [Vybrat]

print(snake(
    [[1,3,5,7,6],
     [2,5,8,2,5],
     [9,2,4,6,2],
     [5,7,8,1,2],
     [4,2,3,5,6],
     [8,6,5,4,2]]
))
Výsledek:

Kód: [Vybrat]

[1, 3, 5, 7, 6, 5, 2, 2, 6, 2, 4, 5, 6, 8, 4, 5, 9, 2, 5, 8, 2, 6, 1, 5, 3, 2, 7, 2, 4, 8]
Moje řešení - Python

Kód: [Vybrat]

def snake(mya):
    column = lambda a: [x[a] for x in mya]

    right = lambda inside : mya[inside][inside:-1-inside]
    down  = lambda inside : column(len(mya[0]) - inside - 1)[inside:-1-inside]
    left  = lambda inside : list(reversed(mya[len(column(0)) - inside - 1]))[inside:-1-inside]
    up    = lambda inside : list(reversed(column(inside)))[inside:-1-inside]

    output = []
    inside = 0
    while True:
        add = right(inside) + down(inside) + left(inside) + up(inside)
        if add:
            output += add
            inside += 1
        else:
            return output
Moje dotazy

• Opravdu je možné se zlepšit v programování cvičením třeba na www.codewars.com. Udělal jsem si tam asi 20 cvičení na různé algoritmy, a najednou mi přišlo, že mi to jde lépe a lépe. Přičemž jsem si vždycky myslel, že na to jako linux admin mozek nemám, teď prostě začínám pomalu přicházet na to, že to možná je hodně o cviku, že to že jsem to před lety dost mizerně zvládal je možná fakt, že jsem prostě málo cvičil a nemám v tom praxi, ne že jsem hloupej - což mě napadlo jako první.
• Trvalo mi to napsat 3-4 hodiny, jak si vedu?
• Co bych na tomhle kódu mohl zlepšit?
• Kdyžtak můžete nasdílet vlastní řešení v libovolném jazyce

Jo před lety mě jako programátora nevzali. Stále o programování uvažuji, i když dělám admina, ale je podle mě těžké být samouk. Ty codewars mi přijdou bezvadné v tom, že je tam úloha, člověk se to pokusí vyřešit, a pak se podívá, jak to vyřešili ostatní, ale zas je to jen na algoritmy, a přeci jenom programování je dnes ekosystém (frameworky, prostředí, testování, scrum)... Nicméně rád bych se naučil alespoň na úroveň mírně pokročilého v Pythonu, protože ten mě baví víc než Java, a částečně mě zajímá AI a BigData, kde je Python lídrem.

[Reklama]

[honzik]

Zajimava uloha.
1.

Opravdu je možné se zlepšit v programování cvičením

Ano
2. 30 minut, cekal jsem od sebe lepsi vykon.. holt uz je po pulnoci..
3. Prijde mi to celkem v pohode. Zlepsit muzes testovani (nefunguje to treba dobre pro lichy pocet radku)
4. Prikladam svoje reseni. V podstate to same, akorat misto hlidani "inside" se pouzije rekurze.

Kód: [Vybrat]

def snake(mya):
if not mya: return [] # empyt list
if len(mya)==1: return mya[0][:] # e.g. [[1,2,3]]
if len(mya[0])==1: return [row[0] for row in mya] # e.g. [[1],[2],[3]]
ret = mya[0][:] # top row
ret += [row[-1] for row in mya[1:-1]] # right col (without 1st and last elem)
ret += mya[-1][::-1] # reversed bottom row
ret += [row[0] for row in mya[::-1][1:-1]] # rev. left col (without 1st and last elem)
mya2 = [row[1:-1] for row in mya[1:-1]] # mya without "top layer"
ret += snake(mya2)
return ret


[Kolemjdouci]

Moje dotazy

• Opravdu je možné se zlepšit v programování cvičením třeba na www.codewars.com. Udělal jsem si tam asi 20 cvičení na různé algoritmy, a najednou mi přišlo, že mi to jde lépe a lépe. Přičemž jsem si vždycky myslel, že na to jako linux admin mozek nemám, teď prostě začínám pomalu přicházet na to, že to možná je hodně o cviku, že to že jsem to před lety dost mizerně zvládal je možná fakt, že jsem prostě málo cvičil a nemám v tom praxi, ne že jsem hloupej - což mě napadlo jako první.

Cvičení dělá mistra, a platí to i u "computer science". Na univerzitách je běžný postup že k naučení teorie jsou přednášky, ale prakticky si to osvojíte až na cvičeních - a bez cvičení složitou teorii buď nepochopíte vůbec, nebo jen velmi povrchně či špatně. Bez toho abyste odladil program (nebo spíš spoustu programů) který funguje na základě algoritmů sestavených podle teorie z přednášek si nemůžete být jistý že tu teorii chápete správně. A často bez odladěných programů nedostanete zápočet, a bez zápočtu nemůžete na zkoušku. Codewars mi připadají že mohou fungovat jako ta cvičení, ale obávám se že bez znalosti patřičné teorie se u složitějších problémů zaseknete a buď na tu teorii nakonec přijdete sám (bude to zdlouhavé), nebo si ji odněkud dostudujete, nebo to nevyřešíte vůbec.

• Trvalo mi to napsat 3-4 hodiny, jak si vedu?

S trochou cviku by to mělo mohlo být rychlejší, ale důležité je že se to nakonec podařilo.

• Co bych na tomhle kódu mohl zlepšit?

Python neznám, odpověď nechám na jiných.

• Kdyžtak můžete nasdílet vlastní řešení v libovolném jazyce

Tady je standardní ukecaná Java (ale použitá tak základním způsobem že by to šlo přímočaře přepsat do C):

Kód: [Vybrat]

public class Snake {

    public static int[] solve(int[][] input) {
        int height = input.length;
        int width = height == 0 ? 0 : input[0].length;
        int[] result = new int[width*height];
        int res = 0;
        int iterations = (Math.min(width, height) + 1) / 2;
        for (int i=0; i<iterations; i++) {
            for (int j=i; j<width-i; j++) {
                result[res++] = input[i][j];
            }
            for (int j=i+1; j<height-i; j++) {
                result[res++] = input[j][width-1-i];
            }
            for (int j=width-2-i; j>=i; j--) {
                result[res++] = input[height-1-i][j];
            }
            for (int j=height-2-i; j>i; j--) {
                result[res++] = input[j][i];
            }
        }
        if (res != result.length) {
            throw new IllegalStateException("res="+res+" != "+result.length);
        }
        return result;
    }

    public static void main(String[] args) {
        int[][] input = new int[][] {
            {1,3,5,7,6},
            {2,5,8,2,5},
            {9,2,4,6,2},
            {5,7,8,1,2},
            {4,2,3,5,6},
            {8,6,5,4,2}
        };
        int[] result = solve(input);
        for (int i : result) {
            System.out.println(i);
        }
    }
}


[python_lopata]

Tak já ti dám jedno řešení, abys měl o čem přemýšlet :

Kód: [Vybrat]

def snake(mya):
    output = []
    while mya:
        output.extend(mya[0])
        mya = map(list, zip(*mya[1:]))[::-1]
    return output
Upozorňuju, že je to python2, v pythonu3 by se to muselo napsat lehce jinak.

Je to dobré a elegantní řešení? Asi ne, takový kód si vyslouží pár WTF od člověka, který to bude studovat a navíc to není ani moc efektivní. Ale na pohovor asi dobré, zkoušející se alespoň nebudou nudit .

[noef]

Hezky ukol, donutil me si zase sahnout na Haskell. Tady je moje ctvrhodinka snazeni:

Kód: [Vybrat]

import Data.List

snakeWalk :: [[Integer]] -> [Integer]
snakeWalk (x:xs) = x ++ snakeWalk (reverse $ transpose xs)
snakeWalk [] = []


[Reklama]

[atarist]

Hezky ukol, donutil me si zase sahnout na Haskell. Tady je moje ctvrhodinka snazeni:

Kód: [Vybrat]

import Data.List

snakeWalk :: [[Integer]] -> [Integer]
snakeWalk (x:xs) = x ++ snakeWalk (reverse $ transpose xs)
snakeWalk [] = []


Haskell sice vubec neznam, ale jestli ten zapis znamena: vrat prvni radek pole spojeny s vysledkem rekurzivniho volani na otocenem poli bez prvniho radku, tak je to prudce elegantni a asi nejlepsi (ne nejefektivnejsi, ale to tady neva).

[noef]

...
Haskell sice vubec neznam, ale jestli ten zapis znamena: vrat prvni radek pole spojeny s vysledkem rekurzivniho volani na otocenem poli bez prvniho radku, tak je to prudce elegantni a asi nejlepsi (ne nejefektivnejsi, ale to tady neva).

Jop, to to dela. Ne no, neni to asi prehnane efektivni z pohledu vykonu* a asi ne ani nejvice idiomaticky Haskell (tipuju, ze pujde pouzit nejaka higherorder funkce, pripadne prepsat pointfree styl).

*: Pochybuji, ze to prekladac zvladne optimalizovat na uroven pruchodu polem v cyklu a vypisem primo pri provadeni.

PS: Tak nejaky pointfree convertor mi vytvoril tohle monstrum:

Kód: [Vybrat]

snakeWalk = fix ((`ap` tail) . (. head) . flip ((.) . (++)) . (. (reverse . transpose)))Osobne si myslim, ze neni vsude nutne cpat point-free, pokud to nezlepsi citelnost kodu.

[python_lopata]

Haskell sice vubec neznam, ale jestli ten zapis znamena: vrat prvni radek pole spojeny s vysledkem rekurzivniho volani na otocenem poli bez prvniho radku, tak je to prudce elegantni a asi nejlepsi (ne nejefektivnejsi, ale to tady neva).

noef neopisovat! Tak se zamysli, co dělá ten můj python, to stejné, jenom bez rekurze:

Kód: [Vybrat]

mya = map(list, zip(*mya[1:]))[::-1]
map(list, zip(*mya[1:])) je transpozice matice bez prvního řádku, [::-1] je otočení.

[noef]

Po pravde jsem si nebyl jisty co to Pythoni reseni dela (z fci map a zip bych to moc necekal, ze je to to stejne jako ten snippet z Haskellu). Na to, ze se v Pythonu udajne jede na citelnost, mi tohle jako nezasvecenemu moc citelne neprislo .

[v]

Pochybuji, ze to prekladac zvladne optimalizovat na uroven pruchodu polem v cyklu a vypisem primo pri provadeni.

co knihovna stream-fusion?

[aaa]

2. Trvalo mi to napsat 3-4 hodiny, jak si vedu?

Na pohovore chceme aspon myslienku niecoho takeho za 30 minut, takze by to chcelo zrychlit.
Vacsina algoritmickych problemov je o rozdeleni vstupu na mensie casti a poslani rovnakeho algoritmu na tieto casti. To nerobis, takze sa nadries s indexami a nie je na prvy pohlad zrejme, ze to funguje v kazdej situacii. Honzik sa o to snazi, ale riesi 4 strany namiesto jednej - to ma hned nuti zamysliet sa, ako funguje ten vstup, ktory nezvladas ty.
Najjednoduchsie riesenie je zobrat prvy riadok a otocit vstup o 90 stupnov, ako tu uz ti posledni robia.

Algoritmy su o korektnosti. Vzdy si skus najskor napisat nieco aj exponencialne, co zrejme funguje a az nasledne ries ako to spravit lepsie. Zrejme fungujuci algoritmus velmi pomoze pri testoch, ked ti staci vymysliet si vstupy a porovnat vystupy algoritmov, netreba pisat vystupy.

3. Co bych na tomhle kódu mohl zlepšit?

Hlavne otestovat ho, ako sa chova na obdlzniky ako 1xN a Nx1 a opravit to.

[kojot4]

Hezky ukol, donutil me si zase sahnout na Haskell. Tady je moje ctvrhodinka snazeni:

Kód: [Vybrat]

import Data.List

snakeWalk :: [[Integer]] -> [Integer]
snakeWalk (x:xs) = x ++ snakeWalk (reverse $ transpose xs)
snakeWalk [] = []


Haskell sice vubec neznam, ale jestli ten zapis znamena: vrat prvni radek pole spojeny s vysledkem rekurzivniho volani na otocenem poli bez prvniho radku, tak je to prudce elegantni a asi nejlepsi (ne nejefektivnejsi, ale to tady neva).

Mě by docela zajímalo, jestli ty vývojáře, co tu odstraňují první řádek a otáčí čtverec, jestli už někdy nějaký podobný algoritmus viděli, nebo jeho části a jenom to rychle zkombinovali, případně jestli to mají z nějaké teorie jak to řešit, nebo je to fakt za 10 minut napadlo jako úplně z nuly.

I když se zamýšlím, že třeba hodně dělá i to, že člověk zná možnosti, mě by nenapadlo, že je nějaký jednoduchý způsob jak celé to pole otočit o 90 stupňů, v životě jsem to neviděl, že by se to dělalo, tak prostě moje myšlenky ani tímto směrem nemohly jít.

[Fernet]

To je o matematickém základu. Pokud v dvourozměrném poli automaticky vidíš matici, tak k transpozici v tomto případě dojdeš během pár minut.

[Kolemjdouci]

To je o matematickém základu. Pokud v dvourozměrném poli automaticky vidíš matici, tak k transpozici v tomto případě dojdeš během pár minut.

Jen pro pořádek: tady se nepoužívá transpozice matice ale otočení, to jsou úplně jiné věci.

[Fernet]

Pravda. Ale nic to nemění na tom, že si řešení představí rychle ten, který v tom dvourozměrném poli vidí matici

Jsem si dovolil to řešení v Haskellu přepsat do Elixiru.

Kód: [Vybrat]

defmodule Snake do

  def snake_walk([]),           do: []
  def snake_walk([head | tail]) do
    head ++ (tail |> rotate_field |> snake_walk)
  end

  defp rotate_field(field) do
    field
    |> List.zip
    |> Enum.map(fn(x) -> Tuple.to_list(x) end)
    |> Enum.reverse
  end
end