860 lines
28 KiB
HTML
860 lines
28 KiB
HTML
<!DOCTYPE html>
|
||
<html lang="en">
|
||
<head>
|
||
<meta charset="UTF-8">
|
||
<meta name="viewport" content="width=device-width, initial-scale=1.0">
|
||
<title>Cut Rod Problem — Live Visualizer</title>
|
||
<style>
|
||
*, *::before, *::after { box-sizing: border-box; margin: 0; padding: 0; }
|
||
|
||
:root {
|
||
--bg: #0d1117;
|
||
--surf: #161b22;
|
||
--surf2: #21262d;
|
||
--border: #30363d;
|
||
--text: #e6edf3;
|
||
--dim: #7d8590;
|
||
--purple: #7c6aff;
|
||
--red: #ff6b6b;
|
||
--yellow: #ffd43b;
|
||
--green: #3fb950;
|
||
--blue: #58a6ff;
|
||
--orange: #f0883e;
|
||
--pink: #f778ba;
|
||
}
|
||
|
||
body {
|
||
font-family: -apple-system, BlinkMacSystemFont, 'Segoe UI', sans-serif;
|
||
background: var(--bg);
|
||
color: var(--text);
|
||
min-height: 100vh;
|
||
padding: 24px 16px;
|
||
}
|
||
|
||
/* ── HEADER ─────────────────────────────────── */
|
||
header {
|
||
text-align: center;
|
||
margin-bottom: 24px;
|
||
}
|
||
header h1 {
|
||
font-size: 1.9rem;
|
||
font-weight: 700;
|
||
background: linear-gradient(120deg, var(--purple), var(--pink), var(--red));
|
||
-webkit-background-clip: text;
|
||
-webkit-text-fill-color: transparent;
|
||
background-clip: text;
|
||
}
|
||
header p {
|
||
color: var(--dim);
|
||
font-size: 0.88rem;
|
||
margin-top: 4px;
|
||
}
|
||
|
||
/* ── CONTROLS ────────────────────────────────── */
|
||
.controls {
|
||
display: flex;
|
||
flex-wrap: wrap;
|
||
align-items: center;
|
||
gap: 12px;
|
||
justify-content: center;
|
||
background: var(--surf);
|
||
border: 1px solid var(--border);
|
||
border-radius: 12px;
|
||
padding: 14px 20px;
|
||
margin-bottom: 20px;
|
||
max-width: 1120px;
|
||
margin-left: auto;
|
||
margin-right: auto;
|
||
}
|
||
.ctrl-group {
|
||
display: flex;
|
||
align-items: center;
|
||
gap: 8px;
|
||
}
|
||
.ctrl-group label { color: var(--dim); font-size: 0.82rem; white-space: nowrap; }
|
||
input[type=number] {
|
||
width: 64px;
|
||
background: var(--surf2);
|
||
border: 1px solid var(--border);
|
||
color: var(--text);
|
||
padding: 6px 10px;
|
||
border-radius: 7px;
|
||
font-size: 0.9rem;
|
||
}
|
||
input[type=range] { width: 110px; accent-color: var(--purple); }
|
||
.speed-val { font-size: 0.8rem; color: var(--dim); min-width: 24px; }
|
||
.btn {
|
||
padding: 7px 18px;
|
||
border: none;
|
||
border-radius: 8px;
|
||
cursor: pointer;
|
||
font-size: 0.88rem;
|
||
font-weight: 600;
|
||
transition: opacity .15s, transform .1s;
|
||
}
|
||
.btn:active { transform: scale(.96); }
|
||
.btn-primary { background: var(--purple); color: #fff; }
|
||
.btn-primary:hover { opacity: .85; }
|
||
.btn-secondary { background: var(--surf2); color: var(--dim); border: 1px solid var(--border); }
|
||
.btn-secondary:hover { color: var(--text); border-color: #555; }
|
||
|
||
/* ── LAYOUT ──────────────────────────────────── */
|
||
.layout {
|
||
display: grid;
|
||
grid-template-columns: 1fr 320px;
|
||
gap: 16px;
|
||
max-width: 1120px;
|
||
margin: 0 auto;
|
||
}
|
||
@media (max-width: 800px) {
|
||
.layout { grid-template-columns: 1fr; }
|
||
}
|
||
|
||
/* ── PANEL ───────────────────────────────────── */
|
||
.panel {
|
||
background: var(--surf);
|
||
border: 1px solid var(--border);
|
||
border-radius: 12px;
|
||
padding: 18px 20px;
|
||
}
|
||
.panel + .panel { margin-top: 14px; }
|
||
.panel-title {
|
||
font-size: 0.72rem;
|
||
text-transform: uppercase;
|
||
letter-spacing: .09em;
|
||
color: var(--dim);
|
||
margin-bottom: 14px;
|
||
}
|
||
|
||
/* ── ROD VISUAL ──────────────────────────────── */
|
||
#rod-desc {
|
||
font-size: 0.84rem;
|
||
color: var(--dim);
|
||
margin-bottom: 10px;
|
||
min-height: 20px;
|
||
}
|
||
.rod-bar {
|
||
display: flex;
|
||
height: 64px;
|
||
border-radius: 8px;
|
||
overflow: hidden;
|
||
margin-bottom: 10px;
|
||
transition: all .25s;
|
||
}
|
||
.rod-seg {
|
||
display: flex;
|
||
align-items: center;
|
||
justify-content: center;
|
||
flex-direction: column;
|
||
font-weight: 700;
|
||
color: rgba(0,0,0,.75);
|
||
transition: all .25s;
|
||
min-width: 12px;
|
||
overflow: hidden;
|
||
}
|
||
.rod-seg .seg-len { font-size: .95rem; line-height: 1; }
|
||
.rod-seg .seg-price{ font-size: .65rem; opacity: .8; margin-top: 2px; }
|
||
.rod-cut {
|
||
width: 3px;
|
||
background: #fff;
|
||
box-shadow: 0 0 8px rgba(255,255,255,.7);
|
||
flex-shrink: 0;
|
||
}
|
||
#rod-subtext {
|
||
font-size: 0.82rem;
|
||
color: var(--dim);
|
||
min-height: 36px;
|
||
}
|
||
|
||
/* ── DP TABLE ────────────────────────────────── */
|
||
#dp-scroll { overflow-x: auto; }
|
||
.dp-tbl {
|
||
border-collapse: collapse;
|
||
font-size: .82rem;
|
||
min-width: 100%;
|
||
}
|
||
.dp-tbl th, .dp-tbl td {
|
||
border: 1px solid var(--border);
|
||
padding: 7px 11px;
|
||
text-align: center;
|
||
transition: background .25s, color .2s, box-shadow .2s;
|
||
min-width: 38px;
|
||
}
|
||
.dp-tbl th { background: var(--surf2); color: var(--dim); font-size: .72rem; }
|
||
.dp-tbl td.empty { color: #3d444d; }
|
||
.dp-tbl td.done { background: #122620; color: var(--green); font-weight: 600; }
|
||
.dp-tbl td.active { background: #2b2400; color: var(--yellow); font-weight: 700; box-shadow: inset 0 0 0 2px var(--yellow); }
|
||
.dp-tbl td.ref { background: #0d1f36; color: var(--blue); font-weight: 600; }
|
||
.dp-tbl td.s-done { background: #1a1030; color: var(--purple); font-weight: 600; }
|
||
.dp-tbl td.s-active { background: #2b2400; color: var(--yellow); font-weight: 700; box-shadow: inset 0 0 0 2px var(--yellow); }
|
||
|
||
/* ── PROGRESS ────────────────────────────────── */
|
||
.prog-row {
|
||
display: flex;
|
||
align-items: center;
|
||
gap: 10px;
|
||
margin-top: 12px;
|
||
}
|
||
.prog-bar {
|
||
flex: 1;
|
||
height: 4px;
|
||
background: var(--surf2);
|
||
border-radius: 2px;
|
||
overflow: hidden;
|
||
}
|
||
.prog-fill {
|
||
height: 100%;
|
||
background: linear-gradient(90deg, var(--purple), var(--pink));
|
||
transition: width .3s;
|
||
}
|
||
.prog-label { font-size: .72rem; color: var(--dim); white-space: nowrap; }
|
||
|
||
/* ── STEP INFO ───────────────────────────────── */
|
||
#step-msg {
|
||
font-size: .88rem;
|
||
line-height: 1.65;
|
||
min-height: 60px;
|
||
}
|
||
.formula-box {
|
||
margin-top: 10px;
|
||
padding: 9px 13px;
|
||
background: var(--bg);
|
||
border-radius: 7px;
|
||
font-family: 'SFMono-Regular', 'Consolas', monospace;
|
||
font-size: .85rem;
|
||
border-left: 3px solid var(--purple);
|
||
color: var(--text);
|
||
}
|
||
|
||
/* ── PSEUDOCODE ──────────────────────────────── */
|
||
.pseudo {
|
||
font-family: 'SFMono-Regular', 'Consolas', monospace;
|
||
font-size: .78rem;
|
||
line-height: 1.8;
|
||
background: var(--bg);
|
||
border-radius: 8px;
|
||
padding: 12px 14px;
|
||
}
|
||
.pseudo .ln {
|
||
display: block;
|
||
padding: 1px 6px;
|
||
border-radius: 4px;
|
||
transition: background .2s, color .2s;
|
||
color: var(--dim);
|
||
white-space: pre;
|
||
}
|
||
.pseudo .ln.hl {
|
||
background: #2b2400;
|
||
color: var(--yellow);
|
||
}
|
||
.pseudo .kw { color: var(--purple); }
|
||
.pseudo .num { color: var(--orange); }
|
||
|
||
/* ── PRICE TABLE ─────────────────────────────── */
|
||
#price-scroll { overflow-x: auto; }
|
||
.price-tbl {
|
||
border-collapse: collapse;
|
||
font-size: .78rem;
|
||
}
|
||
.price-tbl th, .price-tbl td {
|
||
border: 1px solid var(--border);
|
||
padding: 5px 9px;
|
||
text-align: center;
|
||
}
|
||
.price-tbl th { background: var(--surf2); color: var(--dim); }
|
||
.price-tbl td { color: var(--green); font-weight: 600; }
|
||
.price-tbl td.hl-price { background: #122620; box-shadow: inset 0 0 0 2px var(--green); }
|
||
|
||
/* ── RESULT ──────────────────────────────────── */
|
||
#result-panel {
|
||
display: none;
|
||
background: #0a1f12;
|
||
border: 1px solid #2d6a4f;
|
||
border-radius: 12px;
|
||
padding: 18px 20px;
|
||
margin-top: 14px;
|
||
}
|
||
.result-rod {
|
||
display: flex;
|
||
height: 72px;
|
||
border-radius: 8px;
|
||
overflow: hidden;
|
||
margin: 12px 0;
|
||
}
|
||
.result-seg {
|
||
display: flex;
|
||
flex-direction: column;
|
||
align-items: center;
|
||
justify-content: center;
|
||
font-weight: 700;
|
||
color: rgba(0,0,0,.8);
|
||
border-right: 2px solid rgba(0,0,0,.25);
|
||
min-width: 28px;
|
||
overflow: hidden;
|
||
transition: flex .4s;
|
||
}
|
||
.result-seg:last-child { border-right: none; }
|
||
.result-seg .r-len { font-size: 1rem; }
|
||
.result-seg .r-price { font-size: .68rem; opacity: .85; margin-top: 2px; }
|
||
.stats-row { display: flex; gap: 12px; flex-wrap: wrap; }
|
||
.stat {
|
||
background: var(--surf2);
|
||
border-radius: 8px;
|
||
padding: 10px 14px;
|
||
flex: 1;
|
||
min-width: 90px;
|
||
}
|
||
.stat .s-lbl { font-size: .7rem; color: var(--dim); margin-bottom: 4px; }
|
||
.stat .s-val { font-size: 1.3rem; font-weight: 700; color: var(--green); }
|
||
|
||
/* ── COLORS ──────────────────────────────────── */
|
||
.y { color: var(--yellow); }
|
||
.g { color: var(--green); }
|
||
.b { color: var(--blue); }
|
||
.r { color: var(--red); }
|
||
.p { color: var(--purple); }
|
||
.o { color: var(--orange); }
|
||
|
||
/* ── LEGEND ──────────────────────────────────── */
|
||
.legend {
|
||
display: flex;
|
||
flex-wrap: wrap;
|
||
gap: 10px 20px;
|
||
justify-content: center;
|
||
max-width: 1120px;
|
||
margin: 0 auto 20px;
|
||
padding: 12px 20px;
|
||
background: var(--surf);
|
||
border: 1px solid var(--border);
|
||
border-radius: 10px;
|
||
font-size: .78rem;
|
||
}
|
||
.legend-item {
|
||
display: flex;
|
||
align-items: center;
|
||
gap: 7px;
|
||
color: var(--dim);
|
||
}
|
||
.swatch {
|
||
width: 14px;
|
||
height: 14px;
|
||
border-radius: 3px;
|
||
flex-shrink: 0;
|
||
}
|
||
.swatch-outline {
|
||
width: 14px;
|
||
height: 14px;
|
||
border-radius: 3px;
|
||
flex-shrink: 0;
|
||
border: 2px solid;
|
||
}
|
||
|
||
/* ── EXPLAINER ───────────────────────────────── */
|
||
.explainer {
|
||
max-width: 1120px;
|
||
margin: 20px auto 0;
|
||
display: grid;
|
||
grid-template-columns: repeat(3, 1fr);
|
||
gap: 14px;
|
||
}
|
||
@media (max-width: 800px) {
|
||
.explainer { grid-template-columns: 1fr; }
|
||
}
|
||
.exp-card {
|
||
background: var(--surf);
|
||
border: 1px solid var(--border);
|
||
border-radius: 12px;
|
||
padding: 18px 20px;
|
||
}
|
||
.exp-card h3 {
|
||
font-size: .8rem;
|
||
text-transform: uppercase;
|
||
letter-spacing: .08em;
|
||
color: var(--dim);
|
||
margin-bottom: 12px;
|
||
}
|
||
.exp-card p, .exp-card li {
|
||
font-size: .83rem;
|
||
line-height: 1.65;
|
||
color: #a0aab4;
|
||
}
|
||
.exp-card ul { padding-left: 16px; }
|
||
.exp-card li { margin-bottom: 5px; }
|
||
.exp-card code {
|
||
font-family: 'SFMono-Regular', 'Consolas', monospace;
|
||
font-size: .8rem;
|
||
background: var(--bg);
|
||
padding: 1px 5px;
|
||
border-radius: 4px;
|
||
color: var(--orange);
|
||
}
|
||
.exp-card .accent { color: var(--text); font-weight: 600; }
|
||
</style>
|
||
</head>
|
||
<body>
|
||
|
||
<header>
|
||
<h1>Cut Rod Problem</h1>
|
||
<p>Bottom-Up Dynamic Programming — step-by-step live visualization</p>
|
||
</header>
|
||
|
||
<div class="controls">
|
||
<div class="ctrl-group">
|
||
<label>Rod Length</label>
|
||
<input type="number" id="inp-n" value="10" min="1" max="25">
|
||
</div>
|
||
<div class="ctrl-group">
|
||
<label>Speed</label>
|
||
<input type="range" id="inp-speed" min="1" max="10" value="5">
|
||
<span class="speed-val" id="speed-lbl">5×</span>
|
||
</div>
|
||
<button class="btn btn-primary" id="btn-play">▶ Play</button>
|
||
<button class="btn btn-secondary" id="btn-step">⏭ Step</button>
|
||
<button class="btn btn-secondary" id="btn-back">⏮ Back</button>
|
||
<button class="btn btn-secondary" id="btn-reset">↺ Reset</button>
|
||
</div>
|
||
|
||
<!-- LEGEND -->
|
||
<div class="legend">
|
||
<div class="legend-item">
|
||
<div class="swatch" style="background:var(--red)"></div>
|
||
<span>Cut piece — sells for <strong style="color:var(--text)">p[i]</strong></span>
|
||
</div>
|
||
<div class="legend-item">
|
||
<div class="swatch" style="background:var(--blue)"></div>
|
||
<span>Remainder — best revenue already known as <strong style="color:var(--text)">r[j−i]</strong></span>
|
||
</div>
|
||
<div class="legend-item">
|
||
<div class="swatch-outline" style="border-color:var(--yellow);background:#2b2400"></div>
|
||
<span><strong style="color:var(--yellow)">Yellow cell</strong> — currently being computed</span>
|
||
</div>
|
||
<div class="legend-item">
|
||
<div class="swatch" style="background:#122620"></div>
|
||
<span><strong style="color:var(--green)">Green cell</strong> — finalized value</span>
|
||
</div>
|
||
<div class="legend-item">
|
||
<div class="swatch" style="background:#0d1f36"></div>
|
||
<span><strong style="color:var(--blue)">Blue cell</strong> — value being read (r[j−i])</span>
|
||
</div>
|
||
<div class="legend-item">
|
||
<div class="swatch" style="background:#1a1030"></div>
|
||
<span><strong style="color:var(--purple)">Purple cell</strong> — optimal first cut stored in s[j]</span>
|
||
</div>
|
||
</div>
|
||
|
||
<div class="layout">
|
||
|
||
<!-- LEFT COLUMN -->
|
||
<div>
|
||
<div class="panel">
|
||
<div class="panel-title">Rod Visualization</div>
|
||
<div id="rod-desc"></div>
|
||
<div class="rod-bar" id="rod-bar"></div>
|
||
<div id="rod-subtext"></div>
|
||
</div>
|
||
|
||
<div class="panel">
|
||
<div class="panel-title">DP Table</div>
|
||
<div id="dp-scroll"></div>
|
||
<div class="prog-row">
|
||
<div class="prog-bar"><div class="prog-fill" id="prog-fill" style="width:0%"></div></div>
|
||
<span class="prog-label" id="prog-lbl">0 / 0</span>
|
||
</div>
|
||
</div>
|
||
|
||
<div id="result-panel">
|
||
<div class="panel-title" style="color:var(--green)">Optimal Solution</div>
|
||
<div class="result-rod" id="result-rod"></div>
|
||
<div class="stats-row" id="stats-row"></div>
|
||
</div>
|
||
</div>
|
||
|
||
<!-- RIGHT COLUMN -->
|
||
<div>
|
||
<div class="panel">
|
||
<div class="panel-title">Current Step</div>
|
||
<div id="step-msg"><span style="color:var(--dim)">Press ▶ Play to begin…</span></div>
|
||
</div>
|
||
|
||
<div class="panel">
|
||
<div class="panel-title">Algorithm</div>
|
||
<div class="pseudo" id="pseudo">
|
||
<span class="ln" data-ln="1"><span class="kw">def</span> bottom_up_cut_rod(p, n):</span>
|
||
<span class="ln" data-ln="2"> r = [<span class="num">0</span>] * (n + <span class="num">1</span>) <span style="color:#444"># r[0]=0</span></span>
|
||
<span class="ln" data-ln="3"> <span class="kw">for</span> j <span class="kw">in</span> range(<span class="num">1</span>, n+<span class="num">1</span>):</span>
|
||
<span class="ln" data-ln="4"> q = <span class="num">-∞</span></span>
|
||
<span class="ln" data-ln="5"> <span class="kw">for</span> i <span class="kw">in</span> range(<span class="num">1</span>, j+<span class="num">1</span>):</span>
|
||
<span class="ln" data-ln="6"> q = max(q, p[i] + r[j-i])</span>
|
||
<span class="ln" data-ln="7"> r[j] = q</span>
|
||
<span class="ln" data-ln="8"> <span class="kw">return</span> r[n]</span>
|
||
</div>
|
||
</div>
|
||
|
||
<div class="panel">
|
||
<div class="panel-title">Price Table (p[i])</div>
|
||
<div id="price-scroll"></div>
|
||
</div>
|
||
</div>
|
||
|
||
</div>
|
||
|
||
<!-- EXPLAINER -->
|
||
<div class="explainer">
|
||
|
||
<div class="exp-card">
|
||
<h3>The Problem</h3>
|
||
<p>
|
||
You have a rod of length <span class="accent">n</span> inches and a price table
|
||
<code>p[1..n]</code> where <code>p[i]</code> is what a piece of length <code>i</code> sells for.
|
||
You can cut the rod into any combination of integer lengths. The goal is to
|
||
<span class="accent">maximize total revenue</span>.
|
||
</p>
|
||
<br>
|
||
<p>
|
||
A rod of length 4 sold whole earns $9, but two pieces of length 2 earn $5 + $5 = <span class="accent">$10</span>.
|
||
Finding the best combination by brute force takes O(2ⁿ) time — dynamic programming reduces this to <span class="accent">O(n²)</span>.
|
||
</p>
|
||
</div>
|
||
|
||
<div class="exp-card">
|
||
<h3>How the Algorithm Works</h3>
|
||
<ul>
|
||
<li><span class="accent">Build up from small rods.</span> Compute the best revenue for length 1, then 2, then 3 … up to n. Each answer reuses earlier answers.</li>
|
||
<li><span class="accent">For each length j</span>, try every possible first cut at position <code>i = 1 … j</code>. The candidate revenue is <code>p[i] + r[j−i]</code>: sell the first piece and optimally cut the rest.</li>
|
||
<li><span class="accent">Store the best.</span> <code>r[j]</code> holds the maximum over all cuts. <code>s[j]</code> records which cut produced that maximum — used later to reconstruct the actual pieces.</li>
|
||
<li><span class="accent">Reconstruct.</span> Follow <code>s[n] → s[n−s[n]] → …</code> to read off the optimal cut sequence.</li>
|
||
</ul>
|
||
</div>
|
||
|
||
<div class="exp-card">
|
||
<h3>Reading the Visualization</h3>
|
||
<ul>
|
||
<li><span class="accent">Rod bar:</span> the red segment is the piece being sold now (length <code>i</code>); the blue segment is the remainder whose best revenue is already in the table.</li>
|
||
<li><span class="accent">DP table row r[j]:</span> fills left-to-right. The yellow cell is being computed right now; blue cells are the ones being looked up.</li>
|
||
<li><span class="accent">DP table row s[j]:</span> once a cell is finalized (purple), it tells you the optimal first cut for that rod length.</li>
|
||
<li><span class="accent">Pseudocode:</span> the highlighted line shows exactly which line of the algorithm the current step corresponds to.</li>
|
||
<li><span class="accent">Optimal Solution</span> (shown at the end): the colored bar divides the rod into its best pieces, each labeled with its length and sale price.</li>
|
||
</ul>
|
||
</div>
|
||
|
||
</div>
|
||
|
||
<script>
|
||
// ── DATA ────────────────────────────────────────
|
||
const PRICE_DATA = [0,1,5,8,9,10,17,17,20,24,30,33,31,31,31,40,39,20,45,42,46,70,76,77,80,85,90,95,100,110,120,111,200,678];
|
||
|
||
const SEG_COLS = [
|
||
'#FF6B6B','#FFD43B','#69DB7C','#74C0FC','#FF922B',
|
||
'#DA77F2','#38D9A9','#F783AC','#A9E34B','#63E6BE',
|
||
'#FFA94D','#748FFC','#4DABF7','#F06595','#20C997',
|
||
'#E599F7','#FFC078','#6BCB77','#4D96FF','#CC5DE8',
|
||
'#FFD93D','#6BCBF7','#FF9F43','#A29BFE','#55EFC4',
|
||
];
|
||
|
||
// ── STEP BUILDER ─────────────────────────────────
|
||
function buildSteps(prices, n) {
|
||
const steps = [];
|
||
const r = new Array(n + 1).fill(null);
|
||
const s = new Array(n + 1).fill(null);
|
||
r[0] = 0;
|
||
|
||
steps.push({
|
||
type:'init', r:[...r], s:[...s], j:null, i:null, pseudo:2,
|
||
msg:`<span class="g">Initialize:</span> r[0] = 0 — a rod of length 0 earns nothing.`,
|
||
formula:`r[0] = 0`
|
||
});
|
||
|
||
for (let j = 1; j <= n; j++) {
|
||
let q = -Infinity;
|
||
|
||
steps.push({
|
||
type:'start_j', r:[...r], s:[...s], j, i:null, pseudo:3,
|
||
msg:`<span class="y">j = ${j}:</span> Computing best revenue for a rod of length <span class="y">${j}</span>.`,
|
||
formula:`r[${j}] = max(p[i] + r[${j}−i]) for i = 1…${j}`
|
||
});
|
||
|
||
steps.push({
|
||
type:'init_q', r:[...r], s:[...s], j, i:null, pseudo:4,
|
||
msg:`Set q = −∞ — will track the best candidate for <span class="y">r[${j}]</span>.`,
|
||
formula:`q = −∞`
|
||
});
|
||
|
||
for (let i = 1; i <= j; i++) {
|
||
const rji = r[j - i] ?? 0;
|
||
const candidate = prices[i] + rji;
|
||
const isBetter = candidate > q;
|
||
|
||
steps.push({
|
||
type:'try_cut', r:[...r], s:[...s], j, i, candidate, q, isBetter, pseudo:6,
|
||
msg:`Try cut at <span class="b">i = ${i}</span>: p[${i}] + r[${j-i}] = <span class="b">${prices[i]}</span> + <span class="b">${rji}</span> = <span class="${isBetter?'g':'r'}">${candidate}</span>${isBetter?' <span class="g">✓ new best</span>':''}`,
|
||
formula:`p[${i}] + r[${j-i}] = ${prices[i]} + ${rji} = ${candidate}`
|
||
});
|
||
|
||
if (isBetter) {
|
||
q = candidate;
|
||
s[j] = i;
|
||
}
|
||
}
|
||
|
||
r[j] = q;
|
||
|
||
steps.push({
|
||
type:'set_r', r:[...r], s:[...s], j, i:s[j], pseudo:7,
|
||
msg:`<span class="g">r[${j}] = ${q}</span> — best first cut is at <span class="p">${s[j]}</span>, leaving remainder <span class="b">${j - s[j]}</span>.`,
|
||
formula:`r[${j}] = ${q} (s[${j}] = ${s[j]})`
|
||
});
|
||
}
|
||
|
||
// Reconstruct optimal cuts
|
||
const cuts = [];
|
||
let rem = n;
|
||
while (rem > 0 && s[rem] != null) { cuts.push(s[rem]); rem -= s[rem]; }
|
||
|
||
steps.push({
|
||
type:'done', r:[...r], s:[...s], j:null, i:null, cuts, pseudo:8,
|
||
msg:`<span class="g">Done!</span> Maximum revenue for length ${n} is <span class="g">${r[n]}</span>.`,
|
||
formula:`Optimal cuts: [${cuts.join(', ')}]`
|
||
});
|
||
|
||
return steps;
|
||
}
|
||
|
||
// ── STATE ─────────────────────────────────────────
|
||
let steps = [], idx = 0, playing = false, timer = null, N = 10;
|
||
|
||
// ── RENDER HELPERS ────────────────────────────────
|
||
function getDelay() {
|
||
const s = parseInt(document.getElementById('inp-speed').value);
|
||
return Math.max(40, 1300 - s * 120);
|
||
}
|
||
|
||
function renderPriceTable(prices, n, hiI) {
|
||
const lim = Math.min(n, prices.length - 1);
|
||
let h = '<table class="price-tbl"><tr><th>i</th>';
|
||
for (let i = 1; i <= lim; i++) h += `<th>${i}</th>`;
|
||
h += '</tr><tr><th>p[i]</th>';
|
||
for (let i = 1; i <= lim; i++) {
|
||
const cls = i === hiI ? ' class="hl-price"' : '';
|
||
h += `<td${cls}>${prices[i]}</td>`;
|
||
}
|
||
h += '</tr></table>';
|
||
document.getElementById('price-scroll').innerHTML = h;
|
||
}
|
||
|
||
function renderDpTable(r, s, n, activeJ, refJI) {
|
||
let h = '<table class="dp-tbl"><tr><th>j</th>';
|
||
for (let j = 0; j <= n; j++) h += `<th>${j}</th>`;
|
||
h += '</tr>';
|
||
|
||
// r row
|
||
h += '<tr><th>r[j]</th>';
|
||
for (let j = 0; j <= n; j++) {
|
||
let cls = 'empty'; let val = '—';
|
||
if (r[j] !== null) { cls = 'done'; val = r[j]; }
|
||
if (j === activeJ) cls = 'active';
|
||
if (j === refJI && j !== activeJ && r[j] !== null) cls = 'ref';
|
||
h += `<td class="${cls}">${val}</td>`;
|
||
}
|
||
h += '</tr>';
|
||
|
||
// s row
|
||
h += '<tr><th>s[j]</th>';
|
||
for (let j = 0; j <= n; j++) {
|
||
let cls = 'empty'; let val = '—';
|
||
if (s[j] !== null) { cls = 's-done'; val = s[j]; }
|
||
if (j === activeJ) cls = 's-active';
|
||
h += `<td class="${cls}">${val}</td>`;
|
||
}
|
||
h += '</tr></table>';
|
||
|
||
document.getElementById('dp-scroll').innerHTML = h;
|
||
}
|
||
|
||
function renderRod(j, i, r, prices) {
|
||
const bar = document.getElementById('rod-bar');
|
||
const desc = document.getElementById('rod-desc');
|
||
const sub = document.getElementById('rod-subtext');
|
||
bar.innerHTML = '';
|
||
|
||
if (!j) { desc.innerHTML = ''; sub.innerHTML = ''; return; }
|
||
|
||
desc.innerHTML = `Rod of length <span class="y">${j}</span>`;
|
||
|
||
if (i === null) {
|
||
// Whole rod, no cut shown
|
||
const seg = document.createElement('div');
|
||
seg.className = 'rod-seg';
|
||
seg.style.cssText = `background:${SEG_COLS[j % SEG_COLS.length]};flex:${j}`;
|
||
seg.innerHTML = `<span class="seg-len">${j}</span>`;
|
||
bar.appendChild(seg);
|
||
sub.innerHTML = '';
|
||
return;
|
||
}
|
||
|
||
// Left piece
|
||
const left = document.createElement('div');
|
||
left.className = 'rod-seg';
|
||
left.style.cssText = `background:var(--red);flex:${i}`;
|
||
left.innerHTML = `<span class="seg-len">${i}</span><span class="seg-price">$${prices[i]}</span>`;
|
||
bar.appendChild(left);
|
||
|
||
const remainder = j - i;
|
||
if (remainder > 0) {
|
||
const cut = document.createElement('div');
|
||
cut.className = 'rod-cut';
|
||
bar.appendChild(cut);
|
||
|
||
const right = document.createElement('div');
|
||
right.className = 'rod-seg';
|
||
right.style.cssText = `background:var(--blue);flex:${remainder}`;
|
||
const rVal = r[remainder] ?? 0;
|
||
right.innerHTML = `<span class="seg-len">${remainder}</span><span class="seg-price">r=${rVal}</span>`;
|
||
bar.appendChild(right);
|
||
}
|
||
|
||
const rji = r[j - i] ?? 0;
|
||
sub.innerHTML =
|
||
`<span style="color:var(--red)">■</span> Cut piece: length <b>${i}</b>, price = <b>$${prices[i]}</b>` +
|
||
` <span style="color:var(--blue)">■</span> Remainder: length <b>${j-i}</b>, best revenue = <b>${rji}</b>`;
|
||
}
|
||
|
||
function renderResult(cuts, r, prices, n) {
|
||
const panel = document.getElementById('result-panel');
|
||
const rod = document.getElementById('result-rod');
|
||
const stats = document.getElementById('stats-row');
|
||
panel.style.display = 'block';
|
||
rod.innerHTML = '';
|
||
|
||
cuts.forEach((len, k) => {
|
||
const seg = document.createElement('div');
|
||
seg.className = 'result-seg';
|
||
seg.style.cssText = `background:${SEG_COLS[k % SEG_COLS.length]};flex:${len}`;
|
||
seg.innerHTML = `<span class="r-len">${len}"</span><span class="r-price">$${prices[len]}</span>`;
|
||
rod.appendChild(seg);
|
||
});
|
||
|
||
const revenue = r[n];
|
||
const nCuts = cuts.length - 1;
|
||
stats.innerHTML = `
|
||
<div class="stat"><div class="s-lbl">Best Revenue</div><div class="s-val">$${revenue}</div></div>
|
||
<div class="stat"><div class="s-lbl">Cuts Made</div><div class="s-val">${nCuts}</div></div>
|
||
<div class="stat"><div class="s-lbl">Pieces</div><div class="s-val" style="font-size:.95rem">${cuts.join(' + ')}</div></div>
|
||
`;
|
||
}
|
||
|
||
function highlightPseudo(ln) {
|
||
document.querySelectorAll('#pseudo .ln').forEach(el => {
|
||
el.classList.toggle('hl', parseInt(el.dataset.ln) === ln);
|
||
});
|
||
}
|
||
|
||
// ── APPLY STEP ────────────────────────────────────
|
||
function applyStep(step) {
|
||
const { type, r, s, j, i, msg, formula, pseudo, cuts } = step;
|
||
|
||
// Step info
|
||
document.getElementById('step-msg').innerHTML =
|
||
msg + (formula ? `<div class="formula-box">${formula}</div>` : '');
|
||
|
||
// Pseudocode highlight
|
||
highlightPseudo(pseudo);
|
||
|
||
// Determine referenced cell in DP table
|
||
const refCell = (type === 'try_cut') ? j - i : null;
|
||
renderDpTable(r, s, N, (type === 'done' || type === 'init') ? null : j, refCell);
|
||
|
||
// Rod
|
||
if (type === 'init' || type === 'done') {
|
||
renderRod(null, null, r, PRICE_DATA);
|
||
} else if (type === 'start_j' || type === 'set_r' || type === 'init_q') {
|
||
renderRod(j, null, r, PRICE_DATA);
|
||
} else if (type === 'try_cut') {
|
||
renderRod(j, i, r, PRICE_DATA);
|
||
}
|
||
|
||
// Price table highlight
|
||
renderPriceTable(PRICE_DATA, N, type === 'try_cut' ? i : null);
|
||
|
||
// Result
|
||
if (type === 'done') {
|
||
renderResult(cuts, r, PRICE_DATA, N);
|
||
stopPlay();
|
||
} else {
|
||
document.getElementById('result-panel').style.display = 'none';
|
||
}
|
||
|
||
// Progress
|
||
const pct = steps.length > 1 ? (idx / (steps.length - 1)) * 100 : 0;
|
||
document.getElementById('prog-fill').style.width = pct + '%';
|
||
document.getElementById('prog-lbl').textContent = `${idx + 1} / ${steps.length}`;
|
||
}
|
||
|
||
// ── PLAYBACK ──────────────────────────────────────
|
||
function stopPlay() {
|
||
playing = false;
|
||
clearTimeout(timer);
|
||
document.getElementById('btn-play').textContent = '▶ Play';
|
||
}
|
||
|
||
function advance() {
|
||
if (idx < steps.length - 1) {
|
||
idx++;
|
||
applyStep(steps[idx]);
|
||
if (playing && idx < steps.length - 1) {
|
||
timer = setTimeout(advance, getDelay());
|
||
}
|
||
}
|
||
}
|
||
|
||
function init() {
|
||
N = Math.max(1, Math.min(25, parseInt(document.getElementById('inp-n').value) || 10));
|
||
steps = buildSteps(PRICE_DATA, N);
|
||
idx = 0;
|
||
stopPlay();
|
||
document.getElementById('result-panel').style.display = 'none';
|
||
renderPriceTable(PRICE_DATA, N, null);
|
||
applyStep(steps[0]);
|
||
}
|
||
|
||
// ── EVENTS ────────────────────────────────────────
|
||
document.getElementById('btn-play').addEventListener('click', () => {
|
||
if (playing) {
|
||
stopPlay();
|
||
} else {
|
||
if (idx >= steps.length - 1) init();
|
||
playing = true;
|
||
document.getElementById('btn-play').textContent = '⏸ Pause';
|
||
timer = setTimeout(advance, getDelay());
|
||
}
|
||
});
|
||
|
||
document.getElementById('btn-step').addEventListener('click', () => {
|
||
stopPlay();
|
||
if (idx < steps.length - 1) { idx++; applyStep(steps[idx]); }
|
||
});
|
||
|
||
document.getElementById('btn-back').addEventListener('click', () => {
|
||
stopPlay();
|
||
if (idx > 0) { idx--; applyStep(steps[idx]); }
|
||
});
|
||
|
||
document.getElementById('btn-reset').addEventListener('click', () => {
|
||
stopPlay();
|
||
init();
|
||
});
|
||
|
||
document.getElementById('inp-n').addEventListener('change', () => {
|
||
stopPlay();
|
||
init();
|
||
});
|
||
|
||
document.getElementById('inp-speed').addEventListener('input', e => {
|
||
document.getElementById('speed-lbl').textContent = e.target.value + '×';
|
||
});
|
||
|
||
// ── BOOT ─────────────────────────────────────────
|
||
init();
|
||
</script>
|
||
</body>
|
||
</html>
|